Tabular Algorithms for TAG Parsing

Miguel A. Alonso Departamento de Computación

Univesidad de La Coruña Campus de Elviña s/n

15071 La Coruña

Spain alonso@dc.fi.udc.es

David Cabrero Departamento de Computación

Univesidad de La Coruña Campus de Elviña s/n 15071 La Coruña Spain cabrero@dc.fi.udc.es

Eric de la Clergerie

INRIA Domaine de Voluceau Rocquencourt, B.P. 105 78153 Le Chesnay Cedex

France

Eric.De La Clergerie@inria.fr

Manuel Vilares Departamento de Computación

Univesidad de La Coruña Campus de Elviña s/n 15071 La Coruña Spain vilares@dc.fi.udc.es

Abstract

We describe several tabular algorithms for Tree Adjoining Grammar parsing, creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum.

1 Introduction

Tree Adjoining Grammars are a extension of CFG introduced by Joshi in (Joshi, 1987) that use trees instead of productions as the primary representing structure. Several parsing algorithms have been proposed for this formalism, most of them based on tabular techniques, ranging from simple bottom-up algorithms (Vijay-Shanker and Joshi, 1985) to sophisticated extensions of the Earley’s algorithm (Schabes and Joshi, 1988; Schabes, 1994; Nederhof, 1997). However, it is difficult to inter-relate different parsing algorithms. In this paper we study several tabular algorithms for TAG parsing, showing their common characteristics and how one algorithm can be derived from another in turn, creating a continuum from simple pure bottom-up to complex predictive algorithms.

Formally, a TAG is a 5-tuple G = (V_{N}, V_{T} , S, I, A), where V_{N} is a finite set of non-terminal symbols, V_{T} a finite set of terminal symbols, S the axiom of the grammar, I a finite set of initial trees and A a finite set of auxiliary trees. I ∪A is the set of elementary trees. Internal nodes are labeled by non-terminals and leaf nodes by terminals or ε, 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 elementary tree from the root node to the foot node is called the spine of the tree.

New trees are derived by adjoining: let α be a tree containing a node N^{α} labeled by A and let β be an auxiliary tree whose root and foot nodes are also labeled by A. Then, the adjoining 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 use β ∈ adj(N^{α}) to denote that a tree β may be adjoined at node N^{α} of the elementary tree α.

In order to describe the parsing algorithms for TAG, 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 TAG by considering each elementary tree γ as formed by a set of context-free productions P(γ): a node N^{γ} and its children N_{1}^{γ} … N_{g}^{γ} are 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, except for the case of elements belonging to V_{T} ∪ {ε} in the right-hand side of production. Those elements may not have children and are not candidates to be adjunction nodes, so we identify such nodes labeled by a terminal with that terminal.

To simplify the description of parsing algorithms we consider an additional production ⊤ → R^{α} for each initial tree and the two additional productions ⊤ → R^{β} and F^{β} → ⊥ for each auxiliary tree β, 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.

The relation ⇒ of derivation on P(γ) is defined by δ ⇒ ν if there are δ′, δ′′, M^{γ}, υ such that δ = δ′M^{γ}δ′′, ν = δ′υδ′′ and M^{γ} → υ ∈ P(γ) exists. The reflexive and transitive closure of ⇒ is

denoted ⇒^{∗} .

In a abuse of notation, we also use ⇒^{∗} to represent derivations involving an adjunction. So, δ ⇒^{∗} ν if there are δ′, δ′′, M^{γ}, υ such that δ =

δ′M^{γ}δ′′, R^{β} ⇒^{∗} υ_{1}F^{β}υ_{3}, β ∈ adj(M^{γ}), M^{γ} → υ_{2}

and ν = δ′υ_{1}υ_{2}υ_{3}δ′′ .

Given two pairs (p, q) and (i, j) of integers, (p, q) ≤ (i, j) is satisfied if i ≤ p and q ≤ j. Given two integers p and q we define p ∪ q as p if q is undefined and as q if p is undefined, being undefined in other case.

1.1 Parsing Schemata

We will describe parsing algorithms using Parsing Schemata, a framework for high-level description of parsing algorithms (Sikkel, 1997). An interesting application of this framework is the analysis of the relations between different parsing algorithms by studying the formal relations between their underlying parsing schemata. Originally, this framework was created for context-free grammars but we have extended it to deal with tree adjoining grammars.

