Generalized LR Parsing for Extensions of Context-Free Grammars

Miguel A. Alonso, David Cabrero & Manuel Vilares

Universidade da Coruña

Abstract

We present a Generalized LR parsing algorithm for extensions of context-free grammars. It differs from previous approaches in the use of dynamic programming techniques to cope with non determinism, instead of a graph-structured stack. The steps for deriving the algorithm from the classical Earley’s parsing algorithm are shown.

1 Introduction

LR parsing strategies can analyze LR grammars, which are deterministic. If we consider LR parsing tables in which each entry can contain several actions, we obtain non-deterministic LR parsing, often known as generalized LR parsing (GLR), which can analyze non-deterministic context-free grammars. In this context, some mechanism is needed in order to represent the non-deterministic evolution of the stack. Tomita (1996) has proposed an algorithm based on a graph-structured stack but it has problems with cyclic and hidden left recursive constructions. Rekers (1992) has modified the original algorithm to overcome these limitations. Space and time bounds can be reduced transforming the form of the grammar (Sheil 1976). Some approaches also use transformations in the construction of the LR automaton and in these the treatment of cyclicity is even more complex and so is often avoided (Nederhof & Sarbo 1996).

Generalized LR parsing can be extended to deal with grammatical formalisms which have a context-free backbone, such as unification-based grammars, lexical-functional grammars or definite clause grammars. As has been shown by De la Clergerie (1993), there is a straightforward extension of automata-based context-free parsing techniques to Horn-clause analysis. The most common grammatical framework based on Horn-clauses is Definite Clause Grammars (Pereira & Warren 1980), which is the formalism chosen to work with in this article.

2 MIGUEL A. ALONSO, DAVID CABRERO & MANUEL VILARES

1.1 Notation

A context-free grammar (CFG) is a tuple (V_{N}, V_{T} , P, S), where V_{N} is a finite set of non-terminal symbols, V_{T} is a finite set of terminal symbols, P is a finite set of productions A → α and S ∈ V_{N} is the start symbol or axiom of the grammar. We will write A, B … for elements in V_{N}, a, b … for elements in V_{T}, X, Y … for elements in V = V_{N} ∪ V_{T} and α, β … for elements in V^{∗}. The relation ⇒ on V^{∗} ×V^{∗} is defined by α ⇒ β if there are α′, α′′, A, γ such that α = α′Aα′′, β = α′γα′′ and A → γ ∈ P exists. We can suffix each element in a production r, thus A_{r,0} → A_{r,1}A_{r,2} … A_{r,n_{r}}.

We can think of a definite clause grammar (DCG) as a CFG skeleton with attributes associated to grammatical symbols. A DCG is defined by a tuple (V_{N}, V_{T} , P, S, V, F), where V is a finite set of variables, F is a finite set of functors and P is a set of definite clauses

A_{r,0}(t_{r,0}^{1}, …, t_{r,0}^{m_{0}}) → A_{r,1}(t_{r,1}^{1}, …, t_{r,1}^{m_{1}}) … A_{r,n_{r}}(t_{r,n_{r}}^{1}, …, t_{r,n_{r}}^{m_{nr}})

where A_{r,0} ∈ V_{N}, A_{r,i} ∈ (V_{N} ∪ V_{T})^{∗} for 1 ≥ i ≥ n_{r} and t_{r,i}^{m_{j}} are terms, which are inductively defined as being either a constant functor of arity 0, a variable or a compound term f(t_{1}, …, t_{l}), where f is a functor of arity l and t_{1}, …, t_{l} are terms. If A_{r,i} ∈ V_{T}, the terms t_{r,i}^{1}, …, t_{r,i}^{m_{i}} are related to the lexical entry A_{r,i} and therefore the elements in V_{T} are preterminals rather than actual terminals. For each clause γ_{r} we define the vector \overrightarrow{T_{r}} of variables appearing in γ_{r}. When possible, definite clauses will be written in short as A_{r,0} → A_{r,1} … A_{r,n_{r}}.

