为什么bison不符合这个语法规则？

Question

我有这些

lex

代币：

,[Yy] {
    return COMMAY;
}

(?xi:
    ADC|AND|ASL|BCC|BCS|BEQ|BIT|BMI|BNE|BPL|BRK|
    BVC|BVS|CLC|CLD|CLI|CLV|CMP|CPX|CPY|DEC|DEX|
    DEY|EOR|INC|INX|INY|JMP|JSR|LDA|LDX|LDY|LSR|
    NOP|ORA|PHA|PHP|PLA|PLP|ROL|ROR|RTI|RTS|SBC|
    SEC|SED|SEI|STA|STX|STY|TAX|TAY|TSX|TXA|TXS|
    TYA
) {
    yylval.str = strdup(yytext);
    for(char *ptr = yylval.str; *ptr = tolower(*ptr); *ptr++);

    return MNEMONIC;
}

\$[0-9a-fA-F]{2} {
    yylval.str = strdup(yytext);
    return ZEROPAGE;
}

[a-zA-Z_][a-zA-Z0-9_]+ {
    yylval.str = strdup(yytext);
    return IDENTIFIER;
}

以及

bison

中的这些语法规则：

expression:
    MNEMONIC '(' zp_identifier ')' COMMAY   { statement($1, $3,     "(zp),y"); }
|   MNEMONIC '(' zp_abs_identifier ')'      { statement($1, $3,     "(zp)"); }
;

zp_identifier:
    ZEROPAGE
|   IDENTIFIER
;

zp_abs_identifier:
    ZEROPAGE
|   ABSOLUTE
|   IDENTIFIER
;

由于某种原因这段代码：

; absolute indirect
lda ($9000)
lda (steps) 

; zp indirect
lda ($90)
lda (gold)

在

lda (steps)

处生成语法错误。我想说这符合

MNEMONIC '(' zp_abs_identifier ')'

规则，但看起来它试图寻找上面规则的

COMMAY

部分（并且失败）。

当我用

COMMAY

删除规则时，这部分会被正确解析。

Answer 1

我已将您的词典和语法插入 lex 和 bison 并生成结果解析器。 当用 bison 生成语法时，bison 显示语法有 2 个归约/归约冲突。

技术含义：

Shift/Reduce 解析器是表驱动的，有两个操作：shift 和 reduce。 这些操作由一个表定义，该表考虑了当前状态和先行标记。 Bison 是一个自动生成这些表格的工具。

当解析器可以从单个状态下的多个操作中进行选择时，就会发生冲突。 有两种类型：

• Shift/Reduce：解析器可能会移位或减少。
• Reduce/Reduce：解析器可能会减少两种不同的产生式规则

通常，Shift/Reduce 冲突会通过默认的 Shift 操作自动解决。这通常有效，但并非总是有效。因此，转移/减少冲突不一定是一个问题。

然而，Reduce/Reduce 冲突是一个关键问题，没有适当的方法来解决这种冲突。因此，如果您看到这些冲突，您可能会遇到意想不到的行为。

为什么会出现reduce/reduce冲突？

发生冲突是因为解析器需要决定它必须探索哪个产生式规则。规则一旦选定就不会再回头。 由于产生式规则有一个公共部分，解析器足够聪明，可以先解析公共部分，然后再决定产生式规则应该是什么。

但是，要解析标识符，它必须决定生成 zp_identifier 或 zp_abs_identifier 非终结符。当两个非终结符都工作时，它会猜测一些非终结符。 在这种情况下，它默认选择 zp_identifier，因为选择了这个非终结符，它强制生产规则成为第一条规则。

这就是它期望 COMMAY 的原因。

如何解决这个问题：

该问题是由于缺乏前瞻或使用不够强大的解析算法引起的。

一个简单的解决方案是使用 Bison 的 GLR 版本：https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html， 这使得解析器分别探索不明确的选择，这将导致两个标识符都被探索，随后具有错误标识符的分支被销毁，仅保留有效分支。 请注意，如果语法本质上是不明确的，即使 GLR 也无法拯救您，语法重建是这种情况下唯一剩下的工具。

另一种方法是通过语法重构来消除reduce/reduce冲突。 这是一个相当复杂的方法，这肯定会降低你的语法的逻辑性。 在这种情况下，问题是由 zp_abs_identifier 和 zp_identifier 中的公共部分引起的。

我建议去掉 ABSOLUTE 的特殊情况，并使用可选的 COMMAY 终端来制作一般情况：

expression:
    MNEMONIC LEFT_PARENTHESIS ABSOLUTE RIGHT_PARENTHESIS
    | MNEMONIC LEFT_PARENTHESIS zp_identifier RIGHT_PARENTHESIS optional_commay
    ;

optional_commay:
    |
    COMMAY
    ;

zp_identifier:
    ZEROPAGE
    | IDENTIFIER
    ;

这样就不存在reduce/reduce冲突了，特殊情况还是解决了。