如何将以下模糊语法转换为明确？

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作为分词器时，作为一个经验法则，最好让它匹配的记号大到有意义......因为匹配正则表达式（理论上至少）比匹配正则表达式更快上下文无关语法 - 这可能已经产生了双字符标记方法。