Re: Parsing techniques

I can't get too much into this, but...


Most of the literature says "use LALR(1) vs LL(1)" for two main reasons
that I can think of.
    1) performance of table-driven (most LALR implementations) is
          usually better than recursive-descent (most LL implementations)
    2) LALR(1) is stronger than LL(1) (it can handle more grammars)


Now to attack these...
    1) depending on the implementation and on how carefully the parser
          is written, the performance difference is very small, especially
          in light of today's processor speeds. It mattered a great deal
          when LALR was born, because processors were nowhere near as fast
          as today, but it's not as big a deal now. (Note that I'm still
          saying that LALR is usually a slightly faster performer...)
    2) Today we have predicated LL(k) grammars, which are (methinks) at
          least as strong as LALR(1). (One example of this is ANTLR, PCCTS'
          parser generator.) In practice, most grammars will only need one
          or two tokens of lookahead. There are evil languages, such as
          C++, that need "infinite lookahead" in spots to determine whether
          something is a type or not, or a decl vs expr. These can be
          implemented by either hacking with a tightly-coupled scanner/parser
          or by using predicated grammars that can check semantics and
          simply "try it to see if it works" when selecting which alternative
          to match.
    3) Debugging recursive-desecent is much easier (IMHO) than a table-
          driven parser. (Maintenance, ya know.)
    4) If you have the right parser-generator, error recovery can
          be pretty simple (as in ANTLR, using "parser exception handling.")


That's my (limited) input for now...
-- Scott




Kent Rollins wrote:
> [what's the relative merits of LALR vs. LL, especially for C++ ?]


--
Scott Stanchfield
MetaWare Incorporated
Santa Cruz, CA


--

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