Re: Strange behavior

[Laurent Deniau]

Tim Van Holder wrote:
> 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.


This is also what I think. Here is what I really have:

direct_abstract_declarator_opt
    :
    | direct_abstract_declarator
    ;

As you can see, it is really empty. In fact, for the moment the grammar 
is free of code until I reach a clean set of rules (on top of the 
standard grammar) for solving the typename problem.

>  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.

No for the moment, nothing is attached to it, but it will at the end. So 
are you meaning that attaching code (neutral for the rule like $$=NULL) 
to a rule may change his behavior? I have tried to change all my 
optional rules to what they will be, that is:

THE_RULE_opt
        : { $$ = NULL; }
        | THE_RULE { $$ = $1; }
        ;

and nothing changed in either cases as expected.

Thanks for your help.

Regards,

ld.