Bison reduce/reduce conflict

Question

I'm getting a reduce/reduce conflict on the following grammar (excerp)

 declaration : type list_of_id

        list_of_id : ID                             
                   | list_of_id ',' ID              
                   ;

        type : PATH   
             | SCAL 
             ;

        assignment : ID ":=" param
                   | ID ":=" expr

        param :  point relative_param
              | ID relative_param   

        point : '(' expr ',' expr ')'
              | '(' expr  ':' expr ')'

         relative_param : /* empty rule */ 
                        | "--" '+' param
                        | "--" CYCLE relative_param     
                        | "--" param 

        expr : NB                          
             | ID                         ``                               
             | expr '+' expr              
             | expr '-' expr             
             | expr '*' expr                   
             | expr '/' expr                   
             | '(' expr ')'

I see that when the input is : foo := bar , there are two possible derivations:

assignment-> ID ":=" param and param -> ID
assignment-> ID ":=" expr and expr-> ID

I used ID twice in the grammar because a variable can be either of type path or scal. How can i remove this conflict without using the glr-parser option ?

I tried to split ID in two possibilies : ID_PATH and ID_SCAL and change productions param and expr to :

param : point relative_param
        | ID_PATH relative_param
        ;

  expr : NB
       | ID_SCAL
       | expr '+' expr
       | expr '-' expr
       | expr '/' expr
       | '(' expr ')'

but in this case , how can i differenciate those two (ID_SCAL and ID_PATH) in the lexer ?

Chris Dodd Chris Dodd · Accepted Answer · 2013-04-20T18:20:56

Well, as you've diagnosed, the problem is that your grammar is ambiguous -- it has two different ways of parsing an input like Foo := Bar. So the first thing you need to decide is, which should it be? and how do you know? If you (a human reading the code) were to see this in the language you're trying to parse, how would you know if Bar is an expression or a param with no relative_param?

If it depends on some previous declaraion of Bar, then that is how you need to solve this. You need to keep information about the previously seen declarations in a symbol table, and then use that symbol table in the lexer to look up identifiers they are recognized in order to decide if the lexer should return ID_PATH or ID_SCAL.

If it depends on a previous declaration of Foo then you do something similar, but you'll need to change the grammar to be something more like:

assignment: ID_PATH ":=" param
          | ID_SCAL ":=" expr
          ;

Bison reduce/reduce conflict

1 Answers