Non-Deterministic Recursive Ascent Parsing

Non-Deterministic Recursive Ascent Parsing, Renee Leermakers. 1991 conference on European chapter of the Association for Computational Linguistics.

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. functions 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 Kruseman 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.

How LR parsers worked always confused me until I learned about their presentation in terms of recursive ascent.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Derivation of a Typed Functional LR Parser

In this vein, this paper is cool: Derivation of a Typed Functional LR Parser Ralf Hinze and Ross Patterson 2005 (PDF)

It doesn't seem to have been mentioned on LtU before.

Also, Essence

Thanks for the link! I knew about Michael Sperber and Peter Thiemann's work on Essence, a recursive ascent parser generator that uses partial evaluation is also pretty neat, but not about that.

Ascent through Descent

In a similar vein, you might also be interested in some techniques that can transform (portions of) a parser from recursive ascent to recursive descent.