Head-driven Parsing for Lexicalist Grammars: Experimental Results

Head-driven Parsing for Lexicalist Grammars: Experimental Results Gosse Bouma & Gertjan van Noord vakgroep Alfa-informatica, University of Groningen Postbus 716 NL 9700 AS Groningen Abstract We present evidence that head-driven pars- ing strategies lead to efficiency gains over standard parsing strategies, for lexicalist, concatenative and unification-based gram- mars. A head-driven parser applies a rule only after a phrase matching the head has been derived. By instantiating the head of the rule important information is ob- tained about the left-hand-side and the other elements of the right-hand-side. We have used two different head-driven parsers and a number of standard parsers to parse with lexicalist grammars for English and for Dutch. The results indicate that for important classes of lexicalist grammars it is fruitful to apply parsing strategies which are sensitive to the linguistic notion 'head'. 1 Introduction Lexicalist grammar formalisms, such as Head-driven Phrase Structure Grammar (HPSG) and Categorial Unification Grammar (CUG) have two characteristic properties. Lexical elements and phrases are associ- ated with categories that have considerable internal structure. Second, instead of construction specific rules, a small set of generic rule schemata is used. Consequently, the set of constituent structures de- fined by a grammar cannot be 'read off' the rule set directly, but is defined by the interaction of the rule schemata and the lexicM categories. Applying standard parsing algorithms to such grammars is unsatisfactory for a number of rea- sons. Earley parsing is intractable in general, as the rule set. is simply too general. For some grammars, naive top-down prediction may even fail to termi- nate. [Shieber, 1985] therefore proposes a modified version of the Earley-parser, using restricted top- down prediction. While this modification leads to termination of the prediction step, in practice it eas- ily leads to a trivial top-down prediction step, thus leading to inferior performance. Bottom-up parsing is far more attractive for lexi- calist formalisms, as it is driven by the syntactic in- formation associated with lexical elements. Certain inadequacies remain, however. Most importantly, the selection of rules to be considered for application may not be very efficient. Consider, for instance, the following DCG rule: s([ ]) -~ Arg, vp([Arg]). (1) A parser in which application of a rule is driven by the left-most daughter, as it is for instance in a stan- dard bottom-up active chart parser, will consider the application of rule (1) each time an arbitrary con- stituent Arg is derived. For a bottom-up active chart parser, for instance, this may lead to the introduc- tion of large amounts of active items. Most of these items will be useless. For instance, if a determiner is derived, there is no need to invoke the rule in (1), as there are simply no vP's selecting a determiner as subject. Parsers in which the application of a rule is driven by the rightmost daughter, such as shift-reduce and inactive bottom-up chart parsers, encounter a similar problem for rules such as (2). vp(Args) --* vp([Arg[Args]), Arg. (2) Each time an arbitrary constituent Arg is derived, the …

Content truncated to 500 words