LR(1) 解析器如何处理空规则？

Question

我使用过一些解析器（Yacc、Bison 和 Menhir）。如果我没记错的话，它们都允许一个规则为空。这是我使用 Menhir 的一个例子，它是我用得最多的一个。

some_list:
 | {[]}
 | some_non_empty_list {  }

some_non_empty_list:
 | SEMICOLON some_list {  }
 | element { [] }
 | element some_non_empty_list {  ::  }

重要的是some_list可以减少虚无。

我目前对构建解析算法的理解 table（构建 NFA，从 NFA 构建 DFA，最小化）使我认为这会导致整个 shift/reduce 冲突地方。但它显然没有，因为我的代码当时有效。

那么如何构建一个可以接受那些空规则的解析table？

Answer 1

为什么您认为空规则比具有一个右侧标记的规则更难处理？

过于简单化，语法规则 L = R1 R2 R3 ;表示 "reduce to L if you see R1 R2 R3"。不简化，如果我们有 X= A L B ；那么我们的 L 规则意味着“如果你的左上下文是 A，你已经看到 R1 R2 R3，并且下一个标记是 first(B)，则减少到 L。

如果L = R1 R2，这个思路是一样的； L = R1 ;.

甚至对于（空规则）的极限情况：L = ;

除非您已经看到它的左边上下文、它的内容以及后面的开头，否则您不能缩小到 L。所以你不能在 "any time".

减少到一个空规则

您需要做的是了解 LR 解析器的工作原理，方法是学习如何在构建解析状态时跟踪项目集。在纸上做一次，（痛苦的是，值得的是）一个小语法，LR 解析器将变得清晰。你可以在任何关于 LR 解析的书中找到这个过程，包括 Aho 等人的经典编译器。