A substitution σ is a finite mapping {R_{1}/t_{1}, …, R_{n}/t_{n}} from variables R_{i} to terms t_{i}. The application of σ to a term t is denoted tσ and it is achieved by replacing in t any occurrence of R_{i} by t_{i}. A term t generalizes or subsumes t′ if there exists a substitution σ such that t′ = tσ and it is denoted t ⪯ t′. The unification of two terms t and t′ without common variables returns the most general substitution σ = mgu(t, t′), unique to the renaming of variables, so that tσ = t′σ.

Parsing algorithms will be described using Parsing Schemata, a framework for high-level description of parsing algorithms (Sikkel 1997). 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 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 η_{1}, …, η_{k} ⊢ ξ, meaning that if all antecedents η_{i} of a deduction step are present, then the consequent ξ should be generated by the parser. A set F ⊆ I of final items represent the recognizing of a sentence. A parsing schema is a parsing system parameterized by a context-free grammar and a sentence.

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 IP_{Alg} corresponding to the parsing schemata 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 Relating Earley and LR parsing algorithms

Given a context-free grammar G and a input string a_{1} … a_{n}, an Earley parser (Earley 1970) for G constructs a sequence of n + 1 sets of items. Each item [A → α • β, i, j] indicates that α ⇒^{∗} a_{i+1} … a_{j}, with 0 ≤ i ≤ j, and that symbol A has been predicted in the item set i. Parsing begins with a set of initial items [S → •α, 0, 0], where S → α ∈ P, and successively applies three operations until new items can not be generated:

scanner operation can be applied if there exists an item [A → α • aβ, i, j]

and a_{j+1} = a, yielding the item [A → αa • β, i, j + 1]. predictor operation, which represents the predictive descendent phase of

the algorithm, can be applied when an item [A → α • Bβ, i, j] exists, generating an item [B → •γ, j, j] for each B → γ ∈ P.

completer operation can be applied if two items [A → α • Bβ, i, k] and [B → γ•, k, j] exist, and produces a new item [A → αB • β, i, j], which represents that a_{k+1} … a_{j} can be reduced to B and therefore, as we know that α reduces the input a_{i+1} … a_{k}, we can ensure that αB reduces a_{i+1} … a_{j}.

The input sentence belongs to the language described by the grammar if the final item [S → α•, 0, n] is generated.

The parsing system IP_{Earley} corresponding to the parsing schemata Earley describing the Earley’s algorithm is the following (Sikkel 1997:76):

I_{Earley} = {[A → α • β, i, j]} | A → αβ ∈ P , 0 ≤ i ≤ j}

H_{Earley} = {[a, i, i + 1] | a = a_{i}}

D_{Earley}^{Init} = {⊢ [S → •α, 0, 0]}

D_{Earley}^{Scan} = { [A → α • aβ, i, j], [a, j, j + 1] ⊢ [A → αa • β, i, j + 1] }

D_{Earley}^{Pred} = {[A → α • Bβ, i, j] ⊢ [B → •γ, j, j]}

D_{Earley}^{Comp} = { [A → α • Bβ, i, k], [B → γ•, k, j] ⊢ [A → αB • β, i, j] }

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

F_{Earley} = {[S → α•, 0, n]}

The previous parsing system corresponds to “uncompiling” an LR(0) parser: while LR(0) parsers compile the D_{Earley}^{Pred} steps into a finite state control, an Earley parser uses run-time items. What D_{Earley}^{Pred} really does is compute the closure function in run-time.

In order to obtain a version closer to LR stack computations, we can make several minor changes in the Scan and Comp steps, involving a slightly different use of indices: the components i and j of an item [A → α • β, i, j] will now represent the part of the input string recognized by the element in α just before the dot. If α = ε then i = j. As a consequence, the completer step must now have m elements as antecedents, where m is the length of the right hand side of the production to be reduced. In the new LR(0) deduction steps, the Scan and Comp steps are called Shift and Reduce because they show a close relation to shift and reduce operations of LR parsers:

