Re: Top-Down Parser Construction Conjectures

W.Purvis@daresbury.ac.uk (Bill Purvis, ext 3357)
Mon, 18 Jan 1993 09:53:17 GMT

          From comp.compilers

Related articles
Top-Down Parser Construction Conjectures bart@cs.uoregon.edu (1993-01-18)
Re: Top-Down Parser Construction Conjectures W.Purvis@daresbury.ac.uk (1993-01-18)
Re: Top-Down Parser Construction Conjectures sja@vinkku.hut.fi (1993-01-18)
Re: Top-Down Parser Construction Conjectures parrt@ecn.purdue.edu (1993-01-19)
Re: Top-Down Parser Construction Conjectures pardo@cs.washington.edu (1993-01-20)
Recursive descent parsing is better than LL(1) jan@klikspaan.si.hhs.nl (1993-01-22)
| List of all articles for this month |

Newsgroups: comp.compilers
From: W.Purvis@daresbury.ac.uk (Bill Purvis, ext 3357)
Organization: Daresbury Laboratory, UK
Date: Mon, 18 Jan 1993 09:53:17 GMT
References: 93-01-122
Keywords: parse, LL(1), theory

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


Post a followup to this message

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