Re: Compiler Books? Parsers?

I don't really wish to negate what Jeff, Chris, and Quinn have said,
but I do think that it is sometimes advantageous to code a parser by
hand, so I just want to provide a quick 'other side of the coin' here.


Quinn Tyler Jackson wrote:


> It has been my experience (as a parsing tool architect) that the tool route
> is, overall, the better of the two routes for several reasons. (For any
> value of "better"....)
>
> 1. Optimizations made to the parsing engine are reflected across all (or
> most, anyway) generated parsers that use that engine. Time and time again
> when I have improved the Meta-S engine, other parsers have benefited by
> those same improvements, without any consideration for those other parsers
> having been taken during optimization.


One /potential/ problem with parser generators is that 'pessimisms'
(bugs!) also get propagated in this way. You /might/ optimise all
your generated parsers by introducing an optimisation into the parser
generator, but you /could/ also break all of them, by introducing a
bug into the parser generator. Obviously, the (good) parser generator
writers know this, and take pains not to do it.


> 2. Generated parsers are generated from specifications that can be checked
> in some automated way for "correctness."


A possible problem is that this could instill a false sense of
confidence (there are many errors in a specification that a generator
cannot detect). Obviously the solution is the old "Don't do that!"
Don't be so silly as to think that if the tool accepted it, it must be
right.


But it's a gotcha you have to know about to avoid. Some people do use
a parser generator foolishly thinking that it will enable them to
solve a complex problem quickly and easily (especially if they are the
kind of people who believe advertising literature :-)


> 3. Parsers generated from a specification can be modified and maintained in
> ways that hand-written ones typically aren't. (Chris said enough on this
> already.)


Absolutely true. Sometimes, however, the reverse is true. If you are
clever about hand writing a parser, you can build factorisations into
it to make certain anticipated future tweaks and modifications easy
(and safe). The specification language of a parser generator generally
prevents such factorisations.


I am currently writing an Ada compiler. The Ada syntax is very stable
(even at the introduction of a new revision, which happens about once
every ten years). Thus the need for changes to the parser due to
changes in the syntax will be minimal. I anticipate changes due to
changes in the output data (parsed tree) will also be minimal. Where I
do anticipate most change and improvement will be in the
sophistication and breadth of the error diagnostics. This desire to be
able to (eventually) achieve very sophisticated diagnostics is one of
the main things that puts me off using a parser generator tool.


> 4. Parsers generated from a specification can be written by domain
> specialists. Hand-written parsers can be written by domain specialists who
> also happen to be programmers in the host language.


Also perfectly true, but if it so happens that the parsed language and
parser (host) language are the same, the problem (almost) goes away.


I am writing my Ada compiler in Ada!


> 5. Parser generators can (more and more these days) produce parsers that can
> be hosted by a multitude of language environments. One specification can be
> used by a Delphi, C++, VB, C#, or Java host if the engine happens to support
> interfaces to each of these. The grammar writer need not know how to program
> in ANY of these environments for this to come about.


Fine, but it's not very often a particular parser needs to be hosted by
more than one language. And implementing a generator that targets multiple
host languages might open up more cracks for bugs to creep in (obviously
this is another product quality issue).


> 6. Parser generators encourage standardization and community. There are
> well-known ways to write grammar subsections that parse function parameter
> lists, white space, and dangling-else's. Most of these well known ways are
> expressed in the syntax of parser generator specifications. Delphi, C++, VB,
> C#, Java, Perl programmers can benefit from the knowledge of others who have
> already solved the same parsing issues at a level of abstraction above the
> implementation language. (Without parser generators, many of the questions
> found in this newsgroup could not be concisely expressed, and answers
> provided by experts would adhere to no standard.)


As Devil's advocate, one might also argue that really new and innovative
approaches to parsing (and its associated activities, such as syntax error
diagnostics) are likely to be somewhat stifled by this standardisation.


But I'm fairly sure that, for most people who need a parser, "it works" is
a much higher priority than "it's totally rad, man" (or whatever ;-)


Also, I would assert that forums such as comp.compilers tend to do much to
foster and aid such innovation.


--
Nick Roberts

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