Re: Error reporting, was infinite look ahead

wclodius@los-alamos.net (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
indicate:


(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.

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