Search code examples
ccompiler-constructionbisonlex

Conflict Bison parser

I'm new to Bison and I'm having trouble with shift/reduce conflicts...

I'm writing the rules for grammar for the C language: ID is a token that identifies a variable, and I wrote this rule to ensure that the identifier can be considered even if it is written in parentheses.

id              : '(' ID ')'    {printf("(ID) %s\n", $2);}
                |     ID        {printf("ID %s\n", $1);}
                ;

Output of Bison conflicts is:

State 82

   12 id: '(' ID . ')'
   13   | ID .

    ')'  shift, and go to state 22

    ')'       [reduce using rule 13 (id)]
    $default  reduce using rule 13 (id)

How can I resolve this conflict?

I hope I was clear and thanks for your help.

Solution

  • Your id rule in itself cannot cause a shift/reduce error. There must be some other rule in your grammar that uses ID. For example, you have an expression rule such as:

    expr: '(' expr ')'
    | ID
    ;

    In the above example, ID can reduce to id or to expr and the parser doesn't know which reduction to take. Check what is in state 22.

    Edit: you ask "what can I do to solve the conflict?"

    I'm writing the rules for grammar for the C language: ID is a token that identifies a variable, and I wrote this rule to ensure that the identifier can be considered even if it is written in parentheses

    A variable in parenthesis as a left-hand side is invalid in C, so it can only occur in a right-hand side. Then you can consider it an expression, so just remove your rule and where you use id replace that with expr.