Selective Magic HPSG Parsing

Proceedings of EACL '99 Selective Magic HPSG Parsing Guido Minnen* Cognitive and Computing Sciences, University of Sussex Falmer, Brighton BN1 9QH United Kingdom Guido.Minnen@cogs.susx.ac.uk www.cogs.susx.ac.uk/lab/nlp/minnen/minnen.html Abstract We propose a parser for constraint- logic grammars implementing HPSG that combines the advantages of dy- namic bottom-up and advanced top- down control. The parser allows the user to apply magic compilation to spe- cific constraints in a grammar which as a result can be processed dynamically in a bottom-up and goal-directed fash- ion. State of the art top-down process- ing techniques are used to deal with the remaining constraints. We discuss vari- ous aspects concerning the implementa- tion of the parser as part of a grammar development system. 1 Introduction In case of large grammars the space requirements of dynamic parsing often outweigh the benefit of not duplicating sub-computations. We propose a parser that avoids this drawback through combin- ing the advantages of dynamic bottom-up and ad- vanced top-down control. 1 The underlying idea is to achieve faster parsing by avoiding tabling on sub-computations which are not expensive. The so-called selective magic parser allows the user to apply magic compilation to specific constraints in a grammar which as a result can be processed dy- namically in a bottom-up and goal-directed fash- ion. State of the art top-down processing tech- niques are used to deal with the remaining con- straints. Magic is a compilation technique originally de- veloped for goal-directed bottom-up processing of logic programs. See, among others, (Ramakrish- nan et al. 1992). As shown in (Minnen, 1996) *The presented research was carried out at the Uni- versity of Tfibingen, Germany, as part of the Sonder- forschungsbereich 340. 1A more detailed discussion of various aspects of the proposed parser can be found in (Minnen, 1998). magic is an interesting technique with respect to natural language processing as it incorporates fil- tering into the logic underlying the grammar and enables elegant control independent filtering im- provements. In this paper we investigate the se- lective application of magic to typed feature gram- mars a type of constraint-logic grammar based on Typed Feature Logic (Tgv£:; GStz, 1995). Typed feature grammars can be used as the basis for implementations of Head-driven Phrase Structure Grammar (HPSG; Pollard and Sag, 1994) as dis- cussed in (GStz and Meurers, 1997a) and (Meur- ers and Minnen, 1997). Typed feature grammar constraints that are inexpensive to resolve are dealt with using the top-down interpreter of the ConTroll grammar development system (GStz and Meurers, 1997b) which uses an advanced search function, an advanced selection function and in- corporates a coroutining mechanism which sup- ports delayed interpretation. The proposed parser is related to the so-called Lemma Table deduction system (Johnson and DSrre, 1995) which allows the user to specify whether top-down sub-computations are to be tabled. In contrast to Johnson and DSrre's deduc- tion system, though, the selective magic parsing approach combines top-down and bottom-up con- trol strategies. As such it resembles the parser of the grammar development system Attribute Language Engine (ALE) of (Carpenter …

Content truncated to 500 words