|[7 earlier articles]|
|Re: Compiler Compiler Compiler firstname.lastname@example.org (Chris F Clark) (2001-03-27)|
|Re: Compiler Compiler Compiler email@example.com (Ingo Dittmer) (2001-03-27)|
|Re: Compiler Compiler Compiler firstname.lastname@example.org (2001-03-27)|
|Re: Compiler Compiler Compiler email@example.com (2001-03-31)|
|Re: Compiler Compiler Compiler firstname.lastname@example.org (Matthias Blume) (2001-03-31)|
|Re: compiler compiler compiler email@example.com (Toon Moene) (2001-03-31)|
|Re: Compiler Compiler Compiler firstname.lastname@example.org (Joachim Durchholz) (2001-04-04)|
|Re: compiler compiler compiler email@example.com (2001-04-04)|
|Re: Compiler Compiler Compiler firstname.lastname@example.org (Ira D. Baxter) (2001-04-10)|
|Re: Compiler Compiler Compiler email@example.com (Chris F Clark) (2001-04-10)|
|LL vs. LR, was Compiler Compiler Compiler firstname.lastname@example.org (Mike Dimmick) (2001-04-10)|
|Re: Compiler Compiler Compiler email@example.com (2001-04-10)|
|LL vs. LR, was Compiler Compiler Compiler firstname.lastname@example.org (Dan Feriozi) (2001-04-15)|
|From:||"Joachim Durchholz" <email@example.com>|
|Date:||4 Apr 2001 00:25:25 -0400|
|Posted-Date:||04 Apr 2001 00:25:25 EDT|
Mike Dimmick <firstname.lastname@example.org> 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]
Return to the
Search the comp.compilers archives again.