An Improved Error-Correcting Parser for a Context-Free Language

Eiichi TANAKA  

IEICE TRANSACTIONS (1976-1990)   Vol.E67   No.7   pp.379-385
Publication Date: 1984/07/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages

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

This paper describes an error-correcting parser for a context-free language based on the Graham-Harrison-Ruzzo's context-free recognizer (GHR). The parser has similar characteristics as GHR:
(1) The parser unifies both the top-down error-correcting parser by Lyon and the bottom-up error-correcting parsers by Tanaka-Fu and Yamasaki-Tonomura.
(2) The parser is conceptually simpler than the Lyon's parser, and may be much faster than the bottom-up error-correcting parsers.