解决小班次减少冲突

Solving small shift reduce conflict

我遇到了 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) 来完成。

这绝对是对这种 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。