Is right recursive C grammar necessary?

[Steven Ryan]

In article <433 at dmk3b1.UUCP> dmk at dmk3b1.UUCP (David Keaton) writes:
>     No, and in fact if you're using yacc you want left recursion
>instead, wherever reasonable.  This is because the yacc-generated parser
>has to keep all the states around until the appropriate rules get
>reduced, and with right recursion this can make the stack get huge.

This depends on how much memory you have. On VM it shouldn't matter,
unless YACC is incredibly stupid and Fortranish by using a fixed size
stack. You shouldn't have to stand a grammar on its head for anything
advertised as an LR(1) parse generator.

>     If you were using a recursive descent parser or an LL(1) parser,
>then you would use right recursion to avoid ambiguity.

Not ambiguity, but infinite recursion if you're not careful. An LL(k)
parser needs to know the first k terminals of each production:

      A -> A b.

You need the first k terminals of A b which needs the first k terminals of A
which needs the first k terminals of A b which needs the first k terminals ...

This is not an ambiguity, but it does require cleverness. Or right recursion.