NEW TABULAR ALGORITHMS FOR LIG PARSING

Miguel A. Alonso Jorge Graña Manuel Vilares Departamento de Computación Universidad de La Coruña Campus de Elviña s/n 15071 La Coruña (Spain)

{alonso,grana,vilares}@dc.fi.udc.es

Eric de la Clergerie

INRIA Domaine de Voluceau Rocquecourt, B.P. 105 78153 Le Chesnay (France)

Eric.De La Clergerie@inria.fr

Abstract We develop a set of new tabular parsing algorithms for Linear Indexed Grammars, including bottom-

up algorithms and Earley-like algorithms with and without the valid prefix property, creating a continuum in which one algorithm can in turn be derived from another. The output of these algorithms is a shared forest in the form of a context-free grammar that encodes all possible derivations for a given input string.

1 Introduction

Tree Adjoining Grammars (TAG) [8] and Linear Indexed Grammars (LIG) [7] are extensions of Context Free Grammars (CFG). Tree adjoining grammars use trees instead of productions as primary representing structure and seems to be adequate to describe syntactic phenomena occurring in natural language, due to their extended domain of locality and to their ability for factoring recursion from the domain of dependencies. Linear indexed grammars associate a stack of indices with each non-terminal symbol, with the restriction that the indices stack of the head non-terminal of each production (the father) can be inherited by at most one body non-terminal (the dependent child) while the other stacks must have a bounded stack size.

Several parsing algorithms have been proposed for TAG, ranging from simple bottom-up algorithms, like CYK [17], to sophisticated extensions of the Earley’s algorithm [9]. In order to improve efficiency, it is usual to translate the source tree adjoining grammar into a linear indexed grammar [16, 12, 13, 17]. However, in some cases is not possible to translate the parsing strategy from TAG to LIG, as there are parsing strategies for TAG which are not incorporated in any parsing algorithm for LIG. To eliminate this drawback, we present in this paper several parsing algorithms for LIG which mimic the most popular parsing strategies for TAG [1].

1.1 Linear Indexed Grammars

A linear indexed grammar is a tuple (V_{T} , V_{N}, V_{I}, P, S), where V_{T} is a finite set of terminals, V_{N} a finite set of non-terminals, V_{I} is a finite set of indices, S ∈ V_{N} is the start symbol and P is a finite set of productions. Following [7] we consider productions in which at most one element can be pushed on or popped from a stack of indices:

A_{0}[∘∘γ] → A_{1}[ ] … A_{i−1}[ ] A_{i}[∘∘γ′] A_{i−1}[ ] … A_{m}[ ]
A_{0}[ ] → a

where m is the length of the production, A_{j} ∈ V_{N} for each 0 ≤ j ≤ m, A_{i} is the dependent child, ∘∘ is the part of the indices stack transmitted from the father to the dependent child, γ, γ′ ∈ V_{I} ∪ {ϵ} and for each production either γ or γ′ or both must be ϵ and a ∈ V_{T} ∪ {ϵ}.

The derivation relation ⇒ is defined for LIG as Υ ⇒ Υ′

• if Υ = Υ_{1}A[αγ] Υ_{4} and there exists a production A[∘∘γ] → Υ_{2}A′[∘∘γ′] Υ_{3} such that Υ′ = Υ_{1}Υ_{2}A′[αγ′] Υ_{3}Υ_{4}

• or else if Υ = Υ_{1}A[ ] Υ_{4} and there exists a production A[ ] → a such that Υ′ = Υ_{1} a Υ_{4}

where A ∈ V_{N}, α ∈ V_{I}^{∗} and γ, γ′ ∈ V_{I} ∪ {ϵ}. The reflexive and transitive closure of ⇒ is denoted by ⇒^{∗}. The language defined by a LIG is the set of strings w ∈ V_{T}^{∗} such that S[ ] ⇒^{∗} w.

To parse this type of grammars, tabulation techniques with polynomial complexity can be designed based on a property defined in [17], that we call context-freeness property of LIG, establishing that if A[γ] ⇒^{∗} uB[ ]w where u, w ∈ V_{T}^{∗}, A, B ∈ V_{N}, γ ∈ V_{I} ∪ {ϵ} and B[ ] is a dependent descendant of A[γ], then for each Υ_{1}, Υ_{2} ∈ (V_{N}[V_{I}^{∗}] ∪ V_{T})^{∗}and β ∈ V_{I}^{∗} we have Υ_{1}A[βγ]Υ_{2} ⇒^{∗} Υ_{1}uB[β]wΥ_{2}. Also, if B[γ] is a dependent descendant of A[ ] and A[ ] ⇒^{∗} uB[γ]w then Υ_{1}A[β]Υ_{2} ⇒^{∗} Υ_{1}uB[βγ]wΥ_{2}.

1.2 Parsing Schemata

We will describe parsing algorithms using Parsing Schemata, a framework for high-level description of parsing algorithms [15]. 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.

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 [14], where items are called formula schemata, deduction steps are inference rules, hypothesis are axioms and final items are goal formulas.

2 A CYK-like Algorithm

We have chosen the CYK-like algorithm for LIG described in [16] 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 having two elements, or one element which must be a terminal, in the right-hand side of each production. This restriction could be considered as the transposition of the Chomsky normal form to linear indexed grammars.

The algorithm works by recognizing in a bottom-up way the part of the input string spanned by each grammar element. The items used in the tabular interpretation of this algorithm are of the form [A, γ, i, j | B, p, q] and represent one of the following types of derivation:

