1

我在理解如何使用自下而上的解析器（例如，输入字符串1 + 2 * 3）从“底部”到“顶部”时遇到了一些麻烦。

这是我正在使用的语法（我会说它是正确的，因为它是在 Crafting a Compiler 中找到的）

E = E plus T
  | T;

T = T times integer
  | integer;

这是我的反向推导：

int(1)
T(1)
E(1)
E(1) plus int(2)
E(1) plus T(2)
E(1) plus E(2)
E(1) plus E(2) times int(3)
E(1) plus E(2) times E(3) <-- can't do anything here

问题是每次我得到一个整数作为输入时，它都会自动“转换”为E.

我很肯定给定的语法是正确的。我还在 sablecc 中尝试了一些输入字符串（使用我制作的 Pretty Printer 访问者），它们都产生了正确的结果。

这样，我知道问题出在我身上，而不是语法本身。那我做错了什么？

谢谢！

4

1 回答 1

1

shift-reduce 冲突是语法中最常见的冲突类型。在你的情况下，T(2) 可以减少到 E(2)，或者时间可以改变。默认情况下，大多数解析器生成器更喜欢移位而不是减少。但是他们仍然会将 T(1) 减少到 E(1)，因为他们知道在 T 之后移动加号是没有意义的。

于 2011-04-09T16:35:22.807 回答