Re: Left Recursion in Yacc

Hi Mike,


> I have a question about left recursive rules in Yacc/Bison. Suppose I
> have a left recursive rule
>
> expression: expression ',' ITEM
> | ITEM
>
> Now I want to create a list of items separated by a ',' from my
> input.
>
> ...
>
> [You can make the list any way you want, although if you do the
> simplest think and link $1 to $3 in your first rule, you'll end up
> with a backwards list. It's easy enough to make one pass at the end
> and reverse the links. -John]


Just to add to what others have already written, make sure you don't
simply set $1->next to $3 in an attempt to append ITEM to expression.


Assuming you don't want to place list reversal code where you can
determine that list construction has finished you need to append $3 to
the list represented by $1.


Don't do


        expression: expression ',' ITEM { $1->next = $3; }
                | ITEM
                ;


as that, in your example, will do


        one->next = two
        one->next = three
        one->next = four
        one->next = five


since expression's value is the head of the list. You need


        expression: expression ',' ITEM {
                        node *p;


                        for (p = $1; p->next; p = p->next);
                        p->next = $3;
                }
                | ITEM
                ;


preferably with the aid of an `APPEND' macro.


Ralph Corderoy.
[I prefer $3->next = $1; $$ = $3; and list reversal. It's faster and
less complicated. -John]

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