A BIDIRECTIONAL BOTTOM-UP PARSER FOR TAG ^{∗}

Víctor J. Díaz Vicente Carrillo

Dpto. de Lenguajes y Sistemas Informáticos, Universidad de Sevilla

Avda. Reina Mercedes s/n, 41012 Sevilla (Spain)

{vjdiaz,carrillo}@lsi.us.es

Miguel A. Alonso 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

1 Introduction

Several parsing algorithms have been proposed for Tree Adjoining Grammars (TAGs), most of them derived from context-free tabular parsers [1]. However, only a few bidirectional parsing algorithms have been proposed [3, 5] although this kind of strategy seems to be naturally adapted for TAG. In this paper, we present a new bidirectional bottom-up parser for TAG derived from the context-free parser defined by de Vreught and Honig [4], which has several interesting characteristics: (i) the bidirectional strategy allow us to implement the recognition of the adjoining operation in a simple way, (ii) the bottom-up behavior allow us to take advantage of lexicalization, reducing the number of trees under consideration during the parsing process, and (iii) in the case of ungrammatical input sentences, the parser is able to recover most of partial parsings according to lexical entries.

2 The parser

A Tree Adjoining Grammar is a 5-tuple G = (V_{N}, V_{T} , S, I, A), where V_{N} and V_{T} are finite sets of non-terminal and terminal symbols, S the axiom of the grammar, and I and A are finite sets of initial trees and auxiliary trees, respectively. I ∪ A is the set of elementary trees. The reader is referred to [2] for details in the definition and properties of TAGs. Given an elementary tree γ, a node N^{γ} and its g children N_{1}^{γ} … N_{g}^{γ} are represented by a production N^{γ} → N_{1}^{γ} … N_{g}^{γ}. P(γ) is the set of productions formed in such a way for every node in γ. Terminal symbols and ε will be represented in the productions with the proper symbol. Also, we consider additional productions: ⊤ → R^{α}, ⊤ → R^{β} and F^{β} → ⊥ for each initial tree α and each auxiliary tree β, where R^{α} is the root node of α and R^{β} and F^{β} are the root node and foot node of β, respectively. The nodes ⊤ and ⊥ are considered no-adjoining nodes.

We will define the parser using the Parsing Schemata framework [4]. To this end, we assume the reader is familiar with this kind of parser specification. Let be the input string w = a_{1} … a_{n} with n ≥ 0, the parser works with items [N^{γ} → ν • δ • ω, i, j, p, q], where N^{γ} → νδω ∈ P(γ) is 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 indicate that part of w spanned by δ. If γ ∈ A, the indices p and q indicate that part of w spanned by the foot node of γ. In other case p = q = −, representing they are undefined.

∗This work was partially supported by the FEDER of EU (project 1FD97-0047-C04-02) and Xunta de Galicia (projects PGIDT99XI10502B and XUGA20402B97).

The deduction steps of the parser are the following:

D^{Ini} = \frac{[a, j − 1, j]}{[N^{γ} → ν • a • ω, j − 1, j, −, −]} D^{ϵ} = \overline{[N^{γ} → ••, j, j, −, −]} D^{Inc} = \frac{[M^{γ} → •δ•, i, j, p, q]}{[N^{γ} → ν • M^{γ} • ω, i, j, p, q]} D^{Con} = \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′]}

D^{Foot} = \frac{[M^{γ} → •δ•, k, l, p, q]}{[F^{β} → •⊥•, k, l, k, l]}

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

The steps D^{Init} and D^{ϵ} are the initializer deduction steps in charge of starting the parsing process. The steps D^{Inc} and D^{Con} traverse elementary trees when no adjoining is performed. Finally, given β ∈ adj(M^{γ}), the steps D^{Foot} and D^{Adj} are used to recognize the adjoining operation, 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.

Given α ∈ I, the input string w belongs to the language defined by the grammar when an item [⊤ → •R^{α}•, 0, n, −, −] is deduced. 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 adjoining step since presents the maximum number of relevant input variables (j, m, k, l, p, q). With respect to the size of the grammar, the time-complexity is O(|G|^{2}), since at most two elementary trees are simultaneously considered in a single step. 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.

References

[1] Alonso, M. A., D. Cabrero, E. de la Clergerie and M. Vilares. 1999. Tabular algorithms for TAG parsing. Proc. of EACL’99, pages 150–157, Bergen, Norway.

[2] Joshi, A. K. and Y. Schabes. 1997. Tree-adjoining grammars. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages. Vol 3: Beyond Words, chapter 2, pages 69–123. Springer-Verlag, Berlin/Heidelberg/New York.

[3] Lavelli, A. and G. Satta. 1991. Bidirectional parsing of lexicalized tree adjoining grammars. Proc. of EACL’91, Berlin, Germany.

[4] Sikkel, K. 1997. Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms. Springer-Verlag, Berlin/Heidelberg/New York.

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