Syntax, Preference, and Right Attachment

1. Syntaetie Approaehes

Recent discussion of the issue of how and where to attach right-hand phrases (and more generally, clauses) in sentence analysis was started by the claims of Frazier and Fodor {1979). They offered two rules :

(i) Right Assoeiation

which is that phrases on the right should be attached as low as possible on a syntax tree, thus

JOHN BOUGHT THE BOOK THAT I HAD BEEN TRY­ ING TO OBTAIN (FOR SUSAN)

which attaches to OBTAIN not to BOUGHT. But this rule fails for

~ JOHN BOUGHT THE BOOK (FOR SUSAN) which requires attachment to BOUGHT not BOOK. A second principle was then added :

(ii) Minimal Attachment

which is that a phrase must be attached higher in a tree if doing that minimizes the number of nodes in the tree (and this rule is to take precedence over (i)).

So, in :

which Shieber's conflict reduction rule must get wrong. For Shieber's version of lexical preference there will be problems with :

~ THE WOMAN WANTED THE DRESS (FOR HER DAUGHTER)

which the rules he gives for WANT must get wrong.

(ii) Schubert

Schubert (1984) presents some of the above counter-examples in an attack on syntactically based methods. He proposes a syntactico-semantic network system of what he calls preference trade-offs. He is driven to this, he says, because he rejects any sys­ tem based wholly on lexically-based semantic preferences (which is part of what we here will call preference semantics, see below, and which would subsume the simpler Versions of lexical preference). He does this on the grounds that there are clear cases where "syn­ tactic preferences prevail over much more coherent alternatives" (Schubert, 1984, p.248), where by "coherent" he means interpreta­ tions im~ed by semanticsf pragmatics. His examples are : - -

(p.Aw~ ~WHO HÄDTIVED WITH HER ~WHILE "oN MATERNITY LEA VE)

(where fulllines show the "natural" pragmatic interpretations, and dotted ones the interpretations that Schubert says are imposed willy- nilly by the syntax). Our informants disagree with Schubert : they attach as the syntax suggests to LIVE, but still insist that the leave is Mary's (i .e. so interpreting the last clause that it con­ tains an elided (WHILE) SHE WAS (ON .... ). If that is so the example does not split off semantics from syntax in the way Schu­ bert wants, because the issue is who is on leave and not when something was done. In such circumstances the example presents no special problems.

"- ........

Here our informants attach the phrase resolutely to MET as com­ monsense dictates (i .e. they ignore or are able to discount the built-in distance effect of the very long NP). A more difficult and interesting case arises if the last phrase is (AT A WEDDING), since the example then seems to fall withing the exclusion of an "attachment unless it yields zero information" rule deployed within preference semantics (Wilks, 1973), which is probably, in its turn, a close relative of Grice's (1975) maxim concerned with infor­ mation quantity. In the (AT A WEDDING) case, informants con­ tinue to attach to MET, seemingly discounting both the syntactic indication and the information vacuity of MARRIED AT A WED­ DING.

/-,

"' \ JOHN WAS NAMED (AFTER HIS TWIN SISTER)

Here our informants saw genuine ambiguity and did not seem to mind much whether attachment or lexicalization of NAMED AFTER was preferred. Again, information vacuity teils against the syntactic attachment (the example is on the model of:

HE WAS NAMED AFTER HIS FATHER

Wilks 1973, which was used to make a closely related point), but normal geodering of names teils against the lexi'Calization of the verb to NAME+AFTER.

Our conclusion from Schubert's examples is the reverse of his own : these are not simple examples but very complex ones, involving distance and (in two cases) information quantity phenomena. In none of the cases do they support the Straightfor­ ward primacy of syntax that his case against a generalized "lexical preference hypothesis" (i.e. one without rules (i) and (ii) as default cases, as in Ford et al.'s lexical preference) would require. We shall therefore consider that hypothesis, under the name preference semantics, to be still under consideration.

(iii) Hirst

Hirst (1984) aims to produce a conflation of the approaches of Ford et al. , described above, and a principle of Crain and Steed­ man (1984) called The Principle of Parsimony, which is to make an attachment that corresponds to leaving the minimum number of presuppositions unsatisfied . The example usually given is that of a "garden path" sentence like :

