parsing - LR(0) 解析器的运算符优先级

Question

一个典型的 BNF 定义算术运算：

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

有没有办法重写这个语法，以便它可以用 LR(0) 解析器来实现，同时仍然保留运算符的优先级和左关联性？我认为通过引入某种消歧非终端应该是可能的，但我不知道该怎么做。

谢谢！

score 1 · Accepted Answer

如果一种语言是无前缀的，则它只能具有 LR(0) 语法，这意味着该语言中的任何字符串都不是另一种的前缀。在这种情况下，您描述的语言不是无前缀的。例如，字符串number + number是的前缀number + number + number。

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

S→E；

E → E + T | 吨

T → T * F | F

F → 数字 | (五)

1 回答 1