
形式言語・BNFと構文解析
用語の意味
形式言語は、決められた記号から作られる文字列の集合です。BNFは構文の規則を表す記法で、置換される非終端記号と、最終的な文字列に現れる終端記号を区別します。
使いどころと問題の見方
例えば <符号> ::= + | - なら、符号をプラスかマイナスのどちらかに置き換えます。再帰を含む規則では、何回繰り返せるかに加えて、置換が終了する選択肢があるかを確認します。構文木は適用した規則を木構造で表します。
確認問題【オリジナル】
<数字列> ::= <数字> | <数字><数字列> で、<数字> が0〜9の1文字なら、生成できる最短の文字列は何文字ですか。
ア.2文字
イ.3文字
ウ.1文字
エ.0文字
正解と理由
正解はウです。左の選択肢で数字1文字を選ぶと再帰せず終了します。