Re: empty component causes shift/reduce conflict

[Hans Aberg]

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