Parsing with an Extended Domain of Locality

Proceedings of EACL '99 Parsing with an Extended Domain of Locality John Carroll, Nicolas Nicolov, Olga Shaumyan, Martine Smets g¢ David Weir School of Cognitive and Computing Sciences University of Sussex Brighton, BN1 9QH, UK Abstract One of the claimed benefits of Tree Ad- joining Grammars is that they have an extended domain of locality (EDOL). We consider how this can be exploited to limit the need for feature structure uni- fication during parsing. We compare two wide-coverage lexicalized grammars of English, LEXSYS and XTAG, finding that the two grammars exploit EDOL in different ways. 1 Introduction One of the most basic properties of Tree Adjoining Grammars (TAGS) is that they have an extended domain of locality (EDOL) (Joshi, 1994). This refers to the fact that the elementary trees that make up the grammar are larger than the cor- responding units (the productions) that are used in phrase-structure rule-based frameworks. The claim is that in Lexicalized TAGS (LTAGs) the el- ementary trees provide a domain of locality large enough to state co-occurrence relationships be- tween a lexical item (the anchor of the elemen- tary tree) and the nodes it imposes constraints on. We will call this the extended domain of locality hypothesis. For example, wh-movement can be expressed locally in a tree that will be anchored by a verb of which an argument is extracted. Consequently, features which are shared by the extraction site and the wh-word, such as case, do not need to be percolated, but are directly identified in the tree. Figure 1 shows a tree in which the case feature at the extraction site and the wh-word share the same value) 1The anchor, substitution and foot nodes of trees are marked with the symbols o, $ and *, respectively. Words in parenthesis are included in trees to provide examples of strings this tree can derive. Much of the research on TAGS can be seen as illustrating how its EDOL can be exploited in vari- ous ways. However, to date, only indirect evidence has been given regarding the beneficial effects of the EDOL on parsing efficiency. The argument, due to Schabes (1990), is that benefits to parsing arise from lexicalization, and that lexicalization is only possible because of the EDOL. A parser deal- ing with a lexicalized grammar needs to consider only those elementary structures that can be as- sociated with the lexical items appearing in the input. This can substantially reduce the effective grammar size at parse time. The argument that an EDOL is required for lexicalization is based on the observation that not every set of trees that can be generated by a CFG can be generated by a lexicalized CFG. But does the EDOL have any other more direct effects on parsing efficiency? On the one hand, it is a consequence of the EDOL that wide-coverage LTAGs are larger than their rule-based counterparts. With larger ele- mentary structures, generalizations are lost re- garding the internal structure of the elementary trees. Since parse time depends on …

Content truncated to 500 words