Re: Advice on Writing a Parser Generator

Thant Tessman wrote:


> Stefanie Scherzinger wrote:
>
>
>> I plan to write a parser generator, very similar to YACC, for Java.
>>
>> I was hoping to find some literature and advice on how to best
>> approach this.
>
> People will usually recommend the Dragon book, but that was always a
> tough read for me.


The Dragon book also makes the theory and practice of LALR(1) parser
generators seem much harder than it is, because it was written before
some valuable later research that produced better and more
understandable algorithms. The simplest and best approach to LALR(1)
parser generation, in my view, is that of Bermudez and Logothetis,
see:


@article{bermudez89,
                author="Manuel E. Bermudez and George Logothetis",
                title="Simple Computation of LALR(1) Lookahead Sets",
                journal="Information Processing Letters",
                volume="31",
                publisher=NH,
                year="1989",
                pages="233--238"}


- they cleverly reuse the SLR(1) algorithm on a variant grammar to carry out
the LALR(1) look-ahead calculations.


> However, I was able to follow "Modern Compiler
> Implementation in ML" well enough to build an SLR parser generator (in
> C++ oddly enough). I haven't read it, but there's a version for Java:
>
> http://www.cs.princeton.edu/~appel/modern/java/
>
> -thant


Discovering the Bermudez-Logothetis paper last year made me realise
that the LALR(1) approach is worth the extra effort. The parser
generator called SLRP that comes as part of the OpenProofPower
development tools is an example implementation (see
http://www.lemma-one.com/ProofPower). It is written in Standard ML and
generates Standard ML code.


The output of SLRP is essentially just the parsing tables, so it would
be easy to adapt to other languages. I don't think that the
performance considerations of the 1970s and 1980s that caused parser
generators like yacc to produce a mixture of code and data rather than
just tables to feed into a a generic parsing function apply these days
(or do they?).


Regards,


Rob.
[Yacc produces parse tables, too. What looks like a mix of code and data
is the canned parser code + parse tables + a big switch in which it embeds
the action code to run on reductions. This is a good thing; otherwise
matching up the rule numbers with the action code is an error-prone
pain in the neck.


You can pull out the parse tables if you want, but there's usually no point.
-John]

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