Shift-reduce:什么时候停止减少? [英] Shift-reduce: when to stop reducing?

问题描述

我正在尝试学习移位减少解析.假设我们有以下语法，它们使用受 ANSI C Yacc语法:

I'm trying to learn about shift-reduce parsing. Suppose we have the following grammar, using recursive rules that enforce order of operations, inspired by the ANSI C Yacc grammar:

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?它怎么知道在哪里停下来?

And we want to parse 1+2 using shift-reduce parsing. First, the 1 is shifted as a NUMBER. My question is, is it then reduced to P, then M, then A, then finally S? How does it know where to stop?

假设它确实一直减小到S，然后移位"+".现在，我们将有一个包含以下内容的堆栈:

Suppose it does reduce all the way to S, then shifts '+'. We'd now have a stack containing:

S '+'

如果我们将"2"移位，则减少量可能是:

If we shift '2', the reductions might be:

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

现在，在最后一行的任一侧，S可以是P，M，A或NUMBER，并且在任何组合都可以正确表示文本的意义上，它仍然是有效的.解析器如何知道"以使其成功

Now, on either side of the last line, S could be P, M, A, or NUMBER, and it would still be valid in the sense that any combination would be a correct representation of the text. How does the parser "know" to make it

A '+' M

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

So that it can reduce the whole expression to A, then S? In other words, how does it know to stop reducing before shifting the next token? Is this a key difficulty in LR parser generation?

问题的另一项内容是.

An addition to the question follows.

现在假设我们解析1+2*3.一些移位/归约操作如下:

Now suppose we parse 1+2*3. Some shift/reduce operations are as follows:

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之后不可避免的语法错误?

Is this correct (granted, it's not fully parsed yet)? Moreover, does lookahead by 1 symbol also tell us not to reduce A+M to A, as doing so would result in an inevitable syntax error after reading *3 ?

推荐答案

您要描述的问题是创建LR(0)解析器时遇到的问题-即，自底向上的解析器不会对符号以外的内容进行任何前瞻他们正在解析的当前版本.您所描述的语法似乎不是LR(0)语法，这就是为什么在尝试不先行解析时会遇到麻烦的原因.它看起来确实是LR(1)，因此，通过在输入中查找1个符号可以轻松确定是移动还是减小.在这种情况下，当LR(1)解析器在堆栈上具有1时，它将向前看，看到下一个符号是+，并意识到它不应减少到A之后(因为唯一可以减少到第二个位置的规则仍然与+匹配.)

The problem you're describing is an issue with creating LR(0) parsers - that is, bottom-up parsers that don't do any lookahead to symbols beyond the current one they are parsing. The grammar you've described doesn't appear to be an LR(0) grammar, which is why you run into trouble when trying to parse it w/o lookahead. It does appear to be LR(1), however, so by looking 1 symbol ahead in the input you could easily determine whether to shift or reduce. In this case, an LR(1) parser would look ahead when it had the 1 on the stack, see that the next symbol is a +, and realize that it shouldn't reduce past A (since that is the only thing it could reduce to that would still match a rule with + in the second position).

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

An interesting property of LR grammars is that for any grammar which is LR(k) for k>1, it is possible to construct an LR(1) grammar which is equivalent. However, the same does not extend all the way down to LR(0) - there are many grammars which cannot be converted to LR(0).

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

See here for more details on LR(k)-ness:

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

这篇关于Shift-reduce:什么时候停止减少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！