A parsing system for a grammar G and string a_{1} … a_{n} is a triple ⟨I, H, D⟩, with I a set of items which represent intermediate parse results, H an initial set of items called hypothesis that encodes the sentence to be parsed, and D a set of deduction steps that allow new items to be derived from already known items. Deduction steps are of the form \frac{η_{1},...,η_{k}}{ξ} cond, meaning that if all antecedents η_{i} of 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.

Parsing schemata are closely related to grammatical deduction systems (Shieber et al., 1995), where items are called formula schemata, deduction steps are inference rules, hypothesis are axioms and final items are goal formulas.

A parsing schema can be generalized from another one using the following transformations (Sikkel, 1997):

• Item refinement, breaking single items into multiple items.

• Step refinement, decomposing a single deduction step in a sequence of steps.

• Extension of a schema by considering a larger class of grammars.

In order to decrease the number of items and deduction steps in a parsing schema, we can apply the following kinds of filtering:

• Static filtering, in which redundant parts are simply discarded.

• Dynamic filtering, using context information to determine the validity of items.

• Step contraction, in which a sequence of deduction steps is replaced by a single one.

The set of items in a parsing system ℙ_{Alg} corresponding to the parsing schema Alg describing a given parsing algorithm Alg is denoted I_{Alg}, the set of hypotheses H_{Alg}, the set of final items F_{Alg} and the set of deduction steps is denoted D_{Alg}.

2 A CYK-like Algorithm

We have chosen the CYK-like algorithm for TAG described in (Vijay-Shanker and Joshi, 1985) as our starting point. Due to the intrinsic limitations of this pure bottom-up algorithm, the grammars it can deal with are restricted to those with nodes having at most two children.

The tabular interpretation of this algorithm works with items of the form

[N^{γ}, i, j | p, q | adj]

such that N^{γ} ⇒^{∗} a_{i+1} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗}

a_{i+1} … a_{j} if and only if (p, q) ≠ (−, −) and N^{γ} ⇒^{∗}

a_{i+1} … a_{j} if and only if (p, q) = (−, −), where N^{γ} is a node of an elementary tree with a label belonging to V_{N}.

The two indices with respect to the input string i and j indicate the portion of the input string that has been derived from N^{γ}. If γ ∈ A, p and q are two indices with respect to the input string that indicate that part of the input string recognized by the foot node of γ. In other case p = q = − representing they are undefined. The element adj indicates whether adjunction has taken place on node N^{γ}.

The introduction of the element adj taking its value from the set {true, false} corrects the items previously proposed for this kind of algorithms in (Vijay-Shanker and Joshi, 1985) in order to avoid several adjunctions on a node. A value of true indicates that an adjunction has taken place in the node N^{γ} and therefore further adjunctions on the same node are 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 an auxiliary tree. As a consequence, only one adjunction can take place on an elementary node, as is prescribed by the tree adjoining grammar formalism (Schabes and Shieber, 1994). As an additional advantage, the algorithm does not need to require the restriction that every auxiliary tree must have at least one terminal symbol in its frontier (Vijay-Shanker and Joshi, 1985).

Schema 1 The parsing system ℙ_{CYK} corresponding to the CYK-like algorithm for a tree adjoining grammar G and an input string a_{1} … a_{n} is defined as follows:

I_{CYK} = { [N^{γ}, i, j | p, q | adj] }

such that N^{γ} ∈ P(γ), label(N^{γ}) ∈ V_{N}, γ ∈ I ∪ A, 0 ≤ i ≤ j, (p, q) ≤ (i, j), adj ∈ {true, false}

H_{CYK} = { [a, i − 1, i] | a = a_{i}, 1 ≤ i ≤ n }

D_{CYK}^{Scan} = \frac{[a, i − 1, i]}{[N^{γ}, i − 1, i | −, − | false]} N^{γ} → a

D_{CYK}^{ε} = \overline{[N^{γ}, i, i | −, − | false]} N^{γ} → ε

D_{CYK}^{Foot} = \overline{[F^{γ}, i, j | i, j | false]}

D_{CYK}^{LeftDom} = \frac{\begin{matrix}[M^{γ}, i, k | p, q | adj], \\ [P^{γ}, k, j | −, − | adj′] \end{matrix}}{[N^{γ}, i, j | p, q | false]}

