Re: Left Recursion in Yacc
31 Dec 2000 02:59:09 -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 |

Newsgroups: comp.compilers
Date: 31 Dec 2000 02:59:09 -0500
References: 00-12-110
Keywords: yacc
Posted-Date: 31 Dec 2000 02:59:09 EST

    Mike <> wrote:
> Suppose I have a left recursive rule
> expression:expression ',' 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. More specifically, how exactly would the recursion be
> handled. Would I get the list in reverse order? If yes, why is that.

Both left-recursive and right-recursive can produce the list in its
natural order. But right-recursive costs much more stack because yacc
matches patterns from left to right. So it's better to use left-
recursive than right-recursive if you have a long list.
expression: ITEM ',' expression { $1->next = $3; $$ = $1; }
expression: expression ',' ITEM { $3->next = $1->next; $1->next = $3;
$$ = $3; }
left-recursive returns the tail of the list, so you should use ->next
to get the head of the list.

Post a followup to this message

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