Re: Looking for a LL(1) generator

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'
> ;
>
> thanks!




Francois,


  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
  Clemson University.


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




--
rivers@dignus.com Work: (919) 676-0847
Get your mainframe programming tools at http://www.dignus.com

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