such that N^{γ} → M^{γ}P^{γ} ∈ P(γ), M^{γ} ∈ spine(γ)

D_{CYK}^{RightDom} = \frac{\begin{matrix}[M^{γ}, i, k | −, − | adj], \\ [P^{γ}, k, j | p, q | adj′] \end{matrix}}{[N^{γ}, i, j | p, q | false]}

such that N^{γ} → M^{γ}P^{γ} ∈ P(γ), P^{γ} ∈ spine(γ)

D_{CYK}^{NoDom} = \frac{\begin{matrix}[M^{γ}, i, k | −, − | adj], \\ [P^{γ}, k, j | −, − | adj′] \end{matrix}}{[N^{γ}, i, j | −, − | false]}

such that N^{γ} → M^{γ}P^{γ} ∈ P(γ), M^{γ}, P^{γ} ∉ spine(γ)

D_{CYK}^{Unary} = \frac{[M^{γ}, i, j | p, q | adj]}{[N^{γ}, i, j | p, q | false]} N^{γ} → M^{γ} ∈ P(γ)

D_{CYK}^{Adj} = \frac{\begin{matrix}[R^{β}, i′, j′ | i, j | adj], \\ [N^{γ}, i, j | p, q | false] \end{matrix}}{[N^{γ}, i′, j′ | p, q | true]}

such that β ∈ A, β ∈ adj(N^{γ})

D_{CYK} = D_{CYK}^{Scan} ∪ D_{CYK}^{ε} ∪ D_{CYK}^{Foot} ∪ D_{CYK}^{LeftDom}∪

D_{CYK}^{RightDom} ∪ D_{CYK}^{NoDom} ∪ D_{CYK}^{Unary} ∪ D_{CYK}^{Adj}

F_{CYK} = { [R^{α}, 0, n | −, − | adj] | α ∈ I }

The hypotheses defined for this parsing system are the standard ones and therefore they will be omitted in the next parsing systems described in this paper.

The key steps in the parsing system ℙ_{CYK} are D_{CYK}^{Foot} and D_{CYK}^{Adj}, which are in charge of the recognition of adjunctions. The other steps are in charge of the bottom-up traversal of elementary trees and, in the case of auxiliary trees, the propagation of the information corresponding to the part of the input string recognized by the foot node.

The set of deductive steps D_{CYK}^{Foot} make it possible to start the bottom-up traversal of each auxiliary tree, as it predict all possible parts of the input string that can be recognized by the foot nodes. Several parses can exist for an auxiliary tree which only differs in the part of the input string which was predicted for the foot node. Not all of them need take part on a derivation, only those with a predicted foot compatible with an adjunction. The compatibility between the adjunction node and the foot node of the adjoined tree is checked by a deductive step D_{CYK}^{Adj}: when the root of an auxiliary tree β has been reached, it checks for the existence of a subtree of an elementary tree rooted by a node N^{γ} which satisfies the following conditions:

1. β can be adjoined on N^{γ}.

2. N^{γ} derives the same part of the input string derived from the foot node of β.

If the conditions are satisfied, further adjunctions on N are forbidden and the parsing process continues a bottom-up traverse of the rest of the elementary tree γ containing N^{γ}.

3 A Bottom-up Earley-like Algorithm

To overcome the limitation of binary branching in trees imposed by CYK-like algorithms, we define a bottom-up Earley-like parsing algorithm for TAG. As a first step we need to introduce the dotted rules into items, which are of the form

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

such that δ ⇒^{∗} a_{i+1} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗}

a_{i+1} … a_{j} if and only if (p, q) ≠ (−, −) and δ ⇒^{∗} a_{i+1} … a_{j} if and only if (p, q) = (−, −).

The items of the new parsing schema, denoted buE_{1}, are obtained by refining the items of CYK. The dotted rules eliminate the need for the element adj indicating whether the node in the lefthand side of the production has been used as adjunction node.

Schema 2 The parsing system ℙ_{buE} corresponding to the bottom-up Earley-like parsing algorithm, given a tree adjoining grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{buE} = [N^{γ} → δ • ν, i, j | p, q]

such that N^{γ} → δν ∈ P(γ), γ ∈ I ∪ A, 0 ≤ i ≤ j, (p, q) ≤ (i, j)

