如何顯示此語法不明確？

Question

我想證明這個語法不明確，但我不知道我該怎麼做。我必須使用分析樹嗎？

S -> if E then S | if E then S else S | begin S L | print E 
    L -> end | ; S L 
    E -> i 

Answer 1

你可以把語法到它支持所有的上下文無關文法，上下文無關一般解析器生成解析器生成。生成解析器，然後解析一個您認爲不明確的字符串，並通過查看解析器的輸出來查找。

上下文無關的一般語法分析器生成器生成解析器，該解析器在多項式時間內生成所有派生。這種解析器生成器的示例包括SDF2，Rascal，DMS，Elkhound，ART。還有一個yacc（btyacc）的回溯版本，但我不認爲它是在多項式時間內完成的。通常，輸出被編碼爲一個圖形，其中用於子句子的替代樹使用嵌套替代樹集合進行編碼。

Answer 2

您可以顯示它是不明確的，如果你能找到解析不止一種方法的字符串：

if i then (if i then print i else print i ;) 
if i then (if i then print i) else print i ; 

這恰好是經典的「dangling else」歧義。使用谷歌搜索標籤，標題&語法給出了其他命中。

但是，如果不發生在一個明確的字符串來猜測然後googling your tag(s) & title：

how can i prove that this grammar is ambiguous?

沒有爲證明一個上下文無關文法曖昧不容易的方法 - 在其實， the question is undecidable，通過減少到Post correspondence problem。