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

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

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