Re: Looking for a LL(1) generator

Thomas David Rivers <>
23 Jul 2003 10:39:24 -0400

          From comp.compilers

Related articles
Looking for a LL(1) generator (Francois Gagnon) (2003-07-21)
Re: Looking for a LL(1) generator (Thomas David Rivers) (2003-07-23)
Re: Looking for a LL(1) generator (Parag Patel) (2003-07-25)
Re: Looking for a LL(1) generator (2003-07-26)
| List of all articles for this month |

From: Thomas David Rivers <>
Newsgroups: comp.compilers
Date: 23 Jul 2003 10:39:24 -0400
Organization: Dignus, LLC
References: 03-07-150
Keywords: LL(1)
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'
> ;
> thanks!


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

-- Work: (919) 676-0847
Get your mainframe programming tools at

Post a followup to this message

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