yacc/bison LALR(1)算法如何处理“空”规则？

Question

在LALR（1）解析器中，语法中的规则被转换成一个解析表，有效地表示“如果您迄今为止有这个输入，并且向前看令牌是X，则移至状态Y，或按规则R减少”。我已经成功地在解释性语言（ruby）中构建了一个LALR（1）解析器，而没有使用生成器，而是在运行时计算解析表并使用该解析表评估输入。这很有效，并且表格生成非常琐碎（这让我有些惊讶），支持自我引用的规则和左/右相关性。然而，有一件事我有些难以理解，那就是yacc/bison如何概念化地处理空规则定义。我的解析器无法处理它们，因为在生成表格时，它递归地检查每个规则中的每个符号，“空”不是来自词法分析器的内容，也不会被规则减少。那么，LALR（1）解析器如何处理空规则？它们是否特别对待它，还是这是一个“自然”的概念，一个有效的算法应该能够处理，甚至不需要特别意识到这样的概念？假设存在一个可以匹配任意数量的成对括号且中间无内容的规则：

expr:   /* empty */
      | '(' expr ')'
      ;

像以下这样的输入将匹配此规则：

((((()))))

这意味着当阅读到'('并在展望标记中看到')'时，解析器需要做出以下选择：

1. 将')'移入（不可能）
2. 根据其他规则缩小输入（不可能）
3. 其他操作...

这些选择无法完全适应“移位”或“缩小”的核心算法。实际上，解析器需要将空值推入堆栈、将输入“空值”缩小至expr，然后移动下一个标记')'，得到'(' expr ')'，最终缩小为expr，以此类推。

正是“移位空值”让我感到困惑。解析表如何传达这样的概念？同时还需考虑，可以通过调用某些语义动作，在对空值进行缩小时将值返回给$$，因此如果简单地跳过该项并说堆栈中的'('和展望中的')'应直接转换为移位操作，则不能真正产生序列'(' expr ')'，而只会生成序列'(' ')'。

- d11wtq

---

我相信《编译原理》这本书中有很长的章节来处理这样的规则。但我不认为Stack Overflow是讨论这个问题的正确场所，也许应该去程序员社区问问？ - Damien_The_Unbeliever

谢谢你给我推荐这本书，我现在正在看那个链接。对我来说，Stackoverflow似乎是一个合适的地方。这是一个直接有关算法的问题，而不是主观讨论。如果有人知道答案，很可能会搜索到这个问题，并得到快速的解决方案。 - d11wtq

我想当一个基本点在我脑海中形成时，我其实已经理解了这个问题，而且它非常显而易见和直截了当。会回答这个问题，因为谷歌搜索没有结果，这是一个相当自然的问题 ;) - d11wtq

Answer 1

尽管在写问题并在接下来的几分钟中思考后，我已经思考了几天，但有些事情对我来说非常明显和简单。按照所有规则进行约简总是：从堆栈中取出X输入，其中X是规则中组件的数量，然后将结果移回到堆栈上并转到在此约简之后在表中给出的任何状态。在空规则的情况下，您不需要考虑“空”甚至是一个概念。解析表只需要包括一个转换，即“在堆栈上给出'（'和在向前查看中不是'（'的任何内容的情况下，通过'empty'规则进行约简”。现在，由于空规则大小为零组件，因此从堆栈中弹出零意味着堆栈不变，然后当约简没有任何东西被移回到堆栈时，您正在查看确实出现在语法中的东西，一切都变得清晰明了。

Stack       Lookahead    Remaining Input      Action
--------------------------------------------------------------
$           (            ())$                 Shift '('
$(          (            ))$                  Shift '('
$((         )            )$                   Reduce by /* empty */
$((expr     )            )$                   Shift ')'
$((expr)    )            $                    Reduce by '(' expr ')'
$(expr      )            $                    Shift ')'
$(expr)     $                                 Reduce by '(' expr ')'
$expr                                         Accept

"它之所以“只是起作用”是因为为了通过空规则进行规约，您只需要从堆栈中弹出零个项目。"

- d11wtq

---

事实证明，我解析器中DSL的微小更改使其工作...零规则组件和一个规则组件，即空字符串是两个非常不同的东西。 - d11wtq

Answer 2

也许可以补充一下d11wtq的优秀答案：

在解析器构建过程中，可空规则（派生ϵ的规则）是在函数FOLLOW(X)和FIRST(X)下考虑的。例如，如果你有A -> B x，并且B可以推导出ϵ，则我们必须在FIRST(A)计算的集合中包含x。同时也要包括在FOLLOW(B)的集合中。

此外，在规范的LR(1)项目集中很容易表示空规则。

一个有用的技巧是想象有一个额外的非终结符号$，它代表文件的结束。

让我们来看一下语法：

S -> X | ϵ
X -> id

对于第一个规范的LR(1)项集，我们可以取第一个LR(0)项集，并在符号“$”上添加展望：

S -> . X   , '$'
S -> .     , '$'
X -> . id  , '$'

然后我们有一个针对前瞻是id的例子:

S -> . X   , 'id'
S -> .     , 'id
X -> . id  , 'id'

现在让我们来看一下FIRST和FOLLOW集合：

S -> . X   , '$'

这不是一个“点结束”的项目，所以在这里需要进行移位操作，但仅当集合 FIRST(X) 包含我们的展望符号 $ 时才进行。这是错误的，因此我们不会填写表格条目。

接下来：

S -> .     , '$'

这是一个"点最终"项，所以它希望进行归约。为了验证归约的上下文，我们查看 FOLLOW(S)：我们希望归约的语法符号后面是否跟着前瞻中的内容？确实如此。因为起始符号定义为跟随输入结束符 $，所以它总是在 FOLLOW(S) 中。因此，我们可以进行归约。由于我们正在减少符号 S，所以这个归约实际上就是一个 accept 操作：解析结束了。我们用 accept 操作填充表格条目。

同样的，我们可以重复查看下一个具有前瞻 id 的项目集。让我们跳到 S-推导出空规则：

S -> .     , 'id'

能否将 S 后跟 id ? 几乎不可能。因此这种约简是不适当的。我们不会填充分析器表格项。

可以看出，空规则不会带来问题。它立即转换为一个点终态的 LR(0) 或 LR(1) 项目（取决于解析器构造方法），并且在考虑前瞻和填充表格方面与任何其他点终态项目一样被处理。

- Kaz