Parsing TAGs with Prolog

Par s ing TAGs with Prolog Victor Jesus Dfaz Madrigal Miguel Toro Bo ni ll a Dpt o. Lenguajes y Sistemas lnformaticos Facultad de Informatica y Estadistica Universidad de Sevilla Avd . Reina Mercedes s/n -41012SEVILLA E-mail: [email protected] Abst r act Among fo rm alisms for the computati on of syntactic description of natural language sentences, Tr ee Adjoining Grammars (TAG) play a major rol e. Several classical Co ntext Ft -ee Grammars (CFGs) parsers have been redefined for T AGs , but it is not fr eq uent to find in the liter at ure referenc es to parsing TAGs from a logic programming pojnt of view. In this paper, we will concentrate on this direction, present ing a pur e top-down left-to-rigth recognizer algorithm for TAG, using P roJog, that reduces the problems found in the translation of Lang's axiomatization. Actually, th e algorithm is a parser that, given a grammatical i npu t, produc es th e parse forest using a compact represen ta tion of ev ery parse tree. Al so, a rule represeiltation of TAG's elementary trees is intr od uced in order to write grammars that can be co mpiled directly into Prolog predicates in a sinlllar way that traditionally Definite Clause Grammars (DCGs) does respect to CPGs. Key w ords : Natural Language Parsing, TAG, DCC. 1 Int ro du c tion In the literature, the grammatical formalism Tree Adjoining Grammars (TAGs) arc propagated to be adequate for nat ural language description. The class of TAGs was fir st introduced in [JLT75]; since then, formal and computational properties of this class have been extensively investigated, and the linguistic relevance of TAGs h as been discussed in the literature as we l l. A T AG grammar is a tre e generating formalism rather than a st ring generating system like traditional Chomky's grammars. It is defined by a fini te set of trees co mposed by means of the operation of tr ee adjunction. With respect to Chomsky's hierar chy, TAGs are more powe rful than Context Free Grammars (CFGs) b ut are a st ri ct subset of Context Sensitive Grammars (CSGs). Several general classical pa rsers for CFGs (CKY [Har90], Early [ScJ88]) ha ve been adapted to TAGs, but the excess of expresiveness of TAGs vs. C FGs results in wo rst time complexity. F or mal y, a TAG grammar G is a 5-t uple (v r, VNr, S, J, A) wh e re V.r, VNr are finite sets of term inal and non -ter minal symbols, S E VNr is the axiom symbol, and I and A are finite sets of elementary (Vr U V,vr )-valued trees. Trees in I and A are called initial and a tLxili ary trees resp ect ively and meet the fo ll owing specifications (see figure 1): Internal (uonleaf) nodes in elementary trees are labeled with non terminal symbols. An initial tree has a r oot labeled by S and leaf nodes label ed by symbols in Vr . An auxiliary tr ee 359 S X D6 Figure 1: Elementary Trees. has leaf nod es labeled by symbols in Vr with the addition of one node, called the foo t node, having the same nonterminal label as the root node. The path from the root nod e to the f oot node of an auxiliary tree is called the spine of the auxilary tree. We say t ha t /3 E A is a X-type auxiliary tree, when the label of his root node is the category X . Th e main operation is th e adjunction (see figure 2) that composes an auxiliary tree /3 with a tre e a to produce another tr ee -y. Let o: be a tree with a node labe ll ed X and let /3 be an auxiliary tree with the root labeled with the same symbol X. (Note, that the foot node of /3 is X too, by definition). The tree 1 is co n st ru ct ed as follows. The tre e t dominated by X in a is excised, /3 is inserted at the position of node X in a, and then the tr ee t is attac hed to the foo t node of /3. We say th at 'Y is a derived tree of a. Figure 2: Ad jun ction operation. In a TAG, a derivati on is the process of recursive c:ompos ition of eleme ntar y trees using the adjunction operation. Si11ce ad jun ctions at different nodes can be performed in any order, we can adjoin der ive d tr ees into der ive d trees without affecting our arguments. In TAGs, unlike CFGs. the derived and parse tr ee of a grammatical input are di ff erent in gen er al. The yield Y('y) of a ele mentary (or derived}-tree 1 is the string of symbols composed with the leaves of the tr ee . The set of all initial trees modified by an arbitrary number of adjoinings, T(G), is ca lled the tr ee set of a TAG G. The language of a TAG. L(G), is defined as th e set co ntaining all l ea f strings of trees in T( G). One impor tant characteristic of TAGs is lexicalizati on [JoS92]. Briefl y, this means t hat every grammar struct ure (i. e. elementary tre e), is anchored wit h a le xi ca l item. In 360 general, thi s pr operty is n ot fill for CFGs grammars. Lexi ca li zation is a good computational property because it ca n be proved that reduces the complexi ty of parsers. On th e o th er hand , le xicalization is a we ll li nguistic mo tivated pr operty. 2 Lang's axiomatization The standard axiomatization of CFGs-rules, denomi na ted De fin ite Cl auses Grammars DCGs, consists of associating each CFG-rule with a definite clause where every categorial sy mbol is aumengted with two arguments t hat repres ent po int s of interest over th e input string. It is well known tha t Prolog programs obtained from the DCG trans la - tion, implement top-down left-to-right r ec ognizers or parsers. ln a similar way as C FG s, [Sch 9 0, Lan9 0], TAGs can be axio ma tized wi th definite clauses. N ow , each eleme ntar y tr ee is asoci at ed with a definite clause and th e set of definite clauses can be also interpreted in a top-down fa o; hion. L et w = w 1, • •• , W n be th e input st ring to parse and G = (Vr , VNr, S,J, A) a T AG grammar. In Lang's axiomatizati on fo ur indices are required for eve ry categorial sy mb ol in th e TAG's elementary tr ees (inst ea d of two for CFGs). Th e fo ur positions correspond to th e boundaries of the strin gs to th e left and right of a fo ot node of an auxiliary tre e. Th e pr edicate category(X.J, J, I< , L) axiomatizes the fact th at an auxilia ry tree s pannin g th e su bst rings w 1 .. . w; and WK . .. w1.. , can be adjoined at a n ode lab eled by X. Initial tr ees spa n a contiguous w 1 . •• w; and auxili ary tre es span two su bst rings WJ ••• W; and WK ... WL· Th e pr edic at e term,nal(A, I, J) axiomatizes th e fact t ha t a te rminal symbol A sp ans th e subs tr ing fr om position I to J. S upp ose the elem et ary tr ees of TAG g rammar in figure 3, s s {3 A e e s e Figure 3: TAG Grammar . th e Pr olog pr ogram resulting of Lang's translation, where aO an d bO are names th at ide ntir y elementary trees a and {:J, will be: i ni ti al(aO,s,I , L) :- category(A,s,l,J,K,L) , terminal(e,J,K ) . aux il1 ary (b 0, s,l ,J,K,L) category ( A,s,l,N,P,L ) , terminal ( e,N,P ) , category ( A,s,P,J,K,Q ) , terminal ( e,Q, L) . 361 termi n al(T,I,J) :- ... I• Rec o gnize terminal T •/ category(_,I,I,L,L) . I• No adjunction •I catego r y(C,I,J,K,L ) :- I• Adjunction over auxiliary tree A •I auxiliary(A,C,I,J,K,L) . This represe ntat ion has several oper ational problems with respect to top-down parsing: • As in DCGs, this algorithm l oo ps on left recurs iv e rules. Thi s problem is acuter becau se of the duplication of predicates of the foot and root nodes in auxiliary trees. A twostep parsing strategy enables us to define a top-do wn interpretation of a lexicalized TAGs which will halt in all cases. • If an auxiliary tree derives the striug w1ww2 where w is the deriva tion of its foot node , the actual derivation order is w 1, w 2, w. Therefore, the direction of parsing is not left-to-right and it implies that each internal category must predict in advan ce a segment w 2 of the inpu t. In general, this way of working could be inappropiate because the pr ediction of w 2 does not have into account its precedence sequence w. • The in te rpreta tion of the f our boundaries arguments int o actual lexemes by mean s of difference lists, as in DCGs, is n ot direct. Therefore, it is ne cesary to preprocess the input string to compute the relative positions of input lexemes. 3 An a lte rna tiv e re pre se nta t ion We will present a new representation of TAGs that tries to reduce the problems presented above. Fir st of all, we will describe an alternative notation f or trees that uses a wordbased repr ese ntation instead of the traditional graphical repr ese ntat ion. The notation is as follows: 1. a stands for a E Vr 2. X(ta ... tn ) stands for th e elementary tree having root X E v,...T and direct subtrees t 1, ••• , tn . Wh en X has not children we will use the n otat i on X in stead of X (). For technical purposes, we wil l expr ess the word represent ation of X(t 1 ... tn) in a tr ivially equiva le nt form Xt.t 1 • •• tnXn. In ot h er words, a category symbol X is split into two new non terminal symbols, Xt. an d Xn, that will divide the left and right side co ntext of the symbol. The flat representation of a, in figure 3, will be S 1 e So and respectivelly 81 e S, So e So for {). Thi s new n otation has the minimal effeet of duplicate the number of catcgo rial symbols in a TAG grammar G. Size's grammar , IGI, is now in the order of 2IGJ. The representation of au auxiliary tr ee will be of the form: XL Zt Xi X'R z 2 X R where Z 1 and Z2 are sequences of symbols, being X_ and x· the root and fo ot symbols. If we observe carefull y, we can establish that Z 1 Xi is just the left co ntextual tree, / h, dominated by the ro ot in {) with respect to his f oot node. Similarly the right co ntext , /3n, ,..,.ill be X it Z2. The adju nction ope ration can also be divided in two sides with res pect to th e spine of an auxil ary tree. Supose that (3 is an X-ty pe auxiliary tree with Y( {J) = w1 Xw 2 being 362 w~o w2 E v.;. L et cr be an init ia l tr ee t hat co nta ins a ca tegory X wi th Y(a ) = r 1wr·2, where r 1, w, r 2 E Vi and w is the string tha t spans the category X. When we adjun ct fJ in a at X , producing "/, we have Y('Y) = r1w1 ww2 r 2. We c an see that w1 (resp. w 2) is the string that spans the left (resp. right) contextual tree dominated by X in {3. Both strings w 1, w 2 can be characterized with only two points of interest, i.e., we can r.edu ce the positions associat ed to categorial symbols to two as DOGs does. Briefl y, the trees abov e, can be represen ted using fiat n ota tion as follow s: fJ = XL Y1 Xi, XR_ Y2 X R where zl, z, z2 , }')' y2 are sequences of symbols (just the sequence of symbols in the fiat represen ta tion). With this considerations, the n ext thr ee OFG-based rul es ca n be st ated to translate the elementary trees: x~. +- Yt x;, rule for fJL XR +- XR. Y2 rule for f3R where R is a new non-terminal symbol acting as the new axiom symbol. The fiat representation of {3 is sp lit into t wo rules representing left and right contextual sides. As the adjunction operation at a root and foot node of an auxiliary tree are eq uivalent, we ca n eliminate the reference associated to its root symbol in the rules. When adjunction of {3 takes place in a, following the same considerations that we established abov e, we will have x~. -t ' w1, Z -t• wand XR -tk w 2• Consider a rule with a right hand side of the form XL Z Xu where X 1 ,, XR are the left and right symbol of the category X , and Z is a sequence of sy mbols n ot co ntaining the symbol X R· Every production appl ied over the symbols dominated by XL must be applied to its r es pective symbol dominated by X R in order to complete the ad junct ion operation. In other word s, the adjunction operation looks like a mirror-sustitution oper atio n between left and cigbt p arts of a same category. Operationall y, we can use an adjun ct argument over c at egorial symbols to control this restriction. The adjunction argument can also be used to produce a compact representation of the parse tree. Given an element ar y tree -y , we will represent it s ad ju ction argumen t. by means of a sequen ce based on its fiat representation. Suppose th at S = {X I~. , X2L, . .. , X NL] is the ordered subsequence respe ct to the flat representation of 'Y containing only the left side categorial symbols in 'Y· When constructing S for an auxiliary trees we will not co nsider the left side symbol of the auxiliary tre e's root. If adjun ct ion of an auxiliary tree ,8, named b 0, is performed at node X Li of 'Y wi th 1 ~ i :::; n, the symbol XLi is sub stit uted with [b 0, S0] where So will be the adjunction argume nt of /3. When no adjunction is applied to XL, the symbol XL; in S is substituted wi th []. Adjunct argument has two functions depen di ng on thP context wh ere it takes pla ce: in le ft t:untext pl ays a productor role meanwhile in right con text plays a consumer role. This new axio ma tization of TAGs p erm its us to translate elementary trees into defi ni te clauses with the presence in every categorial symbol of only two (boundaries) arguments over lexem es and one additional arg um e nt to control the sequence of adjunctions. The predicate terminal(T.I , J) axiomatiz es tha t a terminal symbol T spans the substring from position I to J. We associate with eve ry categorial symb ol a predi cate of the form 363 category( X, C, I, J. A) that axiomatizes the fact tha t the C-context of categorial symbol X , where C ranges on the set {left , right}, spans the sequence w 1, . .. , WJ of input stri ng. Argument A ca ptur es the adjunctions performed over the symbols dominated by X . Wi th this considerations, the interpretation of boundaries arguments as difference lists or positions is in terc hangable. A Prolog pure top-down parser fo r TAGs is obtained directly through this axiomatization. The direction of parsing is n ow strictly left to right, i.e., it is not needed to predict sequence of symbol in advance. We pre sent below the alternati ve trans lation of TAG grammar in figure 3. The two CFG-rules (left and right) associated to auxiliary trees are joined into one Prol og predicate using a new operator A = > B whose operational semantics is nearly to th e logic implication ope rat or. This operator acts like a guarded selective ope rat or that discriminates the left and right context side of auxiliary trees. ?- op(255,xfx, == >). initial(aO,s,l,J,A ) category(T,s, le ft,I,K,A), term inal(e ,K ,L), ca tegory(T,s, r ight,L,J,A). auxiliary(bO,Ctx,s,l,J,A) :- (Ctx=le ft => category(T,s , le ft , I,K,A),terminal(e,K , J)) , (Ctx= right ==> terminal(e,l,K) , catego ry (T,s,right , K,J,A)). A== > B :- A,!,B. A ~=> B. We present n ow the Prolog top-do wn left-to-right parser. Th e predicate term inal is tra nsl ated as usually DCG does. Th e predicate category takes into acco unt the poss ibi lty or not of adjunction over au xiliary tr ees. When adjunction operation is performed over an auxiliary tree, its name is recorded in the front of it s adju nction argume nt in or der to comp lete the sequence of adjunctions. terminal(A,[AIL),L). cat eg ory(A,Ctx,XN,XN,O) . category(A,Ctx,XO,XN,[BIAdj]) auxi li ar(B,A,Ctx,XO,XN,Adj). 4 TAGs compiler I• Recognize ter m in al A •I I• No ad junction •I I• Ad junctio n over auxiliary tree A •I We wi ll describe h ow to compile a special flat representation of TAGs grammars into Prolog programs making use of the axiomatization presented before. This can be done using the s tan dard pr edicate of Prol og to expand rules in to predicates. Th e source granunar wi!J be the set of rules which define the TAG grammar. Each rule is rel ated wi th an elementary tree. the head of the ru1P-'> of initial tre es is of the form i ni(I) where I is the nam e of the initial tree . Similarl y, the head of the rules of auxiliary trees will be of the form au x( A) with A being t.he nam e of the auxiliary tree. The body of 364 :.he rules consists of the word-based representation of the elementary tree, where terminal $1'1Dbo ls are prefixed with the + operator and trees dom ina ted by categorial symbols are separated w it h commas. The somce grammar of figu re 3 is as fo llow s: ini(aO) --> s(+e). aux(bO) --> s(+e,s,+e). First of all, to translate a rule we use the = .. predicate to transform the tree into a list sep ara ting the root node Root of the elementary tree fr om the trees Trees dominated by the root. The treatment of Root and Trees are different depencling on the class of elementary tree being pr ocessing. Th en , give n a list of symbols Trees, representing the fla t no tat ion of a tree (or a set of trees), the predica te trans(Trees, PO , PN , XO,XN , TRTrees ,Adj) is applied to genere another list T RT rees. Now the symbols in the T RTr ees list are aumengted wi th boundaries (using PO, PN , XO and XN) and adjun ct ion (using Adj) arguments. This predicate also splits categori es in left and right sides, and marks the categorial symbols associated with the foot node in order to reduce the process of dividing the left and right context side of auxiliary trees. Finally, a new predic ate divide(T RT ree, BodyL , Bod yR) is app li ed to construct actual rule's body and divide the left BodyL and right Bod yR contextual sides of auxiliary trees. ·w h en applied over i ni tial trees, only one argum ent is used because it is not necessary distinguish between the left and right side of the tree. ?- op(255,xf,+). term_expansion((ini(A) -- > B),(Head :-Body)) B• .. [Root I Trees), trans(Trees,XO,XN,Xl,X2,TRTrees,Adjs), divide(TRTrees,BodyTrees,_), Head•initial(A,Root,XO,XN,[AdjiAd js]), Body-(category(Root,left,XO,Xl,Ad j) , BodyTrees, category( R oot,righ t,X2,XN,Ad j)) . term_expansion (( aux (A) --> B ),(Head :- Body )) BR .. [Root I Trees), trans(Tre es,XO,XN,XO,XN,TRT rees ,Ad j) , divide(TRTrees,BodyL,BodyR), Head•auxiliary(A,Root,Ctx,XO,XN,Adj), Body =( (Ctx=left) ==> BodyL,(Ctx=right) ==> BodyR). trans ( 0 , P O, PN, X, X, 0 , 0 ) :- ! . trans([+TIRT],PO,PN ,X O,XN,[terminal(T,XO,Xl)IQ],Adj) trans (R T,PO , PN,Xl,XN,Q , Ad j). trans ([TIRT] ,PO ,PN,XO,XN,[Ql,Q21RQ ], [Adj iAdjs]) Ql af oot (T ,left,XO,PN, Ad j), Q2 •foo t(T,right,PO,X1,Adj ) , atomic (T) • ! , trans( RT,PO,PN,Xl,XN,RQ,Ad js). 365 I . ' trans([TIRTree] ,PO,PN,X O ,XN,Q,[Ad ji Adjs ]) T= .. [RootiTree s], Q1=category(Root,left,XO,X 1,Adj) , Q2=category(Root,right,X2,X3,A dj ), trans (Trees,PO,PN,X1,X2,RQ, Adj 1), trans (RTree,PO,PN,X3,XN,R ,A dj2 ), append(Adj1,Adj2,Ad js), append([Qli RQ ] ,[Q21R],Q) . divide ([ foot (A,left,PO,PN,Aj) IQ] ,category(A, lef t,PO,PN,Aj ) ,R ) · - 1 . .. divide(Q,P, R ). divide ( [foot(A , right , PO,P N,Aj)] ,_,category(A,right,PO,PN,Aj)) : -!. divide([category( A,Ctx, PO,P N,A j)) , categor y(A,Ctx,PO,PN ,Aj), _) :-!. di vid e((termin al (A,PO,PN)) ,terminal( A ,PO ,PN),_) :- !. divide ([foot(A,right,PO,PN,Aj )I Q] ,P, (category(A,right,PO,PN,A j), R) ) :- 1, div id e(Q,R,P) . divide([QIR. Q] , ( Q,RR ), P) divide ( RQ,RR,P ) . 5 C onclusi ons Al tho ugh several par si ng algori thm s have been d efi ned for TAGs gra mmars , the st udy of TAGs parsing fr om a logic programming point of view is not freque nt in th e literatur e. Lang's axio mat ization of TAGs estab li shes a relation between elementary trees an d definite clauses. The key of th is int erp retation consists of associating four indices to categorial symbols that represent boundaries po sit ions over the input. In this paper, we present an alternative representation which only uses two boundaries indices, ju st the number presented in DCGs. An aditio na l argume nt is needed in order to control the adjunctions co mp osition of elementary trees. [n the context of a pure to p-down parser, Lang's axiomatization presents several ope ra tional problems tha t the new approach reduces. Now, the Prolog translation permits a stri ct left to right parsing of the in put and the interchangable interpretation of input lexem es wi th positions or difference lists. Given a g rammar , the parser finds every parse tree for a gra mmati cal inp ut pr oducing a co mpa ct represe nta tion of every parse tree. Adjunction arg uments ove r categories also hel ps us in pro du cing parse tr ees. Fina lly, a PROLOG compiler of TAGs gramma r is defined that uses this alternative appr oach in a similar w ay pr esented in DCG grammars respect to CFG -rules. Refe re nces [AbD89) H. Abramson and V. Da hl. Logic Grammars. Springer Verlag, New York , 1989. [JLT75] A. K. Joshj; L .. S. Levy and M. Takahashi. Tree Adjunct Grammars. J o11rna l of Computer System a nd Scien ce , 10(1), 136-63, 1975. [J oS92 } A. K. Joshi and Y. S cha bes. Tree Adjoining Grammars and Lcxicalized Grammars. Ln Nivat, M (ed .), 7ree Automat a and La nguages. North Holland. 1992 366 [Har90] K. Rarbusch. An Efficient Parsing Algorithm for TAGs. 28th Meeting of A CL, Pittsburgh, 1990 [Lan90j B. Lang. Towards a Uniform Formal Framework for Parsing. In Tomita, M (ed.), Current Issues in Parsing Technologies. Kluwer Accademic Publishers, 1990 [S c h90] -Y. Schabes. Mathematical and Computational Aspects of Lexicalized Grammars. Ph. D. Thesis. Departament of Com_£uter and Information Science, University of Pennsylvania, 1990 [ScJ88] Y. Schabes and A. Joshi. An Early-Type Parsing Algorithm for Tree Adjoining Grammars. 26th M ee ting of ACL , Buffalo, 1988 367