Re: Compiler Compiler Compiler

"Joachim Durchholz" <>
4 Apr 2001 00:25:25 -0400

          From comp.compilers

Related articles
[7 earlier articles]
Re: Compiler Compiler Compiler (Chris F Clark) (2001-03-27)
Re: Compiler Compiler Compiler (Ingo Dittmer) (2001-03-27)
Re: Compiler Compiler Compiler (2001-03-27)
Re: Compiler Compiler Compiler (2001-03-31)
Re: Compiler Compiler Compiler (Matthias Blume) (2001-03-31)
Re: compiler compiler compiler (Toon Moene) (2001-03-31)
Re: Compiler Compiler Compiler (Joachim Durchholz) (2001-04-04)
Re: compiler compiler compiler (2001-04-04)
Re: Compiler Compiler Compiler (Ira D. Baxter) (2001-04-10)
Re: Compiler Compiler Compiler (Chris F Clark) (2001-04-10)
LL vs. LR, was Compiler Compiler Compiler (Mike Dimmick) (2001-04-10)
Re: Compiler Compiler Compiler (2001-04-10)
LL vs. LR, was Compiler Compiler Compiler (Dan Feriozi) (2001-04-15)
| List of all articles for this month |

From: "Joachim Durchholz" <>
Newsgroups: comp.compilers
Date: 4 Apr 2001 00:25:25 -0400
Organization: Compilers Central
References: 01-03-095 01-03-122
Keywords: tools
Posted-Date: 04 Apr 2001 00:25:25 EDT

Mike Dimmick <> wrote:
> An LALR(1) grammar tool produces its syntax trees from the
> bottom up; it therefore processes its input keeping as many
> possibilities in mind (the set of possible reductions) as it can, then
> selecting one when the input becomes unambiguous. The introduction of
> these semantic actions causes problems - the generator cannot know
> which rule is to be reduced, so should it execute the action or not?
> YACC treats the rule containing the action differently from those
> without, I believe. This usually means including the action at the
> equivalent point in all such rules, then backing out if it turns out
> to be incorrect.

Are you *sure* this is correct? yacc doesn't need to undo parsing steps,
and it cannot undo semantic actions (they might delete a file or do
other undoable things), so I'm having trouble to see how this should
have entered yacc's design.

> It seems to me, after some study, that although LR(k) grammars are
> stronger, LL(k) parsers tend to be faster. [...]
> Users of your language will thank you too, because the compiler
> should go one heck of a lot faster if it doesn't have to backtrack.

LR parsers do not backtrack in general, so this is not an argument for
LL parsing. (The only parser generator that I know does backtracking is
of the Earley variant, and that one *must* backtrack because it will
deliver all potential parse trees if the grammar is ambiguous.)

Here's a question: does anybody know whether LL parsers are faster than
LR parsers? I wouldn't expect any differences, but I never had the
opportunity to run a direct comparison.

There are other differences that might be more relevant.
For example, LL parsers have been consistently reported to produce
better error reporting. Does anybody know whether that's a historic
accident, or is there something in LL parsing that makes it inherently
easier to add useful error actions to LL parsers? (I don't mean the
PCCTS error handling mechanism - it's useful but it didn't look
LL-specific to me.)

[Yacc and other LALR parsers don't backtrack, the state machine in the
parser implicitly tracks ambiguous parses, but they all have to be
resolved to something unambiguous before anything reduces. I have
seen an extended yacc with explicit backtracking that someone wrote
to parse C++. -John]

Post a followup to this message

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