tailieunhanh - Báo cáo khoa học: "Non-deterministic Recursive Ascent Parsing"

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, . 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. | Non-deterministic Recursive Ascent Parsing René Leermakers Philips Research Laboratories . Box 5600 JA Eindhoven The Netherlands E-mail leermake@ 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 . 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 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 implementation 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 grammars 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 general 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. Memofunctions are easily implemented in most programming languages. The notion of memo-functions is also used to define an algorithm that constructs a cubic representation for the parse forest . 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