14 Apr 2004 00:24:34 -0400

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

DFA's and LR machine (was Re: Trouble understanding...) cdc@maxnet.co.nz (Carl Cerecke) (2004-04-21) |

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

Re: DFA's and LR machine (was Re: Trouble understanding...) cdc@maxnet.co.nz (Carl Cerecke) (2004-05-08) |

Re: DFA's and LR machine (was Re: Trouble understanding...) cfc@shell01.TheWorld.com (Chris F Clark) (2004-05-09) |

From: | Clint Olsen <clint@0lsen.net> |

Newsgroups: | comp.compilers |

Date: | 14 Apr 2004 00:24:34 -0400 |

Organization: | Comcast Online |

References: | 04-03-042 04-03-057 04-03-072 04-03-091 |

Keywords: | parse |

Posted-Date: | 14 Apr 2004 00:24:34 EDT |

On 2004-03-27, Chris F Clark <cfc@shell01.TheWorld.com> wrote:

*>*

*> RE's integrate quite nicely and easily (at least from a parser*

*> generator user's point of view) with LR parsing. I put forth Yacc++*

*> which has supported RE extended LR parsing since 1990 as at least one*

*> proof point--and it is hardly alone; if you look back at that time*

*> frame you'll find at least 2 other successful implementations of RE+LR*

*> parsers (If I recall correctly, Karsten Nyblad wrote one of them).*

When you mean 'integrate', do you mean deciding if the language at a

certain non-terminal is regular and therefore can be handled with a

DFA, or are you talking about EBNF notation? I know that Yacc++

supports both, but my guess is that you handle the two scenarios much

differently. For example, you support a combined lexer/parser

specification, so you handle all lexical constructs using a DFA, but

EBNF notation would have to be dealt with in your generated DPDA.

In yacc you use left recursion in 'one-or-more items' contexts to keep

the stack size the lowest, but integrating the actions for both cases

becomes problematic - on the first item, initialize a list; append to

the list every time after. The RE notation is inherently right

recursive, which maps nicely to LL but not LR. Your documentation

seems to imply that the necessary states to handle the two cases in a

traditional yacc implementation are created automagically, but you

don't specify what you do with the action code in those cases.

Thanks++

-Clint

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.