曖昧な文法
ambiguous
ある文に対して2つ以上の解析木が作れるような文を「曖昧な文」と言う
逆に言えば、解析木や構文木が一意に確定する文法なら曖昧ではない
曖昧な文を一つでも持つ文法のことを曖昧な文法という
ある文法が曖昧かどうかは判定不能
どういう文法が曖昧になるか
演算子に優先順位がない
ex.
+ と * がが同じ優先順位演算子の結合性が決まっていない
同じ優先順位の演算子でも、左右どちらの結合なのかが決まっていない
ex.
(a+b)-c なのか a+(b-c) なのかが確定しない優先順位付与
左再帰になっている。
左再帰になっているおかげ？で、左結合的であることを表している
曖昧さを排除する方法は2つある
文法を書き換える
新たな非終端記号を導入して演算子間に優先順位を導入する
文法は曖昧なままだが、曖昧さを除去する制約を設ける
具体例
以下のような生成規則を考える
bnfE -> E + E
E -> E - E
E -> E * E
E -> E / E
E -> num文法を書き換えて曖昧さを除去する
T や F などの新しい非終端記号を導入することで演算子の優先順位を表現するbnfE -> E + T
E -> E - T
E -> T
T -> T * F
T -> T / F
T -> F
F -> num文法は曖昧なまま曖昧さを除去する方法は、演算子にルールを加える
「
* と / は、 + と - より優先順位が高い」「
* . / , + , - は左結合的」コレ実際どうやって記述するんだ？
yaccがこんな感じらしい
曖昧な文法の例
参考
『(環境)5 プログラミング言語処理系』 p.110-