Mon, 18 Jan 1993 04:19:55 GMT

Related articles |
---|

Re: Compiler Construction in Ada crigler@osceola.cs.ucf.edu (1993-01-08) |

Re: Compiler Construction in Ada andrewd@cs.adelaide.edu.au (Andrew Dunstan) (1993-01-17) |

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

Re: Recursive descent parsing is better than LL(1) tchannon@black.demon.co.uk (1993-01-23) |

[5 later articles] |

Newsgroups: | comp.compilers |

From: | bart@cs.uoregon.edu (Barton Christopher Massey) |

Organization: | University of Oregon Computer and Information Sciences Dept. |

Date: | Mon, 18 Jan 1993 04:19:55 GMT |

Keywords: | parse, theory, question, LL(1) |

References: | 93-01-048 93-01-121 |

Andrew Dunstan <andrewd@cs.adelaide.edu.au> writes:

...

*> For Compiler Construction courses, it seems to me that there is a benefit*

*> in teaching students how to make a parser from scratch, in just the same*

*> way that we teach kids to do arithmetic manually before letting them loose*

*> on calculators - so that they get an understanding of how it works. Given*

*> the above, this seems to indicate using top-down methods - typically*

*> recursive descent. Interestingly, the GNAT compiler will be using*

*> hand-coded recursive descent, and very impressive performance stats have*

*> been reported in this group. So this technique is of more than simple*

*> academic interest.*

IMHO, for large complex languages, it is error prone and tedious to

hand-construct parsers, or indeed to hand-transform grammars. While LL(1)

parsers are indeed academically interesting for the reasons described, I

will personally choose to use YACC or something similar for parsing until

I can implement an LL(1) parser generator which will take a reasonably

ad-hoc grammar and either transform it to an LL(1) grammar or report

failure to do so, "most of the time".

In order to construct such a tool, I would like to prove or disprove the

following conjectures:

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.

After some thought, it still seems most likely to me that LL1T is true,

but I'm skeptical about LL1D . I posted these conjectures to

comp.compilers previously, but didn't get too far with them then. In a

way, I'm surprised if such apparently important questions haven't been

carefully studied, but I haven't found any very useful references yet.

My interest is inspired by the fact that most YACC grammars for languages

I have designed or implemented seem to be LL(1) transformable (except for

obvious exceptions such as if-then-else) by hand, using left-factorization

and left-recursion-removal.

Comments, anyone?

Bart Massey

bart@cs.uoregon.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.