如何將以下模糊語法轉換爲明確？

Question

我明白兩者之間的區別，多麼模棱兩可意味着至少有一個字符串與2個不同的分析樹，而在一個明確的樹中只有一個。但我似乎無法將一個轉換爲另一個。

我怎麼會在以下二義性文法轉化爲明確的一個？

S -> aSb 
S -> abS 
S -> lambda 

編輯：好吧，我在這個刺會是這樣的

S -> aSb | lambda 
b -> abS | lambda 

有什麼想法？

Answer 1

語法是不明確的，不僅是因爲有匹配「A」作爲下一個令牌兩個規則 - 但是，因爲「AB」可以由第一或第二規則進行匹配是（在每個使用第三對於s代） 。

有這樣的事，作爲一個固有的歧義語法，但這不是一個。

關注這個具體的例子，我開始通過枚舉將解析字符串。我編制了規則1,2和3 - 並且考慮了規則1和規則2在解析中可能出現的所有順序（這是產生終端的兩條規則）。我認爲「lambda」表示空的生產。

1,2 => ab 
11,12 => abab 
21,22 => aabb 
111,112 => ababab 
121,122 => abaabb 
211,212 => aababb 
221,222 => aaabbb 
1111,1112 => abababab 
1121,1122 => ababaabb 
1211,1212 => abaababb 
1221,1222 => abaaabbb 
2111,2112 => aabababb 
2121,2122 => aabaabbb 
2211,2212 => aaababbb 
2221,2222 => aaaabbbb 

從這個練習中，很明顯，我們要匹配「a和b」，其中「A」的終端數量「B」的終端數完全匹配的偶數長度字符串......此外，如果前綴匹配使用第二個規則，則僅匹配的兩個字符串的串聯會導致另一個匹配字符串。

從這個分析，我制定了一些新的作品。

S -> a a X 
S -> a b S 
S -> lambda 
X -> S b b 

這種新的語法也不含糊，但它同樣的字符串作爲曖昧的語法相匹配。它通過引入一個新的非終端X來實現這一點。當這個CFG與下推自動機一起使用時，由於使用S和X而產生的附加狀態信息足以避免模糊。

如果這個問題在使用類似的Yacc或野牛的背景下產生的，模糊往往是，你所做的終端令牌一個糟糕的選擇的指示。如果你選擇'aa'，'ab'和'bb'作爲終端 - 你不會遇到困難。當使用（F）lex作爲分詞器時，作爲一個經驗法則，最好讓它匹配的記號大到有意義......因爲匹配正則表達式（理論上至少）比匹配正則表達式更快上下文無關語法 - 這可能已經產生了雙字符標記方法。