• A[γ] ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j} if and only if (B, p, q) ≠ (−, −, −), B[ ] is a dependent descendent of A[γ] and (p, q) ≤ (i, j).

• A[ ] ⇒^{∗} a_{i+1} … a_{j} if and only if γ = − and (B, p, q) = (−, −, −).

where − means that the value of a component is not bound and (p, q) ≤ (i, j) is used to represent that i ≤ p ≤ q ≤ j when p and q are bound.

These items are like those proposed for the tabulation of linear indexed automata [10] and for the tabulation of bottom-up 2–stack automata [6]. They are slightly different from the items of the form [A, γ, i, j | B, η, p, q] proposed by Vijay-Shanker and Weir in [16] for their CYK-like algorithm, where the element η ∈ V_{I} is redundant: due to the context-freeness property of LIG we have that if

A[γ] ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j} then for any β we have that A[βγ] ⇒^{∗} a_{i+1} … a_{p} B[β] a_{q+1} … a_{j}.

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

I_{CYK} = { [A, γ, i, j | B, p, q] | A, B ∈ V_{N}, γ ∈ V_{I}, 0 ≤ i ≤ j , (p, q) ≤ (i, j) }

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

D_{CYK}^{Scan} = \frac{[a, j, j + 1]}{[A, −, j, j + 1 | −, −, −]} A[ ] → a ∈ P

D_{CYK}^{[∘∘γ][ ][∘∘]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, η, k, j | D, p, q] \end{matrix}}{[A, γ, i, j | C, k, j]} A[∘∘γ] → B[ ] C[∘∘] ∈ P

D_{CYK}^{[∘∘γ][∘∘][ ]} = \frac{\begin{matrix}[B, η, i, k | D, p, q], \\ [C, −, k, j | −, −, −] \end{matrix}}{[A, γ, i, j | B, i, k]} A[∘∘γ] → B[∘∘] C[ ] ∈ P

D_{CYK}^{[∘∘][ ][∘∘]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, η, k, j | D, p, q] \end{matrix}}{[A, η, i, j | D, p, q]} A[∘∘] → B[ ] C[∘∘] ∈ P

D_{CYK}^{[∘∘][∘∘][ ]} = \frac{\begin{matrix}[B, η, i, k | D, p, q], \\ [C, −, k, j | −, −, −] \end{matrix}}{[A, η, i, j | D, p, q]} A[∘∘] → B[∘∘] C[ ] ∈ P

D_{CYK}^{[∘∘][ ][∘∘γ]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, γ, k, j | D, p, q], \\ [D, η, p, q | E, r, s] \end{matrix}}{[A, η, i, j | E, r, s]} A[∘∘] → B[ ] C[∘∘γ] ∈ P

D_{CYK}^{[∘∘][∘∘γ][ ]} = \frac{\begin{matrix}[B, γ, i, k | D, p, q], \\ [C, −, k, j | −, −, −], \\ [D, η, p, q | E, r, s] \end{matrix}}{[A, η, i, j | E, r, s]} A[∘∘] → B[∘∘γ] C[ ] ∈ P

D_{CYK} = D_{CYK}^{Scan} ∪ D_{CYK}^{[∘∘γ][ ][∘∘]} ∪ D_{CYK}^{[∘∘γ][∘∘][ ]} ∪ D_{CYK}^{[∘∘][ ][∘∘]} ∪ D_{CYK}^{[∘∘][∘∘][ ]} ∪ D_{CYK}^{[∘∘][ ][∘∘γ]} ∪ D_{CYK}^{[∘∘][∘∘γ][ ]}

F_{CYK} = { [S, −, 0, n | −, −, −] }

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

Steps in the set D_{CYK}^{Scan} are in charge of starting the parsing process. The other steps are in charge of combining the items corresponding to the elements in the right-hand side of a production in order to generate the item corresponding to the left-hand side element, propagating bottom-up the information about the indices stack.

The space complexity of the algorithm with respect to the length n of the input string is O(n^{4}), as each item stores four positions of the input string. The time complexity is O(n^{6}) and it is given by the deduction steps in D_{CYK}^{[∘∘γ]right} and D_{CYK}^{[∘∘γ]left}. Although these steps involve 7 positions of the input string, by partial application each step can be decomposed in a set of deduction steps involving at most 6 positions.

A CYK-like algorithm generalized for linear indexed grammar with productions manipulating more than one symbol at the top of the indices stacks is described in [17]. The same kind of generalization could be incorporated into the algorithm presented here.

3 A Bottom-up Earley-like Algorithm

The CYK-like algorithm has an important limitation: it can only be applied to linear indexed grammars having at most two children in the right-hand side. To overcome this limitation we use dotted production into items instead single nodes. Thus, we can distinguish the part of a production already processed from the part not yet processed. With respect to notation, we use A to denote a grammar element having the non-terminal A when the associated indices stack is not relevant in that context.

The items of the new parsing system ℙ_{buE} are of the form [A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] and can be obtained by refining the items in ℙ_{CYK}. They represent one of the following two cases:

• A[γ] ⇒ Υ_{1}Υ_{2} ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j} Υ_{2} if and only if (B, p, q) ≠ (−, −, −), B[ ] is a dependent

descendant of A[γ] and (p, q) ≤ (i, j).

