Re: Is there an error correcting parser generator out there?

David Tarditi <dtarditi@cs.cmu.edu> writes:


      The parser generator distributed with the Standard ML of New Jersey
      compiler, mlyacc, implements the simpler techniques described in
      the article.


      To quote from the manual:


            A parser tries to recover from a syntax error by making a
      single token insertion, deletion, or substitution near the point in
      the input stream at which the error was detected. In addition,
      parsers delay the evaluation of semantic actions until parses are
      completed successfully. This makes it possible for parsers to
      recover from syntax errors that occur before the point of error
      detection.


The parser generator that is a part of our (SoftLab of Sweden) tool-box,
ToolMaker, for compiler construction does exactly this. In addition it
considers the different possibilities of correction and chooses the
cheapest one. This allows the compiler writer to assign delete and insert
costs on individual tokens, giving complete control over the recovery.
E.g. to delete the long keyword PROCEDURE should be costly because that is
normally not the problem, on the other hand the insertion of a ';' should
be set cheap as this is a common error.


By performing repeated trial parses with different recoveries the
generated parser can also verify (to some extent) that the recovery does
fit in the context.


The execution of the semantic actions is delayed until the recovery is
complete, and thus the compiler writer does not have to bother about
recovery in the semantic actions. In addition there are handles for the
insertion and deletion of symbols so that the compiler writer has an
opportunity to ensure that the tokens inserted by the recovery process are
semantically correct and that the deletion does not screw anything up.
This results in a parse that is exactly the same as if the user had
provided the corrected input.


ParserMaker also allows specification of fiducial tokens, i.e tokens that
may be considered syncronising tokens, not to be deleted lightly ;-), and
separators, such as comma, frequently occuring in repeated lists.


All in all this automatically creates a generated parser with good error
recovery, and with some tuning it can be made very good.


/Thomas


--
Thomas Nilsson Phone Int.: (+46) 13 23 57 04 **NEW**
SOFTLAB Phone Nat.: 013 - 23 57 04 **NYTT**
Teknikringen 14, S-583 30 LINKÖPING Email: thoni@softlab.se
SWEDEN
--

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