THE HORSE RACED P AST THE BARN FELL

where the natural (initial) preference for the garden path interpre­ tation is to be explained by the fact that, on that interpretation, only the existence of an entity corresponding to THE HORSE is to be presupposed, and that means less presuppositions to which nothing is the memory structure corresponds than is needed to opt for the existence of some THE HORSE RACED P AST THE BARN. One difficulty here is what it is for something to exist in memory: Crain and Steedman themselves note that readers do not garden path with sentences like :

CARS RACED AT MONTE CARLO FETCH HIGH PRICES AS COLLECTOR'S ITEMS

but that is not because readers . know of any particular cars raced at Monte Carlo. Hirst accepts from (Winograd 1972) a general Principle of Referential Success (i .e. to actual existent entities), but the general unsatisfactoriness of restricting a system to actual entities has long been known, for so much of our discourse is about possible and virtual ontologies (for a full discussion of this aspect of Winograd, see Ritchie 1978).

The strength of Hirst's approach is his attempt to reduce the presuppositional metric of Crain and Steedman to criteria mani­ pulable by basic semantic/ lexical codings, and particularly the contrast of definite and indefinite articles. But the general determi­ nation of categories like definite and indefinite is so shaky (and only indirectly related to "the" and " a" in English), and cannot possibly bear the weight that he puts on it as the solid basis of a theory of phrase attachment.

So, Hirst invites counter-examples to his Principle of Referential Success (1984, p.149) adapted from Winograd: "a non­ generic NP presupposes that the thing it describes exists ..... an indefinite NP presupposes only the plausibility of what it describes." But this is just not so in either case :

THE PERPETVAL MOTION MACHINE IS THE BANE OF LIFE IN A PATENT OFFICE

A MAN I JUST MET LENT ME FIVE POUNDS

The machine is perfectly definite but the perpetual motion machine does not exist and is not presupposed by the speaker. We conclude that these notions are not yet in a state to be the basis of a theory of PP attachment. Moreover, even though beliefs about the world must play a roJe in attachment in certain cases, there is, as yet, no reason to believe that beliefs and presuppositions can provide the material for a basic attachment mechanism.

(iv) Preference Semantics

Preference Semantics has claimed that appropriate structur­ ings can be obtained using essentially semantic information, given also a rule of preferring the most densely connected representa­ tions that can be constructed from such semantic information (Wilks 1975, Fass & Wilks 1983).

Let us consider such a position initially expressed as semantic dictionary information attaching to the verb; this is essentially the position of the systems discussed above, as weil as of case grammar and the semantics- based parsing systems (e.g. Riesheck 1975) that have been based on it. When discussing implementation in the last section we shall argue (as in Wilks 1976) that semantic material that is to be the base of a parsing process cannot be thought of as simply attaching to a verb (rather than to nouns and all other word senses)

In what follows we shall assume case predicates in the dic­ tionary entries of verbs, nouns etc. that express part of the mean­ ing of the concept and determine its semantic relations. We shall write as [OBTAIN] the abbreviation of the semantic dictionary entry for OBTAIN, and assume that the following concepts con­ tain at least the case entries shown ( as case predicates and the types of argument fillers) :

The issue here is whether these are plausible preferential meaning constituents: e.g. that to obtain something is to obtain it for a recipient;

to position something is to do it in association with a place; a ticket (in this sense i.e. "billet" rather than " ticket" in French) is a ticket to somewhere, and so on. They do not entail restrictions, but only preferences. Hence, "John brought his dog a hone" in no way violates the coding [BRING]. We shall refer to these case con­ stituents within semantic representations as semantic preferences of the corresponding head concept.

3. A First Trial Attaehment Rule

The examples discussed are correctly attached by the following rule : '

Rule A : moving leftwards from the right hand end of a sentence, assign the attachment of an entity X (word or phrase) to the first entity to the left of X that has a preference that X satisfies; this entails that any entity X can only satisfy the preference of one entity. Assurne also a push down stack for inserting such entities as X into until they satisfy some preference. Assurne also some dis­ tance Iimit (to be empirically determined) and aDEFAULT rule such that, if any X satisfies no preferences, it is attached locally, i.e. immediately to its left.

