Re: Left Recursion in Yacc

Mike <student1330@my-deja.com> writes:


> expression:expression ',' ITEM
>:ITEM


> Now I want to create a list of items separated by a ',' from my input.
> Although it is clear that the grammar would allow me to have a list of
> one or more items. What is confusing for me is the actions that would
> be taken.


Consider this token sequence: ITEM , ITEM , ITEM <something that is not ,>
Then, yacc would act as


ITEM: shift
seeing ,: reduce ITEM -> expression
,: shift
ITEM: shift
,: reduce expression , ITEM -> expression
,: shift
ITEM: shift
seeing <something else>: reduce expression , ITEM -> expression


So if you have an action in the rhs of the first rule, $1 is the
expression representing the first n-1 items, and $3 is the nth item.


> More specifically, how exactly would the recursion be
> handled. Would I get the list in reverse order?


It depends on what the semantic action is. If you do


expression: expression ',' ITEM { $$ = Consexpression($3, $1); }
                    | ITEM { $$ = Consexpression($1, Nilexpression()); }


then yes, the list would be in reverse order. If you append $3 to the
existing $1 list, then you get them in the right order.


Hope this helps,
Martin

Return to the comp.compilers page.
Search the comp.compilers archives again.