Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars* Jason Eisner Dept. of Computer ~ Information Science University of Pennsylvania 200 South 33rd Street, Philadelphia, PA 19104 USA j eisner@linc, cis. upenn, edu Giorgio Satta Dip. di Elettronica e Informatica Universit£ di Padova via Gradenigo 6/A, 35131 Padova, Italy satt a@dei, unipd, it Abstract Several recent stochastic parsers use bilexical grammars, where each word type idiosyncrat- ically prefers particular complements with par- ticular head words. We present O(n 4) parsing algorithms for two bilexical formalisms, improv- ing the prior upper bounds of O(n5). For a com- mon special case that was known to allow O(n 3) parsing (Eisner, 1997), we present an O(n 3) al- gorithm with an improved grammar constant. 1 Introduction Lexicalized grammar formalisms are of both theoretical and practical interest to the com- putational linguistics community. Such for- malisms specify syntactic facts about each word of the language--in particular, the type of arguments that the word can or must take. Early mechanisms of this sort included catego- rial grammar (Bar-Hillel, 1953) and subcatego- rization frames (Chomsky, 1965). Other lexi- calized formalisms include (Schabes et al., 1988; Mel'~uk, 1988; Pollard and Sag, 1994). Besides the possible arguments of a word, a natural-language grammar does well to specify possible head words for those arguments. "Con- vene" requires an NP object, but some NPs are more semantically or lexically appropriate here than others, and the appropriateness depends largely on the NP's head (e.g., "meeting"). We use the general term bilexical for a grammar that records such facts. A bilexical grammar makes many stipulations about the compatibil- ity of particular pairs of words in particular roles. The acceptability of "Nora convened the " The authors were supported respectively under ARPA Grant N6600194-C-6043 "Human Language Technology" and Ministero dell'Universitk e della Ricerca Scientifica e Tecnologica project "Methodologies and Tools of High Performance Systems for Multimedia Applications." party" then depends on the grammar writer's assessment of whether parties can be convened. Several recent real-world parsers have im- proved state-of-the-art parsing accuracy by re- lying on probabilistic or weighted versions of bilexical grammars (Alshawi, 1996; Eisner, 1996; Charniak, 1997; Collins, 1997). The ra- tionale is that soft selectional restrictions play a crucial role in disambiguation, i The chart parsing algorithms used by most of the above authors run in time O(nS), because bilexical grammars are enormous (the part of the grammar relevant to a length-n input has size O(n 2) in practice). Heavy probabilistic pruning is therefore needed to get acceptable runtimes. But in this paper we show that the complexity is not so bad after all: • For bilexicalized context-free grammars, O(n 4) is possible. • The O(n 4) result also holds for head au- tomaton grammars. • For a very common special case of these grammars where an O(n 3) algorithm was previously known (Eisner, 1997), the gram- mar constant can be reduced without harming the O(n 3) property. Our algorithmic technique throughout is to pro- pose new kinds of subderivations …

Content truncated to 500 words