A functional LR parser

M.C.J. Leermakers, A. Augusteijn, F.E.J. Kruseman Aretz

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

Abstract

A purely functional implementation of LR(0) parsers is given, together with a simple correctness proof. For non-LR(0) grammars its time complexity is cubic if the functions that constitute the parser are implemented as memo-functions, i.e. functions that memorize the results of previous invocations. For LR(0) grammars, our algorithm is closely related to the recursive ascent parsers recently discovered by Kruseman Aretz (1988), Barnard and Cordy (1988) and Roberts (1988).
Original languageEnglish
Pages (from-to)313-323
JournalTheoretical Computer Science
Volume104
Issue number2
DOIs
Publication statusPublished - 1992

Fingerprint Dive into the research topics of 'A functional LR parser'. Together they form a unique fingerprint.

Cite this