D_{LR(0)}^{Shift} = { [A → α • aβ, i, j], [a, j, j + 1] ⊢ [A → αa • β, j, j + 1] }

D_{LR(0)}^{Reduce} = { [B → X_{1}X_{2} ⋯ X_{m}•, j_{m−1}, j_{m}], ; ⋮ ; [B → X_{1} • X_{2} ⋯ X_{m}, j_{0}, j_{1}], ; [A → α • Bβ, i, j_{0}] ; ⊢ [A → αB • β, j_{0}, j_{m}] }

D_{LR(0)} = D_{Earley}^{Init} ∪ D_{LR(0)}^{Shift} ∪ D_{Earley}^{Pred} ∪ D_{LR(0)}^{Reduce}

3 Using lookahead: SLR(1) and LR(1)

We can add lookahead to IP_{LR(0)} in order to mimic the behavior of SLR(1) parsers. For this purpose, we introduce a dynamic filter in the Reduce step, using the function ‘follow’, which is defined in relation to a function ‘first’.

Given a context-free grammar, an element a ∈ V_{T} is in first(X), where X ∈ V if X = a or X → ε ∈ P and a = ε or X → Y_{1} ⋯ Y_{i} ⋯ Y_{m} ∈ P and a ∈ first(Y_{i}) and ∀_{j=1}^{i−1} ε ∈ first(Y_{j}). The extension to first(α), where α = X_{1} ⋯ X_{i} ⋯ X_{n} ∈ V, is straightforward: a ∈ first(α) if a ∈ first(X_{1}) ∪ ⋯ ∪ first(X_{i}) and ε ∉ first(X_{i}) and ∀_{j=1}^{i−1} ε ∈ first(X_{j}). If α ⇒^{∗} ε then ε ∈ first(α).

An element a ∈ V_{T} ∪ {$} is in follow(A), where $ is a special end-of-input marker not in V_{T} and A ∈ V_{N}, if a = $ and A is the start symbol or A′ → αAβ ∈ P and a ∈ (first(β) − {ε}) or A′ → αAβ ∈ P and ε ∈ first(β) and a ∈ follow(A′).

Checking of lookahead is performed by the condition ∃[a, j_{m}, j_{m} + 1] ∈ H_{SLR}, a ∈ follow(B) introduced in the Reduce deduction step for SLR(1):

D_{SLR}^{Reduce} = { [B → X_{1}X_{2} ⋯ X_{m}•, j_{m−1}, j_{m}], ⋮ [B → X_{1} • X_{2} ⋯ X_{m}, j_{0}, j_{1}], [A → α • Bβ, i, j_{0}] ⊢ [A → αB • β, j_{0}, j_{m}] | ∃[a, j_{m}, j_{m} + 1] ∈ H_{SLR}, a ∈ follow(B) }

D_{SLR} = D_{Earley}^{Init} ∪ D_{LR(0)}^{Shift} ∪ D_{Earley}^{Pred} ∪ D_{SLR}^{Reduce}

In order to obtain a parsing system for LR(1), we must introduce the notion of lookahead into items, as is done in the classical construction of finite state control for LR(1) parsers (Aho & Ullman 1972). The items in IP_{LR} can be obtained by item refinement of SLR items if we consider that in IP_{Earley} and IP_{SLR} each item represents a set of items having the same dotted production and indices but probably different lookahead:

I_{LR} = {[A → α • β, b, i, j] | A → αβ ∈ P , b ∈ V_{T} , 0 ≤ i ≤ j}

where b represents the lookahead. The parsing system IP_{LR}, in which lookahead is set in D_{LR}^{Pred} and checked in D_{LR}^{Reduce}, is the following:

H_{LR} = H_{Earley}

D_{LR}^{Init} = {⊢ [S → •α, $, 0, 0]}

