parsing - yacc/bison LALR(1) 算法如何处理 "empty"规则？

Question

在 LALR(1) 解析器中，语法中的规则被转换为解析表，该表有效地表示“如果到目前为止有此输入，并且先行标记为 X，则转移到状态 Y，或减少规则R”。

我已经成功地用解释语言(ruby)构建了一个 LALR(1) 解析器，没有使用生成器，而是在运行时计算解析表并使用该解析表评估输入。这工作得非常好，并且表格生成非常简单(这让我有些惊讶)，支持自引用规则和左/右关联。

但是，我有些难以理解的一件事是 yacc/bison 从概念上如何处理空规则定义。我的解析器无法处理它们，因为在生成表时，它会递归地查看每个规则中的每个符号，而“空”并不是来自词法分析器的东西，也不会被规则减少。那么，LALR(1) 解析器如何处理空规则呢？他们是否特别对待它，或者它是一个“自然”概念，有效的算法应该只使用它，甚至不需要对这样的概念有特别的认识？

比方说，一条规则可以匹配任意数量的配对括号，中间没有任何内容:

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

如下输入将匹配此规则:

((((()))))

这意味着在先行标记中读取“(”并看到“)”时，解析器会选择:

1. 移动“)”(不可能)
2. 根据其他规则减少输入(不可能)
3. 还有别的事...

不太适合“shift”或“reduce”的核心算法。解析器实际上需要将任何内容移入堆栈，将“无内容”减少为 expr，然后移动下一个标记 ')'，给出 '(' expr ' )'，当然会简化为 expr，依此类推。

“什么都不改变”让我感到困惑。解析表是如何传达这样的概念的呢？还请考虑，应该可以调用一些语义操作，在减少空值时将值返回到 $$ ，因此从解析表中跳过该值并说 是一个相当简单的 View 堆栈上的 >'(' 和前瞻中的 ')' 应该简单地转换为移位，不会真正产生序列 '(' expr ')'，但只会产生序列 '(' ')'。

Answer 1

尽管我想了好几天这个问题，但自从在写问题时和接下来的几分钟里仔细思考后，我发现有些事情是如此明显和简单。

所有规则的归约始终是:从堆栈中弹出 X 个输入，其中 X 是规则中的组件数量，然后将结果移回堆栈并在归约后转到表中给出的任何状态。

对于空规则，你甚至不需要考虑“空”是一个概念。解析表只需要包含一个转换，表示“在堆栈上给定 '('”，并且在前瞻中“任何不是 '('”的内容，减少 '现在，由于空规则的分量大小为零，因此从堆栈中弹出零意味着堆栈不会更改，那么当减少任何内容的结果转移到堆栈上时，您会看到以下内容确实出现在语法中，一切都变得清晰起来。

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

它“正常工作”的原因是因为为了减少空规则，您只需从堆栈中弹出零项。