grammar - 如何使用表达式 a>>b^c 表明具有位运算符的语法是不明确的

Question

我正在尝试解决这个问题，但我真的不知道如何开始。我会很感激一些帮助。

下表中显示了一种语言的按位运算符和语法。运算符和语法规则的优先级从高到低。字符 a、b 和 c 代表语言中的终端。

语法表：

1. 使用表达式证明语法是不明确的：a >> b ^ c
2. 重写语法，使其明确。

Answer 1

《龙书》说：“为某个句子生成不止一个解析树的语法被称为歧义”。所以要证明一个语法是模棱两可的，你需要为该语法生成​​的单个句子显示至少两个解析树。在这种情况下，要使用的句子已经给你了，所以对于 Q1，你只需要找到两个不同的解析树a >> b ^ c。世平的评论给了你一个很大的线索。

对于 Q2，他们要求您“重写语法”，我怀疑不言而喻的要求是生成的语法生成与原始语法完全相同的语言。（因此，世平提出的在语言中引入括号的建议不会被接受。）这样做的一般方法是为优先级图表中的每个优先级引入一个非终结符，然后修改语法规则以使用新的非终结符在这样的语法只能生成尊重优先级图的解析树的方式。

例如，查看您为 Q1 找到的两棵树。您应该观察到其中一个符合优先级图表，而一个不符合。您需要一种新语法，它允许遵循优先级的树，但不允许其他树。

作为另一个线索，考虑这两种语法之间的区别：

E -> E + E
E -> E * E
E -> a | b

和

E -> E + T
T -> T * F
F -> a | b

尽管它们生成相同的语言，但第一个是模棱两可的，而第二个不是。