D_{LR}^{Shift} = { [A → α • aβ, b, i, j], [a, j, j + 1] ⊢ [A → αa • β, b, j, j + 1] }

D_{LR}^{Pred} = { [A → α • Bβ, b, i, j] ⊢ [B → •γ, b′, j, j] | b′ = first(βb) }

D_{LR}^{Reduce} = { [B → X_{1}X_{2} ⋯ X_{m}•, b′, j_{m−1}, j_{m}] ; ⋮ ; [B → X_{1} • X_{2} ⋯ X_{m}, b′, j_{0}, j_{1}], ; [A → α • Bβ, b, i, j_{0}] ; ⊢ [A → αB • β, b, j_{0}, j_{m}] | ; b′ ∈ first(βb), ; ∃[a, j_{m}, j_{m} + 1] ∈ H_{LR}, ; a = b′ }

D_{LR} = D_{LR}^{Init} ∪ D_{LR}^{Shift} ∪ D_{LR}^{Pred} ∪ D_{LR}^{Reduce}

F_{LR} = {[S → α•, $, 0, n]}

4 Compiling predictive information into tables

A more compact and efficient algorithm can be obtained by avoiding the computation of Pred steps in run-time. Instead, they are compiled, resulting in the construction of an LR automaton as in classical LR algorithms (Aho & Ullman 1972). The items in the new parsing system IP_{LR^{c}} are equivalent to those of IP_{LR} because items [A → α•β, b, i, j] are simply replaced by [st, i, j], where st is the precomputed state of the LR automaton which contains the element [A → α • β, b]. The parsing system IP_{LR^{c}} is the following:

I_{LR^{c}} = {[st, i, j] | st ∈ set of states of LR automaton, 0 ≤ i ≤ j}

H_{LR^{c}} = H_{Earley}

D_{LR^{c}}^{Init} = {⊢ [st_{0}, 0, 0]}

D_{LR^{c}}^{Shift} = { [st, i, j], [a, j, j + 1] ⊢ [st′, j, j + 1] | shift_{st′} ∈ action(st, a) }

D_{LR^{c}}^{Reduce} = \{ \begin{matrix}[st^{m}, j_{m−1}, j_{m}], …, [st^{1}, j_{0}, j_{1}], [st^{0}, i, j_{0}] ⊢ [st, j_{0}, j_{m}] | \\ ∃[a, j_{m}, j_{m} + 1] ∈ H_{LR^{c}}, reduce_{r} ∈ action(st^{m}, a), \\ st^{i} ∈ reveal(st^{i+1}), st ∈ goto(st^{0}, A_{r,0}), \\ m = length(rhs(r)) \end{matrix} \}

D_{LR^{c}} = D_{LR^{c}}^{Init} ∪ D_{LR^{c}}^{Shift} ∪ D_{LR^{c}}^{Reduce}

where st^{i} ∈ reveal(st^{i+1}) is equivalent to st^{i+1} ∈ goto(st^{i}, X) if X ∈ V_{N} and is equivalent to shift_{st^{i+1}} ∈ action(st^{i}, X) if X ∈ V_{T}. More intuitively, we can say that reveal function traverses the finite state control of the automaton backwards.

F_{LR^{c}} = {[st_{f}, 0, n]}

where st_{f} is a final state of the LR automaton.

In the preceding, ‘action’ and ‘goto’ refer to the tables that code the behavior of the LR automaton: action table determines what action should be taken for a given state and

lookahead. In the case of shift actions, it determines the resulting new state and in the case of reduce actions, the production which is to be applied for the reduction.

goto table determines what will be the state after performing a reduce action. Each entry is accessed using the current state and the nonterminal in the left-hand side of the production to be applied for reduction.

A significant advantage with respect to previous parsing systems is that we can now differentiate between LR(1) and LALR(1) algorithms simply by choosing the appropriate compiling methods for the finite state control.

5 GLR parsing for DCG