D_{buE}^{Init} = \overline{[N^{γ} → •δ, i, i | −, −]}

D_{buE}^{Foot} = \overline{[F^{β} → ⊥•, i, j | i, j]}

D_{buE}^{Scan} = \frac{\begin{matrix}[N^{γ} → δ • aν, i, j − 1 | p, q], \\ [a, j − 1, j] \end{matrix}}{[N^{γ} → δa • ν, i, j | p, q]}

D_{buE}^{Comp} = \frac{\begin{matrix}[N^{γ} → δ • M^{γ}ν, i, k | p, q], \\ [M^{γ} → υ•, k, j | p′, q′] \end{matrix}}{[N^{γ} → δM^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

D_{buE}^{AdjComp} = \frac{\begin{matrix}[⊤ → R^{β}•, k, j | l, m], \\ [M^{γ} → υ•, l, m | p′, q′], \\ [N^{γ} → δ • M^{γ}ν, i, k | p, q], \end{matrix}}{[N^{γ} → δM^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

such that β ∈ A, β ∈ adj(M^{γ})

D_{buE} = D_{buE}^{Init} ∪ D_{buE}^{Foot} ∪ D_{buE}^{Scan}∪
D_{buE}^{Comp} ∪ D_{buE}^{AdjComp}

F_{buE} = { [⊤ → R^{α}•, 0, n | −, −] | α ∈ I }

The deduction steps of ℙ_{buE} are obtained from the steps in ℙ_{CYK} applying the following refinement:

• LeftDom, RightDom and NoDom deductive steps have been split into steps Init and Comp.

• Unary and ε steps are no longer necessary, due to the uniform treatment of all productions independently of the length of the production.

The algorithm performs a bottom-up recognition of the auxiliary trees applying the steps D_{buE_{1}}^{Comp}. During the traversal of auxiliary trees, information about the part of the input string recognized by the foot is propagated bottom-up. A set of deductive steps D_{buE}^{Init} are in charge of starting the recognition process, predicting all possible start positions for each rule.

A filter has been applied to the parsing system ℙ_{CYK}, contracting the deductive steps Adj and Comp in a single AdjComp, as the item generated by a deductive step Adj can only be used to advance the dot in the rule which has been used to predict the left-hand side of its production.

4 An Earley-like Algorithm

An Earley-like parsing algorithm for TAG can be obtained by incorporating top-down prediction. To do so, two dynamic filters must be applied to ℙ_{buE}:

• The deductive steps in D_{E}^{Init} will only consider productions having the root of an initial tree as left-hand side.

• A new set D_{E}^{Pred} of predictive steps will be in charge of controlling the generation of new items, considering only those new items which are potentially useful for the parsing process.

Schema 3 The parsing system ℙ_{E} corresponding to an Earley-like parsing algorithm for TAG without the valid prefix property, given a tree adjoining grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{E} = I_{buE}

D_{E}^{Init} = \overline{[⊤ → •R^{α}, 0, 0 | −, −]} α ∈ I

D_{E}^{Pred} = \frac{[N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[M^{γ} → •υ, j, j | −, −]}

D_{E}^{AdjPred} = \frac{[N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[⊤ → •R^{β}, j, j | −, −]}

such that β ∈ adj(M^{γ})

D_{E}^{FootPred} = \frac{\begin{matrix}[F^{β} → •⊥, k, k | −, −], \\ [N^{γ} → δ • M^{γ}ν, i, j | p, q] \end{matrix}}{[M^{γ} → •δ, k, k | −, −]}

such that β ∈ adj(M^{γ})

D_{E}^{FootComp} = \frac{\begin{matrix}[M^{γ} → υ•, k, l | p, q], \\ [F^{β} → •⊥, k, k | −, −], \\ [N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[F^{β} → ⊥•, k, l | k, l]}

such that β ∈ adj(M^{γ}), p ∪ p′ and q ∪ q′ are defined

D_{E}^{AdjComp} = \frac{\begin{matrix}[⊤ → R^{β}•, j, m | k, l], \\ [M^{γ} → υ•, k, l | p, q], \\ [N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[N^{γ} → δM^{γ} • ν, i, m | p ∪ p′, q ∪ q′]}

such that β ∈ adj(M^{γ})

D_{E} = D_{E}^{Init} ∪ D_{buE}^{Scan} ∪ D_{E}^{Pred} ∪ D_{buE}^{Comp}∪

D_{E}^{AdjPred} ∪ D_{E}^{FootPred} ∪ D_{E}^{FootComp}∪ D_{E}^{AdjComp}

F_{E} = F_{buE}

Parsing begins by creating the item corresponding to a production having the root of an initial tree as left-hand side and the dot in the leftmost position of the right-hand side. Then, a set of deductive steps D_{E}^{Pred} and D_{E}^{Comp} traverse each elementary tree. A step in D_{E}^{AdjPred} predicts the adjunction of an auxiliary tree β in 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 D_{E}^{FootPred}, 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 D_{E}^{FootComp} re-takes the traversal of β continuing at the foot node. When the traversal of β is completely finished, a deduction step in D_{E}^{AdjComp} checks if the subtree attached to the foot of β corresponds with the adjunction node. With respect to steps in D_{E}^{AdjComp}, p and q are instantiated if and only if the adjunction node is in the spine of γ.

5 The Valid Prefix Property

Parsers satisfying the valid prefix property guarantee that, as they read the input string from left to right, the substrings read so far are valid prefixes of the language defined by the grammar. More formally, a parser satisfies the valid prefix property if for any substring a_{1} … a_{k} read from the input string a_{1} … a_{k}a_{k+1} … a_{n} guarantees that there is a string of tokens b_{1} … b_{m}, where b_{i} need not be part of the input string, such that a_{1} … a_{k}b_{1} … b_{m} is a valid string of the language.

To maintain the valid prefix property, the parser must recognize all possible derived trees in prefix form. In order to do that, two different phases must work coordinately: a top-down phase that expands the children of each node visited and a bottom-up phase grouping the children nodes to indicate the recognition of the parent node (Schabes, 1991).

During the recognition of a derived tree in prefix form, node expansion can depend on adjunction operations performed in the previously visited part of the tree. Due to this kind of dependencies the set path is a context-free language (Vijay-Shanker et al., 1987). A bottom-up algorithm (e.g. CYK-like or bottom-up Earley-like) can stack the dependencies shown by the context-free language defining the path-set. This is sufficient to get a correct parsing algorithm, but without the valid prefix property. To preserve this property the algorithm must have a top-down phase which also stacks the dependencies shown by the language defining the path-set. To transform an algorithm without the valid prefix property into another which preserves it is a difficult task because stacking operations performed during topdown and bottom-up phases must be correlated some way and it is not clear how to do so without augmenting the time complexity (Nederhof, 1997).

CYK-like, bottom-up Earley-like and Earleylike parsing algorithms described above do not preserve the valid prefix property because footprediction (a top-down operation) is not restrictive enough to guarantee that the subtree attached to the foot node really corresponds with a instance of the tree involved in the adjunction.

To obtain a Earley-like parsing algorithm for tree adjoining grammars preserving the valid prefix property we need to refine the items by including a new element to indicate the position of the input string corresponding to the left-most extreme of the frontier of the tree to which the dotted rule in the item belongs:

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

such that R^{γ} ⇒^{∗} a_{h+1} … a_{i}δνυ and δ ⇒^{∗}

a_{i} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗} a_{i} … a_{j} if and only if

(p, q) ≠ (−, −) and δ ⇒^{∗} a_{i} … a_{j} if and only if (p, q) = (−, −).

Thus, an item [N^{γ} → δ • ν, i, j | p, q] of ℙ_{E} corresponds now with a subset of {[h, N^{γ} → δ • ν, i, j | p, q]} for all h ∈ [0, n]. Schema 4 The parsing system ℙ_{Earley} corresponding to a Earley-like parsing algorithm with the valid prefix property, for a tree adjoining grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{Earley} = [h, N^{γ} → δ • ν, i, j | p, q] N^{γ} → δ • ν ∈ P(γ), γ ∈ I ∪ A, 0 ≤ h ≤ i ≤ j, (p, q) ≤ (i, j)

D_{Earley}^{Init} = \overline{⊢ [0, ⊤ → •R^{α}, 0, 0 | −, −]} α ∈ I

D_{Earley}^{Scan} = \frac{\begin{matrix}[h, N^{γ} → δ • aν, i, j − 1 | p, q], \\ [a, j − 1, j] \end{matrix}}{[h, N^{γ} → δa • ν, i, j | p, q]}

D_{Earley}^{Pred} = \frac{[h, N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[h, M^{γ} → •υ, j, j | −, −]}

D_{Earley}^{Comp} = \frac{\begin{matrix}[h, N^{γ} → δ • M^{γ}ν, i, k | p, q], \\ [h, M^{γ} → υ•, k, j | p′, q′] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

D_{Earley}^{AdjPred} = \frac{[h, N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[j, ⊤ → •R^{β}, j, j | −, −]}

such that β ∈ adj(M^{γ})

D_{Earley}^{FootPred} = \frac{\begin{matrix}[j, F^{β} → •⊥, k, k | −, −], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p, q] \end{matrix}}{[h, M^{γ} → •δ, k, k | −, −]}

such that β ∈ adj(M^{γ})

D_{Earley}^{FootComp} = \frac{\begin{matrix}[h, M^{γ} → υ•, k, l | p, q], \\ [j, F^{β} → •⊥, k, k | −, −], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[j, F^{β} → ⊥•, k, l | k, l]}

β ∈ adj(M^{γ}), p ∪ p′ and q ∪ q′ are defined

D_{Earley}^{AdjComp} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, M^{γ} → υ•, k, l | p, q], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p ∪ p′, q ∪ q′]}

such that β ∈ adj(M^{γ})

D_{Earley} = D_{Earley}^{Init} ∪ D_{Earley}^{Scan} ∪ D_{Earley}^{Pred}∪

D_{Earley}^{Comp} ∪ D_{Earley}^{AdjPred} ∪ D_{Earley}^{FootPred}∪

D_{Earley}^{FootComp} ∪ D_{Earley}^{AdjComp}

F_{Earley} = { [0, ⊤ → R^{α}•, 0, n | −, −] | α ∈ I }

Time complexity of the Earley-like algorithm with respect to the length n of input string is O(n^{7}), and it is given by steps D_{Earley}^{AdjComp}. Although 8 indices are involved in a step D_{Earley}^{AdjComp}, partial application allows us to reduce the time complexity to O(n^{7}).

Algorithms without the valid prefix property have a time complexity O(n^{6}) with respect to the length of the input string. The change in complexity is due to the additional index in items of ℙ_{Earley}. That index is needed to check the trees involved in steps D_{Earley}^{FootPred} and D_{Earley}^{FootComp}. In the other steps, that index is only propagated to the generated item. This feature allows us to refine the steps in D_{Earley}^{AdjComp}, splitting them into several steps generating intermediate items without that index. To get a correct splitting, we must first differentiate steps in D_{Earley}^{AdjComp} in which p and q are instantiated from steps in D_{Earley}^{AdjComp} in which p′ and q′ are instantiated. So, we must define two new sets D_{Earley}^{AdjComp^{1}} and D_{Earley}^{AdjComp^{2}} of steps instead of the single set D_{Earley}^{AdjComp}. Additionally, in

steps in D_{Earley}^{AdjComp^{1}} we need to introduce a new item (dynamic filtering) to guarantee the correctness of the steps.

D_{Earley}^{AdjComp^{1}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, M^{γ} → υ•, k, l | p, q], \\ [h, F^{γ} → ⊥•, p, q | p, q], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | −, −] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p, q]}

such that β ∈ adj(M^{γ})

D_{Earley}^{AdjComp^{2}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, M^{γ} → υ•, k, l | −, −], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p′, q′]}

such that β ∈ adj(M^{γ})

D_{Earley} = D_{Earley}^{Init} ∪ D_{Earley}^{Scan} ∪ D_{Earley}^{Pred}∪

D_{Earley}^{Comp} ∪ D_{Earley}^{AdjPred} ∪ D_{Earley}^{FootPred}∪

D_{Earley}^{FootComp} ∪ D_{Earley}^{AdjComp^{1}} ∪ D_{Earley}^{AdjComp^{2}}

Now, we must refine steps in D_{Earley}^{AdjComp^{1}} into

steps in D_{Earley}^{AdjComp^{0}} and D_{Earley}^{AdjComp^{1′}}, and re-

fine steps in D_{Earley}^{AdjComp^{2}} into steps in D_{Earley}^{AdjComp^{0}}

and D_{Earley}^{AdjComp^{2′}}. Correctness of these splittings is guaranteed by the context-free property of TAG (Vijay-Shanker and Weir, 1993) establishing the independence of each adjunction with respect to any other adjunction.

After step refinement, we get the Earley-like parsing algorithm for TAG described in (Nederhof, 1997), which preserves the valid prefix property having a time complexity O(n^{6}) with respect to the input string. In this schema we also need to define a new kind of intermediate pseudo-items

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

such that δ ⇒^{∗} a_{i} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗} a_{i} … a_{j}

