注釈付きでマークされた文字列の解析 #1

さて、少しだけ複雑にする。
括弧で括ってマーク付けした語に簡単な注釈を加えた英文を解析することを考える。
例えば、次の例では、

The (quick: swift) brown (fox) jumps over the (lazy: one of three virtues of a programmer) (dog).

括弧で括られたquickやlazyのコロンの後が注釈部分である。
括弧内のコロンは注釈の始まりを表す特別な文字になるので、
マーク付け可能な語を構成する文字として使用できない。
今まで通りの括弧で括っただけのfoxやdogのような注釈なしのマーク付けはもちろん許容する。
問題を明確にするために受容すべき英文の定義を構文生成規則としてBNFで記述してみる。

<text> ::= <string-headed> | <marked-string-headed>
<string-headed> ::= <string> | <string> <marked-string-headed>
<marked-string-headed> ::= <marked-string> | <marked-string> <marked-string-headed> | <marked-string> <string-headed>
<marked-string> ::= "(" <marked-string-body-with-annotation> ")"
<string> ::= <char-except-parenthesis> | <string> <char-except-parenthesis>
<char-except-parenthesis> ::= <char-except-special> | ":"
<marked-string-body-with-annotation> ::= <marked-string-body> | <marked-string-body> ":" <annotation>
<marked-string-body> ::= <char-except-special> | <marked-string-body> <char-except-special>
<annotation> ::= <char-except-parenthesis> | <annotation> <char-except-parenthesis>

"("、")"、":"はそれぞれそのままの括弧やコロンを表す終端記号であり、
<char-except-special>がそれ以外の文字を表す終端記号である。
これら以外の記号が非終端記号であり、<text>が開始記号であり受容すべき英文でもある。
これまでと異なり括弧以外の（コロンも含む）文字を表す<char-except-parenthesis>は非終端記号である。
解析によって<string>、<marked-string-body>、<annotation>を区別して出力できるようにする。