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。我建議查看該頁面，瞭解如何解決此問題的想法。