compilation - how to resolve a shiftreduce conflict in bison? - Stack Overflow

admin管理员组

文章数量:1410682

I want to make a compilator for a language similar to C. Declarations go first, then functions. Declarations can only be "int" while functions can return "int" or "void". Below is not the whole grammar, but the part that generates the conflict. I don't understand why this conflict appear. It says that when it encounters a INT, it hesitates between shift if it's a declaration or reduce if it's a function.

My yacc file :

%{
#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);
}

My lex file :

%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);}
%%

My error:

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

I have tried:

• I read the whole Bison manual. It explains a lot but doesn't give solution to this kind of problem.
• I tried other grammars. More States, more rules...
• I tried using operators. %left %right %nonassoc

I know the problem is that my grammar isn't LALR and that yacc cannot make a choice between reduce or shift when encountering a INT token.

But I can't modify the grammar without modifying its meaning.

I want to make a compilator for a language similar to C. Declarations go first, then functions. Declarations can only be "int" while functions can return "int" or "void". Below is not the whole grammar, but the part that generates the conflict. I don't understand why this conflict appear. It says that when it encounters a INT, it hesitates between shift if it's a declaration or reduce if it's a function.

My yacc file :

%{
#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);
}

My lex file :

%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);}
%%

My error:

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

I have tried:

• I read the whole Bison manual. It explains a lot but doesn't give solution to this kind of problem.
• I tried other grammars. More States, more rules...
• I tried using operators. %left %right %nonassoc

I know the problem is that my grammar isn't LALR and that yacc cannot make a choice between reduce or shift when encountering a INT token.

But I can't modify the grammar without modifying its meaning.

• compilation
• bison
• yacc
• lex

Share Improve this question Follow edited Mar 7 at 14:42 mr Klaus asked Mar 6 at 19:09 mr Klausmr Klaus 1733 bronze badges 5

• How did you define INT, VOID & IDENT? – Scott Hunter Commented Mar 6 at 19:15
• 1 Don't say "I've tried everything". You haven't. Please provide the actual error message. – user207421 Commented Mar 7 at 0:14
• @ScottHunter I updated my post. Sorry it's my first question here. – mr Klaus Commented Mar 7 at 14:53
• @user207421 I updated my post. I can give the output file if needed. – mr Klaus Commented Mar 7 at 14:55
• Remembers that shift-reduce conflicts are not necessarily bad. Reduce-Reduce is. – user3344003 Commented Mar 7 at 16:54

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

The basic problem is that you have epsilon-rules function_list: /* empty */ and declaration_list: /*empty*/. This means that when it gets to the end of the declarations, it needs to reduce the empty declaration_list rule to start parsing functions. Problem is, it can't tell when it is at the end of the declaration list based on one token of lookahead, as either a declaration or a function may begin with INT. This is exacerbated by the use of right-recursion in the declaration_list rule, which means that last declaration needs to be recognized in order to start reducing all the declarations, before recognizing functions.

The easiest way to fix this is to get rid of the function epsilon rule and make the rules left recursive instead of right recursive.

declaration_list: declaration_list declaration | ;
function_list: function_list function | function ;

This does require a program to have at least one function, so if you want programs with no functions, you need to add that explicitly:

program: declaration_list function_list | declaration_list ;

本文标签： compilationhow to resolve a shiftreduce conflict in bisonStack Overflow