Re: Error reporting, was infinite look ahead

Max Hailperin <>
Sun, 14 Feb 2010 07:20:53 -0600

          From comp.compilers

Related articles
Infinite look ahead required by C++? ng2010@att.invalid (ng2010) (2010-02-05)
Re: Infinite look ahead required by C++? (Ira Baxter) (2010-02-06)
Re: Infinite look ahead required by C++? (Chris F Clark) (2010-02-10)
Re: Infinite look ahead required by C++? (Ira Baxter) (2010-02-13)
Re: Infinite look ahead required by C++? (2010-02-13)
Re: Error reporting, was infinite look ahead (Max Hailperin) (2010-02-14)
| List of all articles for this month |

From: Max Hailperin <>
Newsgroups: comp.compilers
Date: Sun, 14 Feb 2010 07:20:53 -0600
Organization: Compilers Central
References: 10-02-024 10-02-029 10-02-047 10-02-055 10-02-062
Keywords: LR(1), errors
Posted-Date: 15 Feb 2010 00:09:35 EST (William Clodius) writes:

> The production of good error reports relies on providing as much
> context as possible to the user. LL(k) grammars by definition have a
> clearer context, in particular a clearer dividing point in the
> context, than other grammars. Everything prior to the point where the
> error is discovered can be shown to be syntactically correct. Further
> for such grammars there there is almost always a limited number of
> productions possible and it is reasonable to give messages of the form
> "expexted ..., but ... was found.'" These are intrinsically not
> characteristics to be expected of general LR(k) grammars. ...

Unless I misunderstand you, your claims about LR(k) grammars are
untrue. An LR(k) grammar can be used to construct an LR(k) parser.
And an LR(k) parser can have the two desirable properties you

(1) The "valid prefix" property: at the point where the parser detects
an error, all tokens that it has already consumed constitute a prefix
of some valid string in the language.

(2) The property that when a lookahead is found that cannot extend the
valid prefix (and so indicates an error), an explicit list can be
constructed using only "reasonable" effort of the alternative
lookaheads that would allow the valid prefix to continue (and hence
can be described as "expected").

Property (1) is true even for the LALR parsers that are commonly used
in practice. These parsers may do some extra reduce actions upon
encountering a token that cannot extend any valid prefix, but they
will never shift a token unless it can continue a valid prefix.

Property (2) probably isn't true for LALR parsers (unless you have a
quite elastic definition of "reasonable") because of the
aforementioned spurious reduce actions. But your claim was about
LR(k) grammars in general, and such a grammar can be parsed using a
cannonical LR(k) parser (even if in some cases it also could be parsed
using a LALR parser). And a cannonical LR(k) parser will detect an
error immediately upon encountering a lookahead that does not extend
any valid prefix. It will not even reduce. So the list of "expected"
lookaheads are simply those for which the parsing table shows a shift,
reduce, or accept action given the state on top of the stack.

Post a followup to this message

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