8

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

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

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

假设一个规则可以匹配任意数量的成对括号，中间没有任何内容：

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

如下输入将匹配此规则：

((((()))))

这意味着在前瞻标记中读取 '(' 并看到 ')' 时，解析器会选择：

  1. 移动“）”（不可能）
  2. 根据其他规则减少输入（不可能）
  3. 还有什么...

不太适合“移位”或“减少”的核心算法。解析器实际上需要什么都不移动到堆栈上，将“无”归expr约为 ，然后移动下一个标记')'，给'(' expr ')'，当然归约为expr，依此类推。

让我困惑的是“什么都不做”。解析表是如何传达这样一个概念的？还要考虑到应该可以调用一些语义动作来返回一个值来$$减少空值，所以一个相当简单的视图只是从解析表中跳过它并说'('在堆栈和')'前瞻中应该简单地转换为一个转变，不会真正产生序列'(' expr ')'，而只会产生序列'(' ')'。

4

2 回答 2

9

尽管考虑了好几天，但自从在写问题时和随后的几分钟内仔细考虑了这一点，一些事情让我觉得非常明显和简单。

所有规则的归约总是：从堆栈中弹出 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

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

于 2011-11-23T13:43:07.250 回答
5

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

FOLLOW(X)在函数和下的解析器构造期间考虑了一个可为空的规则（派生 ϵ 的规则）FIRST(X)。例如，如果你有 A -> B x，并且 B 可以导出 ϵ，那么我们必须包含x在由 计算的集合中FIRST(A)。而且还在片场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'

现在让我们看看FIRSTandFOLLOW集合：

S -> . X   , '$'

这不是“点最终”项，所以这里要移位，但前提是集合FIRST(X)包含我们的前瞻符号$。这是错误的，所以我们不填写表格条目。

下一个：

S -> .     , '$'

This is a "dot final" item, so it wants to reduce. To validate the context for a reduce, we look at FOLLOW(S): can the grammar symbol we wish to reduce be followed by what is in the lookahead? Indeed, yes. $ is always in FOLLOW(S) because the start symbol is by definition followed by the end of the input. So yes, we can reduce. And since we are reducing the symbol S, the reduce is actually an accept action: the parse ends. We fill the table entry with an accept action.

Similarly we can repeat for the next item set with lookahead id. Let's skip to the S-deriving-empty rule:

S -> .     , 'id'

Can S be followed by id? Hardly. So this reduction is not appropriate. We don't fill the parser table entry.

So you can see that an empty rule poses no problem. It immediately turns into a dot final LR(0) or LR(1) item (depending on parser construction method), and is treated the same as any other dot final item with regard to considering the lookahead and filling the tables.

于 2012-04-24T00:02:09.073 回答