Context-free grammars have a finite number of grammar symbols. When these grammars are enriched with terms or feature-structures, the number of grammar symbols can not be guaranteed to be finite. Thus the construction of the parsing tables may be a non terminating process. A solution to this problem is to use positive restrictors (Shieber 1985) or negative restrictors (Trujillo 1994) to define a finite number of equivalence classes into which the infinite number of nonterminals may be sorted. The restrictor must be applied to obtain the compiled information: the first and follow functions, the closure of the LR automaton and the action and goto tables.

Several restrictors exist for each grammar but termination is not guaranteed for all of them and furthermore, the best restrictor can not be chosen automatically since it depends on the amount of grammatical information that is to be preserved. In practice, a good balance is obtained if only the underlying context-free grammar is considered during the compilation phase (Vilares et al. 1998).

Deduction steps need to access the terms associated to grammar symbols. As that information is not contained in the states of the automaton, it must be included in items. Applying item refinement to IP_{LR^{c}} items, we obtain the new form of the items [A(t^{1}, …, t^{m}), st, i, j], with a new element that represents an element of a clause. With respect to deduction steps, Shift steps must be refined into:

InitShift, which is applied when the symbol to be shifted is the first symbol

in the right hand side of a clause. Shift, which is applied in the shift of the other symbols in a clause.

The new schema LR(DCG) is the extension of the schema LR^{c} to the case of definite clause grammars and it is defined by the following parsing system IP_{LR(DCG)}:

I_{LR(DCG)} = {[A, st, i, j]}

H_{LR(DCG)} = H_{Earley}

D_{LR(DCG)}^{Init} = {⊢ [−, st_{0}, 0, 0]}

D_{LR(DCG)}^{InitShift} = \{ \begin{matrix}[A, st, i, j], [a, j, j + 1] ⊢ [A_{r,1}, st′, j, j + 1] | \\ shift_{st′} ∈ action(st, a), A_{r,1} = a(t_{r,1}^{1}, …, t_{r,1}^{m}) \end{matrix} \}

D_{LR(DCG)}^{Shift} = \{ \begin{matrix}[A_{r,s}, st, i, j], [a, j, j + 1] ⊢ [A_{r,s+1}, st′, j, j + 1] | \\ shift_{st′} ∈ action(st, a), A_{r,s+1} = a(t_{r,s+1}^{1}, …, t_{r,s+1}^{m}) \end{matrix} \}

D_{LR(DCG)}^{Reduce} = \{ \begin{matrix}[A_{r,m}, st^{m}, j_{m−1}, j_{m}], …, [A_{r,1}, st^{1}, j_{0}, j_{1}], [A, st^{0}, i, j_{0}] \\ ⊢ [A_{r,0}σ, st, j_{0}, j_{m}] | \\ ∃[a, j_{m}, j_{m} + 1] ∈ H_{LR(DCG)}, reduce_{r} ∈ action(st^{m}, a), \\ st^{i} ∈ reveal(st^{i+1}), st ∈ goto(st^{0}, A_{r,0}), \\ m = length(rhs(r)), σ = mgu(A_{r,m}, …, A_{r,1}) \end{matrix} \}

D_{LR(DCG)} = D_{LR(DCG)}^{Init} ∪ D_{LR(DCG)}^{InitShift} ∪ D_{LR(DCG)}^{Shift} ∪ D_{LR(DCG)}^{Reduce}

F_{LR(DCG)} = {[S, st_{f}, 0, n]}

6 GLR Logic Push-Down Automata and dynamic programming

The common framework for parsing described by Lang (1991) is based on dynamic programming interpretation of logic push-down automata, which are push-down automata storing logic atoms in the stack instead of symbols in V_{T} ∪ V_{N}. In that framework, weakly predictive automata, such as LR, can be interpreted in dynamic programming using items containing only the top element of the stack. The resulting automata are very close to inference systems (De la Clergerie 1993:173-175). In this context, IP_{LR(DCG)} can be seen as a dynamic programming interpretation of LR(1) or LALR(1) parsing algorithms using an inference system based on that kind of items. It can be easily transformed into a set of logic push-down transitions, applying implicit binarization of clauses. Thus, the reduction of a clause

