Re: Trouble understanding LL(k) vs. LALR(k) etc.

Christian Maeder wrote:
> Johnathan wrote:
>>Statements = <Statement> | <Statements> <Statement>
>
> That's left recursion (for "Statements"), so the grammar is not LL and
> not suited for recursive descent. Simple reverse to right recursion:
> .... "<Statement> <Statements>"
>
> (Right recursion is less efficient than left recursion for LR parsers,
> though.)


Technically yes, but, practically, there's almost always no difference.


For example, compare R -> r R | r with L -> L l | l.


For a list of length n, both will do n shifts, and n reductions to parse
the list. The only difference is that right recursion will require a
stack that is of length n, while left recursion requires a stack of
length 2. Unless your input has very long lists, you won't notice any
difference.


Of course, the *best* way to parse either of the above is with a regular
expression (i.e. a finite automaton), and not a stack-based machine (LL
or LR) at all. Any decent recursive-descent parser generator allows
regular expressions in its grammar specification, eliminating the need
for much recursion - and leading to a nicer shape abstract syntax tree.


There has been some work integrating regular expressions with LR
parsers, (Kannapinn most recently, if I remember correctly), but RE's
don't tend to fit into LR as naturally as recursive descent.


Cheers,
Carl.

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