Workshop TAG+5, Paris, 25-27 May 2000

Bidirectional parsing of TAG without heads

Víctor J. Díaz^{†}, Miguel A. Alonso^{‡} and Vicente Carrillo^{†}

†Facultad de Informática y Estadística, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla (Spain)

                     {vjdiaz,carrillo}@lsi.us.es

‡Departamento de Computación, Universidad de La Coruña Campus de Elviña s/n, 15071 La Coruña (Spain)

                         alonso@dc.fi.udc.es

Abstract

We present a bottom-up bidirectional parser for Tree Adjoining Grammars that is an extension of the parser defined by De Vreught and Honig for Context Free Grammars. Although this parser does not improve the complexity of the parsers defined in the literature, it presents several characteristics that can be of interest for practical parsing of natural languages.

1. Introduction

Víctor J. Díaz, Miguel A. Alonso & Vicente Carrillo

Several algorithms have been proposed for parsing tree adjoining grammars (TAGs), most of them derived from context-free tabular parsers, ranging from simple bottom-up algorithms, like CYK, to sophisticated extensions of Earley’s algorithm (Alonso et al., 1999). However, some of the bidirectional parsers proposed are not applicable in all the cases. Lavelli and Satta parser (1991) is restricted to elementary trees with only one anchor. Van Noord parser (1994) introduces several improvements to Lavelli and Satta parser: the substitution operation, the foot-driven recognition of auxiliary trees and the notion of headed elementary trees in order to take advantage of lexicalization. According to Van Noord, a headed TAG is a TAG in which each elementary tree is a headed tree. For each internal node in a headed tree, there must be a daughter which is the head of the subtree rooted in that node. The reflexive and transitive closure of the head relation is called the headcorner relation. In order to establish the head-corner relation we must fulfill the following two constraints: (i) the anchor of an initial tree must be a head-corner of the root node of the initial tree and (ii) the foot node of an auxiliary tree must be head-corner of the root of the auxiliary tree. Since there exists the notion of anchor in the context of lexicalized TAG, it seems that the notion of head, as defined by Van Noord, is redundant. Moreover, in the case of anchor siblings the definition of head requires to select only one anchor as the head. In this paper we present a bidirectional bottom-up parser for TAG, called dVH, derived from the context-free parser defined by de Vreught and Honig (de Vreught & Honig, 1989; Sikkel, 1997), which presents several interesting characteristics: (i) the bidirectional strategy allows us to implement the recognition of the adjoining operation in a simple way, (ii) the bottomup behavior allows us to take advantage of lexicalization, reducing the number of trees under consideration during the parsing process, (iii) in the case of ungrammatical input sentences, the parser is able to recover most of partial parsings according to lexical entries, and (iv) the parser can be applied to every kind of anchored elementary trees without introducing the notion of head 1.1. Notation Let G = (V_{T} , V_{N}, S, I, A) be a TAG where V_{T} and V_{N} are the terminal and non-terminal alphabets, S ∈ V_{N} the axiom symbol, and I and A the set of initial and auxiliary trees respectively. As usual, I ∪ A consist of the set 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 TAG by considering each elementary tree γ as formed by a set of context-free productions P(γ): a node N^{γ} in γ and its g children N_{1}^{γ} … N_{g}^{γ} are represented by a production N^{γ} → N_{1}^{γ} … N_{g}^{γ}. The elements of the productions are the nodes of the tree, except for the case of elements belonging to V_{T} ∪{ε} in the right-hand side of productions. Those elements may not have children and are not candidates to be adjunction nodes, so we identify such nodes labeled by a terminal or ε with the label^{1}. We use β ∈ adj(N^{γ}) to denote that β ∈ A may be adjoined at node N^{γ}. If adjunction is not mandatory at N^{γ}, then nil ∈ adj(N^{γ}). With respect to substitution, we use α ∈ sub(M^{γ}) to denote that α ∈ I can be substituted at node M^{γ}. To simplify the description of parsing algorithms we consider additional productions: ⊤ → R^{α}, ⊤ → R^{β} and F^{β} → ⊥ for each α ∈ I and each β ∈ A, where R^{α} is the root node of α and R^{β} and F^{β} are the root node and foot node of β, respectively. After disabling ⊤ and ⊥ as adjunction nodes the generative capability of the grammars remains intact.