A_{r,0} → A_{r,1} … A_{r,n_{r}}

can be equivalently performed as the reduction of the following n_{r}+1 clauses with at most 2 elements on their right-hand side:

A_{r,0} → ∇_{r,0}(\overrightarrow{T_{r}})
∇_{r,0}(\overrightarrow{T_{r}}) → A_{r,1} ∇_{r,1}(\overrightarrow{T_{r}})
⋮
∇_{r,n_{r}−1}(\overrightarrow{T_{r}}) → A_{r,n_{r}} ∇_{r,n_{r}}(\overrightarrow{T_{r}})
∇_{r,n_{r}}(\overrightarrow{T_{r}}) → ε

Applying item refinement to IP_{LR(DCG)} items, we obtain the new form of items, in which the element that previously represented a grammar symbol will now represent a symbol in a clause or a ∇_{r,i} meaning that elements A_{r,i+1} … A_{r,n_{r}} have been reduced. Therefore, ∇_{r,i} is like a dotted clause A_{r,0} → α • β where α = A_{r,1} … A_{r,i} and β = A_{r,i+1} … A_{r,n_{r}}. With respect to deduction steps, Reduce steps must be refined into: Sel, which select the clause to be reduced. Red, which reduce each implicit binary clause. Head, which recognize the left-hand symbol of the clause reduced.

Considering that Head deduction steps correspond to SWAP transitions, Init, InitShift, Shift and Sel steps correspond to PUSH transitions and that Red steps correspond to POP transitions, we can transform the deductive steps of the IP_{LR(DCG)} system into a set of logic push-down transitions, with the advantage that we do not need to deal explicitly with unifications because the operational mechanism of the LPDA is in charge of them. The set of logic push-down transitions is the following:

D_{LR^{S1}(DCG)}^{Init} = {⊢ [−, st_{0}, 0, 0]}

D_{LR^{S1}(DCG)}^{InitShift} = \{ \begin{matrix}[A, st, i, j] ⊢ [A_{r,1}, st′, j, j + 1] [A, st, i, j] | \\ ∃[a, j, j + 1] ∈ H_{LR(DCG)}, shift_{st′} ∈ action(st, a), \\ A_{r,1} = a(t_{r,1}^{1}, …, t_{r,1}^{m_{1}}) \end{matrix} \}

D_{LR^{S1}(DCG)}^{Shift} = \{ \begin{matrix}[A_{r,s}, st, i, j] ⊢ [A_{r,s+1}, st′, i, j + 1] [A_{r,s}, st, i, j] | \\ ∃[a, j, j + 1] ∈ H_{LR(DCG)}, shift_{st′} ∈ action(st, a), \\ A_{r,s+1} = a(t_{r,s+1}^{1}, …, t_{r,s+1}^{m_{s+1}}) \end{matrix} \}

D_{LR^{S1}(DCG)}^{Sel} = \{ \begin{matrix}[A_{r,n_{r}}, st, i, j] ⊢ [∇_{r,n_{r}}(\overrightarrow{T_{r}}), st, j, j] [A_{r,n_{r}}, st, i, j] | \\ ∃[a, j, j + 1] ∈ H_{LR(DCG)}, reduce_{r} ∈ action(st, a) \end{matrix} \}

D_{LR^{S1}(DCG)}^{Red} = \{ \begin{matrix}[∇_{r,s}(\overrightarrow{T_{r}}), st, i, k][A_{r,s}, st, k, j] ⊢ [∇_{r,s−1}(\overrightarrow{T_{r}}), st′, i, j] | \\ st′ ∈ reveal(st) \end{matrix} \}

D_{LR^{S1}(DCG)}^{Head} = \{ [∇_{r,0}(\overrightarrow{T_{r}}), st, i, j] ⊢ [A_{r,0}, st′, i, j] | st′ ∈ goto(st, A_{r,0}) \}

