Paper: Non-Deterministic Recursive Ascent Parsing

ACL ID E91-1012
Title Non-Deterministic Recursive Ascent Parsing
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1991
  • Rene Leermakers (Philips Research Laboratories, Eindhoven The Netherlands)

A purely functional implementation of LR-parsers is given, together with a simple correctness proof. It is presented as a generalization of the recursive descent parser. For non-LR grammars the time-complexity of our parser is cubic if the functions that constitute the parser are implemented as memo-functions, i.e. func- tions that memorize the results of previous invocations. Memo-functions also facilitate a simple way to construct a very compact representation of the parse forest. For LR(0) grammars, our algorithm is closely related to the recursive ascent parsers recently discovered by Kruse- man Aretz [1] and Roberts [2]. Extended CF grammars (grammars with regular expressions at the right hand side) can be parsed with a simple modification of the LR-parser for normal CF grammars.