如何解决Bison中类C语言的INT移进/归约冲突?
类C语言编译器的Bison移进/归约冲突解决问题
我正在开发一款类C语言的编译器,核心规则:
- 声明语句必须放在函数定义之前;
- 声明仅支持int类型,函数返回值可以是int或void。
目前遇到语法冲突:当解析器遇到INT令牌时,Bison无法判断应该执行移进(将其作为声明处理)还是归约(将其作为函数返回值处理)。
Yacc代码
%{ #include <stdio.h> #include <stdlib.h> extern int yylineno; int yylex(void); int yyerror(char* s); %} %token IDENT INT VOID %% program : declaration_list function_list ; declaration_list : declaration declaration_list | ; declaration : test ';'; function_list : function function_list | ; function : test param | VOID IDENT param; test : INT IDENT ; param : '(' ')' '{' '}'; %% int yyerror(char*s) { fprintf(stderr,"%s. Line: %d\n",s,yylineno); exit(1); } int main() { yyparse(); return(0); }
Lex代码
%option noyywrap %{ #include <stdio.h> #include <stdlib.h> #include "y.tab.h" extern int yylineno; %} %% [ \t\n] ; "int" {return INT;} "void" {return VOID;} [a-z]+ {return IDENT;} "(" return '('; ")" return ')'; ";" {return ';';} . {fprintf(stderr,"caractère invalide; %c. Ligne: %d\n", yytext[0], yylineno);} %%
错误信息
warning: 2 conflicts shift/reduce [-Wconflicts-sr] warning: conflict shift/reduce on token INT [-Wcounterexamples] first example: • INT IDENT ';' declaration_list function_list $end Shift derivation $accept ↳ 0: program $end ↳ 1: declaration_list function_list ↳ 2: declaration declaration_list ↳ 4: test ';' ↳ 9: • INT IDENT Second example: • INT IDENT param function_list $end Reduce derivation $accept ↳ 0: program $end ↳ 1: declaration_list function_list ↳ 3: ε • ↳ 5: function function_list ↳ 7: test param ↳ 9: INT IDENT
已尝试的解决方法
- 通读Bison手册,未找到适配该场景的解决方案;
- 尝试调整语法规则、增加解析状态;
- 尝试使用
%left、%right、%nonassoc等运算符优先级指令。
已知问题根源是当前语法不属于LALR文法,但不能修改语法的语义规则,请问该如何解决这个冲突?
内容的提问来源于stack exchange,提问作者mr Klaus
相关产品推荐
相关产品推荐

