Re: Top-Down Parser Construction Conjectures

Sakari Jalovaara writes:
> Transforming a yacc parser into RD is easy-ish since yacc directly gives a
> list of lookahead tokens for any given parse state (e.g. you can easily
> see which tokens can start a declarator.)


You can use PCCTS which generates a fast LL(k) recursive-descent parser in
C; i.e. it computes the lookahead sets automagically (mail to
pccts@ecn.purdue.edu for info).


As an aside, a cute way to determine if your favorite YACC grammar is
LL(1) is to simply place an action on the left edge of every production
and see if it's still LALR(1). If so, your grammar is LL(1) as well;
note, that this will rarely be the case as most LALR grammars use left
recursion, but it's cute. We have a nifty proof of this out for review
(with some other goodies), but [Bro80] made a similar observation.


[Bro80]
Brosgol, Benjamin Michael, "Deterministic Translation Grammars,"
Garland Publishing, New York, 1980, pp 5-40, 5-41, 5-42, 5-53.


Terence
Purdue Electrical Engineering
parrt@ecn.purdue.edu
--

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