• Υ_{1} ⇒^{∗} a_{i+1} … a_{j} if and only if γ = − and (B, p, q) = (−, −, −). If the dependent child is in Υ_{1} then the indices stack associated to A and to the dependent child must be empty.

The set of deduction steps of ℙ_{buE} is obtained by refining the steps in ℙ_{CYK}: steps D_{CYK}^{[∘∘γ][ ][∘∘]}, D_{CYK}^{[∘∘γ][∘∘][ ]}, D_{CYK}^{[∘∘][ ][∘∘]}, D_{CYK}^{[∘∘][∘∘][ ]}, D_{CYK}^{[∘∘][ ][∘∘γ]} and D_{CYK}^{[∘∘][∘∘γ][ ]} are separated into different steps Init and Comp. Finally, the domain is extended to deal with linear indexed grammars having productions of arbitrary length. Schema 2 The parsing system ℙ_{buE} corresponding to the bottom-up Earley-like parsing algorithm for a linear indexed grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{buE} = \left\{{[A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] | A → Υ_{1}Υ_{2} ∈ P , B ∈ V_{N}, γ ∈ V_{I}, \atop 0 ≤ i ≤ j , (p, q) ≤ (i, j)}\right\}

D_{buE}^{Init} = \overline{[A → •Υ, −, i, i | −, −, −]}

D_{buE}^{Scan} = \frac{\begin{matrix}[A[ ] → •a, −, j, j | −, −, −], \\ [a, j, j + 1] \end{matrix}}{[A[ ] → a•, −, j, j + 1 | −, −, −]}

D_{buE}^{Comp[ ]} = \frac{\begin{matrix}[A → Υ_{1} • B[ ] Υ_{2}, γ, i, k | C, p, q], \\ [B → Υ_{3}•, −, k, j | −, −, −] \end{matrix}}{[A → Υ_{1} B[ ] • Υ_{2}, γ, i, j | C, p, q]}

D_{buE}^{Comp[∘∘γ][∘∘]} = \frac{\begin{matrix}[A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, −, i, k | −, −, −], \\ [B → Υ_{3}•, η, k, j | C, p, q] \end{matrix}}{[A[∘∘γ] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, j | B, k, j]}

D_{buE}^{Comp[∘∘][∘∘]} = \frac{\begin{matrix}[A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, −, i, k | −, −, −], \\ [B → Υ_{3}•, η, k, j | C, p, q] \end{matrix}}{[A[∘∘] → Υ_{1} B[∘∘] • Υ_{2}, η, i, j | C, p, q]}

D_{buE}^{Comp[∘∘][∘∘γ]} = \frac{\begin{matrix}[A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , −, i, k | −, −, −], \\ [B → Υ_{3}• , γ, k, j | C, p, q], \\ [C → Υ_{4}•, η, p, q | D, r, s] \end{matrix}}{[A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, η, i, j | D, r, s]}

D_{buE} = D_{buE}^{Init} ∪ D_{buE}^{Scan} ∪ D_{buE}^{Comp[ ]} ∪ D_{buE}^{Comp[∘∘γ][∘∘]} ∪ D_{buE}^{Comp[∘∘][∘∘]} ∪ D_{buE}^{Comp[∘∘][∘∘γ]}
F_{buE} = { [S → Υ• , −, 0, n | −, −, −] }

The space complexity with respect to the input string is O(n^{4}) because each item stores four positions. The time complexity with respect to the input string is O(n^{6}) and it is given by deduction steps in D_{buE}^{Comp[∘∘][∘∘γ]}.

4 An Earley-like Algorithm

The algorithm described by the parsing system ℙ_{buE} does not take into account whether the part of the input string recognized by each grammar element can be derived from S, the axiom of the grammar. Earley-like algorithms limit the number of deduction steps that can be applied in each moment by predicting productions which are candidates to be part of a derivation having as its starting point the axiom of the grammar.

As a first approach, we consider prediction is performed taking into account the context-free skeleton only. The parsing system so obtained is denoted ℙ_{E} and can be derived from ℙ_{buE} by applying the following filters:

• Init deduction steps only consider productions with S as left-hand side.

• Instead of generating items of the form [A → •Υ, −, i, i | −, −, −] for each possible production A → Υ ∈ P and positions i and j, a set of Pred deduction steps generate only those items involving productions with a relevant context-free skeleton.

Schema 3 The parsing system ℙ_{E} corresponding to the Earley-like parsing algorithm for a linear indexed grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{E} = I_{buE}

D_{E}^{Init} = \overline{[S → •Υ, −, 0, 0 | −, −, −]}

D_{E}^{Pred} = \frac{[A → Υ_{1} • B Υ_{2}, γ, i, j | C, p, q]}{[B → •Υ_{3}, −, j, j | −, −, −]}

D_{E} = D_{E}^{Init} ∪ D_{buE}^{Scan} ∪ D_{E}^{Pred} ∪ D_{buE}^{Comp[ ]} ∪ D_{buE}^{Comp[∘∘γ][∘∘]} ∪ D_{buE}^{Comp[∘∘][∘∘]} ∪ D_{buE}^{Comp[∘∘][∘∘γ]}

F_{E} = F_{buE}

