終端記号と非終端記号からなる

「非終端記号1つ」を「非終端記号と終端記号からなる記号列」に置き換える生成規則のみからなる文法

数を数えられたり、括弧で入れ子を表現できる点で正規表現より強力

定義

文脈自由文法は以下の4つから構成される

非終端記号の集合

終端記号の集合

生成規則の集合

曖昧な文法

同じ式に対して異なる構文木が作られるような文法

1-2-3 は (1-2)-3 か 1-(2-3) か決まってないようなやつ

コンパイルする際に問題になるらしい ref: p.39

なんで？

プログラムを記述したり、理解する際にも問題になる

曖昧な文法は曖昧でない文法に変換できることが多い

文法を変換することで除去できる

例えば * を右結合にするためには文法を T→F*T にすればいい

T は項(Term)、 F は因子(Tactor)を表す

F → id | num | (E)

演算子に優先順位をつけることで曖昧さを消すことができる

文脈自由文法の中での関係 ref

LL法 < SL法 < LALR法 < LR法 < GLR法

参考

タイガーブック 3章

『(環境)5 プログラミング言語処理系』 4章