解决小转变减少冲突 [英] Solving small shift reduce conflict

问题描述

我遇到了减少班次的冲突，并将其简化为几行:

I have had a shift-reduce conflict and reduced it to a couple of lines:

start               : instruction_A;

instruction_A       : instruction_A instruction
                    |
                    ;

instruction         : RETURN 'X'
                    | RETURN
                    | 'X' '!'
                    ;

3: shift/reduce conflict (shift 6, reduce 5) on 'X'
state 3
    instruction : RETURN . 'X'  (4)
    instruction : RETURN .  (5)

    'X'  shift 6
    $end  reduce 5
    RETURN  reduce 5

我的猜测是表达式 X！无法解析RETURN X！，因为当解析器到达"X"令牌时，它不知道是否应该继续该指令或开始另一条指令.

My guess is that the expression X! RETURN X! cannot be parsed because when the parser reaches the 'X' token, it does not know if it should continue the instruction or start another one.

基本上，预期的安排是:

Basically, the expected arrangements are:

{X！返回} {X！}

{X！返回X}

该如何解决?好像读一个额外的令牌似乎可以解决问题，但这必须使用LALR(1)完成.

How to solve this? It seems like reading an extra token would solve the problem, but this must be done with LALR(1).

推荐答案

这绝对是对这种减少班次冲突的正确分析.语法是明确的，但是LALR(2).

That's definitely the correct analysis of this shift-reduce conflict. The grammar is unambiguous but LALR(2).

有一种从LALR( k )语法构造LALR(1)语法的机械方法，该方法可以应用于本示例.但是我没有写出来，因为它很长，我怀疑它是否真的有用.我怀疑原始语法更像是

There is a mechanical procedure to construct an LALR(1) grammar from a grammar which is LALR(k), and that could be applied to this example. But I didn't write it out because it's quite long, and I doubt that it is actually useful. I suspect that the original grammar was more like

statement
    : return_statement
    | expr_statement
    | ...
return_statement
    : "return" expression
    | "return"
expression_statement
    : expression '!'

其中 X 已被非终结符替换，该终结符可以导出无限制长度的短语.结果，该语法不是任何 k 的LALR( k ).但这仍然是明确的.

Where X has been replaced with a non-terminal which can derive phrases of unbounded length. As a result, this grammar is not LALR(k) for any k. But it's still unambiguous.

因此，最好的选择可能是要求Bison生成GLR解析器，该解析器可以处理任意明确的语法.如果您使用的是野牛，而在实践中很少发生冲突状态，则GLR的开销非常小，因为野牛针对确定性状态优化了GLR.

So your best option is probably to ask Bison to generate a GLR parser, which can handle arbitrary unambiguous grammars. If you're using bison and the conflicted states occur rarely in practice, then the overhead of GLR is very small, since bison optimises GLR for deterministic states.

这篇关于解决小转变减少冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！