5

我正在尝试了解 shift-reduce 解析。假设我们有以下语法，使用强制操作顺序的递归规则，受ANSI C Yacc 语法的启发：

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

我们想使用 shift-reduce 解析来解析 1+2。首先，将 1 作为数字移动。我的问题是，它是否会被简化为 P，然后是 M，然后是 A，最后是 S？它怎么知道在哪里停下来？

假设它确实一直减少到 S，然后移动“+”。我们现在有一个堆栈，其中包含：

S '+'

如果我们移动'2'，减少可能是：

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

现在，在最后一行的任一侧，S 可以是 P、M、A 或 NUMBER，并且它仍然有效，因为任何组合都是文本的正确表示。解析器如何“知道”它

A '+' M

这样它就可以将整个表达式简化为A，然后S？换句话说，它如何知道在移动下一个令牌之前停止减少？这是 LR 解析器生成的关键难点吗？

编辑：对问题的补充如下。

现在假设我们解析1+2*3. 一些移位/减少操作如下：

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

这是正确的（当然，它还没有完全解析）？此外，1 符号前瞻是否也告诉我们不要减少A+M到A，因为这样做会导致读取后不可避免的语法错误*3？

4

2 回答 2

5

您描述的问题是创建LR(0)解析器的问题 - 也就是说，自下而上的解析器不会对它们正在解析的当前符号之外的符号进行任何前瞻。您描述的语法似乎不是LR(0)语法，这就是为什么您在尝试解析它时遇到麻烦的原因。但是，它看起来确实是，LR(1)因此通过在输入中向前查看 1 个符号，您可以轻松确定是移动还是减少。在这种情况下，LR(1)解析器会在堆栈上有 时向前看1，看到下一个符号是 a +，并意识到它不应该归约过去A（因为这是它唯一可以归约到的仍然匹配 a规则+在第二个位置）。

文法的一个有趣特性LR是，对于任何为 的文法，LR(k)都k>1可以构造一个LR(1)等价的文法。但是，这并没有一直延伸到LR(0)- 有许多语法无法转换为LR(0).

有关LR(k)-ness 的更多详细信息，请参见此处：

http://en.wikipedia.org/wiki/LR_parser

于 2010-04-13T03:50:24.643 回答
1

我不太确定 Yacc / Bison 解析算法以及它何时更喜欢转移而不是减少，但是我知道 Bison 支持 LR(1) 解析，这意味着它有一个前瞻标记。这意味着令牌不会立即传递到堆栈。相反，他们等到没有更多的减少发生。然后，如果移动下一个标记有意义，则应用该操作。

首先，在您的情况下，如果您正在评估 1 + 2，它将移动 1。它将将该标记减少为 A，因为“+”前瞻标记表明它是唯一有效的课程。由于没有更多的减少，它会将“+”标记移到堆栈上并保持 2 作为前瞻。它将移动 2 并归约为 M，因为 A + M 产生 A 并且表达式是完整的。

于 2010-04-13T04:11:51.473 回答