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

Carl Cerecke <cdc@maxnet.co.nz>
19 Mar 2004 23:49:54 -0500

          From comp.compilers

Related articles
Trouble understanding LL(k) vs. LALR(k) etc. zork_666@nospammail.net (Johnathan) (2004-03-11)
Re: Trouble understanding LL(k) vs. LALR(k) etc. maeder@tzi.de (Christian Maeder) (2004-03-15)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-03-15)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cdc@maxnet.co.nz (Carl Cerecke) (2004-03-19)
Re: Trouble understanding LL(k) vs. LALR(k) etc. derkgwen@HotPOP.com (Derk Gwen) (2004-03-26)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-03-26)
Re: Trouble understanding LL(k) vs. LALR(k) etc. f40mczf02@sneakemail.com (Karsten Nyblad) (2004-04-03)
Re: Trouble understanding LL(k) vs. LALR(k) etc. clint@0lsen.net (Clint Olsen) (2004-04-14)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-04-15)
Re: Trouble understanding LL(k) vs. LALR(k) etc. clint@0lsen.net (Clint Olsen) (2004-04-15)
[4 later articles]
| List of all articles for this month |

From: Carl Cerecke <cdc@maxnet.co.nz>
Newsgroups: comp.compilers
Date: 19 Mar 2004 23:49:54 -0500
Organization: TelstraClear
References: 04-03-042 04-03-057
Keywords: parse
Posted-Date: 19 Mar 2004 23:49:54 EST

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.


Post a followup to this message

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