文脈自由文法
context-free grammar
数を数えられたり、括弧で入れ子を表現できる点で正規表現より強力 定義
文脈自由文法は以下の4つから構成される
生成規則の集合
曖昧な文法
同じ式に対して異なる構文木が作られるような文法
1-2-3は(1-2)-3か1-(2-3)か決まってないようなやつ
コンパイルする際に問題になるらしい ref: タイガーブック.icon p.39
なんで？
プログラムを記述したり、理解する際にも問題になる
曖昧な文法は曖昧でない文法に変換できることが多い
文法を変換することで除去できる
例えば*を右結合にするためには文法をT→F*Tにすればいい
Tは項(Term)、Fは因子(Tactor)を表す
F→id|num|(E)
演算子に優先順位をつけることで曖昧さを消すことができる
参考