|Looking for a LL(1) generator email@example.com (Francois Gagnon) (2003-07-21)|
|Re: Looking for a LL(1) generator firstname.lastname@example.org (Thomas David Rivers) (2003-07-23)|
|Re: Looking for a LL(1) generator email@example.com (Parag Patel) (2003-07-25)|
|Re: Looking for a LL(1) generator firstname.lastname@example.org (2003-07-26)|
|From:||Thomas David Rivers <email@example.com>|
|Date:||23 Jul 2003 10:39:24 -0400|
|Posted-Date:||23 Jul 2003 10:39:24 EDT|
Francois Gagnon wrote:
> I am looking for a tool which would take an "almost LL(1)" grammar and
> would generate an LL(1) grammar production for it. This can certainly be
> impossible (for case of left recursion for instance or if the grammar is
> just not in the LL(1) class), but I wondered if there is a tool that can
> at least handle some "sub set" of such a grammar (I think that the
> Dragon book had an algorithm for this... It'd have to dig this up...)
> A simple example:
> x : 'a' 'x'
> | 'a' 'y'
> Such tool could generate something like:
> x : 'a' x1
> x1 : 'x'
> | 'y'
You can generalize your approach to include regular
expressions in the "first set." Something like:
x: 'a'* 'x1
And, when you do this; you wind up being able
to accept languages that are larger than LL1
(albeit still "smaller" than LR1.) I had
named such languages Top Down Regular.
My master thesis, now many years ago, discusses
this approach... and details the algorithm
to accomplish it. As far as I knew then,
it was original work... I don't know if this
'corner' has been visited by other people...
Using the algorithms described there, you could produce
such a tool. It's available (print only) from
- Dave Rivers -
(It's strange that I've been able to mention
that twice this year... without even a peep
about it for 15 years... I wonder if this
qualifies as a 'trend?')
firstname.lastname@example.org Work: (919) 676-0847
Get your mainframe programming tools at http://www.dignus.com
Return to the
Search the comp.compilers archives again.