文脈自由文法

文脈自由文法は、各生成規則の左辺が一つの非終端記号で、右辺が終端・非終端記号の任意の列から成る形式文法です。

■ 試験で押さえるポイント

• 非終端記号の置換が周囲の記号という文脈に依存しないため文脈自由と呼ばれ、再帰規則で任意の深さの括弧や式を表せます。

• BNFは文脈自由文法を記述する代表的な記法で、構文解析器は入力から導出又は構文木を作ります。

• 正規文法より表現力が高く、有限オートマトンでは扱えない入れ子を扱えますが、全ての文脈依存条件を表せるわけではありません。

• 変数が宣言済みか、型が一致するか、関数引数数が正しいか等は、通常は構文解析後の意味解析や記号表で確認します。

■ 選択肢での判断ポイント

左辺が単一の非終端記号であることと、再帰的な入れ子構造を表せることを押さえます。

例: S ::= "(" S ")" S ｜ ε は、空文字、()、(())、()()のように正しく対応した括弧列を生成でき、単純な有限状態だけでは任意の深さを保持できません。