# Re: Left Recursion in Yacc

## Martin von Loewis <loewis@informatik.hu-berlin.de>31 Dec 2000 03:01:42 -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: Martin von Loewis Newsgroups: comp.compilers Date: 31 Dec 2000 03:01:42 -0500 Organization: Humboldt University Berlin, Department of Computer Science References: 00-12-110 Keywords: yacc, parse Posted-Date: 31 Dec 2000 03:01:42 EST

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

Post a followup to this message