编写yacc算术表达式校验程序出现shift/reduce冲突如何解决

冲突原因 #

你遇到的2个移位/规约冲突由以下两个问题共同导致：

• 你将+、-、*、/四种优先级、结合性完全不同的运算符统一归为OPERATOR这一个token，yacc无法区分不同运算符的优先级差异
• 没有显式指定运算符的结合性，解析连续同优先级运算时，yacc无法判断应该优先规约左边的表达式，还是优先移位读入右边的运算符

修复步骤 #

1. 修改lex代码，拆分运算符token返回值 #

不要统一返回OPERATOR，改为为每个运算符返回独立的token：

%{
    #include "y.tab.h"
%}

%%
[0-9]+ { return NUMBER; }
[_a-zA-Z][_a-zA-Z0-9]* { return ID; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return MUL; }
"/" { return DIV; }
.|\n { return *yytext; }
%%

int yywrap(){
    return 1;
}

2. 修改yacc代码，指定运算符结合性和优先级 #

通过%left指定左结合性，按优先级从低到高排列运算符，优先级低的写在前面，优先级高的写在后面：

%{
    #include<stdio.h>
    int yylex();
    void yyerror(const char*);
%}

%token NUMBER ID
/* 指定结合性和优先级，越靠后优先级越高 */
%left PLUS MINUS
%left MUL DIV

%%
E : E '\n' { return 0; }
  | E PLUS E
  | E MINUS E
  | E MUL E
  | E DIV E
  | '(' E ')'
  | NUMBER
  | ID
  ;
%%

void yyerror(const char* s){
    printf("%s\n", s);
}

int main(){
    if(yyparse() == 0)
        printf("Valid Arithmetic Expression\n");
    else
        printf("Invalid Arithmetic Expression\n");
}

修改完成后重新编译即可消除移位/规约冲突警告，同时解析逻辑也符合常规算术运算的优先级和结合性规则。

内容的提问来源于stack exchange，提问作者Ashutosh Aswal