Re: top-down vs bottom-up parsers

Dennis Taylor asked how to go about learning how LR parsing worked, to
which Tim Hollebeek replied with the sensible solution:


> What I would suggest is writing (or finding) a parser for such a
> construct, then turn the debugging on (e.g. YYDEBUG in bison) and look
> at the output. Feed it the smallest construct whose parsing confusing
> you. Read through its output as it parses the expression, possibly
> also refering to the table of states and rules (generated by bison
> -verbose).


The only thing I would add is you might wish to pick a parser
generator designed for readability to do the project with. Several
groups have developed parser generators specifically with teaching how
they work in mind. One that I have a link to is Dr Susan Rodger at
Duke University:


http://www.cs.duke.edu/~rodger/tools/tools.html


There was another one done at University of Missouri which was
documented in an ACM or IEEE journal if I remember correctly, but the
details have long left my memory.


Another likely source is Dr Tim Budd's group in Oregon as they do a
lot of visual teaching aids.


Commercially, there is Visual Parse++.


By the way, I do not recommend Yacc++ for this task. Although it has
a readable table mode, which when we implemented it was very easy to
follow. It has since been surpassed in this area and we haven't put
any additional improvements into that part of the product, as it is
good enough for non-teaching purposes. Of course, someday, we'll get
back to that part. . . .


----------------------------------------------------------------------


The other thing I would recommend is building some tables by hand for
cases that look interesting. If you do this with the idea that the
parser generator is trying to build a machine which searches all the
paths in parallel, you will quickly see how the paths are built up.
Equally quickly, you will learn how the number of states and amount of
work you do gets large very fast, and thus why Steve Johnson automated
the process with yacc. At the same time try different grammars for
the same constructs, and see whether they generate the same tables or
different ones and figure out why.


Also helpful, is trying to find different pictures to describe the
tables you are building, i.e. don't just make a matrix and fill it in,
but draw the state machine--see if you can make it look like a
"railroad" diagram (and figure out why you succeeded or failed to do
so).


Similarly, you should try to understand when the generated parser
"knows" what construct it is parsing, and why they call LR parsing
bottom up. How does context effect how things are parsed? Can the
context a rule is used in effect the portion of the tables used to
represent a rule? If so, how and why? If not, why not?


-Chris Clark
************************************************************************
Compiler Resources, Inc. email: compres@world.std.com
3 Proctor St. http://world.std.com/~compres
Hopkinton, MA 01748 phone: (508) 435-5016
USA 24hr fax: (508) 435-4847
--

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