Non-deterministic Recursive Ascent Parsing

Non-deterministic Recursive Ascent Parsing Ren~ Leermakers Philips Research Laboratories, P.O. Box 80.000, 5600 JA Eindhoven, The Netherlands E-mail:leermake@rosetta.prl.philips.nl ABSTRACT 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. 1 Introduction In this paper we give a purely functional implementa- tion of LR-parsers, applicable to general CF grammars. It will be obtained as a generalization of the well-known recursive descent parsing technique. For LR(0) gram- mars, our result implies a deterministic parser that is closely related to the recursive ascent parsers discovered by Kruseman Aretz [1] and Roberts [2]. In the gen- eral non-deterministic case, the parser has cubic time complexity if the parse functions are implemented as memo-functions [3], which are functions that memorize and re-use the results of previous invocations. Memo- functions are easily implemented in most programming languages. The notion of memo-functions is also used to define an algorithm that constructs a cubic represen- tation for the parse forest, i.e. the collection of parse trees. It has been claimed by Tomita that non-deterministic LR-parsers are useful for natural language processing. In [4] he presented a discussion about how to do non- deterministic LR-parsing, with a device called a graph- structured stack. With our parser we show that no ex- plicit stack manipulations are needed; they can be ex- pressed implicitly with the use of appropriate program- ming language concepts. Most textbooks on parsing do not include proper correctness proofs for LR-parsers, mainly because such proofs tend to be rather involved. The theory of LR- parsing should still be considered underdeveloped, for this reason. Our presentation, however, contains a sur- prisingly simple correctness proof. In fact, this proof is this paper's major contribution to parsing theory. One of its lessons is that the CF grammar class is often the natural one to proof parsers for, even if these parsers are devoted to some special class of grammars. If the gram- marlis restricted in some way, a parser for general CF grammars may have properties that enable smart imple- mentation tricks to enhance efficiency. As we show be- low, the relation between LR-parsers and LR-grammars is of this kind. Especially in natural language processing, standard CF grammars are often too limited in their strong gen- erative power. The extended CF grammar formalism, allowing rules to have regular expressions at the right hand side, is a useful extension, for …

Content truncated to 500 words