标签: shift-reduce

给出一个简单的语法,就像

rule1
    := token1 token2 token3 token4
    || token1 token2 token3 token3;

转移前三个令牌,然后查看第四个令牌以查看要减少哪个规则,并简单地执行三个令牌的前瞻以查看要减少哪个规则之间有什么区别？

我正在尝试学习Lemon解析器生成器的基础知识,但我很快就陷入了困境.

这是一个很小的语法:

%right PLUS_PLUS.
%left DOT.

program ::= expr.

member_expr ::= expr DOT IDENTIFIER.

lhs_expr ::= member_expr.

expr ::= lhs_expr.
expr ::= PLUS_PLUS lhs_expr.

它导致1个解析冲突:

State 3:
      (3) expr ::= lhs_expr *
      (4) expr ::= PLUS_PLUS lhs_expr *

                           DOT reduce       3      expr ::= lhs_expr
                           DOT reduce       4       ** Parsing conflict **
                     {default} reduce       4      expr ::= PLUS_PLUS lhs_expr

然而,如果我重写最后一条规则如下:

expr ::= PLUS_PLUS expr DOT IDENTIFIER.

然后它不会导致冲突.但我不认为这是正确的方法.

如果有人能解释什么是正确的方式,为什么,我会很感激.

我正在尝试学习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 …

我一直试图解决一个看似简单的转变/减少冲突,但无济于事.当然,如果我忽略冲突,解析器工作正常,但如果我重新组织我的规则,我会觉得更安全.在这里,我简化了一个相对复杂的语法到单一冲突:

statement_list
  : statement_list statement 
  | 
  ;

statement
  : lvalue '=' expression
  | function
  ;

lvalue
  : IDENTIFIER
  | '(' expression ')'
  ;

expression
  : lvalue
  | function
  ;

function
  : IDENTIFIER '(' ')'
  ;

使用yacc中的verbose选项,我得到此输出文件描述具有上述冲突的状态:

state 2

    lvalue  ->  IDENTIFIER .   (rule 5)
    function  ->  IDENTIFIER . '(' ')'   (rule 9)

    '('  shift, and go to state 7

    '('  [reduce using rule 5 (lvalue)]
    $default reduce using rule 5 (lvalue)

谢谢你的帮助.

LL(1) 解析器需要一个前瞻符号来决定使用哪个产生式。这就是为什么我一直认为使用术语“先行”的原因，当解析器查看下一个输入标记而不“消耗”它时（即它仍然可以通过下一个操作从输入中读取）。然而，LR(0) 解析器让我怀疑这是正确的：

我见过的每个 LR(0) 解析器示例也使用下一个输入标记来决定是移动还是减少。在减少的情况下，不消耗输入令牌。

我使用免费软件工具“ParsingEmu”生成 LR 表并在下面对单词“aab”执行 LR 评估。如您所见，列标题包含标记。从评估中您可以看到解析器正在通过查看下一个输入标记来决定使用哪一列。但是当解析器在步骤 4 - 6 中减少时，输入不会改变（尽管解析器在执行到下一个状态的转换时需要知道下一个输入标记“$”）。

语法：

S -> A
A -> aA
A -> b

桌子：

评估：

现在由于我的困惑，我做了以下假设：

1. 我对“lookahead”定义的假设（lookahead = input token not be used）是错误的。Lookahead 对于 LL 解析器或 LR 解析器意味着两种不同的东西。如果是这样，那么如何定义“前瞻”？

2. LR 解析器具有（从理论的角度来看，当您使用下推自动机时）额外的内部状态，它们通过将输入标记放在堆栈上来消耗输入标记，因此能够通过查看来做出移位减少决策在堆栈上。

3. 上面显示的评估是LR(1)。如果为真，LR(0) 评估会是什么样子？

现在什么是正确的，1、2 或 3 还是完全不同的东西？