Re: Top-Down Parser Construction Conjectures

parrt@ecn.purdue.edu (Terence J Parr)
Tue, 19 Jan 1993 21:55:46 GMT

          From comp.compilers

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

Newsgroups: comp.compilers
From: parrt@ecn.purdue.edu (Terence J Parr)
Organization: Compilers Central
Date: Tue, 19 Jan 1993 21:55:46 GMT
References: 93-01-128
Keywords: parse, LL(1), LR(1), tools, bibliography

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


Post a followup to this message

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