解决小班次减少冲突

Question

我遇到了 shift-reduce 冲突并将其减少到几行：

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' 标记时，它不知道是应该继续指令还是开始另一个指令。

基本上，预期的安排是：

{X! RETURN} {X!}

{X! RETURN X}

如何解决这个问题？似乎读取额外的令牌可以解决问题，但这必须使用 LALR(1) 来完成。

Answer 1

这绝对是对这种 shift-reduce 冲突的正确分析。语法明确但 LALR(2).

有一个从 LALR(k) 文法构造 LALR(1) 文法的机械过程，可以应用于此示例。但是我没有写出来，因为它很长，而且我怀疑它是否真的有用。我怀疑原来的语法更像是

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

其中 X 已替换为可以导出无限长度短语的非终结符。因此，对于任何 k，此文法都不是 LALR(k)。但是还是很明确的。

所以你最好的选择可能是让 Bison 生成一个 GLR 解析器，它可以处理任意明确的语法。如果您使用的是 bison 并且冲突状态在实践中很少发生，那么 GLR 的开销非常小，因为 bison 为确定性状态优化了 GLR。

解决小班次减少冲突

Solving small shift reduce conflict

bison

yacc

lex

shift-reduce-conflict

lalr