An Earley-Based Universal Error-Correcting Parser
摘要
Motivated by educational applications, we present an extension of the Earley parser in order to compute all possible corrections that take a given word into a context-free target language. Unlike classical error-correcting parsers, which compute a single correction or a set of minimal corrections, our approach targets the possibly infinite set of all corrections represented as a shared packed parse forest. It is achieved by extending the theory of syntactic corrections and normal-forms thereof. We introduce optimisations that eliminate redundant computations and thus, indicate a runtime improvement.