Re: Crenshaw's Tutorial

Jack Crenshaw <jcrens@earthlink.net> schrieb:
>
> One big advantage of an LALR parse is that it can handle syntax
> constructs that LL (recursive-descent) parsers cannot. That is true.
> But these constructs rarely show up in practice, and there is at least
> a reasonable argument that if you're designing a programming language,
> you would be better off to choose one that _IS_ easily parsed.


Two remarks are in order here.


1) I'm not aware of any consensus about which form of grammar is more
"natural" or "easily parsed". For example, the LL paradigma is "give
me the first symbol and I'll know what comes", while LR says "give me
the left context and I know what comes". Which of these is easier to
read for a human is something that I'd really like to know.


2) Non-LL languages may be rare (I don't really know), but non-LL
grammars are very common. I found writing lists for LL grammars a
painful exercize and was relieved when I found that LR grammars don't
object to left recursion. Of course, for a novice, even raw BNF
without braces is quite inscrutable, and still you get used to
it... but I still take this more as an argument in favor of keeping it
simple: most programmers never see a compiler from the inside and have
never had a chance to get used to the contortions that are needed to
make a grammar LL or LR.


> That is the general philosophy behind all of Wirth's languages, and
> it is no accident that Pascal compilers generally run twice or more
> as fast as equivalent C compilers.


I'd be interested to hear whether that is due to differences in
parsing speed or to other factors. For example, the Borland compilers
have traditionally neglected optimization in favor of compilation
speed.


> Finally, RD parsers are generally acknowledged to provide for better
> and more meaningful error detection and reporting.


Agreed.


> In an RD parser, it is easy to see what part of the parse the error
> appeared at, and what the probably error is. This is much more
> difficult in a table-driven parser, in which all one can say is that
> I got an illegal state change.


It's a bit better than that... but good error reporting seems to be more
work for an LALR parser all right.


Regards,
Joachim

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