我了解两者之间的区别，歧义如何意味着至少有一个字符串具有 2 个不同的解析树，而一棵明确的树中只有一个。但我似乎无法将一个转换为另一个。
如何将以下模棱两可的语法转换为明确的语法？
S -> aSb
S -> abS
S -> lambda
编辑：好的，我的尝试是这样的
S -> aSb | lambda
b -> abS | lambda
有什么想法吗？
问问题
2823 次
1 回答
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 或 Bison 之类的上下文中出现此问题，那么模棱两可通常表明您选择了错误的终端令牌。如果你选择'aa'、'ab' 和'bb' 作为终端 - 你不会遇到困难。当使用 (F)lex 作为分词器时，根据经验，最好使匹配的分词尽可能大……因为匹配正则表达式（至少在理论上）比匹配上下文无关语法——当然，这可能会产生两个字符的标记方法。
于 2011-09-23T19:13:19.250 回答