Re: Writing a compiler compiler

> So here goes my question - how do you start writing a parser generator?
> I am probably considering a LALR parser, but what are the main
> differences between the different types? Specifically, why is an LR
> parser unable to parse Python or C++? [source: Wikipedia]


I think you start writing a parser generator by writing a parser.
Once you have the parsing details down, writing the traditional
yacc interface on top is pretty simple. The hard part is getting
the parsing engine running in the first place.


Even if you need something more powerful than LALR, I'd start
with LR(0) and SLR just to cement your understanding of
whta's going on. I recently implemented a GLR parser.
It was only a reasonable amount of work because I first
made sure I understood LR(0) and then SLR and LR(1) well.


Although few people do use Earley and Tomita parsers in
practice now, I think general approaches, especially GLR,
are gaining ground.


Some references I have found useful:


John Aycock and Nigel Horspool,
Directly-Executable Earley Parsing, CC 2001


John Aycock and Nigel Horspool,
Faster Generalized LR Parsing, CC 1999.


Bryan Ford,
Parsing Expression Grammars: A Recognition-Based Syntactic Foundation,
POPL 2004


Scott McPeak and George C. Necula,
Elkhound: a Fast, Practical GLR Parser Generator,
CC 2004


Scott McPeak,
Elkhound: a Fast, Practical GLR Parser Generator,
UC Berkeley Tech Report UCB/CSD-2-1214, December 2002
(a longer more detailed version of the CC paper)


Russ

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