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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Earley-Based Universal Error-Correcting Parser

  • Maurice Herwig,
  • Norbert Hundeshagen,
  • Martin Lange

摘要

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.