How to remove shift/reduse warning?

Question

I am trying to make a compiler and I am now trying to make the parser. I get a warning on this state : State 89

   62 expr: '(' expr . ')'
   66     | expr . '+' expr
   67     | expr . '-' expr
   68     | expr . '*' expr
   69     | expr . '/' expr
   70     | expr . '%' expr
   74     | expr . '&' expr
   75     | expr . '|' expr
   77 cond: expr .
   78     | '(' expr . ')'
   82     | expr . '=' expr
   83     | expr . "<>" expr
   84     | expr . '<' expr
   85     | expr . '>' expr
   86     | expr . ">=" expr
   87     | expr . "<=" expr

    "<>"  shift, and go to state 91
    ">="  shift, and go to state 92
    "<="  shift, and go to state 93
    '+'   shift, and go to state 94
    '-'   shift, and go to state 95
    '|'   shift, and go to state 96
    '*'   shift, and go to state 97
    '/'   shift, and go to state 98
    '%'   shift, and go to state 99
    '&'   shift, and go to state 100
    '='   shift, and go to state 101
    '<'   shift, and go to state 102
    '>'   shift, and go to state 103
    ')'   shift, and go to state 119


$default  reduce using rule 77 (cond)


State 119

   62 expr: '(' expr ')' .
   78 cond: '(' expr ')' .

    "and"     reduce using rule 62 (expr)
    "and"     [reduce using rule 78 (cond)]
    "or"      reduce using rule 62 (expr)
    "or"      [reduce using rule 78 (cond)]
    ':'       reduce using rule 62 (expr)
    ':'       [reduce using rule 78 (cond)]
    ')'       reduce using rule 62 (expr)
    ')'       [reduce using rule 78 (cond)]
    $default  reduce using rule 62 (expr)

My grammar for this part is :

expr:
    T_const |
    T_char_const | 
    l_value | 
    '(' expr ')' | 
    func_call |
    '+' expr | 
    '-' expr | 
    expr '+' expr |
    expr '-' expr | 
    expr '*' expr | 
    expr '/' expr | 
    expr '%' expr |
    T_true | T_false |
    '!' expr | 
     expr '&' expr |
    expr '|' expr
;

cond:
    '(' cond ')' |
     expr |
     T_not cond |
     cond T_and cond |
     cond T_or  cond |
     expr '=' expr |
     expr T_not_equal expr |
     expr '<' expr |
     expr '>' expr |
     expr T_greater_equal expr |
     expr T_less_equal expr
 ;

What is the problem here and how could i probably fix it?I have already fixed some shift/reduce problems, but generally i haven't understand what this problem is. Thank you very much

Answer 1

The grammar quoted by your question has the production:

cond: '(' cond ')'

But the one quoted from the output file has the production:

cond: '(' expr ')'

There are some other discrepancies which make it clear that the output file was not generated from the quoted​ grammar. That complicates the task of answering your question, although at the root the problem is the same in both cases. I'm using the output file as a reference for the remainder of the answer.

Since you also have:

cond: expr

there is an ambiguity in any context in which a cond derives a parenthesized string. (The conflict shown for State 119 shows that pretty clearly.) Suppose, for example, the parser encounters

not ( x )

x can only be reduced to expr (via l_value), but then there are two possibilities:

not ( expr ) => not expr [ from expr: ( expr ) ]
             => not cond [ from cond: expr ]
not ( expr ) => not cond  [ from cond: ( eχpr ) ]

This ambiguity exists in all contexts where cond is allowed.

Dividing expressions syntactically into boolean and non-boolean expressions is tricky, and mostly unnecessary. You eventually allow any expression to be used as a boolean (cond: expr), and it is quite likely that you will allow (or your users will expect you to allow) a boolean value to be assigned to a variable. So the easiest and most common solution is to just say that a value is a value and an expression is an expression, without special-casing booleans.

If you really feel the need to syntactically separate the two, you'll find an example in this recent question.