Top-Down Parser Construction Conjectures

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

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