This algorithm, which has a space complexity O(n^{4}) and a time complexity O(n^{6}), is very close to the Earley-like algorithm described by Schabes and Shieber in [13] although the latter can only be applied to a specific class of linear indexed grammars obtained from tree adjoining grammars. However, both algorithms share an important feature: they are weakly predictive as they do not consider the contents of the indices stacks when predictive steps are applied. In appearance, the algorithm proposed by Schabes and Shieber in [13] consults the element on the top of the indices stack at prediction, but a deeper study of the behavior of the algorithm makes it clear that this is not really true, as the authors store the context-free skeleton of the elementary trees of a TAG into the indices stacks, reducing the non-terminal set of the resulting LIG to {t, b}. Indeed, a production b[∘∘η] → t[η_{1}] … t[∘∘η_{s}] … t[η_{n}] is equivalent to η^{b}[∘∘] → η_{1}^{t}[ ] … η_{s}^{t}[∘∘] … η_{n}^{t}[ ] and a production b[∘∘η] → t[η_{1}] … t[η_{n}] is equivalent to η^{b}[ ] → η_{1}^{t}[ ] … η_{n}^{t}[ ].

5 An Earley-like Algorithm Preserving the VPP

Parsers satisfying the valid prefix property (VPP) 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}, it 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.

In the case of LIG, preserving the valid prefix property requires checking if each predicted production A[∘∘γ] → •Υ satisfies S[ ] ⇒^{∗} w A[αγ] Υ where γ ∈ V_{I} ∪ {ϵ}. Therefore, to obtain an Earley-like parsing algorithm for LIG preserving this property we need to modify the Pred steps of the parsing system ℙ_{E} in order to predict information about the indices stacks. As a consequence, items must be also modified, introducing a new element that allows us to track the contents of the predicted indices stacks. The items are now of the form [E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] and they represent one of the following types of derivation:

• S[  ]  ⇒^{∗}  a_{1} … a_{h} E[α] Υ_{4}  ⇒^{∗}  a_{1} … a_{h} … a_{i} A[αγ] Υ_{3}Υ_{4}  ⇒^{∗}

a_{1} … a_{h} … a_{i} … a_{p} B[α] a_{q+1} … a_{j} Υ_{2}Υ_{3}Υ_{4} if and only if (B, p, q) ≠ (−, −, −), A[αγ] is a dependent descendent of E[α] and B[α] is a dependent descendent of A[αγ] . This type of derivation corresponds to the completer of the dependent child of a production having the non-terminal A as left-hand side. The indices stack associated to that non-terminal is not empty.

• S[ ] ⇒^{∗} a_{1} … a_{h} E[α] Υ_{4} ⇒^{∗} a_{1} … a_{h} … a_{i} A[αγ] Υ_{3}Υ_{4} ⇒^{∗} a_{1} … a_{h} … a_{i} … a_{j} Υ_{2}Υ_{3}Υ_{4} if and only if

(E, h) ≠ (−, −), (B, p, q) = (−, −, −), A[αγ] is a dependent descendant of E[α], Υ_{1} does not contain the descendent child of A[αγ] and (p, q) ≤ (i, j). This type of derivation refers to a prediction of the non-terminal A with a non-empty indices stack.

• S[ ] ⇒^{∗} a_{1} … a_{i}A[ ]Υ_{4} ⇒^{∗} a_{1} … a_{i} … a_{j} Υ_{2}Υ_{4} if and only if (E, h) = (−, −), γ = − and (B, p, q) =

(−, −, −). If Υ_{1} includes the dependent child of A[ ] then the indices stack associated to that dependent child is empty. This type of derivation refers to the prediction or completer of a nonterminal A with an empty indices stack.

The new set of items so defined is a refinement of the items in the parsing system ℙ_{E}: the element γ is used to store the top of the predicted indices stacks (in the parsing system ℙ_{E}, γ = − for items resulting of a prediction) and the pair (E, h) allows us to track the item involved in the prediction.

With respect to the deduction steps, the completer steps must be adapted to the new form of the items in order to manipulate the new components E and h and the predicted steps must be refined taking into account the different types of productions. Schema 4 The parsing system ℙ_{Earley_{1}} corresponding to the Earley-like parsing algorithm preserving the valid-prefix property for a linear indexed grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{Earley_{1}} = \left\{{[E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] | A → Υ_{1}Υ_{2} ∈ P , B, C ∈ V_{N}, γ ∈ V_{I}, \atop 0 ≤ h ≤ i ≤ j , (p, q) ≤ (i, j)}\right\}

D_{Earley_{1}}^{Init} = \overline{[−, − | S → •Υ, −, 0, 0 | −, −, −]}

D_{Earley_{1}}^{Scan} = \frac{\begin{matrix}[−, − | A[ ] → •a, −, j, j | −, −, −], \\ [a, j, j + 1] \end{matrix}}{[−, − | A[ ] → a•, −, j, j + 1 | −, −, −]}

D_{Earley_{1}}^{Pred[ ]} = \frac{[E, h | A → Υ_{1} • B[ ] Υ_{2}, γ, i, j | C, p, q]}{[−, − | B → •Υ_{3}, −, j, j | −, −, −]}

D_{Earley_{1}}^{Pred[∘∘γ][∘∘]} = \frac{\begin{matrix}[E, h | A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [M, m | E → •Υ_{3}, γ′, h, h | −, −, −] \end{matrix}}{[M, m | B → •Υ_{4}, γ′, j, j | −, −, −]}

D_{Earley_{1}}^{Pred[∘∘][∘∘]} = \frac{[E, h | A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −]}{[E, h | B → •Υ_{3}, γ, j, j | −, −, −]}

D_{Earley_{1}}^{Pred[∘∘][∘∘γ]} = \frac{[E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2}, γ′, i, j | −, −, −]}{[A, i | B → •Υ_{3}, γ, j, j | −, −, −]}

