Re: empty component causes shift/reduce conflict

[Jibin Han]

Hello Hans,
    Thanks for your reply. It's clearer now for me, though I can not say it's
completely clear. In your reply you mentioned this example,

list: '[' items ']'

items:
    /* empty */
  | item ',' items

    It reminds me another problem: how to draw a parse tree to this? Is the
following correct?

    list----'['   items   ']'
                      |
                      ------------- item   ,  items
                      |
                      ------------- /* empty */

    I was told if I can draw the parsing tree correctly, then it's easy to see
the shift/reduce conflict, but from this tree above, it is not so easy for
me to
do that. I Guess I am still needing pass some early learning curve somewhere.

thanks,

jibin han

Hans Aberg wrote:

> Reply-to: address@hidden
>
> At 14:59 -0700 2003/02/07, Jibin Han wrote:
> >    I am new to bison, but from my experience, if there is an empty
> >component in a rule like this,
> >        result: /* empty */
> >                |
> >                comp1 comp2 {...}
> >
> >    then it definetely causes shift/reduce conflict.
>
> No, that is not the case; properly written empty RHS rules do not cause
> shift/reduce conflicts. For example,
>
> list: '[' items ']'
>
> items:
>     /* empty */
>   | item ',' items
>
> will usually not cause any conflicts (unless "item" contains some stuff
> causing it).
>
> > But such conflict
> >in this case is harmless because the Bison default choice, shift comp1,
> >is always what we want.
>
> Try to avoid relying on Bison's default, because then the grammar may still
> compile properly if you some day would switch to another parser algorithm
> than the LALR(1) that Bison normally uses.
>
> Shift/reduce conflicts can often be resolved by putting attributes %left,
> etc. onto some suitable tokens of the involved rules.
>
> Also, if you have multiple adjacent rules in the grammar expansion, that
> will cause conflicts, because the parser generator will not know which
> actions of which empty rules to apply to. For example:
> A1: /* empty */ {a0}
>   | B1          {b1}
>
> B1: /* empty */ {b0}
>   | C1
> ...
>
> Here, if he input leads to a C1, any combination of actions a0, b0 can be
> applied, because the grammar with actions is ambiguous. -- If we were only
> interested in grammars without actions, this would not be a problem though,
> as the empty expansion would be unique.
>
> Read more about it in the Bison manual, ch 5, and also it calculator example.
>
>   Hans Aberg
>
> _______________________________________________
> address@hidden http://mail.gnu.org/mailman/listinfo/help-bison