if and only if (p, q) ≠ (−, −) and δ ⇒^{∗} a_{i} … a_{j} if and only if (p, q) = (−, −) .

Schema 5 The parsing system ℙ_{Earley} corresponding to a the final Earley-like parsing algorithm with the valid prefix property having time complexity O(n^{6}), for a tree adjoining grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{Earley}^{1} = { [h, N^{γ} → δ • ν, i, j | p, q] }

such that N^{γ} → δ • ν ∈ P(γ), γ ∈ I ∪ A, 0 ≤ h ≤ i ≤ j, (p, q) ≤ (i, j)

I_{Earley}^{2} = { [[N^{γ} → δ • ν, i, j | p, q]] }

such that N^{γ} → δ • ν ∈ P(γ), γ ∈ I ∪ A, 0 ≤ i ≤ j, (p, q) ≤ (i, j)

I_{Earley} = I_{Earley}^{1} ∪ I_{Earley}^{2}

D_{Earley}^{Init} = \overline{⊢ [0, ⊤ → •R^{α}, 0, 0 | −, −]} α ∈ I

D_{Earley}^{Scan} = \frac{\begin{matrix}[h, N^{γ} → δ • aν, i, j − 1 | p, q], \\ [a, j − 1, j] \end{matrix}}{[h, N^{γ} → δa • ν, i, j | p, q]}