D_{Earley_{1}}^{Comp[ ]} = \frac{\begin{matrix}[E, h | A → Υ_{1} • B[ ] Υ_{2}, γ, i, j | C, p, q], \\ [−, − | B → Υ_{3}•, −, j, k | −, −, −] \end{matrix}}{[E, h | A → Υ_{1} B[ ] • Υ_{2}, γ, i, k | C, p, q]}

D_{Earley_{1}}^{Comp[∘∘γ][∘∘]} = \frac{\begin{matrix}[E, h | A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [M, m | E → •Υ_{3}, γ′, h, h | −, −, −], \\ [M, m | B → Υ_{4}•, γ′, j, k | C, p, q] \end{matrix}}{[E, h | A[∘∘γ] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, k | B, j, k]}

D_{Earley_{1}}^{Comp[∘∘][∘∘]} = \frac{\begin{matrix}[E, h | A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [E, h | B → Υ_{3}•, γ, j, k | C, p, q] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, k | C, p, q]}

D_{Earley_{1}}^{Comp[∘∘][∘∘γ]} = \frac{\begin{matrix}[E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −], \\ [A, i | B → Υ_{3}• , γ, j, k | C, p, q], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s]}

D_{Earley_{1}} = D_{Earley_{1}}^{Init} ∪ D_{Earley_{1}}^{Scan} ∪ D_{Earley_{1}}^{Pred[ ]} ∪ D_{Earley_{1}}^{Pred[∘∘γ][∘∘]} ∪ D_{Earley_{1}}^{Pred[∘∘][∘∘]} ∪ D_{Earley_{1}}^{Pred[∘∘][∘∘γ]}∪
D_{Earley_{1}}^{Comp[ ]} ∪ D_{Earley_{1}}^{Comp[∘∘γ][∘∘]} ∪ D_{Earley_{1}}^{Comp[∘∘][∘∘]} ∪ D_{Earley_{1}}^{Comp[∘∘][∘∘γ]}
F_{Earley_{1}} = { [−, − | S → Υ• , −, 0, n | −, −, −] }

The space complexity of the algorithm with respect to the length n of the input string is O(n^{5}), due to the five positions of the input string stored in each item. The time complexity is O(n^{7}) due to deduction steps in the set D_{Earley_{1}}^{Comp[∘∘][∘∘γ]}. To reduce the time complexity we will use a technique similar to that used in [5, 2] to reduce the complexity of the tabular interpretations of automata for tree adjoining languages. In this case, we split each deduction step in D_{Earley_{1}}^{Comp[∘∘][∘∘γ]} into two different steps such that their final complexity is at most O(n^{6}). The resulting parsing schema is defined by the following parsing system. Schema 5 The parsing system ℙ_{Earley} corresponding to the Earley-like parsing algorithm preserving the valid-prefix property working with a time complexity O(n^{6}) for a linear indexed grammar G and a input string a_{1} … a_{n} is defined as follows:

I_{Earley^{(1)}} = \left\{{[E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] | A → Υ_{1}Υ_{2} ∈ P , B, C ∈ V_{N}, γ ∈ V_{I}, \atop 0 ≤ h ≤ i ≤ j , (p, q) ≤ (i, j)}\right\}

I_{Earley^{(2)}} = \left\{{[[A → Υ•, γ, i, j | B, p, q]] | A → Υ ∈ P , B ∈ V_{N}, \atop γ ∈ V_{I}, i ≤ j , (p, q) ≤ (i, j)}\right\}

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

D_{Earley}^{Comp[∘∘][∘∘γ]^{0}} = \frac{\begin{matrix}[A, i | B → Υ_{3}• , γ, j, k | C, p, q], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[[B → Υ_{3}• , γ, j, k | D, r, s]]}

D_{Earley}^{Comp[∘∘][∘∘γ]^{1}} = \frac{\begin{matrix}[[B → Υ_{3}• , γ, j, k | D, r, s]], \\ [E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s]}

D_{Earley} = D_{Earley_{1}}^{Init} ∪ D_{Earley_{1}}^{Scan} ∪ D_{Earley_{1}}^{Pred[ ]} ∪ D_{Earley_{1}}^{Pred[∘∘γ][∘∘]} ∪ D_{Earley_{1}}^{Pred[∘∘][∘∘]} ∪ D_{Earley_{1}}^{Pred[∘∘][∘∘γ]}∪
D_{Earley_{1}}^{Comp[ ]} ∪ D_{Earley_{1}}^{Comp[∘∘γ][∘∘]} ∪ D_{Earley_{1}}^{Comp[∘∘][∘∘]} ∪ D_{Earley}^{Comp[∘∘][∘∘γ]^{0}} ∪ D_{Earley}^{Comp[∘∘][∘∘γ]^{1}}
F_{Earley} = F_{Earley_{1}}

Deduction steps Comp[∘∘][∘∘γ]^{0} generate an intermediate item of the form [[B → Υ_{3}• , γ, j, k | D, r, s]] that will be taken as antecedent for steps Comp[∘∘][∘∘γ]^{1} and that represents a derivation

