Re: Left Recursion in Yacc (Ralph Corderoy)
9 Jan 2001 23:27:06 -0500

          From comp.compilers

Related articles
Left Recursion in Yacc (Mike) (2000-12-24)
Re: Left Recursion in Yacc (2000-12-31)
Re: Left Recursion in Yacc (Martin von Loewis) (2000-12-31)
Re: Left Recursion in Yacc (2001-01-09)
| List of all articles for this month |

From: (Ralph Corderoy)
Newsgroups: comp.compilers
Date: 9 Jan 2001 23:27:06 -0500
Organization: InputPlus Ltd.
References: 00-12-110
Keywords: yacc
Posted-Date: 09 Jan 2001 23:27:06 EST

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]

Post a followup to this message

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