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。我建议查看该页面，了解如何解决此问题的想法。