Re: Another bison problem (and also left vs. right recursion)

[Carl Cerecke]

Andrei Harangus wrote:
> Hy,
>  
> After solving the previous problem I would like to direct your attention 
> to a more complicated one.
> I am writing a rather large grammar that generates shift/reduce and 
> reduce/reduce conflicts:
> ...
> call : ID '(' call_list ')' {;}
> call_list : expr ',' call_list
>           | call ',' call_list
>           | expr
>           | call
> ;
>  
> expr : ...
>      | call <-- HERE IT DOES
> ;
> ...
>  
> I know that the grammar is ambiguous, but I was wondering wether just by 
> defining operator priorities
> I could solve the problem (which I wasn't able to do), or I'll have to 
> change the grammar
> (and I don't know how).

Operator precedence will not help here. You'll have to change the grammar.

I suggest removing
call_list -> call ',' call_list
and
call_list -> call

you don't need the above two rules because
call_list -> expr ',' call_list
and
call_list -> expr

cover the first two cases, because expr -> call




While we are on the topic of modifying grammars, does anyone
know the speed difference (if any) between left recursion
and right recursion in bison?
i.e.
is
call_list -> expr ',' call_list
less efficient than
call_list -> call_list ',' expr

I know right recursion results in stack growth proportional to
the number of items in the list, but for practical purposes is
there enough of a difference to matter?