Re: Strange behavior

[Tim Van Holder]

Laurent Deniau wrote:
> I am using Bison 1.35 and 1.875 to parse the ISO C99 grammar and I found 
> a strange behavior on a very simple case:
>
> If I use the rule:
>
> direct_abstract_declarator
>   : '(' abstract_declarator ')'
>   | direct_abstract_declarator_opt '[' assignment_expression_opt ']'
>   | direct_abstract_declarator_opt '[' '*' ']'
>   | '(' parameter_type_list_opt ')'
>   | direct_abstract_declarator '(' parameter_type_list_opt ')'
>   ;
>
> I have only one shift/reduce conflict for all the grammar (the IF ELSE 
> one). But if I use the rule
>
> direct_abstract_declarator
>   : '(' abstract_declarator ')'
>   | direct_abstract_declarator_opt '[' assignment_expression_opt ']'
>   | direct_abstract_declarator_opt '[' '*' ']'
>   | direct_abstract_declarator_opt '(' parameter_type_list_opt ')'
>   ;
>
> So while as far as I know
>
>   | '(' parameter_type_list_opt ')'
>   | direct_abstract_declarator '(' parameter_type_list_opt ')'
>
> and
>
>   | direct_abstract_declarator_opt '(' parameter_type_list_opt ')'
>
> should be equivalent, the second rule introduces two new shift/reduce 
> conflicts...

It's because of bison only seeing 1 step ahead.
In the first rule, if a '(' is seen, bison can munge it and get the next
token in order to decide whether it's an abstract_declarator or a
parameter_type_list_opt.
In the second rule, when bison sees a '(', it has 2 options: it can
simply munge it and go for an abstract_declarator (i.e. shift), or it
can throw away direct_abstract_declarator_opt as empty before munging it
and continuing with a parameter_type_list_opt (i.e. reduce).
Now if the empty production in direct_abstract_declarator_opt has no
action associated with it, these two choices are really equivalent (as
far as I can see), and I suppose bison could avoid generating a S/R
conflict in that case.  But since you say this is a full grammar, there
probably IS an action associated with the empty production in _opt rules
(e.g. "$$ = NULL"), in which case bison has to decide between running
that or not running anything, resulting in a real conflict.