D_{LR^{S1}(DCG)} = D_{LR^{S1}(DCG)}^{Init} ∪ D_{LR^{S1}(DCG)}^{InitShift} ∪ D_{LR^{S1}(DCG)}^{Shift}∪
D_{LR^{S1}(DCG)}^{Sel} ∪ D_{LR^{S1}(DCG)}^{Red} ∪ D_{LR^{S1}(DCG)}^{Head}

7 Conclusion

We have considered Earley’s algorithm as a starting point for deriving other well known parsing algorithms, such us Generalized LR. Several intermediate parsing systems have been used in the path from Earley to LR, applying simple and intuitive transformations in each step. The resulting algorithm has been extended to deal with definite clause grammars and it has been integrated in the common framework for parsing in dynamic programming proposed by Lang. An implementation of a parser for DCGs based on our specification of LALR(1) parsers has been described in (Vilares & Alonso forthcoming).

Acknowledgements. This work has been partially supported by the FEDER of the European Union (1FD97-0047-C04-02), Government of Spain (HF97-223) and Xunta de Galicia (XUGA10505B96 and XUGA20402B97).

REFERENCES

Aho, Alfred V. & Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation

and Compiling. Englewood Cliffs: Prentice Hall. De la Clergerie, Eric. 1993. Automates à Piles et Programmation Dynamique.

DyALog : Une Application à la Programmation en Logique. Ph.D. dissertation. Université Paris 7. Paris, France.

Earley, J. 1970. “An Efficient Context-Free Parsing Algorithm”. Communica-

tions of the Associattion for Computing Machinery (CACM) 13:2.94-102. Lang, Bernard. 1991. “Towards a Uniform Formal Framework for Parsing”. Cur-

rent Issues in Parsing Technology ed. by Masaru Tomita, 153-171. Norwell: Kluwer Academic.

Nederhof, Mark-Jan & J. J. Sarbo. 1996. “Increasing the Applicability of LR Parsing”. Recent Advances in Parsing Technology ed. by H. Bunt & M. Tomita, 35-57. Dordrecht: Kluwer Academic.

Pereira, Fernando C. N. & David H. D. Warren. 1980. “Definite Clause Grammars for Language Analysis: A Survey of the Formalism and a Comparison with Augmented Transition Networks”. Artificial Intelligence, 13.231-278.

Rekers, Jan. 1992. Parsing Generation for Interactive Environments. Ph.D.

dissertation, Amsterdam: University of Amsterdam. Sheil, B. A. 1976. “Observations on Context-Free Grammars”. Statistical Meth-

ods in Linguistics, 71-109, Stockholm, Sweden. Shieber, Stuart. 1985. “Using Restriction to Extend Parsing Algorithms for

Complex-Feature-Based Formalisms”. Proceedings of the 23th Annual Meeting of the Association for Computational Linguistics (ACL’85), 145-152.

Sikkel, Klaas. 1997. Parsing Schemata: A Framework for Specification and

Analysis of Parsing Algorithms. Heidelberg: Springer-Verlag. Tomita, Masaru. 1986. Efficient Parsing for Natural Language. Boston: Kluwer

Academic. Trujillo, Arturo. 1994. “Computing First and Follow Functions for Feature-

Theoretic Grammars”. Proceedings of the Fifteenth International Conference on Computational Linguistics (COLING’94). Kyoto, Japan.

Vilares, Manuel & Miguel A. Alonso. Forthcoming. “An LALR Extension for DCGs in Dynamic Programming”. To appear in Mathematical Linguistics II ed. by Carlos Martín Vide. Amsterdam: John Benjamins. , David Cabrero & Miguel A. Alonso. 1998. “A Comparison for Unification-Based Parsers”. Proceedings of APPIA-GULP-PRODE 1998 Joint Conference on Declarative Programming (AGP’98) ed. by Moreno Falaschi, José L. Freire & Manuel Vilares, 113–123. La Coruña, Spain.