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

Clint Olsen <clint@0lsen.net>
14 Apr 2004 00:24:34 -0400

          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)
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)
| List of all articles for this month |

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.