Variants of mixed parsing of TAG and TIG

Variants of mixed parsing of TAG and TIG Miguel A. Alonso*—Víctor J. Díaz** *Departamento de Computación, Universidade da Coruña Campus de Elviña s/n, 15071 La Coruña (Spain) [email protected] **Departamento de Lenguajes y Sistemas Informáticos, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla (Spain) [email protected] ABSTRACT. Tree Adjoining Grammar (TAG) is a useful formalism for describing the syntactic structure of natural languages. In practice, a large part of wide coverage TAGs is formed by trees that satisfy the restrictions imposed by Tree Insertion Grammar (TIG), a simpler formalism. This characteristic can be used to reduce the practical complexity of TAG parsing, applying the standard adjunction operation only in those cases in which the simpler cubic-time TIG adjunction cannot be applied. A major obstacle to this task is posed by the fact that simultaneous adjunctions are forbidden in TAG but they are allowed in TIG. In this article, we describe several algorithms for mixed parsing of TAG and TIG: a first one forbidding simultaneous adjunctions, a second one allowing this kind of adjunctions, and a third one which extends the second one to preserve the correct prefix property. RÉSUMÉ. La Grammaire d’Arbres Adjoints (TAG) est un formalisme utile pour décrire la structure syntaxique des langues naturelles. En pratique, la plupart des TAG à large couverture contiennent des arbres qui satisfont les restrictions imposées par la Grammaire d’Insertion d’Arbres (TIG), qui est un formalisme plus simple. Cette caractéristique peut être employée pour réduire la complexité pratique de l’analyse TAG, en appliquant l’opération d’adjonction standard seulement dans les cas où l’adjonction TIG, plus simple, ne peut pas être appliquée. L’un des plus grands obstacles à cette tâche réside dans le fait que les adjonctions simultanées sont interdites en TAG mais elles sont permises en TIG. Dans cet article, nous décrivons plusieurs algorithmes pour l’analyse mixte de TAG et de TIG : 1) celui qui interdit les adjonctions simultanées; 2) celui qui permet ce type d’adjonction; et 3) celui qui étend le deuxième afin de préserver la propriété du préfixe correcte. KEYWORDS: parsing, tree adjoining grammar, tree insertion grammar. MOTS-CLÉS : analyse syntaxique, grammaires d’arbres adjoints, grammaires d’insertion d’arbres. TAL. Volume 44 - n◦3/2003, pages 41 à 65 42 TAL. Volume 44 - n◦3/2003 1. Introduction Tree Adjoining Grammar (TAG) [JOS 75, JOS 97, ABE 00] and Tree Insertion Grammar (TIG) [SCH 95] are grammatical formalisms that make use of a tree-based operation called adjunction. However, adjunctions are more restricted in the case of TIG than in the case of TAG, which has important consequences with respect to the set of languages generated and the worst-case complexity of parsing algorithms: – TAG generates tree adjoining languages, a strict superset of context-free languages, and the complexity of parsing algorithms is in O(n6)for time and in O(n4) for space with respect to the length nof the input string. – TIG generates context-free languages and can be parsed in O(n3)for time and in O(n2)for space. – The correct prefix property [SCH 91] is preserved by TIG parsers without increasing their computational cost. In the case of TAG, preserving this property involves an increase in the space complexity from O(n4)to O(n5)[NED 99]. Although the powerful adjunction provided by TAG makes it useful for describing the syntax of natural languages, most of the trees involved in wide coverage grammars like XTAG [DOR 94] do not make use of such operation, and so a large portion of XTAG is in fact a TIG [SCH 95]. As the full power of a TAG parser is only put into practice in adjunctions involving a given set of trees, to apply a parser working in O(n6)time complexity when most of the work can be done by a O(n3)parser seems to be a waste of computing resources. In this article, we propose to improve the practical efficiency of TAG parsers by applying mixed parser strategies that takes the best of both worlds: those parts of the grammar that correspond to a TIG are managed in O(n3)time and O(n2)space complexity, and only those parts of the grammar involving the full kind of adjunction present in TAG are managed in O(n6)time and O(n4)space complexity (O(n5)space complexity in the case of parsers satisfying the correct prefix property). This article may be outlined as follows. The remainder of this section is devoted to describe the notation used in the article. In section 2 we present a mixed parsing algorithm in which at most one auxiliary tree is allowed to be adjoined at a given node. This algorithm is modified in section 3 to allow simultaneous adjunctions. New modifications are considered in section 4 in order to preserve the correct prefix property. The computational complexity of these algorithms is analyzed in section 5 and their practical efficiency is studied in section 6. Section 7 presents final conclusions. 1.1. Tree Adjoining Grammars Formally, a TAG is a 5-tuple G= (VN, VT, S, I,A), where VNis a finite set of non-terminal symbols, VTa finite set of terminal symbols, S∈VNthe axiom of the grammar, Ia finite set of initial trees and Aa finite set of auxiliary trees.I∪A is the set of elementary trees. Internal nodes of elementary trees are labeled by non- Variants of mixed parsing of TAG and TIG 43 S S Adv NP VP VP VP runs slowly John NP VP John VP Adv slowlyruns spine Inital tree Auxiliary tree Derived tree Figure 1. Adjunction operation terminals and leaf nodes by terminals or the empty string ε, except for just one leaf per auxiliary tree (the foot) which is labeled by the same non-terminal used as the label of its root node. The path in an auxiliary tree from the root node to the foot node is called the spine of the tree. New trees are derived by adjunction: let γbe an elementary orderived tree containing a node Nγlabeled by Aand let βbe an auxiliary tree whose root and foot nodes are also labeled by A. Then, the adjunction of βat the adjunction node Nγis obtained by excising the subtree of γwith root Nγ, attaching βto Nγand attaching the excised subtree to the foot of β. We can add constraints on the nodes of elementary trees so the adjunction on a node can be mandatory, optional or forbidden. The string language of a TAG Gis defined as the set of yields of all the trees derived from initial trees rooted by the axiom of the grammar [JOS 97]. We illustrate the adjunction operation in Fig. 1, where we show a simple TAG with two elementary trees: an initial tree rooted S and an auxiliary tree rooted VP. The derived tree obtained after adjoining the VP auxiliary tree at the node labeled by VP located in the initial tree is also shown.1 1.2. Tree Insertion Grammars We can consider the set Aas formed by the union of the sets AL, containing left auxiliary trees in which every nonempty frontier node2is to the left of the foot node, AR, containing right auxiliary trees in which every nonempty frontier node is to the right of the foot node, and AW, containing wrapping auxiliary trees in which nonempty frontier nodes are placed both to the left and to the right of the foot node. Figure 2 shows three derived trees resulting from the adjunction of a wrapping, left and right auxiliary tree, respectively. We can note from that picture that the trees derived by the adjunction of left an right auxiliary trees are simpler than those derived 1. The operation of substitution can also be defined for TAG, but it does not increase the generative power of the formalism. The incorporation of substitution to the parsing algorithms defined in this article is straightforward and does not modify their complexity. 2. An empty frontier node is a leaf node labeled by the empty string ε. 44 TAL. Volume 44 - n◦3/2003 Wrapping auxiliary tree Left auxiliary tree Right auxiliary tree Figure 2. Adjunction of left, right and wrapping auxiliary trees α β L βR S S S S S b a c Figure 3. Example of TIG grammar by wrapping auxiliary trees. It is just this evidence which introduces the notion of Tree Insertion Grammars. Given an auxiliary tree, those nodes placed on the spine are called spine nodes and those nodes placed to the left (resp. right) of the spine are called left nodes (resp. right nodes). The set ASL ⊆AL(resp. ASR ⊆AR) of strongly left (resp. strongly right) auxiliary trees is formed by trees in which no adjunction is permitted on right (resp. left) nodes and only strongly left (resp. right) auxiliary trees are allowed to adjoin on spine nodes. We denote by A′the set A−(ASL ∪ASR). Given the set Aof a TAG, we can determine the set ASL as follows: firstly, we determine the set ALexamining the frontier of the trees in Aand we set ASL := AL; secondly, we eliminate from ASL those trees that permit adjunctions on nodes to the right of their spine; and thirdly, we iteratively eliminate from ASL those trees that allow adjoining trees in A−ASL on nodes of their spine. ASR is determined in an analogous way. In essence, a TIG is a restricted TAG where auxiliary trees must be either strongly left or strongly right and adjunctions are not allowed in root and foot nodes of auxiliary trees. There is also a different approach between both formalism with respect to the way adjunctions are performed. In contrast with TAG, where only an auxiliary tree can be adjoined at a node, TIG enables simultaneous adjunctions, i.e., the adjunction of several auxiliary trees on a node of a tree. We illustrate this point in Figure 3 where a TIG grammar with an initial tree α, a left auxiliary tree βLand a right auxiliary tree Variants of mixed parsing of TAG and TIG 45 βRis depicted. When simultaneous adjunction of βLand βRis allowed at the root node of α, the TIG language is a∗bc∗, i.e., an optional sequence of a’s followed by a band followed by an optional sequence of c’s. In contrast, if simultaneous adjunction was not allowed, we could not combine the left and right auxiliary trees, and the language generated would be the union of the strings ab and bc.3 1.3. Notation for parsing algorithms We will describe parsing algorithms using Parsing Schemata, a framework for high-level descriptions of parsing algorithms [SIK 97]. A parsing system for a grammar Gand string a1. . . anis a triple hI,H,Di, with Ia set of items which represent intermediate parse results, Han initial set of items called hypothesis that encodes the sentence to be parsed, and Da set of deduction steps that allow new items to be derived from already known items. Deduction steps are of the form η1,...,ηk ξcond, meaning that if all antecedents ηiof a deduction step are present and the conditions cond are satisfied, then the consequent ξshould be generated by the parser. A set F ⊆ I of final items represent the recognition of a sentence. A parsing schema is a parsing system parameterized by a grammar and a sentence. Given an input string a1. . . an, the hypothesis of all parsing systems described in this article will be defined in the standard way: H=[a, i −1, i]|a=ai,1≤i≤n In order to describe the parsing algorithms for tree-based formalisms, we must be able to represent the partial recognition of elementary trees. Parsing algorithms for context-free grammars usually denote partial recognition of productions by dotted productions. We can extend this approach to the case of tree-based grammars by considering each elementary tree γas formed by a set of context-free productions P(γ): a node Nγand its children Nγ 1. . . Nγ gare represented by a production Nγ→ Nγ 1. . . Nγ g. Thus, the position of the dot in the tree is indicated by the position of the dot in a production in P(γ). The elements of the productions are the nodes of the tree. To simplify the description of parsing algorithms we consider an additional production ⊤ → Rαfor each α∈Iand the two additional productions ⊤ → Rβand Fβ→ ⊥ for each β∈A, where Rβand Fβcorrespond to the root node and the foot node of β, respectively. After disabling ⊤and ⊥as adjunction nodes the generative capability of the grammars remains intact. We introduce also the following notation: given two pairs (p, q)and (i, j)of integers, (p, q)≤(i, j)is satisfied if i≤pand q≤jand given two integers pand qwe define p∪qas pif qis undefined and as qif pis undefined, being undefined in other case. We use β∈adj(Nγ)to denote that an auxiliary tree βmay be adjoined at node Nγof the tree γ. If adjunction is not mandatory at Nγthen nil ∈adj(Nγ)where 3. We remind you that TIG forbids adjunction at the root nodes of auxiliary trees. 46 TAL. Volume 44 - n◦3/2003 γ N δ R γ ν i jqp γ F Figure 4. Graphical representation of the items in the set IMix1 nil /∈I∪Ais a dummy symbol. If adjunction is not allowed at Nγthen {nil}= adj(Nγ). We also use label(Nγ)to denote the label of a node Nγbelonging to an elementary tree γ. 2. Mixed parsing without simultaneous adjunctions In this section we define a parsing system P Mix1=hIMix1,H,DMix1icorresponding to an Earley-like TAG parser merged with an Earley-like TIG parser, in which the adjunction of strongly left and strongly right auxiliary trees will be managed by specialized deduction steps, the rest of adjunctions will be managed with the classical deduction steps included in most TAG parsers [ALO 99]. In this parsing algorithm, simultaneous adjunctions are not allowed. Thus, we follow the standard TAG definition of adjunction. With slight modifications, this parsing system corresponds to the parsing algorithm shown in [ALO 02]. 2.1. Items The items in the set IMix1are of the form [Nγ→δ•ν, i, j |p, q |adj]such that Nγ→δν ∈ P(γ),γ∈I∪A,0≤i≤j≤n,(p, q) = (−,−)or (p, q)≤(i, j), and adj ∈ {true,false}. The two indices with respect to the input string iand jindicate the portion of the input string that has been spanned from δ(see figure 4). If γ∈A,p and qare two indices with respect to the input string that indicate that part of the input string recognized by the foot node of γif it is a descendant of δ. In other case they are undefined, which is denoted by p=q=−. The last boolean component adj is needed to manage mandatory adjunction: adj = true if and only if an adjunction has Variants of mixed parsing of TAG and TIG 47 taken place at Nγ, otherwise adj = false. Therefore, this kind of items satisfy one of the following conditions: 1) γ∈A′,(p, q)6= (−,−)and δ6=εspans ai+1 . . . apFγaq+1 . . . aj 2) δ6=ε,(p, q) = (−,−)and δspans the string ai+1 . . . aj. 3) δ=ε,(p, q) = (−,−),i=j,adj = false. The last boolean component indicates that any tree has been adjoined at Nγ. 4) δ=ε,(p, q) = (−,−),adj = true and there exists a β∈ASL such that β∈adj(Nγ)and Rβspans ai+1 . . . aj(i.e., βhas been adjoined at Nγ). In this case, iand jindicate the portion of the input string spanned by the left auxiliary tree adjoined at Nγ. In this algorithm, the last boolean component of items is also used to control that at most one adjunction has been performed on a node. A value of true indicates that an adjunction has taken place on the node Nγand therefore further adjunctions on the same node will be forbidden. A value of false indicates that no adjunction was performed on that node. In this case, during future processing this item can play the role of the item recognizing the excised part of an elementary tree to be attached to the foot node of a right auxiliary tree. As a consequence, only one adjunction can take place on a node, as is usual for TAG parsers. 2.2. Deduction steps The set of deduction steps is formed by the following subsets: DMix1=DInit Mix1∪ DScan Mix1∪ Dε Mix1∪ DPred Mix1∪ DComp Mix1∪ DAdjPred Mix1∪ DFootPred Mix1∪ DFootComp Mix1∪ DAdjComp Mix1∪ DLAdjPred Mix1∪ DLAdjComp Mix1∪ DRAdjPred Mix1∪ DRAdjComp Mix1∪ DLRFoot Mix1 The parsing process starts by creating the items corresponding to productions having the root of an initial tree as right-hand side and the dot in the leftmost position of the right-hand side: DInit Mix1=[⊤ → •Rα,0,0| −,− | false] α∈I∧S= label(Rα) A set of deductive steps in DPred Mix1and DComp Mix1traverse each elementary tree while steps in DScan Mix1and Dε Mix1scan input symbols and the empty symbol, respectively: DPred Mix1=[Nγ→δ•Mγν, i, j |p, q |adj] [Mγ→ •υ, j, j | −,− | false] nil ∈adj(Mγ)∨ (∃β∈ASL ∪ASR, β ∈adj(Mγ)) 48 TAL. Volume 44 - n◦3/2003 DComp Mix1= [Nγ→δ•Mγν, i, j |p, q |adj], [Mγ→υ•, j, k |p′, q′|adj′] [Nγ→δMγ•ν, i, k |p∪p′, q ∪q′|adj] with (nil ∈adj(Mγ)∧adj′= false) ∨ (∃β∈A, β ∈adj(Mγ)∧adj′= true) DScan Mix1= [Nγ→δ•Mγν, i, j |p, q |adj], [a, j, j + 1] [Nγ→δMγ•ν, i, j + 1 |p, q |adj]a= label(Mγ) Dε Mix1=[Nγ→δ•Mγν, i, j |p, q |adj] [Nγ→δMγ•ν, i, j |p, q |adj]ε= label(Mγ) The rest of steps are in charge of managing adjunction operations. If a strongly left auxiliary tree β∈ASL can be adjoined at a given node Mγ, a step in DLAdjPred Mix1 starts the traversal of β. When βhas been completely traversed, a step in DLAdjComp Mix1 starts the traversal of the subtree corresponding to Mγand sets the last element of the item to true in order to forbid further adjunctions on this node. DLAdjPred Mix1=[Mγ→ •υ, i, i | −,− | false] [⊤ → •Rβ, i, i | −,− | false] β∈adj(Mγ)∧β∈ASL DLAdjComp Mix1= [Mγ→ •υ, i, i | −,− | false], [⊤ → Rβ•, i, j | −,− | false] [Mγ→ •υ, i, j | −,− | true] β∈ASL ∧β∈adj(Mγ) If a strongly right auxiliary tree β∈ASR can be adjoined at a given node Mγ, when the subtree corresponding to this node has been completely traversed, a step in DRAdjPred Mix1starts the traversal of the tree β. When βhas been completely traversed, a step in DRAdjComp Mix1updates the input positions spanned by Mγtaking into account the part of the input string spanned by β, and sets the last element of the item to true in order to forbid further adjunctions on this node. DRAdjPred Mix1=[Mγ→υ•, i, j |p, q |false] [⊤ → •Rβ, j, j | −,− | false] β∈ASR ∧β∈adj(Mγ) DRAdjComp Mix1= [Mγ→υ•, i, j |p, q |false], [⊤ → Rβ•, j, k | −,− | false] [Mγ→υ•, i, k |p, q |true] β∈ASR ∧β∈adj(Mγ) Variants of mixed parsing of TAG and TIG 49 No special treatment is given to the foot node of strongly left and right auxiliary trees and so, it is simply skipped by a step in the set DLRFoot Mix1. DLRFoot Mix1=[Fβ→ •⊥, j, j, adj] [Fβ→ ⊥•, j, j, adj]β∈ASL ∪ASR A step in DAdjPred Mix1predicts the adjunction of an auxiliary tree β∈A′at a node of an elementary tree γand starts the traversal of β. Once the foot of βhas been reached, the traversal of βis momentary suspended by a step in DFootPred Mix1, which re-takes the subtree of γwhich must be attached to the foot of β. At this moment, there is no information available about the node in which the adjunction of βhas been performed, so all possible nodes are predicted. When the traversal of a predicted subtree has finished, a step in DFootComp Mix1re-takes the traversal of βcontinuing at the foot node. When the traversal of βis completely finished, a deduction step in DAdjComp Mix1checks if the subtree attached to the foot of βcorresponds with the adjunction node. The traversal of Mγ(and therefore the adjunction of βat Mγ) is finished by a step in DComp Mix1, taking into account that p′and q′are instantiated if and only if the adjunction node is on the spine of γ. It is interesting to remark that we follow the approach of [NED 99], splitting the completion of an adjunction between DAdjComp Mix1and DComp Mix1. DAdjPred Mix1=[Nγ→δ•Mγν, i, j |p, q |adj] [⊤ → •Rβ, j, j | −,− | false] β∈A′∧β∈adj(Mγ) DFootPred Mix1=[Fβ→ •⊥, k, k | −,− | false] [Mγ→ •υ, k, k | −,− | false] β∈A′∧β∈adj(Mγ) DFootComp Mix1= [Fβ→ •⊥, k, k | −,− | false], [Mγ→υ•, k, l |p′, q′|false] [Fβ→ ⊥•, k, l |k, l |false] β∈A′∧β∈adj(Mγ) DAdjComp Mix1= [⊤ → Rβ•, j, m |k, l |false], [Mγ→υ•, k, l |p′, q′|false] [Mγ→υ•, j, m |p′, q′|true] β∈A′∧β∈adj(Mγ) The input string belongs to the language defined by the grammar if a final item in the set F=[⊤ → Rα•,0, n | −,− | false] |α∈I∧S= label(Rα)is generated. 3. Mixed parsing with simultaneous adjunctions Let us consider now that the trees in Figure 3 define a TAG. In this case, to generate the language a∗bc∗we need to perform several adjunctions of βLand βRat their root 56 TAL. Volume 44 - n◦3/2003 tree involved in each item belongs to A′. Therefore, the value of adj has the same meaning than for items in I(1a) Mix3but now the value of hmust be set to the position of the input string at which the traversal of βwas started. For trees in A′, the position his needed to ensure the correct prefix property is preserved at the time of predicting the subtrees pending from their foot nodes. I(2b) Mix3:A subset with items of the form [h, Nβ→δ•ν, i, j | −,− | adj]such that Nβ→δν ∈ P(β),β∈A′,0≤h≤i≤j,adj ∈ {true,false}and the foot node of βis not a descendant of any node in δ. These items are similar to items in the subset I(1b) Mix3, in particular the value of adj has the same meaning than for items in I(1b) Mix3. I(2c) Mix3:A subset with items of the form [h, Nβ→δ•ν, i, j |p, q |adj]such that Nβ→δν ∈ P(β),β∈A′,0≤h≤i≤j,adj ∈ {true,false},(p, q)≤(i, j) and the foot node of βis a descendant of a node in δ. The substring spanned by δis ai+1 . . . apFβaq+1 . . . aj. Thus, pand qare positions in the input string indicating a discontinuity in the string recognized by β, due to the substring ap+1 . . . aqshould be spanned by the node at which the auxiliary tree βhas been adjoined. With respect to the boolean component, adj = true if some auxiliary tree has been previously adjoined at Nγ, otherwise adj = false. I(3) Mix3:A subset with items of the form [[Mγ→υ•, i, j |p, q |true]] such that Mγ→υ∈ P(β),β∈A′,0≤i≤jand (p, q) = (−,−)or (p, q)≤(i, j). These items are generated as a kind of intermediate items during the completion of the adjunctions of auxiliary trees in A′. 4.2. Deduction steps The set of deduction steps is formed by the following subsets: DMix3=DInit Mix3∪ DScan Mix3∪ Dε Mix3∪ DPred1 Mix3∪ DPred3 Mix3∪ DComp Mix3∪ DLAdjPred Mix3∪ DLAdjComp Mix3∪ DRAdjPred Mix3∪ DRAdjComp Mix3∪ DLRFoot Mix3∪ DAdjPred Mix3∪ DFootPred Mix3∪ DFootComp Mix3∪ DAdjComp1 Mix3∪ DAdjComp2 Mix3 The parsing process starts by creating the items corresponding to productions having the root of an initial tree as right-hand side and the dot in the leftmost position of the right-hand side: DInit Mix3=[−,⊤ → •Rα,0,0| −,− | false] α∈I∧S= label(Rα) Variants of mixed parsing of TAG and TIG 57 In order to preserve the correct prefix property, we must be very careful when predicting the left-most child of a given node Nγ. Thus, to generate the consequent item in a deduction step corresponding to the subset DPred1 Mix3 DPred1 Mix3=[h, Nγ→ •Mγν, i, j | −,− | adj] [h, Mγ→ •υ, j, j | −,− | false] one of the following conditions must be satisfied: 1) Adjunction is forbidden at node Nγand adj = false. 2) Adjunction is optional at node Nγbut any strongly left auxiliary tree can be adjoined at this node. As a consequence, the value of adj should be false. 3) Adjunction is optional at node Nγand some strongly left auxiliary tree can be adjoined at this node or there exists some auxiliary trees belonging to A′∪ASR that can be adjoined at Nγ. No restriction is applied on the value of adj. 4) Adjunction is mandatory at node Nγbut only strongly left auxiliary trees can be adjoined at this node. The value of adj should be true to guarantee that at least one adjunction has been performed at Nγ. 5) Adjunction is mandatory at node Nγbut any strongly left auxiliary tree can be adjoined at this node. As a consequence, the value of adj should be false. 6) Adjunction is mandatory at node Nγbut there exists some auxiliary trees belonging to A′∪ASR that can be adjoined at Nγ. The value of adj is not restricted at this moment. The rest of children of a given node Nγare predicted as in the P Mix2parsing system: DPred2 Mix3=[h, Nγ→δ•Mγν, i, j |p, q |adj] [h, Mγ→ •υ, j, j | −,− | false] δ6=ε Once the children of Mγhave been completely traversed, a step in DComp Mix3 DComp Mix3= [h, Nγ→δ•Mγν, i, j |p, q |adj], [h, Mγ→υ•, j, k |p′, q′|adj′] [h, Nγ→δMγ•ν, i, k |p∪p′, q ∪q′|adj] should be applied, checking that one of the following conditions is satisfied: 1) Adjunction is mandatory at Mγand adj′= true. 2) Adjunction is forbidden at Mγand adj′= false. 3) Adjunction is optional at Mγand therefore there are no restrictions on the value of adj. Input symbols and the empty string are recognized by deduction steps in DScan Mix3 and Dε Mix3, respectively: 58 TAL. Volume 44 - n◦3/2003 DScan Mix3= [h, Nγ→δ•Mγν, i, j |p, q |adj], [a, j, j + 1] [h, Nγ→δMγ•ν, i, j + 1 |p, q |adj]a= label(Mγ) Dε Mix3=[h, Nγ→δ•Mγν, i, j |p, q |adj] [h, Nγ→δMγ•ν, i, j |p, q |adj]ε= label(Mγ) If a strongly left auxiliary tree β∈ASL can be adjoined at a given node Mγ, a step in DLAdjPred Mix1starts the traversal of β. When βhas been completely traversed, a step in DLAdjComp Mix1starts the traversal of the subtree corresponding to Mγand sets the last element of the item to true in order to indicate that an adjunction has taken place on this node. As in P Mix2, simultaneous adjunctions of several strongly left auxiliary trees on a node Mγis achieved by applying a pair of steps DLAdjPred Mix3and DLAdjComp Mix3 for each auxiliary tree. DLAdjPred Mix3=[h, Mγ→ •υ, i, j | −,− | adj] [−,⊤ → •Rβ, j, j | −,− | false] β∈adj(Mγ)∧β∈ASL DLAdjComp Mix3= [h, Mγ→ •υ, i, j | −,− | adj], [−,⊤ → Rβ•, j, k | −,− | false] [h, Mγ→ •υ, i, k | −,− | true] β∈ASL ∧β∈adj(Mγ) If a strongly right auxiliary tree β∈ASR can be adjoined at a given node Mγ, when the subtree corresponding to this node has been completely traversed, a step in DRAdjPred Mix1starts the traversal of the tree β. When βhas been completely traversed, a step in DRAdjComp Mix1updates the input positions spanned by Mγtaking into account the part of the input string spanned by β, and sets the last element of the item to true in order to indicate that an adjunction has taken place on this node. As in P Mix2, simultaneous adjunctions of several strongly right auxiliary trees on a node Mγis achieved by applying a pair of steps DRAdjPred Mix3and DRAdjComp Mix3for each auxiliary tree. DRAdjPred Mix3=[h, Mγ→υ•, i, j |p, q |adj] [−,⊤ → •Rβ, j, j | −,− | false] β∈ASR ∧β∈adj(Mγ) DRAdjComp Mix3= [h, Mγ→υ•, i, j |p, q |adj], [−,⊤ → Rβ•, j, k | −,− | false] [h, Mγ→υ•, i, k |p, q |true] β∈ASR ∧β∈adj(Mγ) Variants of mixed parsing of TAG and TIG 59 The foot nodes of strongly left and right auxiliary trees are skipped by a step in the set DLRFoot Mix3: DLRFoot Mix3=[−,Fβ→ •⊥, j, j | −,− | adj] [−,Fβ→ ⊥•, j, j | −,− | adj]β∈ASL ∪ASR A step in DAdjPred Mix3predicts the adjunction of an auxiliary tree β∈A′in a node of an elementary tree γ, storing the position jat which the traversal of βwas started. DAdjPred Mix3=[h, Mγ→ •υ, i, j | −,− | adj] [j, ⊤ → •Rβ, j, j | −,− | false] β∈A′∧β∈adj(Mγ) Once the foot of βhas been reached, the traversal of βis momentary suspended by a step in DFootPred Mix3, which re-takes the subtree of γwhich must be attached to the foot of β, checking the position at which the traversal of γwas suspended is compatible with the position at which the traversal of βwas started. DFootPred Mix3= [h, Mγ→ •υ, i, j | −,− | adj] [j, Fβ→ •⊥, k, k | −,− | adj] [h, Mγ→ •υ, k, k | −,− | adj]β∈A′∧β∈adj(Mγ) When the traversal of Mγhas been completed, a step in DFootComp Mix3re-takes the traversal of βcontinuing at the foot node, checking again that the position at which the traversal of γwas suspended is compatible with the position at which the traversal of βwas started. These checkings are needed to guarantee the correct prefix property is preserved at any moment. DFootComp Mix3= [h, Mγ→ •υ, i, j | −,− | adj], [j, Fβ→ •⊥, l, l | −,− | adj], [h, Mγ→υ•, l, m |p′, q′|adj′] [j, Fβ→ ⊥•, l, m |l, m |adj]β∈A′∧β∈adj(Mγ) When the traversal of βis completely finished, a deduction step in DAdjComp1 Mix3checks if the subtree attached to the foot of βcorresponds with the adjunction node. The adjunction if finished by a step in DAdjComp2 Mix3, taking into account that p′and q′are instantiated if and only if the adjunction node is on the spine of γ. DAdjComp1 Mix3= [j, ⊤ → Rβ•, j, r |l, m |false], [h, Mγ→υ•, l, m |p′, q′|adj] [[Mγ→υ•, j, r |p′, q′|true]] β∈A′∧β∈adj(Mγ) DAdjComp2 Mix3= [h, Mγ→ •υ, i, j | −,− | adj], [[Mγ→υ•, j, r |p′, q′|true]], [h, Mγ→υ•, l, m |p′, q′|adj] [h, Mγ→υ•, i, r |p′, q′|true] β∈A′∧β∈adj(Mγ) 60 TAL. Volume 44 - n◦3/2003 Simultaneous adjunctions of several auxiliary trees in β∈A′is achieved by using the consequent item generated by a deduction step in DFootPred Mix3as antecedent of a deduction step in DAdjPred Mix3to start the adjunction of an auxiliary tree β′∈A′. When the traversal of β′has finished, a step in DFootComp Mix2re-takes the traversal of βat the foot node. The process is repeated foreach auxiliary tree which is to be simultaneously adjoined. A major difference of this parsing system with respect to P Mix2is that Comb steps are not needed, due to the strong prediction performed by steps in DPred1 Mix3guarantees that simultaneous adjunctions are applied from left to right with respect to the input string. The input string belongs to the language defined by the grammar if a final item in the set F=[−,⊤ → Rα•,0, n | −,− | false] |α∈I∧S= label(Rα)is generated. 5. Complexity The worst-case space complexity of the algorithms described by P Mix1and P Mix2 is in O(n4), as at most four input positions are stored into items corresponding to auxiliary trees belonging to A′. For P Mix3, the worst-case space complexity is in O(n5). In all cases, initial trees and strongly left and right auxiliary trees contribute O(n2)to the final result. With respect to the worst-case time complexity: – TIG adjunction, the adjunction of a strongly left or right auxiliary tree on a node of a tree belonging to I∪ASL ∪ASR, is managed in O(n3)by LAdjComp and RAdjComp steps in all algorithms. – In P Mix1and P Mix2, full TAG adjunction is managed in O(n6)by AdjComp deduction steps, which are in charge of dealing with auxiliary trees belonging to A′. In fact, O(n6)is only attained when a wrapping auxiliary tree is adjoined on a spine node of a wrapping auxiliary tree. The adjunction of a wrapping auxiliary tree on a right node of a wrapping auxiliary tree is managed in O(n5)due to Comp deduction steps. – In P Mix3, full TAG adjunction is managed in O(n6)by AdjComp1steps and in O(n5)by AdjComp2steps when a wrapping auxiliary tree is adjoined on a spine node of a wrapping auxiliary tree, thus given an overall complexity of O(n6). The adjunction of a wrapping auxiliary tree on a right node of a wrapping auxiliary tree is managed in O(n4)by AdjComp1steps and in O(n3)by AdjComp2steps, but in O(n5)by Comp deduction steps. – The adjunction of a strongly right auxiliary tree on a spine or right node of a wrapping auxiliary tree is managed in O(n5)time due to RAdjComp deduction steps. Variants of mixed parsing of TAG and TIG 61 – Other cases of adjunction, e.g., the adjunction of a strongly left or right auxiliary tree on a spine node of a tree belonging to (AL−ASL)∪(AR−ASR), are managed in O(n4). Transitive and Ditransitive (1) Srini bought a book (2) Srini bought Beth a book Arguments and Adjuncts (3) Srini bought a book at the bookstore (4) he put the book on the table (5) *he put the book Ergative and Intransitive (6) the sun melted the ice (7) the ice melted (8) Elmo borrowed a book (9) *a book borrowed Sentential Complements (10) he hopes Muriel wins (11) he hopes that Muriel wins Relative Clauses (12) the man who Muriel likes bought a book (13) the man that Muriel likes bought a book Auxiliary Verbs (14) the music should have been being played for the president Extraction (15) Clove caught a frisbee (16) who caught a frisbee (17) what did Clove catch Unbounded Dependencies (18) the aardvark smells terrible (19) the emu thinks that the aardvark smells terrible (20) who does the emu think smells terrible (21) who did the elephant think the panda heard the emu said smells terrible Adjectives (22) Herbert is angry (23) Herbert is angry and furious (24) Herbert is more livid than angry (25) Herbert is more livid and furious than angry Table 1. Sentences used in the XTAG experiment 62 TAL. Volume 44 - n◦3/2003 6. Experimental results We have incorporated the parsing algorithms described in this article into a naive implementation in Prolog of the deductive parsing machine presented in [SHI 95]. As a first experiment, we have compared the performance of the Earley-like parsing algorithms for TIG [SCH 95] and TAG [ALO 99] with respect to TIGs. For this purpose, we have made the experiments on two simple TIGs GL={α, βL}and GR={α, βR} (see Figure 3). For a TIG, the time complexity of the adjunction completion step of a TAG parser is O(n4), in contrast with the O(n3)complexity of left and right adjunction completion for a TIG parser. Therefore, we expected the TIG parser to be considerably faster than the TAG parser. In effect, for GLwe have observed that the TIG parser is up to 18 times faster than the TAG parser, but in the case of GRthe difference becomes irrelevant. These results have been corroborated by a second experiment performed on artificial TAGs with the mixed ( P Mix) and the TAG parser: the performance of the mixed parser improves when strongly left auxiliary trees are involved in the analysis of the input string. In a third experiment, we have taken a subset of the XTAG grammar [DOR 94], consisting of 27 elementary trees that cover a variety of English constructions: relative clauses, auxiliary verbs, unbounded dependencies, extraction, etc. In order to eliminate the time spent by unification, we have not considered the feature structures of elementary trees. Instead, we have simulated the features using local constraints. The set of sentences used in the experiment is shown in table 1. Every sentence has been parsed without previous filtering of elementary trees. First of all, we have implemented a combined parser P Mix1where simultaneous adjunctions are forbidden and we have corroborated the results included in [ALO 02]: the application of the parser P Mix1results in a reduction in time, with respect to classical Earley-like parsers for TAG, that varies in percentage from 31% to 0%, depending on the kind of trees involved in the analysis of each sentence. Then, we have compared the parsers P Mix1, P Mix2and P Mix3to test the benefits of simultaneous adjunctions and preserving the correct prefix property. Table 2 shows the results of this experiment: – The first column is the number of the corresponding sentence in table 1. – The second and third column show the time, in seconds, spent by parsers P Mix1 and P Mix2in the analysis of each sentence, respectively. – The fourth column, labeled ∆12, shows the difference, in percentage, of the time spent by P Mix2with respect to P Mix1. Negative values indicate real improvements. As we can observe, P Mix2obtains a reduction in time that varies in percentage from 46% to 12%, depending on the kind of trees involved in the analysis of each sentence. We would like to address the results obtained by our approach in sentences 12, 13 and 14 where simultaneous adjunctions of left and right auxiliary trees must be applied. In these cases, the parser P Mix1needs to apply a classical wrapping adjunction. Variants of mixed parsing of TAG and TIG 63 – The fifth column shows the time, in seconds, spent by the parser P Mix3for each sentence. – The sixth column, labeled ∆23, shows the difference, in percentage, of the time spent by P Mix3with respect to P Mix2. It is interesting to remark that preserving the correct prefix property increases the computational cost of the parsing process from 11% to 50%. These results suggest that, although the time complexity is in O(n6)for both parsers, some constants involved in the expression of complexity for P Mix3must be greater than the corresponding ones for P Mix2. A detailed examination of the trace of both executions shows that: 1) In the traversal of initial and strongly left and right auxiliary trees, the number of deduction steps applied by both parsers is the same, i.e., all the gain in performance due to considering a part of the grammar as a TIG is attained by P Mix2. 2) In the traversal of wrapping auxiliary trees, the number of deduction steps applied by P Mix3is slightly lower than P Mix2. 3) Independently of the kind of trees involved in the analysis of a sentence, the number of inferences (i.e., the number of CALL and REDO performed by the Prolog interpreter) is higher in P Mix3than in P Mix2, due to the complex checkings performed by Pred1steps. – Finally, the seventh column, labeled ∆13, shows the difference, in percentage, of the time spent by P Mix3with respect to P Mix1. We can observe that P Mix3obtain better results for 76% of the sentences. 7. Conclusion We have defined several parsing algorithms which reduce the practical complexity of TAG parsing by taking into account that a large part of actual TAG grammars can be managed as a TIG. Several approaches has been tried: the first parser forbid simultaneous adjunctions, the second one extends the classical adjunction operation in TAG by considering the possibility of simultaneous adjunctions at a given node, and the third one allows simultaneous adjunctions at the time it preserves the correct prefix property. Practical experiments performed on a subset of the XTAG grammars show that considering simultaneous adjunctions improves highly the parsing efficiency due to a larger number of adjunctions can be managed as TIG adjunctions. In contrast, preserving the correct prefix property in mixed parsers have shown to be of little interest due to the high cost involved by the stronger predictions that must be performed to satisfy such property. The performance of the algorithms could be improved by means of the application of practical optimizations, such as the replacement of the components pand qof items [Nγ→δ•ν, i, j |p, q]∈ I(a) Mix by the list of all adjunctions that are still under com- 64 TAL. Volume 44 - n◦3/2003 Time Time Time Sentence P Mix1 P Mix2∆12 P Mix3∆23 ∆13 (1) 0.13 0.08 -38.46% 0.12 +50.00% +7.69% (2) 0.17 0.11 -35.29% 0.15 +35.36% -11.76% (3) 0.21 0.15 -28.57% 0.20 +33.33% -4.76% (4) 0.18 0.13 -27.78% 0.18 +38.46% -0.00% (5) 0.10 0.07 -30.00% 0.10 +42.85% -0.00% (6) 0.17 0.11 -35.29% 0.16 +45.45% -5.88% (7) 0.10 0.07 -30.00% 0.09 +28.57% -10.00% (8) 0.13 0.08 -38.46% 0.11 +37.05% -15.38% (9) 0.08 0.06 -25.00% 0.08 +33.33% -0.00% (10) 0.21 0.14 -33.33% 0.19 +35.71% -9.52% (11) 0,27 0.20 -25.93% 0.27 +35.00% -0.00% (12) 0,32 0,24 -25.00% 0.36 +50.00% +12.50% (13) 0.28 0.21 -25.00% 0.30 +42.85% +7.14% (14) 0.33 0.29 -12.12% 0.41 +37.93% +24.24% (15) 0.12 0.09 -25.00% 0.11 +22.22% -8.33% (16) 0.12 0.09 -25.00% 0.11 +22.22% -8.33% (17) 0.13 0.07 -46.15% 0.10 +42.85% -23.08% (18) 0.10 0.07 -30.00% 0.09 +28.57% -10.00% (19) 0.32 0.27 -15.63% 0.38 +40.74% +18.75% (20) 0.21 0.12 -42.86% 0.19 +58.33% -9.52% (21) 0.58 0.39 -32.76% 0.59 +51.28% +1.72% (22) 0.09 0.07 -22.22% 0.08 +14.28% -11.11% (23) 0.14 0.09 -35.71% 0.10 +11.11% -28.57% (24) 0.12 0.08 -33.33% 0.11 +25.00% -8.33% (25) 0.13 0.10 -23.08% 0.12 +20.00% -7.69% Table 2. XTAG results, in seconds, for P Mix1and P Mix2and P Mix3parsers pletion on Nγ[CLE 01], albeit this modification increase the worst-case complexity of the algorithm. Acknowledgements: We would like to thank Margarita Alonso for her comments and suggestions. This research has been supported in part by Ministerio de Ciencia y Tecnología (grants TIC2000-0370-C02-01, FIT-150500-2002-416, HP2001-0044 and HF2002-81), Xunta de Galicia (grants PGIDT01PXI10506PN, PGIDIT02SIN01E and PGIDIT03SIN30501PR) and Universidade da Coruña. 8. References [ABE 00] ABEILLÉ A., RAMBOW O., “Tree Adjoining Grammar: an Overview”, ABEILLÉ A., RAMBOW O., Eds., Tree Adjoining Grammars. Formalisms, Linguistic Analysis and Variants of mixed parsing of TAG and TIG 65 Procesing, vol. 107 of CSLI Lecture Notes, chapter 1, p. 1–68, CSLI Publications, Stanford, California, 2000. [ALO 99] ALONSO M., CABRERO D., DE LA CLERGERIE E., VILARES M., “Tabular Algorithms for TAG Parsing”, Proc. of EACL’99, Ninth Conference of the European Chapter of the Association for Computational Linguistics, Bergen, Norway, June 1999, p. 150–157. [ALO 02] ALONSO M., CARRILLO V., DÍAZ V., “Mixed Parsing of Tree Insertion and Tree Adjoining Grammars”, GARIJO F. J., RIQUELME J. C., TORO M., Eds., Advances in Artificial Intelligence - IBERAMIA 2002, vol. 2527 of Lecture Notes in Artificial Intelligence, p. 694–703, Springer-Verlag, Berlin-Heidelberg-New York, 2002. [ALO 03] ALONSO M., DÍAZ V., “Parsing Tree Adjoining Grammars and Tree Insertion Grammars with simultaneous adjunctions”, Proc. of 8th International Workshop on Parsing Technologies (IWPT 2003), p. 19–30, Nancy, France, April 2003. [CLE 01] DE LA CLERGERIE E., “Refining Tabular Parsers for TAGs”, Proceedings of Language Technologies 2001: The Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL’01), CMU, Pittsburgh, PA, USA, June 2001, p. 167–174. [DOR 94] DORAN C., EGEDI D., HOCKEY B. A., SRINIVAS B., ZAIDEL M., “XTAG System — A Wide Coverage Grammar for English”, Proc. of the 15th International Conference on Computational Linguistics (COLING’94), Kyoto, Japan, August 1994, p. 922–928. [JOS 75] JOSHI A. K., LEVY L. S., TAKAHASHI M., “Tree Adjunt Grammars”, Journal of Computer and System Sciences, vol. 10, num. 1, 1975, p. 136–162. [JOS 97] JOSHI A. K., SCHABES Y., “Tree-Adjoining Grammars”, ROZENBERG G., SALOMAA A., Eds., Handbook of Formal Languages. Vol 3: Beyond Words, chapter 2, p. 69–123, Springer-Verlag, Berlin/Heidelberg/New York, 1997. [NED 99] NEDERHOF M.-J., “The Computational Complexity of the Correct-Prefix Property for TAGs”, Computational Linguistics, vol. 25, num. 3, 1999, p. 345–360. [SCH 91] SCHABES Y., “The Valid Prefix Property and Left to Right Parsing of TreeAdjoining Grammar”, Proc. of II International Workshop on Parsing Technologies, IWPT’91, Cancún, Mexico, 1991, p. 21–30. [SCH 95] SCHABES Y., WATERS R. C., “Tree Insertion Grammar: A Cubic-Time Parsable Formalism That Lexicalizes Context-Free Grammar Without Changing the Trees Produced”, Computational Linguistics, vol. 21, num. 4, 1995, p. 479–513, Also as Technical Report TR-94-13, June 1994, Mitsubishi Electric Research Laboratories, Cambridge, MA, USA. [SHI 95] SHIEBER S. M., SCHABES Y., PEREIRA F., “Principles and Implementation of Deductive Parsing”, Journal of Logic Programming, vol. 24, num. 1–2, 1995, p. 3–36. [SIK 97] SIKKEL K., Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms, Texts in Theoretical ComputerScience — An EATCS Series, SpringerVerlag, Berlin/Heidelberg/New York, 1997.