Top-Down Parser Construction Conjectures

bart@cs.uoregon.edu (Barton Christopher Massey)
Mon, 18 Jan 1993 04:19:55 GMT

          From comp.compilers

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]
| List of all articles for this month |

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.