A Unification-Based Parser for Relational Grammar

A UNIFICATION-BASED PARSER FOR RELATIONAL GRAMMAR David E. Johnson IBM Research Division P.O. Box 218 Yorktown Heights, NY 10598 dj ohns @ war son. ibm. com Adam Meyers Linguistics Department New York University New York, NY 10003 meyers@acf2.nyu.edu Lawrence S. Moss Mathematics Department Indiana University Bloomington, IN 47401 lmoss@indiana.edu Abstract We present an implemented unification-based parser for relational grammars developed within the stratified feature grammar (SFG) frame- work, which generalizes Kasper-Rounds logic to handle relational grammar analyses. We first in- troduce the key aspects of SFG and a lexicalized, graph-based variant of the framework suitable for implementing relational grammars. We then de- scribe a head-driven chart parser for lexicalized SFG. The basic parsing operation is essentially ordinary feature-structure unification augmented with an operation of label unification to build the stratified features characteristic of SFG. INTRODUCTION Although the impact of relational grammar (RG) on theoretical linguistics has been substan- tial, it has never previously been put in a form suitable for computational use. RG's multiple syn- tactic strata would seem to preclude its use in the kind of monotonic, unification-based parsing sys- tem many now consider standard ([1], [11]). How- ever, recent work by Johnson and Moss [2] on a Kasper-Rounds (KR) style logic-based formalism [5] for RG, called Stratified Feature Grammar (S FG), has demonstrated that even RG's multiple strata are amenable to a feature-structure treat- ment. Based on this work, we have developed a unification-based, chart parser for a lexical ver- sion of SFG suitable for building computational relational grammars. A lexicalized SFG is sim- ply a collection of stratified feature graphs (S- graphs), each of which is anchored to a lexical item, analogous to lexicalized TAGs [10]. The ba- sic parsing operation of the system is S-graph unification (S-unification): This is essentially ordinary feature-structure unification augmented with an operation of label unification to build the stratified features characteristic of SFG. RELATED WORK Rounds and Manaster-Ramer [9] suggested en- coding multiple strata in terms of a "level" at- tribute, using path equations to state correspon- dences across strata. Unfortunately, "unchanged' relations in a stratum must be explicitly "car- ried over" via path equations to the next stra- tum. Even worse, these "carry over" equations vary from case to case. SFG avoids this problem. STRATIFIED FEATURE GRAM- MAR SFG's key innovation is the generalization of the concept ]eature to a sequence of so-called re- lational signs (R-signs). The interpretation of a stratified feature is that each R-sign in a se- quence denotes a primitive relation in different strata. 1 For instance, in Joe gave Mary tea there are, at the clause level, four sister arcs (arcs with the same source node), as shown in Figure h one arc labeled [HI with target gave, indicating gave is the head of the clause; one with label [1] and target Joe, indicating Joe is both the predicate- argument, and surface subject, of the clause; one with label [3,2] and target Mary, indicating that l We use the following R-signs: 1 (subject), 2 (direct …

Content truncated to 500 words