明确的语法到歧义

Question

我不知道问这个问题的网站是否合适。但我们正在研究语法歧义。包括最左推导和最右推导。我的练习题是这样的：

E -> E * E | E + E | N
N -> 0N | 1N |
Output: 0110 + 110 * 01111

有没有办法让它变得模棱两可？有什么使语法歧义的技巧吗？

Answer 1

鉴于你的语法，它显然有歧义。在这里，它没有定义 + 和 * 运算符之间的偏好。

如您所说，如果您必须解析此 0110 + 110 * 01111，可以使用两种方法来完成：-

1. 0110 + 110 * 01111 ----> (0110 + 110) * 01111

2. 0110 + 110 * 01111 ----> 0110 + (110 * 01111)

所以，这个语法很含糊，因为它没有定义运算符的优先级。此外，没有提供运算符关联性。

显然，通过指定冲突案例之间的区别来消除歧义，取决于语法指定的产生式规则。在进行自上而下解析时遇到的一些问题是左因式分解和左递归导致语法不明确。

您应该查看 elimination of left recursion 和其他相关教程，因为它太宽泛而无法指定规则。