Is right recursive C grammar necessary?

[Mark Hall]

>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?
>___
>Rich (erc3ba!rsc)

When I first read this, I read ``right-recursive'' as ``left-recursive''
and immediately went into my canned speech about how all left-recursion
can be eliminated in any grammar.  Hopefully, my Cancel msg caught the
missive before anyone read it.

The answer is still `NO'.  The GRAMMAR isn't required by 
anyone, but the LANGUAGE it recognizes IS important.  There is
certainly a left-recursive grammar that recognizes the above 
C-language construct.  This time it is easy to eliminate the 
recursion:

	ds : scs 
	    | scs ds

recognizes the same language as

	ds : ds scs
	    | scs

and this can be proven using induction on the number of scs
productions seen (just act like scs is a terminal and builds
syntax trees for the string ``scs scs scs scs'' for both
grammars).

The production was probably written this way in the first 
place to imply some sort of associative precedence.  This has to
do with the PARSE TREE (implicit or explicit) built during the parse.
Note that, for many constructs, a left recursive grammar 
is useful, because for expressions in Pascal like:
	a - b - c
they naturally build the `correct' parse tree, ie, the one that 
interprets the above as:
	(a - b) - c
a right-recursive production implies a parse tree which makes
the above have the `meaning':
	a - (b - c)
If storage_class_specifiers are right-associative, you probably
want to keep the right-recursive grammar, even though a left-recursive
grammar could recognize the same language (let me point out that
there are ways to build the correct parse tree with a left recursive 
grammar, but you probably just want to use the YACC parse stack 
as your implicit tree, so don't bother).

Note that for LR grammars, it is important to use left-recursion 
whenever it's convenient because that uses less stack
space at parse time.  To be precise, a string of s_c_s productions
of length N requires O(N) stack space to recognize using a right 
recursive grammar, but O(1) space for a left recursive grammar.