New Approaches to Parsing Conjunctions Using Prolog

Introduction

Thc problem addresscd in th is paper is to constrnct a grmnmatical devicc for harnlling roordination in natural languagc t.hat is weil foundctl in linguistic theory and yet compntationally attractive. Thc lingnistic thcory should he powcrful cnough to describc an of the phcnomenon in coordination, bnt. a lso conslraincd enough to reject all nn­ grammat.ical examples without undnc complic:t tions. It is dif!ictdt to achiei'C ~ u ch a fine balanc<'- cspccially since the term gr,111!1lla tica.l itsclf is highly subjectivc. Some exam­ plrs of Lhe kinds of phenomcnon thal must hc handlcd are shown in fig. 1

The theory should also be amenablc to computer implement.ation. For cxample, thc rcpresentation of the phrasc marker should be condncive to both clean process description aud cfficicnt implemcntation of the associatcd operations as defined in the lingnistic thcory.

The goal of the computer implementation is to pro­ dnce a dcvice that can both generate surface sentences given

The RPM Representation

The phrase marker representation used by the theory dcscribed in the next section is essentially that of the Re­ duced Phrase Marker {RPM) of Lasnik & Kupin [1977]. A reduccd phrase marker can bc thought of as a set consist­ ing of monostrings and a terminal string satisfying certain predicat.es. More formally, we have (fig. 2) :-

Let E and N dcnote thc set of terminals and non-terminals respectively.

Let cp,,P,x E (EUN)*.

Let x,y,z E E* .

Let A be a single non-terminal.

Let P be an arbitrary set .

Then cp is a monostring w.r.t. E & N if cp E E*.N.E*.

Suppose cp = xAz and that cp, 1/J E P where P is a some sct of strings. Wc can also definc the following prcdicates :-

Y isa* cp in P if xyz E P

cp dominates 1/J in P if 1/J = xxy. X # 0 and X# A.

cp precedes ·tj; in P if :Jy s. t. y isa* cp in P . ..P = xyx and x i- z.

Then :-

P is an RPM if :JA,z s.t. A,z E P and V{,P,cp} ~ P then

