Re: LL(1) vs LALR(1) parsers

"steve (s.s.) simmons" <simmons@bnr.ca> writes:
> Intellectual bigotry!!!!!
>
> That is, the automated parsers use a great deal of automata theory
> which helps build on the computer science foundation. Recursive descent
> parsers are a small matter of programming (SMOP). I do notice among
> peers in industry that people are no longer snubbing the idea of writing
> a recursive parser when it is appropiate.


I've noticed that, too, and I really wonder why. At the same time that
we're trying desperately to develop tools that do the programming for you
in other areas of software development, and we already have tools (e.g.,
yacc) that can program a parser for you, why are we regressing?


I don't think it is intellectual bigotry (to use automated parsers vs.
hand-crafted ones), I think it's just common sense. We have automated
means of generating parsers, why not use them?


If I were in charge of a compiler project (and I have been), I'd much
rather devote engineering resources to making the generated code better or
the compiler faster or any of a number of other improvements than in coding
a parser.


For certain compilers, there may be good reasons not to use an automated
parser, but in general I'd recommend using a parser generator. Why
reinvent the wheel?


Mr. Simmons says recursive descent parsers are a "small matter of
programming". How small? If it takes more than a couple of hours to
write, it's too much, because it will also take up time later on for others
to learn and fix. All projects have a fixed amount of programmer
resources, so any time spent on a parser is that much less spent elsewhere.


In my opinion, parser generators have (at least) the following advantages
over hand-crafted parsers:


    1. It is easier to find the semantic action code -- it isn't buried
          amongst the parsing. This makes for easier maintenance.


    2. It is easier to change the language. Even standardized languages
          change occasionally, but more importantly you may find that your
          interpretation of the language is incorrect. If you're dealing with a
          language like Fortran, you'll also find that you're constantly asked
          to add extensions to the language. (I suspect C++ will also
          experience this phenomenon for years after the language is
          standardized.)


I've heard many people say that hand-crafted parsers do better at error
recovery. That may be true if you're comparing to yacc, but there are
other parser generators that do better at error recovery, many of which
have features for tuning the error recovery. Furthermore, hand-crafted
parsers only do better if you spend a considerable amount of time tweaking
it. If you spend a comparable amount of time tuning your generated parser,
I bet you'd get pretty close to the same quality.


Besides that, I've seen cases where a project chose a hand-crafted parser
because the error recovery would allegedly be better, only to end up
spending so much time just getting the parser right that there was no time
to implement good error recovery! Conversely, you can spend so much time
on the error recovery that the generated code stinks!


> Remember you don't take a compiler course to learn how to build a
> compiler, surprise... Most people never write a compiler. You take
> it for the following reasons:
>
> - Improving your comp. sci. background to understand
> automata theory with a very good application.


Many curricula separate automata theory from compilers, and in those cases
the compiler course assumes you already know automata theory.


> - Understanding what a compiler may do (or not do) for
> your code.
> - Learning about big system software, data structures, etc.


Those are all good reasons, but they're not the most important to us when
considering hiring a compiler engineer. As a general rule, we don't hire
college grads in the compiler group if they haven't had at least one course
in compilers.


--
Bill Leonard
Harris Computer Systems Corporation
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
Bill.Leonard@mail.hcsc.com
--

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