Benefits of hand-coded bottom-up parsers

dww@inf.fu-berlin.de
Tue, 26 Jan 1993 11:31:57 GMT

          From comp.compilers

Related articles
Benefits of hand-coded bottom-up parsers dww@inf.fu-berlin.de (1993-01-26)
Re: Benefits of hand-coded bottom-up parsers rooi@duteca3.et.tudelft.nl (1993-01-28)
| List of all articles for this month |

Newsgroups: comp.compilers
From: dww@inf.fu-berlin.de
Organization: Free University of Berlin
Date: Tue, 26 Jan 1993 11:31:57 GMT
Keywords: parse, courses, LR(1)

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


Post a followup to this message

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