Re: Compiler Compiler Compiler

Chris F Clark <>
10 Apr 2001 01:18:37 -0400

          From comp.compilers

Related articles
[10 earlier articles]
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)
Re: Compiler Compiler Compiler (2001-04-10)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: 10 Apr 2001 01:18:37 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 01-03-095 01-03-122 01-04-026
Keywords: tools
Posted-Date: 10 Apr 2001 01:18:37 EDT

I don't know the answer to the speed question, you asked although I
should. However, I have a feel for the second question:

> 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 think it is not an accident, but inherent to a key distinction
between LL and LR parsing methods.

In an LL method, there is only 1 rule active at a time (i.e. each
thing on the parser's stack represents an exact rule that the input
must match for the input to be valid). Therefore, when an LL parser
finds something that doesn't fit, it has the exact context of what it
is trying to match and it has only 1 possible interpretation. That
does not mean there is only 1 token that can be legal at the point,
but that the set of tokens is determined from 1 unique context.

In the LR method, generally there are several concurrent rules active
at each point (i.e. each thing on the parser's stack represents a set
of possible rules that may match--that set is the "dotted items").
Thus, in contrast, when an LR parser finds a problem, its stack
represents a cross-product of the sets for each dotted item on the
stack. It doesn't know which entry in that cross-product represents
what the user was trying to do. That limits an LR parsers knowledge
of the context and thus what the "right error to report" is.

Hope this helps,

Chris Clark Internet :
Compiler Resources, Inc. Web Site :
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

Post a followup to this message

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