B[γ′γ] ⇒^{∗} a_{j+1} … a_{p} C[γ′] a_{s+1} … a_{q} ⇒^{∗} a_{j+1} … a_{p} … a_{r} D[ ] a_{s+1} … a_{q} … a_{k}

for some γ′, p and q. Deduction steps Comp[∘∘][∘∘γ]^{1} combine this pseudo-item with an item [E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −] that represents a derivation

S[ ] ⇒^{∗} a_{1} … a_{h} E[α] Υ_{5} ⇒^{∗} a_{1} … a_{h} … a_{i} A[αγ′] Υ_{3}Υ_{5} ⇒^{∗} a_{1} … a_{h} … a_{i} … a_{j} B[αγ′γ] Υ_{2}Υ_{3}Υ_{5}

and with an item [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] representing a derivation

S[ ] ⇒^{∗} a_{1} … a_{h} E[α] Υ_{5} ⇒^{∗} a_{1} … a_{h} … a_{p} C[αγ′] Υ_{4}Υ_{5} ⇒^{∗} a_{1} … a_{h} … a_{p} … a_{r} D[α] a_{s+1} … a_{q} Υ_{4}Υ_{5}

and a new item of the form [E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s] is generated. This last item represent the existence of a derivation

S[ ] ⇒^{∗} a_{1} … a_{h} E[α] Υ_{5}

⇒^{∗} a_{1} … a_{h} … a_{i} A[αγ′] Υ_{3}Υ_{5}

⇒^{∗} a_{1} … a_{h} … a_{i} … a_{j} B[αγ′γ] Υ_{2}Υ_{3}Υ_{5}

⇒^{∗} a_{1} … a_{h} … a_{i} … a_{j} … a_{p} C[αγ′] a_{q+1} … a_{k} Υ_{2}Υ_{3}Υ_{5}

⇒^{∗} a_{1} … a_{h} … a_{i} … a_{j} … a_{p} … a_{r} D[α] a_{s+1} … a_{q+1} … a_{k} Υ_{2}Υ_{3}Υ_{5}

6 The Shared Forest

The algorithms described so far are just recognizers. They do not build a representation of the derived trees. However, we can modify them to build these trees as a shared forest satisfying the following properties: it must store in a compact form all parse trees and it must be possible to retrieve every individual parse tree in linear time with respect to the size of the forest.

Billot and Lang [3] define the shared forest for a context-free grammar G = (V_{T} , V_{N}, P, S) and an input string a_{1} … a_{n} as a context free grammar in which the non-terminals are of the form ⟨A, i, j⟩, where A ∈ V_{N} and i, j ∈ 0..n, and productions are of the form

⟨A_{0}, j_{0}, j_{m}⟩ → w_{0} ⟨A_{1}, j_{0}, j_{1}⟩ w_{1} ⟨A_{2}, j_{1}, j_{2}⟩ … w_{m−1} ⟨A_{m}, j_{m−1}, j_{m}⟩ w_{m}

where A_{0} → w_{0}A_{1}w_{1}A_{2} … w_{m−1}A_{m}w_{m} ∈ P and w_{i} ∈ V_{T}^{∗}, meaning that A_{0} recognizes the part a_{j_{0}+1} … a_{j_{m}} of the input string by applying the production A_{0} → w_{0}A_{1}w_{1}A_{2} … w_{m−1}A_{m}w_{m} such that A_{i} recognizes the part a_{j_{i−1}+1} … a_{j_{i}} of the input string.

We can extend the concept of shared forest for CFG to define the concept of LIGed forest [18]. Given the shared forest of the context-free skeleton of a LIG, when a LIG production A_{0}[∘∘γ] → A_{1}[ ] … A_{d}[∘∘γ′] … A_{m}[ ] is involved in a derivation, a production

⟨A_{0}, j_{0}, j_{m}⟩[∘∘γ] → ⟨A_{1}, j_{0}, j_{1}⟩ … ⟨A_{d}, j_{d−1}, j_{d}⟩[∘∘γ′] … ⟨A_{m}, j_{m−1}, j_{m}⟩

is added to the LIGed forest meaning that A_{0} recognizes the part a_{j_{0}+1} … a_{j_{m}} of the input string by applying the production A_{0}[∘∘γ] → A_{1} … A_{d}[∘∘γ′] … A_{m} such that A_{i} recognizes the part a_{j_{i−1}+1} … a_{j_{i}} of the input string and the indices stack is passed from A_{0} to A_{d} replacing the top index γ for γ′. The LIG so generated does not satisfy our definition of shared forest because single parse trees can not be extracted in linear time. Vijay-Shanker and Weir [18] try to solve this problem by defining a non-deterministic finite state automaton that determines if a given LIGed forest symbol ⟨A, i, j⟩[α] derives a string of terminals. A similar finite-state automata is also defined by Nederhof in [11].

As an alternative approach, Boullier [4] defines the shared forest for a LIG G = (V_{T} , V_{N}, V_{I}, P, S) and an input string w by means of a linear derivation grammar, a context-free grammar recognizing the language defined by the sequences of LIG productions of G that could be used to derive w. Previously to the construction of the linear derivation grammar, we must compute the transitive closure for a set of relations on V_{N} × V_{N}.