D_{Earley}^{Pred} = \frac{[h, N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[h, M^{γ} → •υ, j, j | −, −]}

D_{Earley}^{Comp} = \frac{\begin{matrix}[h, N^{γ} → δ • M^{γ}ν, i, k | p, q], \\ [h, M^{γ} → υ•, k, j | p′, q′] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

D_{Earley}^{AdjPred} = \frac{[h, N^{γ} → δ • M^{γ}ν, i, j | p, q]}{[j, ⊤ → •R^{β}, j, j | −, −]}

such that β ∈ adj(M^{γ})

D_{Earley}^{FootPred} = \frac{\begin{matrix}[j, F^{β} → •⊥, k, k | −, −], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p, q] \end{matrix}}{[h, M^{γ} → •δ, k, k | −, −]}

such that β ∈ adj(M^{γ})

D_{Earley}^{FootComp} = \frac{\begin{matrix}[h, M^{γ} → δ•, k, l | p, q], \\ [j, F^{β} → •⊥, k, k | −, −], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[j, F^{β} → ⊥•, k, l | k, l]}

such that β ∈ adj(M^{γ}), p ∪ p′ and q ∪ q′ are defined

D_{Earley}^{AdjComp^{0}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, M^{γ} → δ•, k, l | p, q], \end{matrix}}{[[M^{γ} → δ•, j, m | p, q]]}

