26 Mar 2004 21:25:32 -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) |

Re: Trouble understanding LL(k) vs. LALR(k) etc. cfc@shell01.TheWorld.com (Chris F Clark) (2004-04-21) |

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.