A PROLOG Implementation of Lexical Functional Grammar

ABSTRAC'l

Lexical functional grammar (LPG) is an attempt to solve problems that arise in transformational grammar and ATN-formalisms (Bresnan, 1982) . Another powerful formalism for describing natural languages follows from a method for expressing grammars in logic, due to Colmerauer (1978) and Kowalski (1974) called definite clause grammars (DCG) (Warren, Pereira, 1980) . Both formalisms are a natural

extension o f context free grammars (CFG) .

The aim of this paper is to show - how LPG can be translated into DCG that the procedural semantics of PROLOG provides an efficient tool for LFG-implementations in that it allows the construction of function structures (f-structures) directly during the parsing process . I.e . it is not necessary to have a separate compo­ nent which first derives a set of functional equa­ tions from the parse tree, and secondly generates a f-structure by solving these equations.

I. Lexical functional grammar

LPG consists o f a standard context free grammar (CFG) annotated with functional schemata , determining the assignment of grammatical functions to the CFG-rules. The crucial elements of the theory are the grammatical functions involved both in the representation of lexic al items and in the CFG-rules. The grammatical functions assumed in Bresnan are classified in subcategorizabl e (or governable) functions , namely SUBJ , OBJ , OBJ2 , OBL COMP , XCOMP, and nonsubcategorizable ones, ADJ and XADJ. The subcategorizable functions are the only ones to which lexical items can make reference. The role of the grammatical functions involved in the functional equations is to provide a mapping bet­ ween surface categorial structure and semantic predicate argument structure.

The encoding of function assigning equations into the CFG is done as fol lows:

• (i) lexical entries: a lexical item is associ­ ated with one or more semantic predicates (for its distinct senses or meanings) together with their argument lists, which consists of the syntactically subcategorized functions of the lexical form .

This report describes work done in the Department of Linguistics at the University of Stuttgart . I t was supported in part by the German Science Foundation proj . Ro 245/12.

Uwe Reyle and Werner Frey

Institute of Linguistics, University of Stuttgart

Example: A typical LPG analysis is the treatment of the passive-construction implied by the lexical entries:

( 1 )(t PRED} = 'buy (< SUBJ, OBJ > ) Ct PRED) = 'buy ( < ¢ SUBJ > ) Ct PRED) = 'buy ( < OBLBY' SUBJ ">

(ii) Equations associated with the CFG- rules: Suppose the underlying CFG rule is of the form

With each C. (i=O, . . . , n-1) is associated a func­ tion assignffient equation of the form (t G.) = ~ or t = "- with a grammatical function G. or a feature assigning equation of the f o rm ( ~~F.) v ~ ~

The lexical and syntactic encodings of gram­ matical functions determine the grammatical rela­ tions of a sentence . These relations are formally represented by f - structures which are pairs of f-names and f-values . An f - name is a function or feature symbol. An f-value is a feature , an f­ structure, a semantic form or a set of value . There are two kinds of semantic forms : those with argument lists - called lexical forms - and those without. Lexical forms specify a list of sub­ categorizable functions.

Consider, for example, the f - structure for the sentence

1. John bought a car

(2 I ) SUBJ = fl'JUM = sing J

in which the lexical form 'buy ( SUBJ, OBJ ) is to be read as containing pointers from the SUBJ to the f - name SUBJ, and from the ~BJ to the f-name OBJ which carry the instantiation of the f-names down to the lexical form . The semantical form 'John' is not a lexical form.

The parsing of a sentence takes place in three steps.

· ·~ · denotes that part of the functional struc­ ture which is initiated by en.

· ~ · deno tes that part of the functional structure which is initiated by Ci .

First a parse tree is generated using the CFG (ignoring the functional equations) . Secondly the functional equations associated with the categories of the parse tree are instantiated. This produces a functional descripition of the sentence which is a set of equations . Finally these equations are solved to produce an f-structure.

If there is more than one solution of t e set of equations the sentence is syntactically am­ biguous . ·Furthermore every f-structure has to meet the following additional conditions in order to be a solution:

-uniqueness (or consistency) : every f-name which has a value has a unique value.

-completeness : the f-structure must contain f ­ values for a ll the f - names subcategorized by its lexical forms.

- coherency: all the subcategorizable functions that the f-structure contains must be subcate­ gorized by its lexical forms.

The ability of lexical items to determine the fea­ tures of other constituents i . e. government rela­ tions, is handled by propagating up the tree the feature set , which is inserted by the lexical item. This is done by the trivial equations 1' = ,&, · In our example the features of 'was ' become the features of the V, then of the VP and finally of the S it­ self. This is (for the feature sing.) expressed in the functional equations marked with (· ). The unique­ ness principle guarantees that the subject of the sentence will have the features of the verb (see equations (··)).

