An Error-Correcting Version of the Leiss's Parser for Context-Free Languages

Ken-ichi KURODA  Eiichi TANAKA  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.12   pp.1528-1531
Publication Date: 1993/12/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Automaton, Language and Theory of Computing
error-correcting parser,  context-free language,  Earley's parser,  Lyon's parser,  Leiss's parser,  

Full Text: PDF(260.5KB)>>
Buy this Article

This paper describes an error-correcting parser (ec-parser) for context-free languages that is an extension of the Leiss's parser. Since the ec-parser uses precomputed informations and a pruning technique by lookahead, the ec-parser is always faster than the Lyon's parser. Several examples are shown.