N e w A p p r o a c h e s to P a r s i n g C o n j u n c t i o n s U s i n g P r o l o g Sand,way Fong Robert C. Berwick Artificial hitelligence Laboratory M.I.T. 545 Technology Square C,'umbridge MA 02t39, U.S.A. Abstract Conjunctions are particularly difficult to parse in tra- ditional, phra.se-based gramniars. This paper shows h ow a different representation, not b.xsed on tree structures, markedly improves the parsing problem for conjunctions. It modifies the union of phra.se marker model proposed by GoodalI [19811, where conjllnction is considered as tile lin- earization of a three-dimensional union of a non-tree I),'med phrase marker representation. A PItOLOG grantm~tr for con- junctions using this new approach is given. It is far simpler and more transparent than a recent phr~e-b~qed extra- position parser conjunctions by Dahl and McCord [1984]. Unlike the Dahl and McCor, I or ATN SYSCONJ appr~ach, no special trail machinery i.~ needed for conjunction, be- yond that required for analyzing simple sentences. While oi contparable ¢tficiency, the new ~tpproach unifies under a single analysis a host of related constructions: respectively sentences, right node raising, or gapping. Another ,'ulvan- rage is that it is also completely reversible (without cuts), and therefore can be used to generate sentences. John and Mary went to tile pictures Ylimplc con s tituent coordhmtion Tile fox and tile hound lived in tile fox hole and kennel respectively CotJstit,wnt coordination "vith r.he 'resp~ctively' reading John and I like to program in Prolog and Hope Simple co nstitmvR co~rdinatiou but c,~, have a col- lective or n.sp,~'tively reading John likes but I hate bananas ~)tl-c,mstitf~ent coordin,~tion Bill designs cars and Jack aeroplanes Gapping with 'resp,~ctively' reading The fox. the honnd and the horse all went to market Multip le c,mjunets *John sang loudly and a carol Violatiofl of coordination of likes *Wire (lid Peter see and tile car? V/o/atio/i of roisrdJ)l=lte str¢/¢'trlz'e constr.~int *1 will catch Peter and John might the car Gapping, hut componcztt ~cnlenccs c .ntain unlike auxiliary verbs ?Tire president left before noon and at 2. Gorbachev Introduction The problem addressed in this paper ~s to construct ,~ gr;unmatical device for lumdling cooL dination in natural language th a t is well founded in lingui.~tic theory and yet computationally attractive. 'the linguistic theory, should be powerful enough to describe ,~ll of the l)henomenon in coordi:tation, hut also constrained enough to reject all u.'l- gr;unmatical examples without undue complications. It is difficult to ;tcldeve such ;t line h;dancc - cspcci,dly since the term grammatical itself is hil,hly subjccl.ive. S o m e exam- ples of the kinds of phenolr-enon th:tt must l)e h;mdh.d are sh.,'.wl hi fig. t '['he theory shouhl Mso be .~menable to computer hnpien:ellt~tion. For example, tilt represeuli~tion of the phrase, marker should be ,'onducive to Imth ¢le~u! process description antl efficient implementation of the associated operations as defined iu the linguistic theory. Fig 1: E x a m p l e S e n t en ce s T he goal of the computer implementation is to pro- d,ce a device that can both generate surface sentences given ;t phrase inarker representation and derive a phrase marker represcnt;Ltion given a surface sentences. Thc huplementa- lion should bc ~ efficient as possible whilst preserving the essential properties of the linguistic theory. W e will present an ir, ph:n,cut,'ttion which is transparent to the grammax and pcrliaps clemler & more nmdular than other systems such ,~ the int,:rpreter for the Modilh:r Structure C ra m- ,,,ar.~ (MSG.,) of l)alll & McCord [1983 I. "]'lie NISG systenl w il l be compared with ~ shnpliGed irnl)lenlenl.;~tion of tile proposed device. A table showin K tile execution thne of both systems for some sample sen- 118tences will be presented. Furthermore, the ,'ulvantages and disadvantages of our device will be discussed in relation to the MSG implementation. Finally we can show how the simplifled device can l)e extended to deal with the issues of extending the sys- tem to handle nmltiple conjuncts ~ d strengthening the constraints of the system. This representation of a phrase marker is equiva- lent to a proper subset of the more c o m m o n syaxtactic tree representation. This means that some trees m a y not be representable by an R P M and all R P M s m a y be re-cast as trees. (For exmnple, trees wit.h shared nodes representing overlapping constituents are not allowed.) An example of a valid RPM is given in fig. 3 :- The R P M Representation The phrase marker representation used by the theory described in the next section is essentially that of the Re- duced Phrase Marker (RP M) of L,'mnik & Kupin [1977]. A reduced phrase maxker c,'m be thought of im a set consist- " ing of monostrings ,'rod a termiual striltg satisfying certain predicates. Mor e formally, we haws (fig. 2) :- Sentence: Alice saw 13ill RPM representation: {S. Alice.saw.Bill. NP.saw.Bill. Alice.V.Bill. Alice.VP.Alice.saw.NP} Fig 3: Aa example of R P M representation Let E and N denote the set of terminals and non-terminals respectively. Let ~o,~, x E: (TI. U N ) ' . Let z, y, z E Z' . Let A be a single non-terminal. Let P be an arbitrary set. Then ~o is a monostrmg w.r.t. ~ & N if ~o E Z'.N.E'. Suppose~o = zAz and that ~ o, $ 6: P where P is a some set of strings. We can also define the following predicates :- y i s a * ~ o i n P i f x y z E P d o m i n a t e s ~b in P if ~b = zXy. X # 0 and x # A . W p r ec ed e s v) in P if 3y s.t. y isa* ~o in P. ~ b = z v X and X # z . Then :- P is an RPM if 3A,z s.t. A,z ~. P and V{~O,~0} C_ P then do mi na tes ~o in P or ~o do minates ~b in P or ~b p re ce d es ~ in P or ~,, p rec ede s ~b in P. Fig 2: Delinitioa of azl R P M 119 This RPM representation forms the basis of i, he linguistic theory described in the next section. The set representation ha.s some dcsir;d~M
View Full Document
Unlocking...