A recursive ascent Earley parser

The discovery of the recursive ascent implementation technique for deterministic and nondeterministic LR-parsers proved that LR-parsers can be implemented purely functionally with very simple correctness proofs. In its primary form, a recursive ascent parser consists of 2 functions for each state. O...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1992-02, Vol.41 (2), p.87-91
Main Author: Leermakers, René
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
Functional programming, language processors
Implementations
Information processing
Speech and sound recognition and synthesis. Linguistics
Techniques
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The discovery of the recursive ascent implementation technique for deterministic and nondeterministic LR-parsers proved that LR-parsers can be implemented purely functionally with very simple correctness proofs. In its primary form, a recursive ascent parser consists of 2 functions for each state. One major application area of the Earley (1970) algorithm is the field of computational linguistics. Tomita's (1986) proposal of a nondeterministic LR-parser to parse natural languages encouraged research to establish the differences between the Earley and Tomita parsers. The Earley algorithm can be considered as a shift-reduce parser and, thus, belongs to the large family of parsers to which nondeterministic LR-parsers also belong. It is shown that implementation techniques for LR-parsers can be applied to the Earley algorithm with the recursive ascent technique.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(92)90260-3