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