19 Mar 2004 23:49:54 -0500

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] |

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.