Shift/reduce conflict example for a C compiler

Question

Here is a part of C compiler:

Exp     :
        INTNUMBER                       { $$ = $1; }
        | lvalue                        { $$ = $1; }
        | REALNUMBER                        { $$ = $1; }
        | CHARVALUE                         { $$ = $1; }
        | TRUE                          { $$ = $1; }
        | FALSE                         { $$ = $1; }
        | Exp '+' Exp                       { $$ = $1 + $3; }
        | Exp '*' Exp                       { $$ = $1 * $3; }
        | Exp '/' Exp                       { $$ = $1 / $3; }
        | Exp '-' Exp                       { $$ = $1 - $3; }
        | Exp '%' Exp                       { $$ = $1 % $3; }
        | Exp AND Exp                           { $$ = $1 && $3; }
        | Exp OR Exp                    { $$ = $1 || $3; }
        | Exp LEQ Exp                   { $$ = $1 <= $3; }
        | Exp GEQ Exp                   { $$ = $1 >= $3; }
        | Exp EQ Exp                    { $$ = $1 == $3; }
        | Exp NEQ Exp                   { $$ = $1 != $3; }
        | Exp GE Exp                        { $$ = $1 > $3; }
        | Exp LE Exp                        { $$ = $1 < $3; }
        | '-' Exp %prec UMINUS                  { $$ = -1 * $2; }
        | STRING                        { $$ = $1; }
        | '('Exp')'                         { $$ = $2; }    
        | lvalue '=' Exp                    { $1 = $3; }
        | ID'('ExpList')'                   {printf("Exp");}
        ;


IDD     :   
        ID                          { printf("IDD"); }
        | IDD '[' Exp ']'                   {printf("IDD");}
        ;

ExpList 
        :                                   { printf("ExpList"); }
         ExpPlus                            {printf("ExpList");}
        |       
        ;

ExpPlus :
        Exp                             { printf("Exp\n"); }
        | Exp ',' ExpPlus                   {printf("ExpPlus");}
        ;

in which, ID is a terminal (that is, in C an ID can start with _ or [a-zA-Z]. While parsing this code with bison using the -v flag, I got a shift/reduce conflict as follow:

52 IDD: ID .
   78 Exp: ID . '(' ExpList ')'

    '('  shift, and go to state 56

    '('       [reduce using rule 52 (IDD)]
    $default  reduce using rule 52 (IDD)

I have resolved all the shift/reduce conflicts that I faced so far. But I cannot understand how this one should be solved.

Thank you

You'll need to show more of your grammar in order for this question to be answered. The excerpt you show does not even indicate in what context `IDD` might be used; furthermore, it is most likely that the conflict is the result of a context in which `Exp` is used, which also is not visible. — rici, Aug 25 '17 at 19:38

score 0 · Answer 1 · answered Aug 25 '17 at 20:50

The conflict itself occurs because, having seen an ID with a parenthesis ( in the lookahead token, the parser could either do a shift and begin working on the ID ( ExpList ) function call syntax, or reduce the ID to an IDD and leave the ( in the token stream.

This is the same problem typically seen with typical LALR grammars to handle:

  if (exp1)
      if (exp2)
         stmt;
/**/else  /* which "if" does this "else" match?! */

where, at this point (with else in the lookahead) the parser can either shift to a new state which will bind the else to the second (deeper-nested) if, or reduce the if (exp2) stmt; to a statement that goes with the first if and leave the else to be an else part for that first if.

Yacc-like parsers, when encountering shift/reduce conflicts, always favor the shift. In this case it's what we want with the if, and it's also what you would want with your grammar fragment. So you are not required to deal with it. (I can't tell, however, if the rest of your grammar is OK, I'm commenting only on this one particular bit. In general shift/reduce conflicts "work the way you expect", and it's reduce/reduce conflicts that are problematic.)

See also Chris Dodd's answer to Reforming the grammar to remove shift reduce conflict in if-then-else.

score 0 · Answer 2 · answered Aug 25 '17 at 20:51

There is not enough information to solve your problem You do not have enough code to figure out what exactly you are trying to do. In particular we have nothing that shows the relationship between the IDD and EXP nonterminals

However, you have

IDD : ID

and

Exp : ID'('ExpList')'

that is causing the problem of whether

  SomeID

in an input stream is an IDD or an EXP.

Shift/reduce conflict example for a C compiler

2 Answers2