Re: Compiler Compiler Compiler

Mike Dimmick <mike@dimmick.demon.co.uk> 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.)


Regards,
Joachim
[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 comp.compilers page.
Search the comp.compilers archives again.