1

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

some_list:
 | {[]}
 | some_non_empty_list { $1 }

some_non_empty_list:
 | SEMICOLON some_list { $2 }
 | element { [$1] }
 | element some_non_empty_list { $1 :: $2 }

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

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

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

4

1 回答 1

2

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

过度简化，语法规则 L = R1 R2 R3 ；意思是“如果你看到 R1 R2 R3，就减少到 L”。不简化，如果我们有 X= ALB ; 那么我们的 L 规则的意思是“如果你的左边上下文是 A，你已经看到 R1 R2 R3，并且下一个标记是 first(B)，则减少到 L。

如果 L = R1 R2 ，这个想法是相同的；和 L = R1 ;。

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

除非你已经看到它的左上下文、它的内容和后面的开头，否则你不能简化为 L。因此，您不能在“任何时候”简化为空规则。

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

于 2018-10-10T12:15:56.740 回答