Re: generated code

Detlef Meyer-Eltz <Meyer-Eltz@t-online.de> writes:


> This code and especially the integration of semantic actions in this
> code is, what I am interested in. That means code for parsers, which
> are generated from parser descriptions like yacc. I am interested in
> the question, how to do something with a parser.
>
> MY THESIS
> ---------
> is, that recursive descent LL compiler compilers for most purposes
> generate the clearest and most flexible code. Parse trees can be
> created, but the processed text can be treated directly too.
...
> There is a discussion appearing again and again in this forum, whether
> LL or LR parsers should be preferred. I think, the advantages and
> disadvantages are reciprocal. But the one decisive argument in favor
> of the LL parsers, generated by recursive descent compiler compilers,
> is the simplicity of the code generated by them.


Your thesis is not without merit. In fact, few will argue that table
driven parsers (either LL or LR ones) are easier to read than
recursive descent parsers. For most people, your thesis holds true.
They want to be able to read the parser generator output as a series
of functions. In fact, the "OO-parsing" that is discussed in another
thread is just a poor-person's hand-implementation of recursive
descent, which in some sense proves your thesis.


There are advantages to table driven parsing technologies, the main
one being that one can do "things" is the interpreter that aren't
obvious. For example, GLR parsing runs multiple copies of an LR
parser in parallel when it encouters an ambiguity. Similarly, we run
Yacc++ engines in a "call-back" mode designed for being used in an
event driven loop. Many of those things are hard (if not impossible)
to do in a recursive descent implementation, because in recursive
descent, one is limited to the semantics of procedures in the target
programming language. If your target programming language doesn't
support parallel procedure calls (or event driven procedures) and most
don't, you can't use a recursive descent implementation to get such
features. (Note, that is one of the reasons I haven't added a
(modified) recursive descent output format to Yacc++. I'm too
addicted to the features that the table driven engine give me.)


Now, if one doesn't need those "features" then the advantages of a
table driven approach tend to disappear. Thus, since most users don't
need such features, most users see recursive descent as a panacea due
to the readable generated output (and in some ways it is).


======================================================================


However, I would caution about the direct processing of the text as
part of the parsing process. That seems seductively simple. However,
it is a false economy and leads one to create a design that does not
generalize properly. The canonical question that illustrates that
problem is the FAQ of "How do I now handle loops (or conditional
statements) in my input?" Handling loops and conditions are easy if
you build an AST, and often not so easy if your code is ad hoc. The
simplifying assumptions one can make when processing the code linearly
fall apart when you have to handle the more complex cases. Thus, it
is better to avoid being able to make such simplifying assumptions and
then have to rework all the code that depends upon them.


In fact, too me the big drawback of recursive descent is that it
allows users to stay in the cocoon of the single threaded top-down
world. In recursive descent, the parser is in control. One starts at
the root and parses according to the grammar, never losing context of
what one has done before. As mentioned, that allows a lot of
simplifying assumptions, and programs written that way tend to be
brittle, because the assumptions are implicit and never challenged
until the program fails. (I have a similar problem with the singleton
design pattern, as it also tends to aid in creating brittle designs.)


Well enough ranting,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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