F-PATR: Functional Constraints for Unification-Based Grammars

F-PATR: FUNCTIONAL CONSTRAINTS FOR UNIFICATION-BASED GRAMMARS Kent Wittenburg Bellcore 445 South St., MRE 2A-347 Morristown, NJ 07962-1910, USA Internet: kentw@bellcore.com Abstract Motivation for including relational constraints other than equality within grammatical formalisms has come from discontinuous constituency and partially free word order for natural languages as well as from the need to define combinatory operations at the most basic level for languages with a two-dimensional syntax (e.g., mathematical notation, chemical equations, and various diagramming languages). This paper presents F-PATR, a generalization of the PATR-II unification-based for- malism, which incorporates relational constraints expressed as user-defined functions. An operational semantics is given for unification that is an adaptation and extension of the approach taken by Ait-Kaci and Nasr (1989). It is designed particularly for unification- based formalisms implemented in functional program- ming environments such as Lisp. The application of unification in a chart parser for relational set languages is discussed briefly. 1. INTRODUCTION For the most part, unification-based grammar for- malisms (e.g., Kaplan and Bresnan 1982; Pereira and Warren 1980; Shieber 1984) have adopted string rewriting conventions from context-free grammar rules, assuming string concatenation as the basic combining operator external to the unification process itself. Kay's Functional Unification Grammar (Kay 1979), while not borrowing the conventions of CFG rewriting rules, still assumed concatenation of strings as the underlying combining operation. However, recent work in HPSG (e.g., Pollard and Sag 1987, Reape 1990, Carpenter et al. 1991) and elsewhere has sought to incorporate con- straints for combining operations into the unification- based representation directly. Part of the motivation for doing so is to accommodate partially free word order and discontinuous constituency without the complica- tion of passing along intermediate "threading" informa- tion within derivations. Such exensions to unification grammars require the use of nonequational constraints, i.e., constraints on values other than simple conditions of equality and the logical connectives built with them. Reape (1990) has proposed, for example, the relations permutation and sequence union to constrain word sequences in his HPSG fragment for German. A different motivation for extending the constraint language for combination within unification grammars comes from languages with a two-dimensional syntax (e.g., mathematical notation, chemical equations, and various diagramming languages). Approaching such domains from a linguistic perspective requires that grammars be capable of dealing with a richer source of data types than just strings and also with specifying a richer set of combinatory operations than simple string concatenation. The approach taken by Helm and Marri- ott (1986, 1990) and Wittenburg, Weitzman, and Talley (1991) [hereafter WWT] is to augment declarative, uni- fication-based grammars with relational constraints. Combinatory operations can then be defined out of the sets of relational constraints present in rule bodies. The approach in WWT includes a set-valued attribute called cover in feature structures. Relations such as above, below, north-east-of, and connected-to are examples that may be incorporated into cover constraints used in grammars for two-dimensional languages. These con- straints apply to sets of the basic input vocabulary, whose members may themselves be complex objects. The use of …

Content truncated to 500 words