2. The parser dVH

The definition of the parser is based on deductive systems similar to Parsing Schemata (Sikkel, 1997). Given the input string w = a_{1} … a_{n} with n ≥ 0 and a TAG grammar, the formulas (called items in this context) in the deductive system will be of the form:

[N^{γ} → ν • δ • ω, i, j, p, q]

where N^{γ} → νδω ∈ P (γ) is a production decorated with two dots indicating the part of the subtree dominated by N^{γ} that has been recognized. When ν and ω are both empty, the whole subtree has been recognized. The two indices i and j denote the substring of w spanned by δ. If γ ∈ A, p and q are two indices with respect to w indicating the substring spanned by the foot node of γ. In other case p = q = −, representing they are undefined. With respect to deduction steps, we have that

D_{dVH} = D_{dVH}^{Ini} ∪ D_{dVH}^{ε} ∪ D_{dVH}^{Inc} ∪ D_{dVH}^{Conc} ∪ D_{dVH}^{Foot} ∪ D_{dVH}^{Adj} ∪ D_{dVH}^{Subs}

The initializer steps deduce those items associated to productions whose right hand side includes a terminal that matches with an input symbol. The position of the terminal in the input string determines the values of the indices. Empty-productions are considered to match any position in the input string. The indices associated to the foot node in the consequent of both deduction steps are undefined since no foot has been recognized yet:

D_{dVH}^{Ini} = \overline{[N^{γ} → ν • a • ω, j − 1, j, −, −]} a = a_{j}
D_{dVH}^{ε} = \overline{[N^{γ} → ••, j, j, −, −]}

Bidirectional parsing of TAG without heads

Once the subtree dominated by a node M^{γ} has been recognized completely, a include step in D_{dVH}^{Inc} continues the bottom-up recognition of the supertree dominated by M^{γ} when no adjoining is mandatory on that node. Indexes are not modified when a step of this type is applied:

1Without lost of generality, we assume that if a node is labeled by ε then it has no siblings.

D_{dVH}^{Inc} = \frac{[M^{γ} → •δ•, i, j, p, q]}{[N^{γ} → ν • M^{γ} • ω, i, j, p, q]} nil ∈ adj(M^{γ})

Given a node N^{γ} such that N^{γ} → νδ_{1}δ_{2}ω, the concatenate steps in D_{dVH}^{Conc} try to combine two partial analysis spanning consecutive parts of the input string, in order to recognize δ_{1} and δ_{2}. The indices i and j in the consequent cover the whole recognized substring. The values of the indices p and q, corresponding to the foot node, are propagated bottom-up:

D_{dVH}^{Conc} = \frac{\begin{matrix}[N^{γ} → ν • δ_{1} • δ_{2}ω, i, j′, p, q], \\ [N^{γ} → νδ_{1} • δ_{2} • ω, j′, j, p′, q′] \end{matrix}}{[N^{γ} → ν • δ_{1}δ_{2} • ω, i, j, p ∪ p′, q ∪ q′]}

where p ∪ q is equal to p if q is undefined and is equal to q if p is undefined, being undefined in other case. The foot steps D_{dVH}^{Foot} introduce in a bottom-up way a new instance of an auxiliary tree β in an adjunction node M^{γ} where β ∈ Adj(M^{γ}). The recognition of the auxiliary tree begins with the introduction of the foot node. The string spanned by the node M^{γ} between position k and l determines the values of the indices in the consequent. The indices p and q in the antecedent are ignored in the consequent because a new adjoining has been introduced. The values of these indices will be considered by adjoining steps in order to conclude the adjoining of β in M^{γ}:

D_{dVH}^{Foot} = \frac{[M^{γ} → •δ•, k, l, p, q]}{[F^{β} → •⊥•, k, l, k, l]} β ∈ adj(M^{γ})

When the recognition of the auxiliary tree β reaches the root node, the adjoining steps D_{dVH}^{Adj} conclude the adjoining on M^{γ}, continuing the bottom-up recognition of the supertree of γ with respect to M^{γ}. This step is only applied when the string spanned by the foot node of β is equal to the string spanned by the adjunction node M^{γ}. Indices p and q in the consequent are obtained from the antecedent associated to the adjunction node. Now, the string spanned by the adjunction node M^{γ} corresponds with the string spanned by the root of the auxiliary tree β:

D_{dVH}^{Adj} = \frac{\begin{matrix}[⊤ → •R^{β}•, j, m, k, l], \\ [M^{γ} → •δ•, k, l, p, q] \end{matrix}}{[N^{γ} → ν • M^{γ} • ω, j, m, p, q]} β ∈ adj(M^{γ})

A substitution is performed when an initial tree α has been completely recognized. The initial tree establishes the string spanned by the node M^{γ} where α can be substituted.

D_{dVH}^{Subs} = \frac{[⊤ → •R^{α}•, i, j, −, −]}{[N^{γ} → ν • M^{γ} • ω, i, j, −, −]} α ∈ sub(M^{γ})

The input string must belong to the language defined by the grammar, given α ∈ I rooted with the axiom symbol, whenever an item [⊤ → •R^{α}•, 0, n, −, −] is deduced. The algorithm so described is just a recognizer. However, it is not difficult to construct an actual chart parser based on the specification presented above. From the set of derived items (the chart), a parser of the input can be constructed retracing the recognition steps in reverse order or annotating the items computed by the recognition algorithm with information about how they were obtained. The time complexity of the algorithm with respect to the length n of the input is O(n^{6}). This complexity is due to deduction steps in D_{dVH}^{Adj} since they present the maximum number of relevant input variables (j, m, k, l, p, q). The space-complexity of the parser is O(n^{4}) since every item is composed of four input positions ranging on the length of the input string.

The number of items deduced by the parser, as stated before, can be reduced if we apply a filter on the concatenate steps. We can note that these steps produce redundant derivations when the trees are not binary branching. If we do so, the parser obtained will not actually be bidirectional. We will not consider this version because of clarity in the exposition.

3. A new parser dVH′

In the context of parsing lexicalized grammars for natural languages, the parser dVH can be slightly modified in order to speed up the recognition process. In this way, we will consider the characteristics of the English grammar defined in (XTAG, 1999). The study will be mainly centered on D_{dVH}^{Init}, D_{dVH}^{ε} and D_{dVH}^{Subs} deduction steps. We will call dVH′ the new parser obtained after modifications. First of all, we must note that D_{dVH}^{Init} steps can be applied on anchors as well. In the case of multi-anchors, the step will deduce one item for every anchor in the elementary tree with the suitable positions respect to the input. Furthermore, this step implies an important reduction in the search space since only those elementary trees with anchors matching the input will be consider in the recognition. In this way, D_{dVH}^{Foot} and D_{dVH}^{Subs} deduction steps will not introduce any elementary tree except for those trees considered by D_{dVH}^{Init} deduction steps. When substitution nodes are siblings of no-substitution nodes the application of D_{dVH}^{Subs} steps can introduce items that are not necessary in order to recognize the input string. The reason is that D_{dVH}^{Subs} deduction steps always try to include an initial tree when this tree is completed. To avoid these redundant substitution operations we can introduce a filter as follows: this step will only applied when M^{γ} is a substitution node whose daughters do not dominate a terminal or the foot node of γ. In other cases, the substitution operation will be performed by the new deduction steps D_{dVH}^{SubsR} and D_{dVH}^{SubsL}.

