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

Carl Cerecke wrote a very good response to the left/right recursion
question (pointing out the RE's are the better solution than either
left or right recursion), but made this tiny statement at the end that
I think needs some slight correcting:
> There has been some work integrating regular expressions with LR
> parsers, (Kannapinn most recently, if I remember correctly), but RE's
> don't tend to fit into LR as naturally as recursive descent.


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


Kannapinn does bring up some interesting points and his model is worth
understanding because it handles some subtle ambiguity issues.
However, even prior to his work there were both practical and
theoretical models that integrated RE's and LR parsing.


Now, it is true that writing a parser generator that integrates RE's
and LR parsing is not as easy and intuitive as the LL equivalent.
However, that is true for most aspects of parser generator
implementation. It is almost always harder to do an LR implementation
of some parsing concept than an LL one. However, I've never seen a
feature that had an LL implementation that did not also have an LR
implementation shortly thereafter.


What is unfortunately true, is that RE's are not integrated with LR
parsing in Bison or normal Yacc. I think that reinforces the
impression that "it hasn't been done yet".


Just me going off on the tangent,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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