Because verbs impose selectional restrictions on their subject , i.e. verbs are subcategorized for their subjects , it follows from the complete­ ness and coherence conditions that verbs govern their subjects . More generally , one can argue by the same reason that lexical items govern all of their subcategorized functions.

As our example shows there can be a relation of referential dependance between an unexpressed subject and an expressed or unexpressed constituent. This r e lation is called control, the unexpressed subject the controlled element and the constituent on which it is referentially dependend is the con­ troller . In CFG it is assumed that only the so­ called open functions XCOMP and XADJ can denote functionally controlled clauses .

II. Definite clause grammar

Like LFG DCG are based on CFG's, too. DCG ' s are the result of a translation of CFG's into a subset of predicate logic , the so-called Horn-clau­ ses . These Horn clauses can be used as a PROLOG­ programme which functions like a top-down parser . DCG' s differ from CFG 's in the following three points:

-context-sensitivity : the arguments of the PROLOG-functions which correspond to non-terminal categories can be used to transport and to test context-sensitive information .

- construction of tree-structures during the parsing process: structures can be built piecemeal, leaving unspecified parts as variables. The struc­ tures can be passed around , and completed as the parsing proceeds. The construction of tree-struc­ tures need not be strictly parallel to the appli­ cation o f the corresponding rules.

-inclusion of additional functions or condi­ tions on functions into the context-free rules .

III. DCG implementation of LFG

Our claim is that using DCG as a PROLOG pro­ gramme the parsing process of a sentence according to the LFG-formalism can be done more efficiently by doing all the three steps described above si­ multaneously .

To do this, we use the content of the function assigning equations to build up parts of the whole f-structure during the parsing process .

Crucial for this is the fact shown by Bres­ nan (1982) , that every phrase has a unique cate­ gory, called its head , with the property, that the features of each phrase are identified with those of its head. The head-category of a phrase is caracterized by the assignment of the trivial function-equation and by the property of contai­ ning a PRED.

The translation of a

with the (pairs of) functional equations FE. into a PROLOG- clause proceeds along the followin~ lines:

• (i) For each category C . there is a fixed set of features. Introduce 1 this feature list as an argument variable of the corresponding PROLOG function ci , i.e. ci ( · feati)
• (ii) For each grammatical function G. appearing in the functional equations annotaEed to C. introduce the f - name of G. as argument 1 variable of C. , i.e . C. 1 wfeat. 'MG.) 1 1 1 1
• (iii) If FE. is of the form 1 =-l- and C is the head of th~ phrase , i.e. , it contai~s the whole grammatical information of the phrase , the corresponding PROLOG- function has as additional arguments all the variables in­ troduced by (i) and (ii) for the other cate­ gory-functions of the phrase , i . e . Ci ( f< Gn_ 1 .wfeatn_ 1 ... * G 0 * feat 0 ) .
• (iv) If FE . is a feature assigning function ( ~ F.f = v we instantiate the feature vari­ able1 * F. in the feature list of C. by v , where v tossibly depends on a lexi~al entry. (see (~PCASE) = OBL 9 in (3 ' )).
• (v) C itsel f is translated into C ( wG. ~feat.) wRere C. is the (unique) head gf the 1 phrase 1 with it~ output *G .. 1
• (vi) The lexi cal entry functions are such that the PRED ' s arguments, namely the f-names of sub­ categorizable functions G. , are shared with the variables containing Br being to contai n the content of the f - value of the G. respec­ tively. (see discussion of coherenc~ beyond)

The uniqueness condition is fulfilled because PROLOG instantiates a variable with ~most one value.

In order to account for the coherence condi­ tion we make special use of the variables which get instantiated by the lexi cal entry of the verb. Suppose this is a lexical form like

Coherence of an f - structure means that onl y the arguments of 'buy ' occur as subcategorizabl e functions . Thus the l exical form of the verb pre­ dicts how its subcategorized functions must look . We use this P.roperty to eliminate the generation of incoherent f - structures in the following way: The variable which i s to carry the conten t of the predicate argument structure of a sentential phrase is "prestructured" by its instantiation with the lexical form of the verb, i.e. , it carries at this point the information 'buy ' (*SUBJ , ~OBJ) that is passed around during the parse , which step by step wil l instantiate the argument variables. A simple check if the variables are instantiated garanties coherency. The mechanism of passing around partially instantiated £-struc­ tures by variables accounts for agreement con­ straints and government.

To account for completeness the non-trivial case is that one has to check for possible re­ ferential dependencies between a controlled ele­ ment and the controller. That means that if the f-structure f is embedded in another f - structure f and the su6categorizable function SUBJ of f 1 h~s no f - value its value can be given by the value of the controller , i .e. , of a subcatego­ rizable function occuring in f 2 . We add to our DCG additional functions which have as input the set of possible controllers and which compute the re­ ferential dependencies espressed by the rules of functional control.(see Bresnan 1982) .

We use LFG as base for the parsing component of our system described in Frey, et al . (1983) .