Benefits of hand-coded bottom-up parsers

I don't really want to fan the flame wars, but I must stress the benefits
of hand-coding an LR parser if your goal is to understand parsing.


My advisor insisted that I hand code an LR-parser for a language with 59
productions, mostly trivial. We fought about this for almost a year: I
felt it was a waste of time, too messy, etc. After a blazing fight I sat
down and did it. I generated the yacc tables first, so that I knew where I
was going. It took about 5 iterations and much gnashing of teeth before I
was able to produce the yacc table myself.


I was then required to draw the state machine on a piece of paper. I
complained. My advisor said: "Take a *big* piece of paper and get
started!" I bought a roll of packing paper and began. During the process
of fitting the 118 states and the over 300 transitions onto a flat piece
of paper, I began to *really* understand what actually is happening during
parsing. I saw how the prefixes are recognized. I "discovered" a number
of theorems that of course have been proved for ages. I now have an
excellent "Gedankenmodell", a thought model of the bottom-up parsing
process, and find it easy to understand theoretical papers about
LR-parsing.


I don't think it is necessary to do such a large language, but even to
hand-construct LR-tables for the expression grammar will give you a
lasting insight into the parsing process. Of course, a large language
gives you a nice big poster to hang on the walls - mine is 600x100 cm !
--
Debora Weber-Wulff dww@inf.fu-berlin.de
Institut fuer Informatik +49 30 89691 124
Nestorstr. 8-9
D-W-1000 Berlin 31
--

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