Shift-reduce:何时停止减少？

Question

我正在尝试学习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被移动为NUMBER.我的问题是,它是否减少到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？

Answer 1

您所描述的问题是创建LR(0)解析器的问题- 也就是说,自下而上的解析器不会对他们正在解析的当前符号之外的符号做任何预测.你所描述的语法似乎不是一种LR(0)语法,这就是为什么你在尝试用前瞻解析它时遇到麻烦的原因.它确实显得LR(1)然而,这样看1个符号超前输入你可以很容易地确定是否转移或减少.在这种情况下,LR(1)解析器1在堆叠时会向前看,看到下一个符号是a +,并且意识到它不应该减少过去A(因为它是唯一可以减少的东西,它仍然会匹配规则+在第二位置).

一个有趣的特性LR语法是,对于任何语法是LR(k)对k>1,就可以构建一个LR(1)语法是等价的.但是,同样不会一直延伸到LR(0)- 有许多语法无法转换为LR(0).

有关LR(k)-ness的详细信息,请参见此处:

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