Rule A gets right all the classes of examples discussed (with one exception, see below) : e.g

where the last requires use of the push-down stack. The phenomenon treated here is assumed to be much more general than just phrases, as in:

".~,

(i .e. a truffied pate of duck, not a pate of truffied ducks!) where we envisage a preference (POSS STUFF) --;.-i .e. prefers to be predi­ cated of substances -- as part of [TRUFFE]. French gender is of no use here , since all the concepts are masculine.

This rule would of course have to be modified for many special factors, e.g. pronouns, because of :

~

A more substantial drawback to this substitution of a single semantics- based rule for all the earlier syntactic complexity is that placing the preferences essentially in the verbs (as did the sys­ tems discussed earlier that used lexical preference) and having lit­ tle more than semantic type information on nouns (except in cases like [TICKET] that also prefers associated cases) but, most impor­ tantly, having no semantic preferences associated with prepositions that introduce phrases, we shall only succeed with rule A by means of a semantic subterfuge for a !arge and simple class of cases, namely: ~

or ~

Given the "low default" component of rule A, these can only be correctly attached if there is a very general case component in the verbs, e.g. some statement of location in all "active types" of verbs (tobe described by the primitive type heads in their codings) like SHOOT i.e. (location *pla), which expresses the fact that acts of this type are necessarily located. (location *pla) is then the preference that (IN THE PARK) satisfies, thus preventing a low default.

Again, verbs like LOVE would need a (REASON ANY) com­ ponent in their coding, expressing the notion that such states ( as opposed to actions, both defined in terms of the main semantic primitives of verbs) are dependent on some reason, which could be anything.

But the clearest defect of Rule A (and, by implication, of all the verb- centered approaches discussed earlier in the paper) is that verbs in fact confront not cases, but PPs fronted by ambigu­ ous prepositions, and it is only by taking account of their prefer­ ences that a general solution can be found.

4. Preposition Semanties: Preplates

In fact rule A was intentionally naive: it was designed to demonstrate (as against Shubert's claims in particular) the wide coverage of the data of a single semantics-based rule, even if that required additional, hard to motivate, semantic information to be given for action and states. It was stated in a verb-based lexical preference mode simply to achieve centrast with the other systems discussed.

For some years, it has been a principle of preference seman­ tics (e.g. Wilks 1973, 1975) that attachment relations of phrases, cl.auses etc. are to be determined by comparing the preferences emanating from all the entities involved in an attachment: they are all , as it were, to be considered as objects seeking other pre­ ferred classes of neighbors, and the best fit, within and between each order of structures built up, is to be found by comparing the preferences and finding a best mutual fit . This point was made in (Wilks 1976) by contrasting preference semantics with the simple verb-based requests of Riesbeck's (1975) MARGIE parser. It was argued there that account had to be taken of both the preferences of verbs (and nouns), and of the preferences cued from the preposi­ tions themselves.

Those preferences were variously called paraplates (Wilks 1975), preplates (Boguraev 1979) and they were, for each preposi­ tion sense, an erdered set of predication preferences restricted by action or noun type . (Wilks 1975) contains examples of erdered paraplate stacks and their functioning, but in what follows we shall stick to the preplate notation of (Huang 1984b ).

We have implemented in CASSEX (see below) a range of alternatives to Rule A : controlling both for "low" and "high" default; for examination of verb preferences first ( or more generally those of any entity which is a candidate for the root of the attach­ ment, as opposed to what is attached) and of what-is-attached first (i.e. prepositional phrases). We can also control for the application of a more redundant form of rule where we attach preferably on the conjunction of satisfactions of the preferences of the root and the attached (e.g. for such a rule, satisfaction would require both that the verb preferred a prepositional phrase of such a class, and that the prepositional phrase preferred a verb of such a class).

In the next section we describe the algorithm that best fits the data and alternates between the use of semantic information attached to verbs and nouns (i.e. the roots for attachments as in Rule A) and that of prepositions; it does this by seeking the best mutual fit between them, and without any fall back to default syn­ tactic rules like (i) and (ii).

5. The CASSEX Strategy

This strategy, implemented within Hua.ng's (1984a, 1984b) CASSEX program, correctly parses all of the example sentences in this paper. CASSEX, which is written in Prolog on the Essex GEC-63, uses a definite clause grammar (DCG) to recognize syn­ tactic constituents and Preference Semantics to provide their semantic interpretation.

For PP attachment CASSEX uses the case preferences of verbs, nouns and prepositions. The case information for verbs and nouns is encoded into their semantic formulas. The formula for one sense of the verb POSITION contains a location case :

sem(position1, ... , preps([prep(at,on,in,by), prep-obj(·pla), case(loc-static )])).

The formula for one sense of the noun TICKET has a direction case, as in "ticket to Paris" :

sem(ticketl, ... , preps([prep(to), prep-obj(·pla), case(direction)])).

The case information for prepositions is encoded into lists of pre­ plates, stored under the names of individual prepositions. Each preplate is comprised of four elements. Below is the Iist of pre­ plates for ON :

preplates(on, [move, instrument, thing, on1],

be, loc-static, ·pla, on2], strik, loc-dynamic, ·physob, on3], ·do-dynamic , loc-static, point, on4], ·ent, location, ·physob, on5], ·do-dynamic, time, event, on6]]).

