Re: Top-Down Parser Construction Conjectures

Bart Massey posed two conjectures about LL(1) grammars:
> LL(1) Transformability: There exists an algorithm
> which, given any grammar G which is unambiguous and
> describes an LL(1) language L(G), produces an LL(1)
> grammar G' for the language L(G).
>
> LL(1) Decidability: There exists an algorithm which,
> given any grammar G which is unambiguous and describes
> a language L(G), decides whether L(G) is an LL(1)
> language.


In Computer Journal, Vol 11, number 1, May 1968, J. Foster describes SID,
a syntax improving program which accepts a fairly arbitrary BNF
description and applies the neccesary transformations to produce an LL(1)
grammar (assuming that the language is LL(1). I think that that fully
covers the first conjecture.


The program is pretty comprehensive and while it might not cover all
cases, I suspect that in practical terms it probably covers the second
conjecture.


I recall porting the program to some ancient machines using obscure
dialects of Algol 60 way back in the distant past. I'm sure it could
easily be done in C or whatever. The original program required a list of
terminal symbols, a list of action names, a list of BNF rules and a
starting symbol. This could then be `compiled' into either a chunk of code
into which you edited the actual actions or into a table which could be
assembled and then interpreted by a parser program.


I guess that the output could be brought up-to-date fairly easily - the
hard bit was the transformations and they are equally valid nowadays. If
anyone is interested, I may have some source code in the depths of my
archives.


Bill Purvis


Daresbury Lab, w.purvis@daresbury.ac.uk
Warrington, +44 925 603357
Cheshire, UK
--

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