为何Bison无法匹配指定语法规则？Lex/Bison解析异常问题

现有定义与代码 #

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 ')'规则，但Bison会优先尝试匹配带COMMAY的规则，当后续没有COMMAY时匹配失败，且不会自动回溯尝试第二个规则。移除带COMMAY的规则后，解析可正常进行。

问题原因与解决方案 #

原因 #

Bison的LR解析器在处理歧义规则时，会优先选择定义顺序更早的规则。这里第一个expression规则是带COMMAY的变体，解析器遇到lda (steps)时，会先尝试匹配该规则，期望后续出现COMMAY令牌，但实际不存在，因此抛出语法错误。

解决方案 #

调整expression规则的顺序，把不带COMMAY的规则放在前面，让解析器优先匹配该规则：

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

这样当解析到lda (steps)时，会直接匹配第一个规则；而遇到带,y的指令（如lda ($10),y）时，解析器会在匹配完zp_identifier和)后，发现后续有COMMAY，从而回溯匹配第二个规则。

内容的提问来源于stack exchange，提问作者Bart Friederichs