Solving shift/reduce conflict in expression grammar

Question

I am new to bison and I am trying to make a grammar parsing expressions. I am facing a shift/reduce conflight right now I am not able to solve.

The grammar is the following:

%left "[" "("
%left "+"

%%

expression_list : expression_list "," expression
                | expression 
                | /*empty*/
                ;


expression :  "(" expression ")"  
           |  STRING_LITERAL      
           |  INTEGER_LITERAL           
           |  DOUBLE_LITERAL
           |  expression "(" expression_list ")" /*function call*/
           |  expression "[" expression "]" /*index access*/
           |  expression "+" expression         
           ;

This is my grammar, but I am facing a shift/reduce conflict with those two rules "(" expression ")" and expression "(" expression_list ")". How can I resolve this conflict?

EDIT: I know I could solve this using precedence climbing, but I would like to not do so, because this is only a small part of the expression grammar, and the size of the expression grammar would explode using precedence climbing.

If that is the entirety of your grammar, it has no shift-reduce conflict. However, I doubt it is your entire grammar. — rici
wow I feel realy stupid right now... I found a typo in another rule, which affected this one — Exagon
That's why we ask for a minimal reproducible example, which is very different from "a few lines of my code". If you produce the minimal reproducible example, it will often solve your problem for you by helping you clarify the issues. — rici

rici rici · Accepted Answer · 2017-03-10T00:46:06

There is no shift-reduce conflict in the grammar as presented, so I suppose that it is just an excerpt of the full grammar. In particular, there will be precisely the shift/reduce conflict mentioned if the real grammar includes:

%start program
%%
program: %empty
       | program expression

In that case, you will run into an ambiguity because given, for example, a(b), the parser cannot tell whether it is a single call-expression or two consecutive expressions, first a single variable, and second a parenthesized expression. To avoid this problem you need to have some token which separates expression (statements).

There are some other issues:

expression_list : expression_list "," expression
                | expression 
                | /*empty*/
                ;

That allows an expression list to be ,foo (as in f(,foo)), which is likely not desirable. Better would be

arguments: %empty
         | expr_list
expr_list: expr
         | expr_list ',' expr

And the precedences are probably backwards. Usually one wants postfix operators like call and index to bind more tightly than arithmetic operators, so they should come at the end. Otherwise a+b(7) is (a+b)(7), which is unconventional.

Solving shift/reduce conflict in expression grammar

1 Answers