D_{dVH′}^{SubsR} = \frac{\begin{matrix}[⊤ → •R^{α}•, j, k, −, −], \\ [N^{γ} → ν • δ • M^{γ}ω, i, j, p, q] \end{matrix}}{[N^{γ} → ν • δM^{γ} • ω, i, k, p, q]}

D_{dVH′}^{SubsL} = \frac{\begin{matrix}[⊤ → •R^{α}•, i, j, −, −], \\ [N^{γ} → νM^{γ} • δ • ω, j, k, j, p, q] \end{matrix}}{[N^{γ} → ν • M^{γ}δ • ω, i, k, p, q]}

With respect to ε productions, the number of items deduced by D_{dVH}^{ε} steps can be an important drawback in the application of the parser when the grammar has a lot of elementary trees with ε productions. As an example, in the English grammar (XTAG, 1999), it is usual that left hand sides of empty productions present a null adjoining constraint. The practical behavior of the parser can be improved if we filter the steps dealing with empty productions. Given a production M^{γ} → ε such that {nil} = adj(M^{γ}), where {nil} = adj(M^{γ}) represents a nulladjoining constraint on M^{γ} and M^{γ} has at least a daughter that dominates a terminal or the foot node of γ, the following deduction steps

D_{dVH′}^{εR} = \frac{[N^{γ} → ν • δ • M^{γ}ω, i, j, p, q]}{[N^{γ} → ν • δM^{γ} • ω, i, j, p, q]}

D_{dVH′}^{εL} = \frac{[N^{γ} → νM^{γ} • δ • ω, i, j, p, q]}{[N^{γ} → ν • M^{γ}δ • ω, i, j, p, q]}

drastically reduce the number of items generated. When the above constraints are not satisfied, a D_{dVH}^{ε} step must be applied.

Input dVH dVH′ VN E Ned

Transitives and Ditransitives

1  0.16 0.05 0.10 0.33 0.33
2  0.27 0.05 0.16 0.38 0.44

Arguments and Adjuncts

3  0.38 0.11 0.22 0.49 0.55
4  0.33 0.05 0.16 0.44 0.49
5  0.16 0.01 0.05 0.27 0.33

Ergatives and Intransitives

6  0.33 0.11 0.22 0.38 0.44
7  0.16 0.05 0.11 0.27 0.27
8  0.16 0.05 0.11 0.33 0.33
9  0.16 0.05 0.11 0.27 0.27

Sentential Complements

10  0.16 0.05 0.11 0.55 0.44
11  0.22 0.05 0.17 0.66 0.49

Relative Clauses

12  0.60 0.16 0.38 0.77 0.88
13  0.55 0.16 0.38 0.66 0.77

Input dVH dVH′ VN E Ned

Auxiliary Verbs

14  0.60 0.22 0.44 0.66 0.77

Extraction

15  0.16 0.05 0.16 0.33 0.33
16  0.22 0.05 0.11 0.33 0.33
17  0.16 0.05 0.11 0.38 0.33

Unbounded Dependencies

18  0.22 0.05 0.11 0.22 0.27
19  0.39 0.11 0.22 0.71 0.61
20  0.28 0.11 0.16 0.55 0.49
21  0.82 0.16 0.49 1.54 1.26

Adjectives

22  0.11 0.05 0.05 0.22 0.27
23  0.16 0.05 0.11 0.27 0.27
24  0.22 0.05 0.11 0.27 0.27
25  0.33 0.05 0.16 0.33 0.33

Table 1: Parsing time in seconds

4. Experimental results

The results we are going to discuss have been obtained using a naive implementation in Prolog of the deductive parsing machine presented in (Shieber et al., 1995) running on a Pentium II. We have implemented and tested the following parsers: E is an Earley-based parser without prefix valid property (Alonso et al., 1999), Ned is an Earley-based parser with prefix valid property (Nederhof, 1999), VN is the bidirectional parser defined by Van Noord, and dVH and dVH′ are the parsers defined in this paper.