The first element represents the preferred semantic class of the head noun or verb preceding the prepositional phrase to be attached; the second element is the case of the preposition; the third is the preferred semantic class of the head noun of the prepo­ sitional phrase.

In CASSEX, the strategy (Rule B) is contained within the prolog goal pp_ attachment which is called by the grammar after the subject, verb and object of a sentential clause has been recog­ nized. pp_attachment consists of seven clauses (see below) which are tried sequentially until one succeeds. There are three stages or phases to the strategy. The firststage (clauses 1, 2 and 3) attempts PP attachment using verb and noun case preferences, starting with the element immediately to the left of the PP and working left­ wards. The second phase (clauses 4 and 5) attempts PP attach­ ment using the case preferences of the preposition, starting with the main sentence verb and working rightwards. The third stage ( clauses 6 and 7) is a default : preferences of the preposition for some classes of action primitives are relaxed and the PP is attached to the main sentence verb.

pp_attachment(Verb_sense, Object, Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) --> % Clause 1 prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun), % Find PP. Get the preplates listed for the preposition; % identify the head noun of the PP. Rebuilt_Object). % Check the noun phrase immediately preceding the pp for % any case preferences. If its preferences are satisfied then % Object.

check_noun_cases(Object, Preplates, Noun_phrase, Head_noun, % attach the pp to the (Object) np, producing Rebuilt_ pp_attachment(Verb_sense, Object,Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) --> % Clause 2 prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun), check_verb_cases(Verb_sense, Preplates, Head_noun, Verb_Modifier). % Check the sense of the verb preceding the pp to see for % any case preferences. If its preferences are satisfied then % attach the pp to the verb as a Verb_Modifier. pp_attachment(Verb_sense, Object, Obj_Head_Noun, Object,[J) --> [] . % Clause 3. No pp attachment is made. The Verb-sense and % the Object of the sentential clause is returned unaltered % CASSEX will then try to attach the pp at the next sent­ % ence Ievel up, starting with the rightmost constituent, by % calling pp_attachment again. If no attachment is possible % at that Ievel, CASSEX tries attachment at the next 'Ievel % up. If no attachment is made then CASSEX remains at % that Ievel and tries clauses 4-7 of pp_attachment, one of % which must succeed. pp_attachment(Verb_sense, Object, Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) --> % Clause 4 prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun), verb_pp_match(Preplates, Noun_phrase, Head_noun, Verb_ sense, Verb_Modifier). % Try to attach the pp to the verb. pp_attachment(Verb_sense, Object, Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) --> % Clause 5 prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun), noun_pp_match(Preplates, Noun_phrase, Head_noun, Object, Rebuilt_Object). % Try to attach the pp to the (Object) noun phrase.

pp_attachment(Verb_sense, Object,Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) -->

% Clause 6

prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun),

{ relax_preplates(Preplates, PreplatesO)},

