A functional LR parser

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)