Off-line Optimization for Earley-style HPSG Processing

Off-line Optimization for Earley-style HPSG Processing Guido Minnen, Dale Gerdemann~ Thilo GStz * Sonderforschungsbereich 340 University of Tfibingen Wilhelmstr. 113 72074-Tfibingen Germany E-mail: minnen@sfs.nphil.uni-t uebingen.de Abstract A novel approach to HPSG based natural language processing is described that uses an off-line compiler to automatically prime a declarative grammar for generation or parsing, and inputs the primed grammar to an advanced Earley-style processor. This way we provide an elegant solution to the problems with empty heads and efficient bidirectional processing which is illustrated for the special case of HPSG generation. Ex- tensive testing with a large HPSG grammar revealed some important constraints on the form of the grammar. 1 Introduction Bidirectionality of grammar is a research topic in natural language processing that is enjoying increas- ing attention (Strzalkowski, 1993a). This is mainly due to the clear theoretical and practical advantages of bidirectional grammar use (see, among others, Appelt, 1987). We address this topic in describing a novel approach to HPSG (Pollard and Sag, 1994) based language processing that uses an off-line com- piler to automatically prime a declarative grammar for generation or parsing, and hands the primed grammar to an advanced Earley processor. The de- veloped techniques are direction independent in the sense that they can be used for both generation and parsing with HPSG grammars. In this paper, we fo- cus on the application of the developed techniques in the context of the comparatively neglected area of HPSG generation. Shieber (1988) gave the first use of Earley's al- gorithm for generation, but this algorithm does not *The presented research was sponsored by 'l~eilpro - jekt B4 "Constraints on Grammar for Efficient Genera- tion" of the Sonderforschungsbereich 340 "Sprachtheo- retische Grundlagen fiir die Computerllnguistik" of the Deutsche Forschungsgemeinschaft. The authors wish to thank Paul King, Detmar Meurers and Shuly Wintner for valuable comments and discussion. Of course, the authors are responsible for all remaining errors. use the prediction step to restrict feature instantia- tions on the predicted phrases, and thus lacks goal- directedness. Though Gerdemann (1991) showed how to modify the restriction function to make top- down information available for the bottom-up com- pletion step, Earley generation with top-down pre- diction still has a problem in that generating the sub- parts of a construction in the wrong order might lead to massive nondeterminacy or even nontermination. Gerdemann (1991) partly overcame this problem by incorpQrating a head-driven strategy into Earley's algorithm. However, evaluating the head of a con- struction prior to its dependent subparts still suffers from efficiency problems when the head of a con- struction is either missing, displaced or underspec- ified. Furthermore, Martinovid and Strzalkowski (1992) and others have observed that a simple head- first reordering of the grammar rules may still make insufficient restricting information available for gen- eration unless the form of the grammar is restricted to unary or binary rules. Strzalkowski's Essential Arguments Approach (Ehh; 1993b) is a top-down approach to generation and parsing with logic grammars that uses off-line compilation to automatically invert parser-oriented logic grammars. …

Content truncated to 500 words