% Relax certain restrictions in the preplates

verb_pp_match(PreplatesO, Noun_phrase, Head_noun, Verb_ sense, Verb_Modifier).

• % Try to attach the pp to the verb.
• pp_attachment(Verb_sense, Object,Obj_Head_Noun, Rebuilt_ Object, Verb_Modifier) -- >

% Clause 7

prepositional_phrase(Prep, Preplates, Noun_phrase, Head_ noun),

{ relax_preplates(Preplates, PreplatesO)},

noun_pp_match(PreplatesO, Noun_phrase, Head_noun, Object, Rebuilt_Object).

• % Try to attach the pp to the noun phrase .

Below, by way of illustration, we show how our strategy correctly attaches PPs in four of the example sentences in this paper :

• r'\ (1) JOHN LOVED THE GIRL (IN THE PARK)
• ~ (2) JOHN STABBED THE GIRL (IN THE PARK)
• JOE BOUGHT THE BOOK THAT I HAD BEEN TRYING TO OBTAI,t.~.::~m~su_s_AN_... ____ _

(4) JOE BOUGHT THE BOOK THAT I LOVED (FOR SUSAN).

Whenever pp-attachment is :called, its first three arguments are always instantiated. In (1), for example, Verb_sense is instan­ tiated to LOVE; Object to THE GIRL, and Obj_Head __ Noun t.0 GIRL. The first clause of pp_attachment calls check_noun_cases (i.e. the noun is checked first) to see if GIRL has any case prefer­ ences. GIRL has none so check_noun_cases fails, failing clause 1. The second clause of pp_attachment is called which calls check_verb_cases to see if LOVE has any case preferences. LOVE has none so check_verb_cases fails, causing the second clause of pp_attachment to fail. The third clause of pp_attachment returns the v and np with the pp not attached to either. GASSEX tries to attach the pp at the next Ievel up, but the sentence has no higher Ievel so clause 3 of pp_attachment eventually fails. The fourth clause of pp_attachment calls verb_pp_match (during this, the second stage of the strategy, the verb is matched first). verb_pp_match matches LOVE against the preplates for IN but does not find a match so verb_pp_match fails and so does clause 4. Clause 5 calls noun_pp_match which matches GIRL against the preplates for IN. The preplate [·physob, location, ·pla, in3] matches so noun_pp_match succeeds, clause 5 succeeds, and the PP is attached to the np THE GIRL.

For (2), the strategy's first stage (clauses 1, 2 and 3) fails again, failing to find a match for either GIRL or STAB. In the second stage, verb_pp_match ( clause 4) finds a preplate ([·do_dynamic, loc_static, ·pla, in4]) that matches STAB (which belong to the ·do_dynamic verb group) to IN THE PARK, so the PP is attached to the v STAB.

For (3), pp_attachment is called while GASSEX is parsing the sentence's relative clause so it tries to attach the PP to that clause. The second clause of pp_attachment Iooks to see if · OBTAIN has any case preferences. Its formula includes a recipient case ([prep(for), prep-obj(·hum), case (recipient)]) so the PP is suc­ cessfully attached to OBTAIN.

For (4), pp_attachment is also called while GASSEXis pars­ ing the sentence's relative clause. Clause 2 of pp_attachment fails because LOVE does not have suitable case preferences. Clause 3 causes returns the pp unattached, along with the sentence Object THE BOOK THAT I LOVED. Processing continues one Ievel up, at sentence Ievel, and pp_attachment is called again. The second clause of pp_attachment Iooks to see if BUY has any case prefer­ ences. Like OBTAIN, the semantic formula for BUY includes a recipient case, so the pp is attached to BUY.

Apart from Rules A and B, we tried three other PP attach­ ment rules -- C, D and E -- and implemented them in CASSEX. The rules varied in their use of case information for PP attach­ ment. Rule A uses only verb and noun-based case information, as does Rule C. Rules D and E use only preposition-based informa­ tion. We also varied the order of application of information and the nature of the default, trying both "high" and "low." The five strategies are summarized below.

Earlier we gave reasons for rejecting an approach like Rule A i.e. it fails to provide the correct attachment for sentences like

