Mon, 18 Jan 1993 09:53:17 GMT

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

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.