# Re: Left Recursion in Yacc

## chenxq@my-deja.com31 Dec 2000 02:59:09 -0500

From comp.compilers

Related articles
Left Recursion in Yacc student1330@my-deja.com (Mike) (2000-12-24)
Re: Left Recursion in Yacc chenxq@my-deja.com (2000-12-31)
Re: Left Recursion in Yacc loewis@informatik.hu-berlin.de (Martin von Loewis) (2000-12-31)
Re: Left Recursion in Yacc ralph@inputplus.demon.co.uk (2001-01-09)
| List of all articles for this month |

 From: chenxq@my-deja.com Newsgroups: comp.compilers Date: 31 Dec 2000 02:59:09 -0500 Organization: Deja.com References: 00-12-110 Keywords: yacc Posted-Date: 31 Dec 2000 02:59:09 EST

Mike <student1330@my-deja.com> wrote:
> 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.
> 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.
right-recursive:
expression: ITEM ',' expression { \$1->next = \$3; \$\$ = \$1; }
left-recursive:
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