'lj1 dominates '(! in P or cp dominates 1/J in P or ~· pn~cedes cp in P or cp prccedes 1p in P.

.f'ig 2: Definition o{ an RPM

This rcprescntation of a phrasc marker is cqniva­ lent to a proper suhsct of the morc common syntactic tree reprcscntation. This meaus that some trces may not be rcpresentablc by an RPM and all llPMs may be rc-cast as trccs. (For example, trees with sJJared nodes reprcsenting ovcrlapping constitucnts are not allowed.) An example of a valid RPM is given in fig. 3 :-

Scntence: Alice saw Bill

RPM rcpresentation .

{S. Alice .saw.Bill. NP.saw.Bill. Alice.V.Bill. Alice . VP.Aiice.saw. NP}

.F'ig 3: An cxample o[ RPM representation

This RPM rcprcsentation forms thc basis of the linguistic theory described in thc ncxt section. The set represcntation has some desirable advantages over a trce rcprcscHtation in tcnns of both simplicity of description and implemcntation of the operations.

Goodall's Theory of Coordination

Goodall's idea in his draft t.hesis [Goodall??] was to extcnd t.hc definition of Lasnik and Kupin's llPM to covcr coordination. The main idea bchind this thcory is to ap­ ply thc notion that coordüwtion results from tlJC union of pllrase warkers to the rcdnced phrase markcr. Sincc RPMs are scts, this has the dcsirable property that the union of llPMs wonld just be thc familiar set union operat ion. For a computcr implementation, thc sct union operation can be realizcd irwxpensively. In contras t, thc corrcsponding op­ erat ion for trees would nccessitatc a much less simple and eflicicnt nnion Operation than set union.

Howevcr, the original dcfinition of the BPM die! not cnvisa~c thc nnion operat.ion 1\eCC'lsary for coonlina­ tion. Thc RPM w<t:> usccl to rcprcscnl. 2-dimcnsion.d struc­ turc only. Hut undcr sct unimr thc IU'M hccontcs a rcp­ n·s·!tttati orr of :l-dimcrrsional st.ruct. nre. Thc adrni ,;,; ihiiit.y prcd i cat~~ deminatc-s a11d preced .·s dclitH!d ''Ii a .·:d of monostrings with a singlc non-terminal string wcrc inadc­ quatc to clcscribc 3-dimensional structure.

Basically, Goodall's original idea was to cxtend the dominates and precedes prcdicatcs to handle llPMs un­ clcr thc set union opcration. This rcsultcd in thc rclations e-dominates and e-precedes as shown in fig. 1 :-

Assuming thc dcfinitions of fig . 2 and in addition Iet w, !1, e E (~ u N)' and q, r, s, t, V E ~·. then

cp e-dominates 1/J in P if cp dominates ,P' in P. xxw = ,P'. 8y!1 = 1/J and x = y in P.

cp e-precedes 1/J in P if y isa* cp in P. v isa* 1/J in P. qyr = svt in P. y i- qyr and v i- svt

wherc the relation =:: (terminal equivalerrceJ is defincd as :-

x := y in P if xxw E P and XYW E P

Figure 4: Extcnded defirritions

This extemlcd definition, in particular - the notion of equivalencc forms the basis of thc compu tational device descrihed in the next section. Howcvcr since thc size of the RPM may be !arge, a dircct implemcntation of thc above definition of equivalence is not computationally feasible. In t.hc actnal systcm, au optimizcd but eqnivalcnt alternative definition is uscd .

Although thcse dcfinitions sufficc for most examples of coonlination, it is not sufficicntly constraincd cnough to rejcct some nngranunatical examples. For cxample, fig. 5 gives the RPM rcprcsentation of "* John sang loudly and a <.arol" in terms of the union of the RPMs for the two conslituent sentenccs :-

(\VIII'// 111<'.'<' I wo Rl'lvfs ill'!' Jlll'l'J.:!'d '<JIIII' of 1111' dt'llii'Jll.~ o[ f/1<' st·l rlo twl sitl isfy La.<uik & J\11piu ·~ origiual rldi­ u i I io11 - t IH'-''' pairs an· :-}

{ John .sang.loudly. John .silng.a.carol} {John.V.Ioudly. John .V.a.carol} {NP.sang .loudly. NP.sang .a.carol}

(None o[ tllt' ; t/JOVI ' p;tirs s<ttidy tll!' c-dominates prcdi­ c;tft· - IJIIt IIH'.Y ;tl/ s;tlisfy e-prcccdes itmll.tcncl' thc ~I'JJ­ teun· i~ itiTI'Jlf:erl <ls illl RPM.}

Fig.5: An examplc of union of RPMs

'l'he abovc cxamplc indicates that thc extended RPM dcfinition of Goodall allows some ungrammatical sentcnces to slip throu~h . Al though thc device prcscnted in the next sect.ion t!oesn 't make direct use of the extendcd dcfinitions, the notion of cquivalence is central to the implcmentation. The basic system describcd in the next section does have this deficicncy but a less simplistic version described later is more constraincd - at the cost of some computational elliciency.

Linearization and Equivalence

Although a theory of coordination has been describcd in tl:c prcvions sections - in order for the theory to be put into practice, there remain two important questions to be c:;,swered :-

• How to produce surfacc strings from a set of sentences to bc conjoined?
• How to prot!uce a set of simple sentences (i.e. sen­ tences witlrout conjunctions) from a conjoined surface string?

This scction will show that the processes of lin­ carizatioiJ and frucling equivalcJJces proviele an answer to boLh quc~tions. For simplicit.y in the follüwing discussion, wc assumc tlw.t the number of simple sentences to bc con­ joincd is two only.

Thc proc('Sscs of lineari:wtion and finding equiva­ lcnus for gcJ icrat.ion can bc dcfincd as :- Given a set of sentcnces and a set of candidatcs which represcnt thc sct of conjoinablc pairs for those sentences, lincarization will output one or more surfacc strings according to a fixcd proce­ dure.

Given a set of scntences. /inding equivalenccs will produce a set of conjoinablc pairs aceortfing to the dcfinition of cquivalcnce of thc linguistic theory.

For generation the second process (Jinding equiva­ lences) is called first to generate a set of candidates which is thcn nsed in the first process (lincarization) to generate the surface strings. For parsing, the definitions still hold - but the processes arc applied in reverse order.

To illustratc the procedure for linearization, con­ sidcr thc following example of a set of simple scntences (fig. 6) :-

{ John likcd ice-crcam. Mary liked chocolate} set of simple sentences {{John. Mary}. {ice-cream. chocolate}} set of conjoinable pairs

Consider the plan view of the 3-dimensional rcpre­ sentation of the union of the two simple sentences shown in fig. 7 :-

Mary < ·ce-cream

John > liked

Pig 7: Exrunple o( 3-dimensional structure

Thc procedure of fi:warization wonld take thc fol­ lowing path shown by thc arrows in fi g. 8 :- Following the path shown we obtain the surface string "John and Mary liked ice-crcam and chocolate".

Thc set of conjoinable pairs is produccd by the pro­ cess of Jinding equivalences. The dcfinition of equivalcnce as given in thc dcscription of thc extended RPM requires thc generation of the comhined RPM of the constituent sen­ tences. However it can be shown [Fong??] by considering the constraints imposcd by the dcfinitions of equivalence and linearization, that the same sct of equivalent terminal strings can be produced just by using the terminal strings of the RPM alone. Thcrc are considcrahle savings of compu­ tational resources in not having to compare every element of the set with every other element to generate all possible equivalent strings - which would take O(n 2 ) time - where n is the cardinality of the set . The corresponding term for the modified definition (given in the next section) is 0(1).

The Implementation in Prolog

This scction describes a runnable specification written in Prolog. The spccification descrihcd also forms the basis for comparison with the MSG intcrpreter of D<thl and Me­ Cord. Thc syutax of thc clauscs to be prcs~ntcd is similar to the Dcc-10 Prolog [Bowen et al.1982] version. The main differcnces are :-

• The symbols ":-" ;md "," havc been replaccd by the more meaningful rcservcd words "if' and "and" re­ spccli vely.
• Tlw ~ymbol "." is nsed a~ t h~ Iist. construclor and "nil" is uscd to rcpresent t hc tlnply Iist.
• An <tn ··xamplc , a Prolog cl ;wse may havt· t.he form :-
• a(X Y ... Z.) if b(U V ... W) and c(R S ... T)

wherc a,b & c are prcdicate names and R,S , ... ,z may represent variables, constants or terms. (Variables are distinguished by capitalization of the first charac­ ter in the variable name.} The intended logical read­ ing of the clause is :-

"a" holds j[ "b" and "c" both hold for consistent bindings of the arguments X,Y, ... ,z, U,Y, .. . ,W, R,S, ... ,T

• Comments ( shown in italics) may be interspersed be­ tween thc arguments in a clause.

Parse and Generate

In the previous section the processes of Jinearization and Jindillg equivalences are described as the two components necessary for parsing and gencrating conjoincd sen­ tences . We will show how these proccsses can be combined to produce a parser and a generator. The device uscd for comparison with Dahl & McCord schcme is a simplified version of the device prescntcd in this scction.

First, dilference lists are used to represent strings in the following scctions. We can now introduce two predi­ cates linearize and equivalcntpairs which corrcspond to the processcs of linearization and Jinding equivalcnce!' re­ spectively ( fig. 9) :-

linearize( pairs 51 E1 and 52 E2 candidates Set gives Sentence)

Linearize lwlds when a pair of diffcrencc lists ({51. E1} & {52. E2}) a11d a set o[ candidatcs (Set) arc consistcut witl1 thc sl.ring (Scntence) as dcfined by tl~e proccdure given in tl1e prcvi­ ous scction .

cquivalentpairs( X V from 51 52)

:Equivnlentpnirs holds wheu a substring X of 51 is cquiva /c:1t to a suhslring V of52 accon fin g to Uw rlcfinition oJ' cqniv;./cr:ce in tl1c liHgnisUc f.lwory.

Fig 9: Predicatcs linearize & equivalentpairs

Additionally, Iet the mct.a-logical prcdicatc setof as in "sctof(Eiement Go <II Set)" hold whcn Set is composed of clcmcnts of thc form Element and that Set contains all instanccs of Element that satisfy the goal Goal. The pred­ icates generate can now be defincd in terms of thcse two processcs as follows (fig. 10) :-

generate(Sentence from 51 52)

if setof(X. V .nil in equivalcntpairs(X Y

from 51 52) is Set)

and linearize( pairs 51 nil and 52 nil candidates Set gives Sentence)

parse( Scntence giving 51 E1) if linearize(pairs 51 E1 and 52 E2 candidates SubSet gives Scntence)

and setof(X. Y .nil in equivalentpairs(X Y /rom 51 52) is Set)

Fig 10: Prolog dcfinition for generate & parse

The dcfinitions for parsing and generating arc al­ most logically eqnivalcnt. Howcvcr thc };nb-goals for pars­ ing are in reverse order to the sub-goals for gcncrating - since the Prolog intcrpretcr wm.ld attcmpt to solvc the sub-goals in a left to right manner. Furthermore, the sub­ set relation rather than set equality is used in the definition for parsing. We can interpret the two definitions as follows {fig. 11) :- Generate holds when Sentence is the con­ joined sentence resulting from the linearization of tl1e pair of difference lists (51. nil) and (52. nil) using as candidate pairs for conjoining, the set of non-redundant pairs of equivalent termi­ nal strings (Set).

Parse holds when Sentence is the conjoined sentence resulting from the linearization of the pair of difference lists (51. E1) and (52. E2) provided that the set of candidate pairs for con­ joining (Subset) is a subset of the set of pairs of equivalent terminal strings (Set).

Fig 11: Logical reading for generate & parse

The subset relation is needed for the above defini­ ~ion of parsing because it can be shown [Fong??J that the process of Jinearization is more constrained (in terms of the penuissibJe conjoinahJe pairs) than the process of lindit1g equiwtlences.

Linearize

We can also fashion a logic specification for t.he process of linearization in the same manner. In this section we will dcscribe the cascs corrcsponding to each Prolog clause neccssary in thc spccification of lincarization. However, for simplicity the actual Prolog codc is not shown here.

In thc following discussion wc assumc that the tem­ plate for prcdicatc linearize has thc form "linearize( pairs 51 E1 and 52 E2 .:andidates Set gives Sentence)" shown previously in .fig. 9. There are three indcpcndent cases to considcr during lincarization :-

1. The Base Case.

If the two diffcrcnce lists ({51 . E1} & {S2. E2}) are both empty ~hen the conjoined string {Sentence) is also cmpty. This simply states that if two empty strings are conjoined then the resnlt is also an empty string.

2. Jdentical Leading Substrings.

The sccond case Jccurs when the two (non-empty) dilfc rencc lists have identicallcading non-empty snb­ strings. Thcn the conjoined string is idcntical to the concatc1~. ation ofthat lcading substring with the lin­ carization of thc TI'St of the two differcnce lists. For example, considcr the linearization of the iwo frag­ mcn!.s "likcs Mary" anrl ''likes Jill" as slwwn in fig. 12

{likcs Mary. likes Jill} which can be linearized a., :- {likes X} where X is the linearization of strings {Mary, Jill}

3. Conjoining.

The last case occurs whei, the two pairs of (non­ empty) difference lists have no common leading sub­ string. Here, the conjoined string will be the con­ catenation of the conjunction of onc of the pairs from the candidate set, with the conjoined string rcsulting from thc linearization of the two strings with their re­ spectivc candidatc substrings deleted. For exa.mple, consider thc linca.rization of the two scntences "John likes Mary" and ''Bill likes Jill'' as shown in fi.g. 13 :-

{ John likes Mary. Bill likes Jill} Given that the uler:tcd candidate pair is {John, Bill}, the conjoined sentence would be :- {John and Bill X} where X

is the linearization of strings {likes Mary. likes Jill}

Fig.l .'J: J<Jxmnple oi conjoiuing substrings

Therc arc somc implcmcntation detaib ihat are dif­ ferent for parsing to generat.ing. IIowever thc thrce cases arc the same for both.

We can illustrate t.he abovc defi ni t ion by showing what. linearizai.ions t.he system would producc for an ex­ ampJc scntcncc. Consider tlw sentcnce "John and Bill liked M<1ry" (fig. H) :-

{ John and Bill liked Mury} would produce tiJC strings:- {John and Bill likcd Mary, John and Bill liked Mary} with candidate set {} { John liked Mary, Bill liked Mary} with candidate set {(John, Bill)} { John Mary. Bill liked Mary} with candidate set {(John. Bill liked)} {John. Billliked Mary} with candidate set {(John, Bill liked Mary)}

All of the strings are then passcd to the predicate findequivalences which should pick out the second pair of strings as the only grammatically correct linearization.

Finding Equivalences

Goodall's definition of equivalence was that two termi­ nal strings were said to be equivalcnt if they had the same left and right. contexts. Furthermore wc had previously as­ serted that the equivalcnt pairs could be produced without scarching the whole RPM. For examplc consider thc cquiv­ alcnt terminal strings in thc two sentences "Alice saw Bill" and "Mary saw Bill" (fig. 15) :-

{ Alice saw Bill. Mary saw Bill} would produrc tlw cquivalent pa.irs :- {Alice saw Bill. Mary saw Bill} { Alice. Mary} { Alice saw. Mary saw}

We also make the rollowing rcstrictions Oll Goodall's ddinition :-

• If there exists two terminal st.rings X & Y such that X=xxO & Y= xyO, then x & 0 should bc thc strongest possiblc left & right contcxts respectivcly - provided x & y arc both nonempty. In thc above example, x= nil and 0= "saw Bill", so the first and the third pairs produced are redundant.

In general, a pair of tcrininal strings are redundant if they have the form (uv, uw) or (uv, xv), in which case - they may be replaced by the pairs ( v, w) and ( u, x) respectively.

• In Goodall's definition any two terminal strings them­ selves are also a pair of equivalent terminal strings ( wl!en x & 0 are botl! null). We exclude this case as it produces simple string concatenation of scntences.

The above restrictions imply that in fig: 15 the only remaining equivalent pair ( {Aiice. Mary} )is the correct one for this example.

However, before finding equivalent pairs for two simple sentences, thc process of finding equivalences must check that the two sentences are actually grammatical. We assume that a recognizer jparser ( e.g. a predicate parse(S E)) already exists for detcrmining the grammaticality of simple sentences. Sincc the process only requires a yes/no answer to grammaticality, any parsing or recognition sys­ tem for simple sentences can be used.

We can now specify a predicate findcandidateslX Y

51 52) that holds whcn {X. Y} is an equivalent pair frorn the two grammatical simple sentences {51. 52} as follows (fig. 16) :-

findcandidates(X and Y in 51 and 52) if parsc(5 1 nil) and parse(52 nil) and equiv(X Y 51 52) whcrc equiv is rldincd as :- equiv(X Y X1 Y1) if appcnd~(Chi X Omega Xl) and tcrminals(X) and appcnd3{Chi Y Omega Y1) and tcrminals(Y)

IV!Jere ,1ppel/ll3(Ll L2 L.3 L'l) lwlri~ w/J('J.I L4 j,; <'<Jilill tu t/ii.· COIJCiil<'lliil.iou of Ll,L2 & [,3. trTIIIillal"(X} lwld" IVhcn X i:; Cl. /i:;l of terminal symbols on/y

Thcn thc predicate findequivalences is simply de­ fincd as (fig. 17) :-

findcquivalences(X and Y in 51 and 52) if findcandidates(X and Y in 51 and 52) and not redundant(X Y)

wiJere redundant implcmcnts t.IJe two rcstrictiuns dcscribcd above

Fig.l7: Logic definition of Ji'indcquivalences

A Note on SYSCONJ

It is worthwlnlc to comparc the phrase marker approach to thc ATN-bascd SYSCON.J mcchanism. Like SYSCONJ, our analysis is extragrammatical: we do not t;unpcr with the basic grammar, bnt add a new component that hand!P-s conjnuction. Unlikc SYSCONJ, our approach is hascd on a prccise drfinition of "equivalcnt phrases" tl1at attcmpts to uuify under one analysis many different. typcs of coordina­ tion phcnomena. SYSCONJ rclicd on a rather wmplicated, int.crrnpt-driven mcthod that. rcstarted s.~nt.encc analysis in gomc previonsly rccordcd machine configurat.ion, but with thc inpnt scqncnce following thc conjnnction. This e<tp­ t.urcs part of thc "multiple planes" analysis ot' the phrasc markcr appn><~.ch, but withont a precisc not.ion of equiva­ lent phrascs. l'crhaps as a resnlt, SYSCON.J hanrllcd only ordi11ary conjunction, and not rc6pectively or gappin;: re:ul­ ing~. In our ;Jppr'l<tch, a ~ :111pl e changc to t.hc J;ncari~at.ion proc('ss a llows 11 s tn handl e [(.tpp in ,;.

Comparison with MSGs

Thc following tablc (fig. 18) gives the execution times in milliscconds for the parsing of some samplc sentences mostly taken from Dahl & McCord [1983]. Both systems wcrc execuled 11sing Dec-20 Prolog. The times shown for the MSG intcrprctcr is based on the time taken to parse and build the syntactic tree only- the time for the subsequent transformations was not included.

From the timings we can conclnde that the pro­ poscd device is comparable to the MSG system in terms of computational efficiency. Ilowcver, thcrc are some othcr ad vantages such as :-

• Transparcncy of thc grammar - There is no need for phrasal rnles such a.s "S -> S and S". The dcvicc also allows non-pltrasal conjunction.
• Since no special grammar or partindar phra~e markcr rcprcsentat.ion i3 reqnircd, any parser can be uscd - the device only requircs a.Jl accept/reject answer.
• The specification is not biased with rcspcct to pars­ ing or gcncration. Thc implementation is reversible allowing it to generate any sentencc it can parse and vice versa.
• Modularit.y of the device. Thc grammaticality of sen­ tences with conjunction is determ;ncd by the defini­ tion of eqnivalence. For instance, if needcd we can filter the equiva!ent tcrminals using semantics.

Extensions to the Basic Device

The dcvice described in the previous section is a sim­ plificd version for rough comparison with the MSG inter­ pretcr. However, the system can easily be generalized to handle multiple conjuncts. The only additional phase re­ quired is to generate templates for multiple readings. Also, gapping can bc handlcd just by adding clauses to the defi­ nition of linearize- which allows a different path from that of fig. 8 to be taken.

The simplified device permits some examples of un­ grammatical sentences to be parsed as if correct (fig. 5) . The modularity of the system allows us to constrain thc definition of equivalence still further. The extended defini­ tions in Goodall's draft theory were not included in his the­ sis [Goodall84] prcsumably because it was not constrained enough . Howevcr in his thesis he proposes another defi­ nition of granunaticality using RPMs. This dcfinition can be used to const.rain equivalence still further in our system at a loss of some efficiency and generality. For example, the rcquircd additional predicatc will need to make explicit use of the combined RPM. Thereforc, a parser will need to produce a RPM rcpresentation as its phrase marker.

Acknow ledgements

This work describes research done at the Artificial Intel· ligencc Labaratory of thc Massachusetts Institute of Tech­ nology. Support for the Laboratory's artificial intclligence research has bcen provided in part by the Advanced Re­ search Projccts Agency of the Department of Dcfense un­ dcr Office of Naval Research contract N00014-80-C-0505. Thc first author is also funded by a schalarship from the Kcnncdy Memorial Trust.