运算符优先于LR(0)解析器

Question

定义算术操作的典型BNF：

E :- E + T
  |  T
T :- T * F
  |  F
F :- ( E )
  | number

有没有办法重写这个语法，这样它就可以用LR(0)解析器实现，同时仍然保留运算符的优先级和左结合性？我认为引入某种消除歧义的非终端机应该是可能的，但我不知道如何去做。

谢谢!

Answer 1

语言只有在没有前缀的情况下才能有LR(0)语法，这意味着语言中没有字符串是另一种语言的前缀。在这种情况下，您所描述的语言并不是无前缀的。例如，字符串number + number是number + number + number的前缀。

解决这一问题的一个常见方法是“结束”您的语言，方法是要求生成的所有字符串以一个特殊的“完成”字符结尾。例如，可以要求所有生成的字符串以分号结尾。如果这样做，您可以使用以下语法为该语言构建一个LR(0)解析器：

S→E； E→E+T_→ T→T*F*F F→数x (E)