Is right recursive C grammar necessary?

[Larry Jones]

In article <428 at erc3ba.UUCP>, rsc at erc3ba.UUCP (Rich Chomiczewski) writes:
> 
> The ANSI C yacc parser written by Jeff Lee contains right recursive rules.
> For example:
> 
> 	declaration_specifiers
> 		: storage_class_specifier
> 	 	| storage_class_specifier declaration_specifiers
> 			etc.
> 		;
> 
> Is this right recursive grammar required by the ANSI C committee?
> Can the above rule be written left recursive and still conform
> to the ANSI C standard?

This is a common confusion.

Strictly speaking,  any grammar can be written with either left or
right recursion -- it doesn't make any difference.  All a grammar does is
indicate which sequences of tokens are valid.  The grammar does not say
anything about how the sequence is interpreted, no precedence, no
associativity, no nothing.  How the grammar is written does affect whether
it satisfies various properties, however, and that brings us to the next
part of the discussion.

When writing a parser, it is frequently necessary to have a grammar that
satisfies a particular property such as LL, SLR, or LALR.  Also, it is
usually handy to arrange things so that the resulting parse tree DOES
accurately specify precedence and associativity.  Common computer language
grammars can almost always be written in a way that does this.  However,
how you write the grammar to arrange this depends on the type of parser
you are writing.  For example, an LALR parser such as those generated by
yacc generates a rightmost derivation (the rightmost nonterminal is replaced
at each step) although it does it in reverse (from the bottom up) whereas
an LL parser such as one you might write by hand generates a leftmost
derivation (from the top down).

The practical result of this difference is that if you are writing an LL
parser, you want your grammar to be right recursive since left recursive
grammers do not possess the LL property.  If you are using yacc to generate
a grammar, you want your grammar to be left recursive since that minimizes
the parse stack depth.  So it's just one more example of what you want
depending on what you're doing.

----
Larry Jones                         UUCP: ...!sdrc!scjones
SDRC                                AT&T: (513) 576-2070
2000 Eastman Dr.                    BIX:  ltl
Milford, OH  45150
"When all else fails, read the directions."