Re: How to read an understand the bison report file ?

[Akim Demaille]

Le 26 juin 2012 à 13:23, Timothy Madden a écrit :

> Hello

Hi!

> I wrote a grammar file for an approximation of the php language (with the 
> purpose of adding braces to single-statements under if, for, while, but that 
> is not included yet), that simply outputs the found tokens back to an output 
> stream.
> 
> My problem is I got like 233 shift/reduce conflicts (and 18 reduce/reduce 
> conflicts) and I do not really understand them. But searching the internet 
> shows most people have like 3 or 4 of them ... what did I do ?

You handle the whitespace characters and the comments at the parser
level, which is quite unusual.

> Is there a way for me to understand that report file bison outputs ?

Yes, read the documentation of the latest Bison release (2.5.1), where
a fair amount of space was devoted to describing these files.

> I looked a lot through it, but I can not get where the conflicts are comming 
> from. It does says something about the first rules, describing whitespace, 
> which I want to preserve as significant part of the grammar.
> 
> I have CenOS 6.2 64-bit (up-to-date), GNU bison 2.4.1 64-bit.

Old.

> The grammar and report files are attached.

For instance, you have:

state 88

    1 t_comment_or_whitespace: . T_WHITESPACE
    2                        | . T_COMMENT
    3 plain_comment_or_whitespace: . t_comment_or_whitespace
    4                            | . plain_comment_or_whitespace 
t_comment_or_whitespace
    5 t_comment_or_whitespaces: .  [T_BOOLEAN_OR]
    6                         | . plain_comment_or_whitespace
   90 boolean_or_expr: boolean_or_expr . t_comment_or_whitespaces T_BOOLEAN_OR 
t_comment_or_whitespaces boolean_and_expr
   91 conditional_expression: boolean_or_expr .  [T_CLOSE_TAG, T_AS, 
T_WHITESPACE, T_COMMENT, T_LOGICAL_AND, T_LOGICAL_OR, T_LOGICAL_XOR, 
T_DOUBLE_ARROW, "+= (T_PLUS_EQUAL)", "-= (T_MINUS_EQUAL)", "*= (T_MUL_EQUAL)", 
"/= (T_DIV_EQUAL)", ".= (T_CONCAT_EQUAL)", "%= (T_MOD_EQUAL)", "&= 
(T_AND_EQUAL)", "|= (T_OR_EQUAL)", "^= (T_XOR_EQUAL)", "<<= (T_SL_EQUAL)", ">>= 
(T_SR_EQUAL)", '}', ':', ',', ')', ']', '?', '=', ';']

    T_WHITESPACE  shift, and go to state 1
    T_COMMENT     shift, and go to state 2

    T_WHITESPACE  [reduce using rule 91 (conditional_expression)]
    T_COMMENT     [reduce using rule 91 (conditional_expression)]
    T_BOOLEAN_OR  reduce using rule 5 (t_comment_or_whitespaces)
    $default      reduce using rule 91 (conditional_expression)

    t_comment_or_whitespace      go to state 3
    plain_comment_or_whitespace  go to state 4
    t_comment_or_whitespaces     go to state 169

which means that Bison does not know whether to reduce or to shift
when a whitespace or a comment arrives after a boolean_or_expr.
By default it chose shift (always the case in S/R conflicts).  Yet
keeping that huge amount of conflicts just because of this is
troublesome, so I would definitely kill as many of these as I can.

In the present case, you want to tell Bison "reduction of the
rule conditional_expr: boolean_or_expr must prevail on the shifting of the 
tokens
whitespace and comments".  The tokens already have a name:
themselves.  The rule does not have a name (actually it's
more like a precedence level), use %prec to do so:

conditional_expression:
    boolean_or_expr %prec RULE
        |
    conditional_expression '?' conditional_expression ':' 
conditional_expression { $$ = $1 + $2; $$ += $3; $$ += $4; $$ += $5; }
    ;

and then, tell Bison that RULE has a lower precedence:

%left RULE
%left T_COMMENT T_WHITESPACE

and see that the conflict is fixed as expected:

state 88

    1 t_comment_or_whitespace: . T_WHITESPACE
    2                        | . T_COMMENT
    3 plain_comment_or_whitespace: . t_comment_or_whitespace
    4                            | . plain_comment_or_whitespace 
t_comment_or_whitespace
    5 t_comment_or_whitespaces: .  [T_BOOLEAN_OR]
    6                         | . plain_comment_or_whitespace
   90 boolean_or_expr: boolean_or_expr . t_comment_or_whitespaces T_BOOLEAN_OR 
t_comment_or_whitespaces boolean_and_expr
   91 conditional_expression: boolean_or_expr .  [T_CLOSE_TAG, T_AS, 
T_LOGICAL_AND, T_LOGICAL_OR, T_LOGICAL_XOR, T_DOUBLE_ARROW, "+= 
(T_PLUS_EQUAL)", "-= (T_MINUS_EQUAL)", "*= (T_MUL_EQUAL)", "/= (T_DIV_EQUAL)", 
".= (T_CONCAT_EQUAL)", "%= (T_MOD_EQUAL)", "&= (T_AND_EQUAL)", "|= 
(T_OR_EQUAL)", "^= (T_XOR_EQUAL)", "<<= (T_SL_EQUAL)", ">>= (T_SR_EQUAL)", '}', 
':', ',', ')', ']', '?', '=', ';']

    T_WHITESPACE  shift, and go to state 1
    T_COMMENT     shift, and go to state 2

    T_BOOLEAN_OR  reduce using rule 5 (t_comment_or_whitespaces)
    $default      reduce using rule 91 (conditional_expression)

    t_comment_or_whitespace      go to state 3
    plain_comment_or_whitespace  go to state 4
    t_comment_or_whitespaces     go to state 169

    Conflict between rule 91 and token T_WHITESPACE resolved as shift (RULE < 
T_WHITESPACE).
    Conflict between rule 91 and token T_COMMENT resolved as shift (RULE < 
T_COMMENT).

Repeat ad nauseam.  You can (and should) use RULE for several rules.