To avoid the use of additional data structures, such as finite automata or precomputed relations, we have been inspired by the use of context-free grammars to represent the parse forest of tree adjoining grammars [18] in order to capture the context-freeness of production application in the case of LIG. Given a linear indexed grammar G = (V_{T} , V_{N}, V_{I}, P, S) and an input string w = a_{1} … a_{n}, the shared forest for G and w is a context-free grammar G^{w} = (V_{T} , V_{N}^{w}, P^{w}, S^{w}). Elements in V_{N}^{w} have the form ⟨A, γ, i, j, B, p, q⟩, where A, B ∈ V_{N}, γ ∈ V_{I} and i, j, p, q ∈ 0 … n. The axiom S^{w} is the non-terminal ⟨S, −, 0, n, −, −, −, ⟩. Productions in P^{w} are of the form:

Case 1a: If A[ ] ⇒ a_{j} then add the production ⟨A, −, j − 1, j, −, −, −⟩ → a_{j}

Case 1b: If A[ ] ⇒ ϵ then add the production ⟨A, −, j, j, −, −, −⟩ → ϵ

Case 2a: If A[∘∘γ] → B[ ] C[∘∘] ∈ P, B[ ] ⇒^{∗} a_{i+1} … a_{k} and C[αη] ⇒^{∗} a_{k+1} … a_{p} D[α] a_{q+1} … a_{j}

then add the production ⟨A, γ, i, j, C, k, j⟩ → ⟨B, −, i, k, −, −, −⟩ ⟨C, η, k, j, D, p, q⟩

Case 2b: If A[∘∘γ] → B[∘∘] C[ ] ∈ P, B[αη] ⇒^{∗} a_{i+1} … a_{p} D[α] a_{q+1} … a_{k} and C[ ] ⇒^{∗} a_{k+1} … a_{j}

then add the production ⟨A, γ, i, j, B, i, k⟩ → ⟨B, η, i, k, D, p, q⟩ ⟨C, −, k, j, −, −, −⟩

Case 3a: If A[∘∘] → B[ ] C[∘∘] ∈ P, B[ ] ⇒^{∗} a_{i+1} … a_{k} and C[αη] ⇒^{∗} a_{k+1} … a_{p} D[α] a_{q+1} … a_{j} then

add the production ⟨A, η, i, j, D, p, q⟩ → ⟨B, −, i, k, −, −, −⟩ ⟨C, η, k, j, D, p, q⟩

Case 3b: If A[∘∘] → B[∘∘] C[ ] ∈ P, B[αη] ⇒^{∗} a_{i+1} … a_{p} D[α] a_{q+1} … a_{k} and C[ ] ⇒^{∗} a_{k+1} … a_{j} then

add the production ⟨A, η, i, j, D, p, q⟩ → ⟨B, η, i, k, D, p, q⟩ ⟨C, −, k, j, −, −, −⟩

Case 4a: If A[∘∘] → B[ ] C[∘∘γ] ∈ P, B[ ] ⇒^{∗} a_{i+1} … a_{k} and C[αηγ] ⇒^{∗}

a_{k+1} … a_{p} D[αη] a_{q+1} … a_{j} and D[αη] ⇒^{∗} a_{p+1} … a_{r} E[α] a_{s+1} … a_{q} then add the production

⟨A, η, i, j, E, r, s⟩ → ⟨B, −, i, k, −, −, −⟩ ⟨C, γ, k, j, D, p, q⟩ ⟨D, η, p, q, E, r, s⟩

Case 4b: If A[∘∘] → B[∘∘γ] C[ ] ∈ P, B[αηγ] ⇒^{∗} a_{i+1} … a_{p} D[αη] a_{q+1} … a_{k} and

C[ ] ⇒^{∗} a_{k+1} … a_{j} and D[αη] ⇒^{∗} a_{p+1} … a_{r} E[α] a_{s+1} … a_{q} then add the production

⟨A, η, i, j, E, r, s⟩ → ⟨B, γ, i, k, D, p, q⟩ ⟨C, −, k, j, −, −, −⟩ ⟨D, η, p, q, E, r, s⟩

Case 5: If A[∘∘γ] → B[∘∘] ∈ P and B[αη] ⇒^{∗} a_{i+1} … a_{p} D[α] a_{q+1} … a_{j} then add the production ⟨A, γ, i, j, B, i, j⟩ → ⟨B, η, i, j, D, p, q⟩

Case 6: If A[∘∘] → B[∘∘] ∈ P and B[αγ] ⇒^{∗} a_{i+1} … a_{p} D[α] a_{q+1} … a_{j} then add the production ⟨A, γ, i, j, D, p, q⟩ → ⟨B, γ, i, j, D, p, q⟩

Case 7: If A[∘∘] → B[∘∘γ] ∈ P and B[αηγ] ⇒^{∗} a_{i+1} … a_{p} D[αη] a_{q+1} … a_{j}

and D[αη] ⇒^{∗} a_{p+1} … a_{r} E[α] a_{s+1} … a_{q} then add the production ⟨A, η, i, j, E, r, s⟩ → ⟨B, γ, i, j, D, p, q⟩ ⟨D, η, p, q, E, r, s⟩ In cases 4a, 4b and 7, derivations starting at ⟨D, η, p, q, E, r, s⟩ allow us to retrieve the rest of the

indices stack corresponding to A. Note that we are assuming a grammar with productions having at most two children. Any production A_{0}[∘∘γ] → A_{1}[ ] … A_{d}[∘∘γ′] … A_{m}[ ] can be translated into