such that β ∈ adj(M^{γ})

D_{Earley}^{AdjComp^{1′}} = \frac{\begin{matrix}[[M^{γ} → δ•, j, m | p, q]], \\ [h, F^{γ} → ⊥•, p, q | p, q], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | −, −] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p, q]}

such that β ∈ adj(M^{γ})

D_{Earley}^{AdjComp^{2′}} = \frac{\begin{matrix}[[M^{γ} → δ•, j, m | −, −]], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p, q] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p, q]}

such that β ∈ adj(M^{γ})

D_{Earley} = D_{Earley}^{Init} ∪ D_{Earley}^{Scan} ∪ D_{Earley}^{Pred}∪

D_{Earley}^{Comp} ∪ D_{Earley}^{AdjPred} ∪ D_{Earley}^{FootPred}∪

D_{Earley}^{FootComp} ∪ D_{Earley}^{AdjComp^{0}}∪
D_{Earley}^{AdjComp^{1′}} ∪ D_{Earley}^{AdjComp^{2′}}

F_{Earley} = { [0, ⊤ → R^{α}•, 0, n | −, −] | α ∈ I }

6 Conclusion

We have described a set of parsing algorithms for TAG creating a continuum which has the CYK-like parsing algorithm by (Vijay-Shanker and Joshi, 1985) as its starting point and the Earley-like parsing algorithm by (Nederhof, 1997) preserving the valid prefix property with time complexity O(n^{6}) as its goal. As intermediate algorithms, we have defined a bottom-up Earley-like parsing algorithm and an Earley-like parsing algorithm without the valid prefix property, which to our knowledge has not been previously described in literature^{1}. We have also shown how to transform one algorithm into the next using simple transformations.Other algorithms could also has been included in the continuum, but for reasons of space we have chosen to show only the algorithms we consider milestones in the development of parsing algorithms for TAG.