The study is based on the English grammar presented in (XTAG, 1999). >From this document we have selected a subset of the grammar consisting of 27 elementary trees that cover a variety of English constructions: relative clauses, auxiliary verbs, unbounded dependencies, extraction, etc. In order to compare only the behavior of the parsers, we have not consider the feature structures of elementary trees. In this way, we have simulated the features using local constraints. Also, we have selected from the document 25 correct and incorrect sentences grouped with respect to the aspect treated. Every sentence has been parsed without previous filtering of elementary trees. Table 1 shows the time in seconds used for every algorithm and sentence.

From table 1, we can observe that VN, dVH and dVH′ obtain better time results than predictive parsers E and Ned. However, in terms of the more expensive step, the adjoining operation, predictive parsers perform equal or less adjoining operations than bottom-up parsers. Therefore, we can argue that this result is a consequence of the implicit filtering of elementary trees of bottom-up strategies.

On the other hand, we can also note that although dVH presents worse time than VN, we can see dVH′ improves the results of VN. Since the adjoining operations performed by all the bottom-up parsers are practically the same, we can conclude that this improvement is basically due to the reduction of items removed by the filter in the rules related to ε productions.

5. Conclusion

A bottom-up bidirectional parser for TAG has been defined based on the parser defined by De Vreught and Honig for CFG. The parser does not improve the worst-case bounds of already known parsing methods for TAG but the experiments show similar or better time results than classical parsers. Other benefits can be argued to consider this algorithm of interest in the context of bidirectional parsers. In particular, with respect to Lavelli-Satta parser the dVH schema can be applied to multi-anchor auxiliary trees. With respect to Van Noord parser, this new approach does not introduce the concept of head and it is applicable to every kind of anchored elementary tree. As further work, it would be interesting to investigate the effects of compacting elementary trees, as performed by Lopez (2000), in the real performance of the parser.

6. Acknowledgments

This research was partially supported by the FEDER of EU (Grant 1FD97-0047-C04-02) and Xunta de Galicia (Grant PGIDT99XI10502B).

References

Alonso M. A., Cabrero D., de la Clergerie E. & Vilares M. (1999). Tabular algorithms for TAG parsing. In Proc. of EACL’99, Ninth Conference of the European Chapter of the Association for Computational Linguistics, p. 150–157, Bergen, Norway: ACL.

de Vreught J. P. M. & Honig H. J. (1989). A Tabular Bottom-up Recognizer. Technical Report 89-78, Department of Applied Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands.

Lavelli A. & Satta G. (1991). Bidirectional parsing of lexicalized tree adjoining grammars. In Proceedings of the 5th Conference of the European Chapter of the Association for Computational Linguistics (EACL’91), Berlin, Germany: ACL.

Lopez P. (2000). Extended partial parsing for lexicalized tree grammars. In Proc. of the Sixth International Workshop on Parsing Technologies (IWPT 2000), p. 159–170, Trento, Italy.

Nederhof M.-J. (1999). The computational complexity of the correct-prefix property for TAGs. Computational Linguistics, 25 (3), p. 345–360.

Shieber S. M., Schabes Y. & Pereira F. (1995). Principles and implementation of deductive parsing. Journal of Logic Programming, 24 (1–2), p. 3–36.

Sikkel K. (1997). Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms. Texts in Theoretical Computer Science — An EATCS Series. Berlin/Heidelberg/New York: Springer-Verlag.

van Noord G. (1994). Head-corner parsing for TAG. Computational Intelligence, 10 (4), p. 525–534.

The XTAG Research Group (1999). A lexicalized tree adjoining grammar for English. http: //www.cis.upenn.edu/~xtag. Technical Report IRCS 95-03, IRCS, Institute for Research in Cognitive Science, University of Pennsylvania