[Menhir-list] Error reporting

[Francois Pottier]

On Thu, Feb 10, 2011 at 01:29:35PM +0100, Rémi Dewitte wrote:
> How hard do you think it will be ?
> If you could give few hints about how to get started to implement this
> feature, I might try.

I am not quite sure.

The supposedly easy part would be to statically compute, for each state of
the automaton, which set of tokens it is willing to accept. That would be
the set of all tokens for which there exists either an outgoing transition
(a shift action) or a reduction.

However, even this part is not so easy as it sounds. This computation would
produce an exact answer only if a canonical LR(1) construction has been
carried out. However, as soon as one merges states (as done by SLR, LALR,
Pager, etc.), one obtains states that appear to be willing to perform a
reduction on a certain token T, yet that reduction will lead to a state where
the token T is rejected. Thus, the computation described in the previous
paragraph will produce an over-approximation of the sets of acceptable tokens.
(This would perhaps not be a problem in practice?)

Then, the somewhat harder part would be to modify the two back-ends (the
code-based back-end and the table-based back-end). The idea would be to let
the SyntaxError exception carry the number of the state where an error was
detected, and to provide a function that maps state numbers to sets of
acceptable tokens. One would need to make sure that there is no interaction
with the somewhat complicated mechanisms associated with the "error" token.

-- 
François Pottier
Francois.Pottier at inria.fr
http://gallium.inria.fr/~fpottier/