An interesting project for the future will be to translate the algorithms presented here to several proposed automata models for TAG which have an associated tabulation technique: Strongly Driven 2–Stack Automata (de la Clergerie and Alonso, 1998), Bottom-up 2–Stack Automata (de la Clergerie et al., 1998) and Linear Indexed Automata (Nederhof, 1998).

7 Acknowledgments

This work has been partially supported by FEDER of European Union (Grant 1FD97-0047-C04-02) and Xunta de Galicia (Grant XUGA20402B97).

References

Eric de la Clergerie and Miguel A. Alonso. 1998. A tabular interpretation of a class of 2-Stack Automata. In COLING-ACL’98, 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Proceedings of the Conference, volume II, pages 1333–1339, Montreal, Quebec, Canada, August. ACL.

Eric de la Clergerie, Miguel A. Alonso, and David Cabrero. 1998. A tabular interpretation of bottom-up automata for TAG. In Proc. of Fourth International Workshop on Tree-Adjoining Grammars and Related Frameworks (TAG+4), pages 42–45, Philadelphia, PA, USA, August.

Aravind K. Joshi. 1987. An introduction to tree adjoining grammars. In Alexis Manaster-Ramer, editor, Mathematics of Language, pages 87–115. John Benjamins Publishing Co., Amsterdam/Philadelphia.

Mark-Jan Nederhof. 1997. Solving the correctprefix property for TAGs. In T. Becker and H.-V. Krieger, editors, Proc. of the Fifth Meeting on Mathematics of Language, pages 124– 130, Schloss Dagstuhl, Saarbruecken, Germany, August.

Mark-Jan Nederhof. 1998. Linear indexed automata and tabulation of TAG parsing. In Proc. of First Workshop on Tabulation in Parsing and Deduction (TAPD’98), pages 1–9, Paris, France, April.

Yves Schabes and Aravind K. Joshi. 1988. An Earley-type parsing algorithm for tree adjoining grammars. In Proc. of 26th Annual Meeting of the Association for Computational Linguistics, pages 258–269, Buffalo, NY, USA, June. ACL.

Yves Schabes and Stuart M. Shieber. 1994. An alternative conception of tree-adjoining derivation. Computational Linguistics, 20(1):91–124.

Yves Schabes. 1991. The valid prefix property and left to right parsing of tree-adjoining grammar. In Proc. of II International Workshop on Parsing Technologies, IWPT’91, pages 21–30, Cancún, Mexico.

Yves Schabes. 1994. Left to right parsing of lexicalized tree-adjoining grammars. Computational Intelligence, 10(4):506–515.

Stuart M. Shieber, Yves Schabes, and Fernando C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24(1&2):3–36, July-August.

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

K. Vijay-Shanker and Aravind K. Joshi. 1985. Some computational properties of tree adjoining grammars. In 23rd Annual Meeting of the Association for Computational Linguistics, pages 82–93, Chicago, IL, USA, July. ACL.

K. Vijay-Shanker and David J. Weir. 1993. Parsing some constrained grammar formalisms. Computational Linguistics, 19(4):591–636.

K. Vijay-Shanker, David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proc. of the 25th Annual Meeting of the Association for Computational Linguistics, pages 104–111, Buffalo, NY, USA, June. ACL.

1Other different formulations of Earley-like parsing algorithms for TAG has been previously proposed, e.g. (Schabes, 1991).