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

Question

在LALR(1)解析器中,语法中的规则被转换为一个解析表,有效地说"如果到目前为止你有这个输入,并且前瞻标记是X,那么转移到状态Y,或者通过规则R减少" .

我已成功构建了一个解释语言(ruby)的LALR(1)解析器,不使用生成器,而是在运行时计算解析表并使用该解析表评估输入.这种方法效果非常好,表格生成非常简单(让我感到有些惊讶),支持自我引用规则和左/右关联.

然而,我有一点难以理解的是,yacc/bison在概念上如何处理空规则定义.我的解析器无法处理它们,因为在生成表时它会递归地查看每个规则中的每个符号,而"空"不是来自词法分析器的东西,也不会被规则缩小.那么,LALR(1)解析器如何处理空规则呢？他们是专门对待它,还是一个有效算法应该使用的"自然"概念,甚至不需要特别了解这样的概念？

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

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

像下面这样的输入符合此规则:

((((()))))

这意味着在前瞻标记中读取'('和see')'时,解析器选择:

1. 转移')'(不可能)
2. 根据其他规则减少输入(不可能)
3. 别的......

不太适合"转移"或"减少"的核心算法.解析器实际上需要不将任何内容转移到堆栈上,减少"无" expr,然后移动下一个令牌')',给予'(' expr ')',当然减少到expr,等等.

这让我感到困惑的是"没有任何转变".解析表如何传达这样一个概念？还要考虑应该可以调用一些语义操作来返回一个值来$$减少空值,所以一个相当简单的视图,只是从解析表中跳过它并说'('在堆栈和')'前瞻中应该简单地转换为一个班次,不会真正产生序列'(' 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

它"正常工作"的原因是因为为了减少空规则,你只需要从堆栈中弹出零项.

Answer 2

如果可能的话，另一种观点可能会完善 d11wtq 的出色答案：

\n\n

FOLLOW(X)在函数和下构建解析器期间会考虑可空规则（派生 \xcf\xb5 的规则）FIRST(X)。例如，如果您有 A -> B x，并且 B 可以导出 \xcf\xb5，那么我们必须将 包含x在由 计算的集合中FIRST(A)。而且还在集合中FOLLOW(B)。

\n\n

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

\n\n

一件有用的事情是想象有一个额外的非终结符号$代表文件结尾。

\n\n

我们来看看语法：

\n\n

S -> X | \xcf\xb5\nX -> id\n

\n\n

对于第一个规范LR(1)项集，我们可以采用第一个LR(0)项集并使用符号“$”添加前瞻：

\n\n

S -> . X   , \'$\'\nS -> .     , \'$\'\nX -> . id  , \'$\'\n

\n\n

然后我们有一个前瞻id：

\n\n

S -> . X   , \'id\'\nS -> .     , \'id\nX -> . id  , \'id\'\n

\n\n

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

\n\n

S -> . X   , \'$\'\n

\n\n

这不是“点最终”项，因此这里要移动，但前提是该集合FIRST(X)包含我们的先行符号$。这是错误的，因此我们不填充表条目。

\n\n

下一个：

\n\n

S -> .     , \'$\'\n

\n\n

这是一个“dot Final”项目，所以它想要减少。为了验证归约的上下文，我们看看FOLLOW(S)：我们希望归约的语法符号后面是否可以跟上前瞻中的内容？完全同意。$始终处于输入状态FOLLOW(S)，因为根据定义，起始符号后跟输入结束符。所以是的，我们可以减少。由于我们正在减少符号S，因此减少实际上是一个accept动作：解析结束。我们用一个动作填充表条目accept。

\n\n

类似地，我们可以使用lookahead重复下一个项目集id。让我们跳到 S-deriving-empty 规则：

\n\n

S -> .     , \'id\'\n

\n\n

可以S跟在id? 几乎不。所以这种减少是不合适的。我们不填充解析器表条目。

\n\n

所以你可以看到空规则不会造成任何问题。它立即变成点最终LR(0)或LR(1)项目（取决于解析器构造方法），并且在考虑前瞻和填充表方面与任何其他点最终项目相同。

\n