BNF文法の曖昧

Question

私は最近、次のBNF

A -> x | yA | yAzA 

where x,y,z are terminals. 

を考えていた私はこの文法が曖昧であるかなり確信しているが、どのように一つは、それを明確にしますか？

Answer 1

特定の文字列が複数の解析木を持つことができる場合、文法はあいまいです。あなたの言語では、文字列yyxzxは、これらの二つの構文解析ツリーのいずれかを持つことができます。

A     A 
/\    /|\`\ 
    y A    y A z A 
    /|\`\   /\ \ 
    y A z A   y A x 
     | |    | 
     x x    x 

したがって文法があいまいです。

実際これはC言語のような有名な "if/then/else"のあいまいさに相当します。ここではy=if,z=else、x=statementです。 http://en.wikipedia.org/wiki/Dangling_else。私は、この問題を回避するためのアイデアについて、そのページをチェックアウトすることをお勧めします。