How to cover a grammar

How to cover a grammar Ren6 Leermakers Philips Research Laboratories, P.O. Box 80.000 5600 JA Eindhoven, The Netherlands ABSTRACT A novel formalism is presented for Earley-like parsers. It accommodates the simulation of non-deterministic pushdown automata. In particular, the theory is applied to non-deterministlc LRoparsers for RTN grammars. 1 Introduction A major problem of computational linguistics is the inefficiency of parsing natural language. The most popular parsing method for context-free natural lan- guage grammars, is the genera/ context-free parsing method of Earley [1]. It was noted by Lang [2], that Earley-like methods can be used for simulating a class of non-determlnistic pushdown antomata(NPDA). Re- cently, Tondta [3] presented an algorithm that simulates non-determlnistic LRoparsers, and claimed it to be a fast Mgorithm for practical natural language processing sys- tems. The purpose of the present paper is threefold: 1 A novel formalism is presented for Earley-like parsers. A key rSle herein is played by the concept of bi- linear grammaxs. These are defined as context-free grammars, that satisfy the constraint that the right hand side of each grammar rule have at most two non-terminals. The construction of parse matrices • for bilinear grammars can be accomplished in cubic time, by an algorithm called C-paxser. It includes an elegant way to represent the (possibly infinite) set of parse trees. A case in point is the use of predict functions, which impose restrictions on the parse matrix, if part of it is known. The exact form and effectiveness of predict functions depend on the bilineax grammar at hand. In order to parse a gen- era] context-free grammar G, a possible strategy is to define a cover for G that satisfies the bilin- ear grammar constraint, and subsequently parse it with C-parser using appropriate predict functions. The resulting parsers axe named Earley-like, and differ only in the precise description for deriving covers, and predict functions. 2 We present the Lang algorithm by giving a bilin- ear grammar corresponding to an NPDA. Em- ploying the correct predict functions, the parser for this grammar is equivalent to Lang's algo- rithm, although it works for a slightly different class of NPDA's. We show that simulation of non- deterministic LR-parsers can be performed in our version of the Lang framework. It follows that Earley-like Tomita parsers can handle all context- free grammars, including cyclic ones, although Tomita suggested differently[3]. 3 The formalism is illustrated by applying it to Recur- sire Transition Networka(RTN)[S]: Applying the techniques of deterministic LR-parsing to gram- mars written as RTN's has been the subject of re- cent studies [9,10]. Using this research, we show how to construct efficient non-deterministic LR- parsers for RTN's. 2 C-Parser The simplest parser that is applicable to all context-free languages, is the well-known Cocke-Younger-Kasa~i (CYK) parser. It requires the grammar to be cast in Chomsky normal form. The CYK parser constructs, for the sentence zl ..zn, a parse matrix T. To each part zi+1 ..zj of the input corresponds the matrix element T.j, the value of which is a set …

Content truncated to 500 words