Re: Error reporting, was Infinite look ahead required by C++?

Hi Chris,


On Sun, 28 Feb 2010, Chris F Clark wrote:


> I hope not to be too disappointing in this response to
> "Joel E. Denny" <jdenny@clemson.edu> who writes:


Not at all. Thanks for your response, and sorry for my slow reply.


> I cannot explain how it works in Pager's algorithm because I never
> completely grasped it


There were definitely a few details of his lane-tracing algorithm that I
wasn't sure about. However, his weak compatibility test has to be the
simplest and most elegant of the correct minimal LR algorithms I've read
about. Of course, it is not meant to handle non-LR grammars with resolved
conflicts.


> but I can explain the perspective from Spector's algorithm because
> we used (a variation on) it in Yacc++.


I've read these Spector papers:


    D. Spector. Full LR(1) parser generation. SIGPLAN Not., 16(8):58b66,
    1981.


    D. Spector. Efficient full LR(1) parser generation. SIGPLAN Not.,
    23(12):143b150, 1988.


Do you know of any other papers that explain Spector's algorithm in any
greater detail?


> In a typical grammar, you will find states where there is only one
> possible non-terminal to reduce to. In those states, splitting will
> not reduce the number of conflicts and is thus pointless.


You say "only one possible non-terminal", but there could be a conflict
between two reductions that have the same nonterminal on the LHS but that
have a different RHS.


> Thus, for a minimal state algorithm there may still be some spurious
> reduces when an error is detected. You could adjust the algorithm
> to avoid those reduces also and I believe you would then get the
> canonical LR(1) tables.


Thanks for confirming.


> Moveover, the work we did was not particularly, groundbreaking.
>
> We implemented the essential "display_expected()" function that
> returns for a given state the tokens (and if desired non-terminals)
> that are not error actions in a given state.


That kind of function seems to be the normal starting point whenever I see
discussions of this issue, and I agree it's fairly obvious. However, how
exactly do you use it? Do you simply provide it for the grammar author to
invoke from semantic actions? Or do your generated parsers invoke it
automatically to prevent extra reductions before a syntax error is
detected?


> Thus, it was natural and important that the "display_expected()"
> function be able to skip reporting all the context dependent
> keywords that were legal simply because an identifier was legal in
> that place.


I'm not quite following this point. Did you mean to say "context
independent keywords"? That is, I can understand why your scanner would
treat a reserved keyword (context independent) as being legal wherever
only an identifier is actually legal, and then I assume your parser would
report a syntax error because the keyword is not actually legal.
However, I don't understand why you would treat a non-reserved keyword
(context dependent) that way, and so I don't understand why
display_expected would need to treat it differently than any other illegal
token.


> It also doesn't help that the parsing problem is not generally
> considered to be academically interesting and thus very few PhD
> students are working on it.


Maybe industry will have some job for us then.

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