Re: Recursive descent and left recursion

mfinney@lynchburg.net wrote:
> I have noticed the occassional post here, as well as assertions in
> various texts, that left recursion is not usable with recursive
> descent (and LR parsers in general).
                                  ^^


I thought certainly someone else would catch this mis-impression, but
since no one has mentioned it. LR parsers allow left-recursion as
well as right recursion and any other recursion. It is LL parsers
which don't like left recursion. In fact, that is the main reason for
using LR (or LALR) parsing over LL. You can write your expression
grammars "naturally" with out inventing extra non-terminals to handle
precedence levels. That is:


        expression : expression "+" expression
| expression "*" expression
. . .


By the way, it is little cited fact that those extra non-terminals to
handle precedence cost something. In a recursive descent parser, they
are extra subroutine calls. In an LR parser they are extra reductions
and in a table driven parser extra columns in each row of the table.


Chris Clark
--

Return to the comp.compilers page.
Search the comp.compilers archives again.