∇_{0}[ ] → ϵ ; ∇_{1}[∘∘] → ∇_{0}[∘∘] A_{1}[ ] ; ⋮ ; ∇_{d−1}[∘∘] → ∇_{d−2}[∘∘] A_{d−1}[ ] ; ∇_{d}[∘∘γ] → ∇_{d−1}[ ] A_{d}[∘∘γ′]  ∇_{d+1}[∘∘] → ∇_{d}[∘∘] A_{d+1}[ ] ; ⋮ ; ∇_{m}[∘∘] → ∇_{m−1}[∘∘] A_{m}[ ] ; A_{0}[∘∘] → ∇_{m}[∘∘]

where the ∇_{i} are fresh symbols that represent partial recognition of the original production. In fact, a ∇_{i} symbol is equivalent to a dotted production with the dot just before the non-terminal A_{i+1} or with the dot at the end of the right-hand side in the case of ∇_{m}.

It is interesting to remark that the set of non-terminals is a subset of the set of items for CYKlike and bottom-up Earley-like algorithms, and Earley-like algorithms without the VPP. The case of the Earley-like algorithm preserving the valid prefix property is slightly different, as a non-terminal ⟨A, γ, i, j, B, p, q⟩ represent the class of items [E, h | A, γ, i, j | D, p, q] for any value of E and h.

Like context-free grammars used as shared forest in the case of TAG [18], the derivations in G^{w} encode derivations of the string w by G but the specific set of terminal strings that is generated by G^{w} is not important. We do however have the language generated by G^{w} is not empty if and only if w belongs to the language generated by G. We can prune G^{w} by retaining only production with useful symbols to guarantee that every non-terminal can derive a terminal string. In this case, derivations of w in the original grammar can be read off by simple reading off of derivations in G^{w}.

The number of possible productions in G^{w} is O(n^{7}). The complexity can be reduced to O(n^{6}) by transforming productions of the form A[∘∘] → B[ ] C[∘∘γ] into two productions A[∘∘] → B[ ] X[∘∘] and X[∘∘] → C[∘∘γ] where X is a fresh non-terminal. A similar transformation must be applied to productions A[∘∘] → B[∘∘γ] C[ ].

7 Conclusion

We have described a set of algorithms for LIG parsing, creating a continuum which has the CYKlike parsing algorithm by Vijay-Shanker and Weir [16] as its starting point and a new Earley-like algorithm which preserves the valid prefix property as its goal. In the middle, a new bottom-up Earley-like algorithm and a new Earley-like algorithm have been described. The time complexity for all these algorithms with respect to the length of the input string is O(n^{6}). Other algorithms could also have 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 LIG.

Acknowledgements

We would like to thank Pierre Boullier, Patrice Lopez and Mark-Jan Nederhof for fruitful discussions. This work was partially supported by the FEDER of EU (project 1FD97-0047-C04-02) and Xunta de Galicia (projects PGIDT99XI10502B and XUGA20402B97).

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] Alonso, M. A., E. de la Clergerie, and D. Cabrero. 1999. Tabulation of automata for tree adjoining languages. Proc. of MOL-6, pages 127–141, Orlando, Florida.

[3] Billot, S. and B. Lang. 1989. The structure of shared forest in ambiguous parsing. Proc. of ACL’89, pages 143–151, Vancouver, British Columbia, Canada.

[4] Boullier, P. 1996. Another facet of LIG parsing. Proc. of ACL’96, Santa Cruz, CA.

[5] De la Clergerie, E. and M. A. Alonso. 1998. A tabular interpretation of a class of 2-Stack Automata. Proc. of COLING-ACL’98, volume II, pages 1333–1339, Montreal, Canada.

[6] De la Clergerie, E., M. A. Alonso, and D. Cabrero. 1998. A tabular interpretation of bottom-up automata for TAG. Proc. of TAG+4, pages 42–45, Philadelphia.

[7] Gazdar, G. 1987. Applicability of indexed grammars to natural languages. In U. Reyle and C. Rohrer, editors, Natural Language Parsing and Linguistic Theories, pages 69–94. D. Reidel Publishing Company.

[8] Joshi, A. K. and Y. Schabes. 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, 1997.

[9] Nederhof, M-J. 1997 Solving the correct-prefix property for TAGs. In T. Becker and H.-V. Krieger, editors, Proc. of MOL-5, pages 124–130, Schloss Dagstuhl, Saarbruecken, Germany.

[10] Nederhof, M-J. 1998. Linear indexed automata and tabulation of TAG parsing. Proc. of TAPD’98, pages 1–9, Paris, France.

[11] Nederhof, M-J. 1999. Models of tabulation for TAG parsing. Proc. of MOL-6, pages 143–158, Orlando, Florida.

[12] Schabes, Y. 1992. Stochastic lexicalized tree-adjoining grammars. Proc. of COLING’92, pages 426–432, Nantes, France.

[13] Schabes, Y. and S. M. Shieber. 1994. An alternative conception of tree-adjoining derivation. Computational Linguistics, 20(1):91–124.

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

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

[16] Vijay-Shanker, K. and D. J. Weir. 1991. Polynomial parsing of extensions of context-free grammars. In Masaru Tomita, editor, Current Issues in Parsing Technology, chapter 13, pages 191–206. Kluwer Academic Publishers, Norwell, MA.

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

[18] Vijay-Shanker, K. and D. J. Weir. 1993. The use of shared forest in tree adjoining grammar parsing. Proc. of EACL’93, pages 384–393.