プログラミング言語の文法を厳密に記述するBNF (バッカス・ナウア記法)。コンパイラ理論の入り口です。
日野 こむぎ
プログラミング言語の文法って、どうやって決めてるの?
藤森 さやか 先生
BNF (Backus-Naur Form) という記法で形式的に定義しているのよ。
コンパイラがプログラムを解析する時の基礎となる理論よ。
青木 澪
BNFは「左辺 ::= 右辺」の形式。
例: <数字> ::= 0 | 1 | 2 | ... | 9 のように「左辺は右辺で定義される」を表現するの。
終端記号と非終端記号の組み合わせで構成するわ。
桃井 すみれ
EBNFって聞いたことありますぅ
青木 澪
EBNF (Extended BNF) はBNFを拡張したもの。
「*」(0回以上)、「[]」(オプション)、「|」(選択) を追加して、より簡潔に書けるようにしたものよ。
藤森 さやか 先生
BNFを使うのが構文解析 (parsing)。
コンパイラが「プログラムが文法的に正しいか」を判定して構文木を作る処理ね。
青木 澪
試験では「次のBNF定義に従い、有効な文字列はどれか」「無効な文字列はどれか」のような問題が定番。
日野 こむぎ
へぇ〜、要はコンパイラの裏側はBNFで動いてるってことだね!
確認クイズ
BNFの記法で「2つ以上の選択肢から1つ選ぶ」ことを表す記号はどれか。
- ::=
- |
- <>
- *
こたえを見る
正解: 2. |
BNFで | は選択 (or) を表します。例: <数字> ::= 0 | 1 | 2 のように、複数の候補から1つを選ぶことを意味します。