or ~

JOHN SHOT THE GIRL (IN THE PARK).

Rule C gets these right but fails on

and THE WOMAN WANTED THE DR~N THE RACK)

because it gets the wrong default attachment. Rules D and E are also inadequate. Rule D gets wrong ~

and ~ THE WO MAN W ANTED THE DRESS (FOR HER DAUGHTER)

because Rule D defaults low ( correct attachment relies on the verb preferences of POSITION and WANT). Rule E gets wrong sen­ tences like

~ JOHN LOST THE TICKET (TO PARIS)

Only Rule B correctly attaches all the sentences.

8. Conclusions

We suggest that correct PP attachment is possible with only semantic information (ignoring, for the purposes of this paper, situations of pragmatic override and exceptional uses of world knowledge, of the Crain and Steedman type) and without syntactic rules, provided the system of preferences allows the interaction of not only verb-based but also noun and preposition-based prefer­ ence. CASSEX has explored a number of alternative arrangements of default and order, and we have presented a best-fit algorithm for the data, without needing syntactic rules or complex syntactico-semantic weighting.

7. References

• Boguraev, B.K. (1979) "Automatie Resolution of Linguistic Ambi­ guities." Technical Report No.ll, University of Cambridge Computer Laboratory, Cambridge.
• Crain, S. & Steedman, M. (1984) "On Not Being Led Up The Gar­ den Path : The Use of Context by the Psychological Parser." In D.R. Dowty, L.J . Karttunen & A.M. Zwicky (Eds.), Syn­ tactic Theory and How People Parse Sentences, Garn­ bridge University Press.
• Fass, D.C. & Wilks, Y.A. (1983) "Preference Semantics, lll­ Formedness and Metapher," American Journal of Com­ putational Linguistics, 9, pp. 178-187.
• Ford, M., Bresnan, J . & Kaplan, R. (1981) "A Competence-Based Theory of Syntactic Closure." In J. Bresnan (Ed.), The Mental Representation of Grammatieal Relations, Cambridge, MA : MIT Press.
• Frazier, L. & Fodor, J. (1979) "The Sausage Machine: A New Two-Stage Parsing Model." Cognition, 6, pp.191-325.
• Grice, H. P. (1975) "Logic & Conversation." In P . Cole & J. Mor­ gan (Eds.), Syntax and Semantics 3 : Speech Acts, Academic Press, pp. 41-58.
• Hirst, G. (1983) "Semantic Interpretation against Ambiguity." Technical Report CS-83-25, Dept. of Computer Science, Brown University.
• Hirst, G. (1984) "A Semantic Process for Syntactic Disambigua­ tion." Proe. of AAAI-84, Austin, Texas, pp. 148-152.
• Huang, X-M. (1984a) "The Generation of Chinese Sentences from the Semantic Representations of English Sentences." Proe. of International Conferenee on Machine Translation, Cranfield, England.
• Huang, X-M. (1984b) "A Computational Treatment of Gapping, Right Node Raising & Reduced Conjunction." Proe. of COLING-84, Stanford, CA., pp. 243-246.
• Riesbeck, C. (1975) "Conceptual Analysis." In R. C. Schank (Ed.), Coneeptual Information Proeessing, Amsterdam North Holland.
• Ritchie, G. (1978) Computational Grammar. Hassecks : ·Har­ vester.
• Shieber, S.M. (1983) "Sentence Disambiguation by a Shift-Reduced Parsing Technique." Proc. of IJCAI-83, Kahlsruhe, W. Germany, pp. 699-703.
• Shubert, L.K. (1984) "On Parsing Preferences." Proe. of COLING-84, Stanford, CA., pp. 247-250.

Wilks, Y.A. (1973) "Understanding without Proofs." Proc. of IJCAI-73, Stanford, CA.

• Wilks, Y.A. (1975) "A Preferential Pattern-Seeking Semantics for Natural Language lnference." Artifleial Intelligenee, 6, pp. 53-74.
• Wilks, Y.A. (1976) "Processing Oase." American Journal of Computational Linguistics, 56.
• Winograd, T. (1972) Understandins Natural Language. New Y ork : Ac adernie Press.