A Comparison of Rule-Invocation Strategies in Context-Free Chart Parsing

A Comparison of Rule-Invocation Strategies in Context-Free Chart Parsing Mats Wirdn Department of Computer and Information Science LinkSping University S-581 83 LinkSping, Sweden Abstract Currently several grammatical formalisms converge towards being declarative and towards utilizing context-free phrase-structure grammar as a back- bone, e.g. LFG and PATR-II. Typically the pro- cessing of these formalisms is organized within a chart-parsing framework. The declarative charac- ter of the formalisms makes it important to decide upon an overall optimal control strategy on the part of the processor. In particular, this brings the rule- invocation strategy into critical focus: to gain max- imal processing efficiency, one has to determine the best way of putting the rules to use. The aim of this paper is to provide a survey and a practical compari- son of fundamental rule-invocation strategies within context-free chart parsing. 1 Background and Introduction An apparent tendency in computational linguistics during the last few years has been towards declara- tive grammar formalisms. This tendency has mani- fested itself with respect to linguistic tools, perhaps seen most clearly in the evolution from ATNs with their strongly procedural grammars to PATR-II in its various incarnations (Shieber et al. 1983, Kart- tunen 1986), and to logic-based formalisms such as DCG (Pereira and Warren 1980). It has also man- ifested itself in linguistic theor/es, where there has been a development from systems employing sequen- tial derivations in the analysis of sentence struc- tures to systems like LFG and GPSG which estab- lish relations among the elements of a sentence in an order-independent and also direction-independent way. For example, phenomena such as rule order- ing simply do not arise in these theories. This research has been supported by the National Swedish Board for Technical Development. In addition, declarative formalisms are, in princi- ple, processor-independent. Procedural formalisms, although possibly highly standardized (like Woods' ATN formalism), typically make references to an (abstract) machine. By virtue of this, it is possible for grammar writ- ers to concentrate on linguistic issues, leaving aside questions of how to express their descriptions in a way which provides for efficient execution by the pro- cessor at hand. Processing efficiency instead becomes an issue for the designer of the processor, who has to find an overall aoptimal~ control strategy for the processing of the grammar. In particular (and also because of the potentially very large number of rules in realis- tic natural-language systems), this brings the rule- invocation strategy I into critical focus: to gain max- imal processing efficiency, one has to determine the best way of putting the rules to use. 2 This paper focuses on rule-invocation strategies from the perspective of (context-free) chart parsing (Kay 1973, 1982; Kaplan 1973). Context-free phrase-structure grammar is of in- terest here in particular because it is utilized as the backbone of many declarative formalisms. The chart-parsing framework is of interest in this connec- tion because, being a C'higher-order algorithm" (Kay 1982:329), it lends itself easily to the processing of different grammatical formalisms. At the same time it is of …

Content truncated to 500 words