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

Grammar
Ascent
Time Complexity
Correctness

Cite this

Leermakers, M.C.J. ; Augusteijn, A. ; Kruseman Aretz, F.E.J. / A functional LR parser. In: Theoretical Computer Science. 1992 ; Vol. 104, No. 2. pp. 313-323.
@article{7ee5279be69b4f77bb591ebcc50dfb4b,
title = "A functional LR parser",
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).",
author = "M.C.J. Leermakers and A. Augusteijn and {Kruseman Aretz}, F.E.J.",
year = "1992",
doi = "10.1016/0304-3975(92)90128-3",
language = "English",
volume = "104",
pages = "313--323",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "2",

}

A functional LR parser. / Leermakers, M.C.J.; Augusteijn, A.; Kruseman Aretz, F.E.J.

In: Theoretical Computer Science, Vol. 104, No. 2, 1992, p. 313-323.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - A functional LR parser

AU - Leermakers, M.C.J.

AU - Augusteijn, A.

AU - Kruseman Aretz, F.E.J.

PY - 1992

Y1 - 1992

N2 - 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).

AB - 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).

U2 - 10.1016/0304-3975(92)90128-3

DO - 10.1016/0304-3975(92)90128-3

M3 - Article

VL - 104

SP - 313

EP - 323

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 2

ER -