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

Derk Gwen <derkgwen@HotPOP.com>
26 Mar 2004 21:25:32 -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)
Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-04-21)
| List of all articles for this month |

From: Derk Gwen <derkgwen@HotPOP.com>
Newsgroups: comp.compilers
Date: 26 Mar 2004 21:25:32 -0500
Organization: Quick STOP Groceries
References: 04-03-072
Keywords: parse
Posted-Date: 26 Mar 2004 21:25:32 EST

# 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.


The issue isn't regular expressions, but whether the implementation is a
DFA or DPDA. It's usually not that hard to convert left recursion LR
state machine from DPDA to a DFA. (In a reduction state, back track
the state graph to find out what state will be the next after the
reduction and then add a link to go to that directly instead of popping
a goto table off a stack.)


The grammar should be presented in the most natural form, since most
transformations like left recursion removal or production factorring
can be automated. Unfortunately this is rarely done.


--
Derk Gwen http://derkgwen.250free.com/html/index.html


Post a followup to this message

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