AN OPTIMAL TABULAR PARSING ALGORITHM 
Mark-Jan Nederhof * 
University of Nijmegen, Department of Computer Science 
Toernooiveld, 6525 ED Nijmegen, The Netherlands 
markj an~cs, kun. nl 
Abstract 
In this paper we relate a number of parsing algorithms 
which have been developed in very different areas of 
parsing theory, and which include deterministic algo- 
rithms, tabular algorithms, and a parallel algorithm. 
We show that these algorithms are based on the same 
underlying ideas. 
By relating existing ideas, we hope to provide an op- 
portunity to improve some algorithms based on features 
of others. A second purpose of this paper is to answer a 
question which has come up in the area of tabular pars- 
ing, namely how to obtain a parsing algorithm with the 
property that the table will contain as little entries as 
possible, but without the possibility that two entries 
represent the same subderivation. 
Introduction 
Left-corner (LC) parsing is a parsing strategy which 
has been used in different guises in various areas of com- 
puter science. Deterministic LC parsing with k symbols 
of lookahead can handle the class of LC(k) grammars. 
Since LC parsing is a very simple parsing technique and 
at the same time is able to deal with left recursion, it is 
often used as an alternative to top-down (TD) parsing, 
which cannot handle left recursion and is generally less 
efficient. 
Nondeterministic LC parsing is the foundation of a 
very efficient parsing algorithm \[7\], related to Tomita's 
algorithm and Earley's algorithm. It has one disad- 
vantage however, which becomes noticeable when the 
grammar contains many rules whose right-hand sides 
begin with the same few grammars symbols, e.g. 
A ~ c~f~l I ~f~2 I ... 
where ~ is not the empty string. After an LC parser 
has recognized the first symbol X of such an c~, it will 
as next step predict all aforementioned rules. This 
amounts to much nondeterminism, which is detrimental 
both to the time-complexity and the space-complexity. 
*Supported by the Dutch Organisation for Scientific Re- 
search (NWO), under grant 00-62-518 
A first attempt to solve this problem is to use predic- 
tive LR (PLR) parsing. PLR parsing allows simulta- 
neous processing of a common prefix c~, provided that 
the left-hand sides of the rules are the same. However, 
in case we have e.g. the rules A --* c~t31 and B --~ ~/32, 
where again ~ is not the empty string but now A ~ B, 
then PLR parsing will not improve the efficiency. We 
therefore go one step further and discuss extended LR 
(ELR) and common-prefix (CP) parsing, which are al- 
gorithms capable of simultaneous processing of all com- 
mon prefixes. ELR and CP parsing are the foundation 
of tabular parsing algorithms and a parallel parsing al- 
gorithm from the existing literature, but they have not 
been described in their own right. 
To the best of the author's knowledge, the various 
parsing algorithms mentioned above have not been dis- 
cussed together in the existing literature. The main 
purpose of this paper is to make explicit the connec- 
tions between these algorithms. 
A second purpose of this paper is to show that CP 
and ELR parsing are obvious solutions to a problem of 
tabular parsing which can be described as follows. For 
each parsing algorithm working on a stack there is a 
realisation using a parse table, where the parse table 
allows sharing of computation between different search 
paths. For example, Tomita's algorithm \[18\] can be seen 
as a tabular realisation of nondeterministic LR parsing. 
At this point we use the term state to indicate the 
symbols occurring on the stack of the original algo- 
rithm, which also occur as entries in the parse table 
of its tabular realisation. 
In general, powerful algorithms working on a stack 
lead to efficient tabular parsing algorithms, provided 
the grammar can be handled almost deterministically. 
In case the stack algorithm is very nondeterministic for 
a certain grammar however, sophistication which in- 
creases the number of states may lead to an increasing 
number of entries in the parse table of the tabular re- 
alization. This can be informally explained by the fact 
that each state represents the computation of a number 
of subderivations. If the number of states is increased 
then it is inevitable that at some point some states 
represent an overlapping collection of subderivations, 
117 
which may lead to work being repeated during parsing. 
Furthermore, the parse forest (a compact representa- 
tion of all parse trees) which is output by a tabular 
algorithm may in this case not be optimally dense. 
We conclude that we have a tradeoff between the case 
that the grammar allows almost deterministic parsing 
and the case that the stack algorithm is very nondeter- 
ministic for a certain grammar. In the former case, so- 
phistication leads to less entries in the table, and in the 
latter case, sophistication leads to more entries, pro- 
vided this sophistication is realised by an increase in 
the number of states. This is corroborated by empirical 
data from \[1, 4\], which deal with tabular LR parsing. 
As we will explain, CP and ELR parsing are more 
deterministic than most other parsing algorithms for 
many grammars, but their tabular realizations can 
never compute the same subderivation twice. This rep- 
resents an optimum in a range of possible parsing algo- 
rithms. 
This paper is organized as follows. First we discuss 
nondeterministic left-corner parsing, and demonstrate 
how common prefixes in a grammar may be a source of 
bad performance for this technique. 
Then, a multitude of parsing techniques which ex- 
hibit better treatment of common prefixes is dis- 
cussed. These techniques, including nondeterministic 
PLR, ELR, and CP parsing, have their origins in theory 
of deterministic, parallel, and tabular parsing. Subse- 
quently, the application to parallel and tabular parsing 
is investigated more closely. 
Further, we briefly describe how rules with empty 
right-hand sides complicate the parsing process. 
The ideas described in this paper can be generalized 
to head-driven parsing, as argued in \[9\]. 
We will take some liberty in describing algorithms 
from the existing literature, since using the original de- 
scriptions would blur the similarities of the algorithms 
to one another. In particular, we will not treat the use 
of lookahead, and we will consider all algorithms work- 
ing on a stack to be nondeterministic. We will only 
describe recognition algorithms. Each of the algorithms 
can however be easily extended to yield parse trees as 
a side-effect of recognition. 
The notation used in the sequel is for the most part 
standard and is summarised below. 
A context-free grammar G = (T, N, P, S) consists of 
two finite disjoint sets N and T of nonterminals and 
terminals, respectively, a start symbol S E N, and a 
finite set of rules P. Every rule has the form A --* c~, 
where the left-hand side (lhs) A is an element from N 
and the right-hand side (rhs) a is an element from V*, 
where V denotes (NUT). P can also be seen as a 
relation on N × V*. 
We use symbols A, B, C,... to range over N, symbols 
a, b, c,... to range over T, symbols X, \]I, Z to range over 
V, symbols c~, \[3, 7,-.. to range over V*, and v, w, x,... 
to range over T*. We let e denote the empty string. The 
notation of rules A --* al, A --* a2,.., with the same 
lhs is often simplified to A ~ c~1\]a21... 
A rule of the form A --~ e is called an epsilon rule. 
We assume grammars do not have epsilon rules unless 
stated otherwise. 
The relation P is extended to a relation ~ on V* × V* 
as usual. The reflexive and transitive closure of ~ is 
denoted by --**. 
We define: B L A if and only if A --* Be for some a. 
The reflexive and transitive closure of / is denoted by 
/*, and is called the left-corner relation. 
We say two rules A --* al and B --* a2 have a com- 
mon prefix \[3 if c~1 = \[3"/1 and a2 = \[3'/2, for some '/1 
and '/2, where \[3 ¢ e. 
A recognition algorithm can be specified by means 
of a push-down automaton A = (T, Alph, Init, ~-, Fin), 
which manipulates configurations of the form (F,v), 
where F E Alph* is the stack, constructed from left 
to right, and v • T* is the remaining input. 
The initial configuration is (Init, w), where Init E 
Alph is a distinguished stack symbol, and w is the input. 
The steps of an automaton are specified by means of the 
relation ~-. Thus, (F,v) ~- (F',v') denotes that (F',v') 
is obtainable from (F, v) by one step of the automaton. 
The reflexive and transitive closure of ~- is denoted by 
F-*. The input w is accepted if (Init, w) F-* (Fin, e), 
where Fin E Alph is a distinguished stack symbol. 
LC parsing 
For the definition of left-corner (LC) recognition \[7\] we 
need stack symbols (items) of the form \[A --~ a • \[3\], 
where A --~ c~\[3 is a rule, and a ¢ e. (Remember that 
we do not allow epsilon rules.) The informal meaning 
of an item is "The part before the dot has just been 
recognized, the first symbol after the dot is to be rec- 
ognized next". For technical reasons we also need the 
items \[S' ~ ..S\] and \[S' --~ S .\], where S' is a fresh 
symbol. Formally: 
I LC = {\[A --* a • f\]l A --* af • Pt A(c~ ¢ eVA -- S')} 
where pt represents the augmented set of rules, consist- 
ing of the rules in P plus the extra rule S t --~ S. 
Algorithm 1 (Left-corner) 
ALe= (T,I Lc, Init,~-, Fin), Init = IS' ---* • S\], Fin = 
\[S t --* S .\]. Transitions are allowed according to the 
following clauses. 
1. (FIB --* f • C'/\], av) ~- 
(F\[B --~/3 • CT\]\[A ~ a • ~\], v) 
where there is A --* ac~ • P~ such that A \[* C 
2. (F\[A --~ a • aft\], av) ~- (F\[A --* c~a •/3\], v) 
3. (FIB ~ \[3 • C'/\]\[d ~ ~ .\], v) 
(rib ~ f • C'/\]\[D ---, A • 6\], v) 
where there is D ~ A5 • pt such that D L* C 
4. (FIB --* \[3 • A'/\]\[A ---* a .\], v) ~- (FIB ~ fA • '/\], v) 
The conditions using the left-corner relation Z* in the 
first and third clauses together form a feature which is 
118 
called top-down (TD) filtering. TD filtering makes sure 
that subderivations that are being computed bottom- 
up may eventually grow into subderivations with the re- 
quired root. TD filtering is not necessary for a correct 
algorithm, but it reduces nondeterminism, and guar- 
antees the correct-prefix property, which means that in 
case of incorrect input the parser does not read past the 
first incorrect character. 
Example 1 Consider the grammar with the following 
rules: 
E ---* E+T\[TTE\[T 
T ~ T*FIT**F IF 
F ---* a 
It is easy to see that E / E,T Z E,T L T, F / T. 
The relation L* contains g but from the reflexive closure 
it also contains F L* F and from the transitive closure 
it also contains F L* E. 
The recognition of a * a is realised by: 
\[E' --* • E-I- a,a 
1 \[E'--~ •E\]\[F--*a•\] *a 
2 \[E'--*•E\]\[T~F•\] *a 
3 \[E'--~QE\]\[T--*T.*F\] *a 
4 \[E'~ •E\]\[T~T.•F\] a 
5 \[E'~.EI\[T--*T.•F\]\[F---*ae\] 
6 \[E' ---* • E\]\[T ---* T * F •\] 
7 \[E'~•E\]\[E~T•\] 
8 \[E'~E•\] 
Note that since the automaton does not use any looka- 
head, Step 3 may also have replaced \[T ---* F •\] by 
any other item besides \[T --* T • • F\] whose rhs starts 
with T and whose lhs satisfies the condition of top- 
down filtering with regard to E, i.e. by \[T --~ T • **F\], 
\[E ~ T. T El, or \[E ~ T •\]. \[\] 
LC parsing with k symbols of lookahead can handle 
deterministically the so called LC(k) grammars. This 
class of grammars is formalized in \[13\]. 1 How LC pars- 
ing can be improved to handle common su~xes effi- 
ciently is discussed in \[6\]; in this paper we restrict our 
attention to common prefixes. 
PLR, ELR, and CP parsing 
In this section we investigate a number of algorithms 
which exhibit a better treatment of common prefixes. 
Predictive LR parsing 
Predictive LR (PLR) parsing with k symbols of looka- 
head was introduced in \[17\] as an algorithm which yields 
efficient parsers for a subset of the LR(k) grammars \[16\] 
and a superset of the LC(k) grammars. How determin- 
istic PLR parsing succeeds in handling a larger class 
of grammars (the PLR(k) grammars) than the LC(k) 
grammars can be explained by identifying PLR parsing 
1In \[17\] a different definition of the LC(k) grammars may 
be found, which is not completely equivalent. 
for some grammar G with LC parsing for some gram- 
mar G t which results after applying a transformation 
called left-factoring. 
Left-factoring consists of replacing two or more rules 
A ~ a/31 \[a/32\[... with a common prefix a by the rules 
A ~ hA' and A' --* ~311f~2\[..., where A' is a fresh non- 
terminal. The effect on LC parsing is that a choice 
between rules is postponed until after all symbols of a 
are completely recognized. Investigation of the next k 
symbols of the remaining input may then allow a choice 
between the rules to be made deterministically. 
The PLR algorithm is formalised in \[17\] by trans- 
forming a PLR(k) grammar into an LL(k) grammar 
and then assuming the standard realisation of LL(k) 
parsing. When we consider nondeterministic top-down 
parsing instead of LL(k) parsing, then we obtain the 
new formulation of nondeterministic PLR(0) parsing 
below. 
We first need to define another kind of item, viz. of 
the form \[A --* ~\] such that there is at least one rule of 
the form A --* a/3 for some ft. Formally: 
I PLR = {\[A ---* ~\] \[ A --* a/3 • pt A (a # e V A = S')} 
Informally, an item \[A --* ~ I PLa a • represents one or 
more items \[A --~ cr •/3\] • I e. 
Algorithm 2 (Predictive LR) 
A PLR = (T, I PLR, Init, F-, Fin), Init = \[S' --~ \], Fin = 
\[S t --~ S\], and F- defined by: 
1. (F\[B --~/3\], av) F- (rib -~/3\]\[A -~ ~\],,) 
where there are A --~ as, B ---* tiC7 • pt such that 
AL*C 
2. (F\[A --* a\], av) F- (r\[A --, ~a\], v) 
where there is A ~ haft • P+ 
3. (FIB--*/3\]\[A -* a\], v) b (rOB--,/3\]\[0--, A\], v) 
where A --* cr • Ptand where there are D 
A~f, B --~ f?C7 • pt such that D/* C 
4. (F\[B --*/3\]\[A --, a\],v) ~- (F\[B --*/~A\], v) 
where A --~ a • pT and where there is B --~/3A7 • 
pt 
Example 2 Consider the grammar from Example 1. 
Using Predictive LR, recognition of a * a is realised by: 
\[E' ~ \] a * a 
\[E' \]\[F a\] • a 
\[E' --~ \]\[T ---* F\] * a 
\[E' --* \]\[T --* T\] * a 
\[E' --* \]\[T ~ T .\] a 
: 
\[E' E\] 
Comparing these configurations with those reached by 
the LC recognizer, we see that here after Step 3 the 
stack element IT --~ T\] represents both \[T ~ T • * F\] 
and \[T --* T • **F\], so that nondeterminism is reduced. 
Still some nondeterminism remains, since Step 3 could 
also have replaced \[T --* F\] by \[Z --* T\], which repre- 
sents both \[E --* T- T E\] and \[E --~ T •\]. \[\] 
119 
Extended Lit parsing 
An extended context-free grammar has right-hand sides 
consisting of arbitrary regular expressions over V. This 
requires an LR parser for an extended grammar (an 
ELR parser) to behave differently from normal LR 
parsers. 
The behaviour of a normal LR parser upon a reduc- 
tion with some rule A --* a is very simple: it pops la\[ 
states from the stack, revealing, say, state Q; it then 
pushes state goto(Q, A). (We identify a state with its 
corresponding set of items.) 
For extended grammars the behaviour upon a reduc- 
tion cannot be realised in this way since the regular 
expression of which the rhs is composed may describe 
strings of various lengths, so that it is unknown how 
many states need to be popped. 
In \[11\] this problem is solved by forcing the parser to 
decide at each call goto(Q, X) whether 
a) X is one more symbol of an item in Q of which some 
symbols have already been recognized, or whether 
b) X is the first symbol of an item which has been 
introduced in Q by means of the closure function. 
In the second case, a state which is a variant of 
goto(Q,X) is pushed on top of state Q as usual. In 
the first case, however, state Q on top of the stack is 
replaced by a variant of goto(Q, X). This is safe since 
we will never need to return to Q if after some more 
steps we succeed in recognizing some rule correspond- 
ing with one of the items in Q. A consequence of the 
action in the first case is that upon reduction we need 
to pop only one state off the stack. 
Further work in this area is reported in \[5\], which 
treats nondeterministic ELR parsing and therefore does 
not regard it as an obstacle if a choice between cases a) 
and b) cannot be uniquely made. 
We are not concerned with extended context-free 
grammars in this paper. However, a very interesting 
algorithm results from ELR parsing if we restrict its ap- 
plication to ordinary context-free grammars. (We will 
maintain the name "extended LR" to stress the origin 
of the algorithm.) This results in the new nondetermin- 
istic ELR(0) algorithm that we describe below, derived 
from the formulation of ELK parsing in \[5\]. 
First, we define a set of items as 
I = {\[A --* c~ •/3\] I A --* 4/3 E pt} 
Note that I LC C I. If we define for each Q G I: 
closure(Q) -= 
QU{\[A--*.a\]I\[B--*/3.CT\]EQAAZ*C} 
then the goto function for LR(0) parsing is defined by 
goto(q,x) = 
closure({\[A ---* aX •/3\] I \[A ~ a • X/3\] E Q}) 
For ELR parsing however, we need two goto func- 
tions, goto I and goto2, one for kernel items (i.e. those 
in I LC) and one for nonkernel items (the others). These 
are defined by 
gotol(Q,X) = 
closure({\[A --* aX • fl\] I \[A ---* (~ • X/3\] E Q A 
(a # e VA = S')}) 
goto2(Q,X ) = 
closure({\[A ~ X •/3\] I \[A --* • X/3\] 6 Q A A # S'}) 
At each shift (where X is some terminal) and each re- 
duce with some rule A --* a (where X is A) we may non- 
deterministically apply gotol, which corresponds with 
case a), or goto2, which corresponds with case b). Of 
course, one or both may not be defined on Q and X, 
because gotoi(Q, X) may be @, for i E {1, 2}. 
Now remark that when using goto I and goto2, each 
reachable set of items contains only items of the form 
A --* a •/3, for some fixed string a, plus some nonkernel 
items. We will ignore the nonkernel items since they 
can be derived from the kernel items by means of the 
closure function. 
This suggests representing each set of items by a new 
kind of item of the form \[{Az, A2,..., A,~} --* a\], which 
represents all items A --* a • /3 for some /3 and A E 
{A1, A2,..., An}. Formally: 
I ELR .~ {\[A ---+ a\] \] 0 C A G {A I A --* aft E pt} A 
(4 # E v a = {s'})} 
where we use the symbol A to range over sets of non- 
terminals. 
Algorithm 3 (Extended LR) 
A ELR = (T, I ELR, Init, t-, Fin), Init = \[{S'} --* \], Fin = 
\[{S'} --* S\], and t- defined by: 
1. (rid -./31, (rid -./3\]\[a' -. a\],v) 
where A' = {A I 3A ~ aa, S --~ flC'y 6 pt\[B E 
A A A Z* C\]} is non-empty 
2. (rid a\], (rid' 
where A' = { A E A \[ A ---* daft E pt } is non-empty 
3. (F\[A --* fl\]\[A' --. a\],v) t- (F\[A --*/3\]\[A" --. A\],v) 
where there is A --* a E pt with A E A', and A" -~ 
{D 130 ---* A6, B --*/3C7 E Pt\[B 6 A A D Z* C\]}is 
non-empty 
4. (F\[A --. fl\]\[A' ---, a\],v) }- (F\[A" --* flA\],v) 
where there is A --* a E pt with A E A', and A" = 
{B E A I B --*/3A',/E pt} is non-empty 
Note that Clauses 1 and 3 correspond with goto 2 and 
that Clauses 2 and 4 correspond with goto 1. 
Example 3 Consider again the grammar from Exam- 
ple 1. Using the ELR algorithm, recognition of a * a is 
realised by: 
\[{E'} -* \] a a 
\[{E'} \]\[{F} 6\] a 
\[{E'} --* \]\[{T} --* F\] a 
\[{E'} --* \]\[{T, E} --* T\] a 
\[{E'} --* \]\[{T} --* T *\] a 
\[{E'} ---* E\] 
120 
Comparing these configurations with those reached by 
the PLR recognizer, we see that here after Step 3 the 
stack element \[{T, E} ~ T\] represents both \[T ---* T • 
• F\] and \[T --, T • * * F\], but also \[E --* T .\] and 
\[E -~ T • T E\], so that nondeterminism is even further 
reduced. \[\] 
A simplified ELR algorithm, which we call the pseudo 
ELR algorithm, results from avoiding reference to A in 
Clauses 1 and 3. In Clause 1 we then have a simplified 
definition of A ~, viz. A ~ = {A \[ 3A --* as, B ---* tiC'7 E 
Pt\[a l* C\]}, and in the same way we have in Clause 3 
the new definition A" = {D \[ 3D ~ AS, B --~ ~C~( E 
Pt\[D \[* C\]}. Pseudo ELR parsing can be more easily 
realised than full ELR parsing, but the correct-prefix 
property can no longer be guaranteed. Pseudo ELR 
parsing is the foundation of a tabular algorithm in \[20\]. 
Common-prefix parsing 
One of the more complicated aspects of the ELR algo- 
rithm is the treatment of the sets of nonterminals in 
the left-hand sides of items. A drastically simplified 
algorithm is the basis of a tabular algorithm in \[21\]. 
Since in \[21\] the algorithm itself is not described but 
only its tabular realisation, 2 we take the liberty of giv- 
ing this algorithm our own name: common-prefix (CP) 
parsing, since it treats all rules with a common prefix 
simultaneously, a 
The simplification consists of omitting the sets of 
nonterminals in the left-hand sides of items: 
I Cp = {\[--* s\] \[ A ~ s/3 e pt} 
Algorithm 4 (Common-prefix) 
A t;r = (T, I cP, Init, ~-, Fin), Init = \[--*\], Fin = \[---+ S\], 
and I- defined by: 
i. (F\[---* /3\], av) ~ (F\[---* /3\]\[4_. a\], v) 
where there are A --~ as, B --~/3C'7 E pt such that 
AL*C 
2. (r\[-~ a\], av) ~ (r\[-~ sa\], v) 
where there is A --~ sa~3 E pt 
3. (F\[--~/3\]\[4_. s\], v) F- (F\[--~ fl\]\[--. A\], v) 
where there are A --* a, D -* A6, B --* /3C'7 E pt 
such that D/* C 
4. (V\[-~/3\]\[4_, s\], v) F- (V\[--*/3A\], v) 
where there are A --* s, B --~/3A'7 E pt 
The simplification which leads to the CP algorithm 
inevitably causes the correct-prefix property to be lost. 
Example 4 Consider again the grammar from Exam- 
ple 1. It is clear that a÷a T ais not acorrect string 
according to this grammar. The CP algorithm may go 
through the following sequence of configurations: 
2An attempt has been made in \[19\] but this paper does 
not describe the algorithm in its full generality. 
3The original algorithm in \[21\] applies an optimization 
concerning unit rules, irrelevant to our discussion. 
1 
2 F\] 
3 \[--*\]\[-* T\] 
4 \[--*\]\[-* E\] 
5 E 
6 E 
7 E 
0 ¢ 
+\] 
÷\]\[--, F\] 
T\] 
T T\] 
a÷aTa 
÷aTa 
÷aT a 
÷aTa 
÷aTa 
aTa 
Ta Ta 
~a 
a 
10 E r a\] 
We see that in Step 9 the first incorrect symbol T is read, 
but recognition then continues. Eventually, the recog- 
nition process is blocked in some unsuccessful configu- 
ration, which is guaranteed to happen for any incorrect 
input 4. In general however, after reading the first incor- 
rect symbol, the algorithm may perform an unbounded 
number of steps before it halts. (Imagine what happens 
for input of the forma+aTa÷a+a+...+a.) \[\] 
Tabular parsing 
Nondeterministic push-down automata can be realised 
efficiently using parse tables \[1\]. A parse table consists 
of sets Ti,j of items, for 0 < i < j _~ n, where al ...an 
represents the input. The idea is that an item is only 
stored in a set Ti,j if the item represents recognition of 
the part of the input ai+l • • • aj. 
We will first discuss a tabular form of CP parsing, 
since this is the most simple parsing technique discussed 
above. We will then move on to the more difficult ELR 
technique. Tabular PLR parsing is fairly straightfor- 
ward and will not be discussed in this paper. 
Tabular CP parsing 
CP parsing has the following tabular realization: 
Algorithm 5 (Tabular common-prefix) P c 
Sets Tij of the table are to be subsets of I . Start 
with an empty table. Add \[-*\] to T0,0. Perform one of 
the following steps until no more items can be added. 
1. Add \[--~ a\] to T~-i,i for a = al and \[--*/3\] E Tj,i-i 
where there are A --* an, B --* /3C'7 E P? such that 
A/*C 
2. Add \[-~ sa\] to Tj,i for a = ai and \[--* a\] E Tj,l-i 
where there is A --* an/3 E pt 
3. Add \[--* A\] to Tj# for \[--* a\] e Tj,i and \[-*/3\] E Th,j 
where there are A --~ s, D --* AS, B --* /3C'7 E pt 
such that D/* C 
4. Add \[--~/3A\] to Th,i for \[--* s\] E Tj,i and \[---~/3\] E Th,j 
where there are A --* s, B --*/3A 7 E pt 
Report recognition of the input if \[--~ S\] E T0,n. 
For an example, see Figure 1. 
Tabular CP parsing is related to a variant of CYK 
parsing with TD filtering in \[5\]. A form of tabular 
4unless the grammar is cyclic, in which case the parser 
may not terminate, both on correct and on incorrect input 
121 
0 1 2 
\[--.\] (0) \[-*\[-*\[--*\[--* T\]E\]F\]a\] (4)(3)(2)(1) \[--. E +\](5) 
1 0 
3 
\[--* E + T\] E\] 
\[4 a\] (6) 
\[--* F\] (7) 
\[--* T\] (s) 
Figure 1: Tabular 
0 
\[--* T T\] (9) 
CP parsing without top-down filtering (i.e. without the 
checks concerning the left-corner relation /*) is the 
main algorithm in \[21\]. 
Without the use of top-down filtering, the references 
to \[---~/9\] in Clauses 1 and 3 are clearly not of much use 
any more. When we also remove the use of these items, 
then these clauses become: 
\[--* T T E\] 
Consider again the grammar from 
Example 1 and the (incorrect) in- 
put a + a T a. After execution 
of the tabular common-prefix al- 
gorithm, the table is as given here. 
The sets Tj,i are given at the j-th 
row and i-th column. 
The items which correspond with 
those from Example 4 are labelled 
with (0), (1),... These labels also 
indicate the order in which these 
items are added to the table. 
1. Add \[--+ a\] to Tc-I,C for a = ai 
where there is A --* ac~ • pt 
3. Add \[--* A\] to Tj,i for \[--+ o~\] • Tj,i 
where there are A ---* a, D --* A6 • pt 
\[--* a\] (Io) 
T\] \[--, E\] 
CP parsing 
However, for certain i there may be many \[A ~ /9\] • 
Tj,c-1, for some j, and each may give rise to a different 
A' which is non-empty. In this way, Clause 1 may add 
several items \[A' --~ a\] to Tc-I,C, some possibly with 
overlapping sets A'. Since items represent computation 
of subderivations, the algorithm may therefore compute 
the same subderivation several times. 
In the resulting algorithm, no set Tc,j depends on any 
set Tg,h with g < i. In \[15\] this fact is used to construct 
a parallel parser with n processors Po,..., Pn-1, with 
each Pi processing the sets Ti,j for all j > i. The flow 
of data is strictly from right to left, i.e. items computed 
by Pc are only passed on to P0,..., Pc-1. 
Tabular ELR parsing 
The tabular form of ELR parsing allows an optimiza- 
tion which constitutes an interesting example of how a 
tabular algorithm can have a property not shared by its 
nondeterministic origin. 5 
First note that we can compute the columns of a 
parse table strictly from left to right, that is, for fixed i 
we can compute all sets Tj,c before we compute the sets 
Tj,C-F1 • 
If we formulate a tabular ELR algorithm in a naive 
way analogously to Algorithm 5, as is done in \[5\], then 
for example the first clause is given by: 
1. Add \[A' --. a\] to Tc-1,c for a = ac and 
\[A ~/9\] • Tj,c-1 
where A' -- {A \] 3A --~ a(~,B --+ /9C~ • Pt\[B • 
A A A Z* C\]} is non-empty 
5This is reminiscent of the admissibility tests \[3\], which 
are applicable to tabular realisations of logical push-down 
automata, but not to these automata themselves. 
We propose an optimization which makes use of the 
fact that all possible items \[A --+/9\] • Tj,i-1 are already 
present when we compute items in Ti-l,i: we compute 
one single item \[A' -+ hi, where A' is a large set com- 
puted using all \[A --+ /9\] • Tj,i-1, for any j. A similar 
to Tj, i • 
\[A ---* c~\] • Tj,i-1 
• A i A -~ c~a/9 • pt } is non-empty 
optimization can be made for the third clause. 
Algorithm 6 (Tabular extended LR) 
Sets T/j of the table are to be subsets of I ELR. Start 
with an empty table. Add \[{S'} ~ \] to T0,0. For 
i ---- 1,..., n, in this order, perform one of the following 
steps until no more items can be added. 
1. Add \[A' --. a\] to Ti-l# for a = ai 
where A' = {A I 3j3\[A --*/9\] • Tj,i-13A ----, ha, B ---* 
/9C0' • pt\[B • A A A Z* C\]} is non-empty 
2. Add \[A' --* aa\] for a = ai and 
where A' = {A 
3. Add \[A" --. A\] to Tj,i for \[A' --* a\]E Tj,i 
where there is A --+ a E pt with A E A', and A" = 
{D \[ 3h3\[A --* /9\] E TtL,j3D ----, A6, B ----, /9C',/ E 
pt\[B E A A D Z* C\]} is non-empty 
4. Add \[A" --./gA\] to Th,i for \[A' --* a\] E Tj,/ and 
\[A --,/9\] • Th,j 
where there is A --* a • pt with A • A', and A" = 
{B • A \] B --~/9A7 • pt} is non-empty 
Report recognition of the input if \[{S'} --* S\] • T0,,~. 
Informally, the top-down filtering in the first and 
third clauses is realised by investigating all left corners 
D of nonterminals C (i.e. D Z* C) which are expected 
122 
from a certain input position. For input position i these 
nonterminals D are given by 
Si = {D \] 3j3\[A ~ fl\] E Td,i 
3B --, tiC"/e Pt\[B E A A D Z* C\]} 
Provided each set Si is computed just after comple- 
tion of the i-th column of the table, the first and third 
clauses can be simplified to: 
1. Add \[A' ~ a\] to Ti-l,i for a = a i 
where A' = {A \[ A --~ aa E pt} M Si-1 is non-empty 
3. Add \[A" ---, A\] to Tj,i for \[A' --, ~\] E Tj,i 
where there is A --, a E pt with A E A', and A" = 
{D \[ D ~ A5 E pt} N Sj is non-empty 
which may lead to more practical implementations. 
Note that we may have that the tabular ELR algo- 
rithm manipulates items of the form \[A --~ a\] which 
would not occur in any search path of the nondeter- 
ministic ELR algorithm, because in general such a A 
is the union of many sets A' of items \[A ~ --~ a\] which 
would be manipulated at the same input position by the 
nondeterministic algorithm in different search paths. 
With minor differences, the above tabular ELR algo- 
rithm is described in \[21\]. A tabular version of pseudo 
ELR parsing is presented in \[20\]. Some useful data 
structures for practical implementation of tabular and 
non-tabular PLR, ELR and CP parsing are described 
in \[S\], 
Finding an optimal tabular algorithm 
In \[14\] Schabes derives the LC algorithm from LR pars- 
ing similar to the way that ELR parsing can be derived 
from LR parsing. The LC algorithm is obtained by not 
only splitting up the goto function into goto 1 and goto 2 
but also splitting up goto~ even further, so that it non- 
deterministically yields the closure of one single kernel 
item. (This idea was described earlier in \[5\], and more 
recently in \[10\].) 
Schabes then argues that the LC algorithm can be 
determinized (i.e. made more deterministic) by manip- 
ulating the goto functions. One application of this idea 
is to take a fixed grammar and choose different goto 
functions for different parts of the grammar, in order 
to tune the parser to the grammar. 
In this section we discuss a different application of 
this idea: we consider various goto functions which are 
global, i.e. which are the same for all parts of a grammar. 
One example is ELR parsing, as its goto~ function can 
be seen as a determinized version of the goto 2 function 
of LC parsing. In a similar way we obtain PLR parsing. 
Traditional LR parsing is obtained by taking the full 
determinization, i.e. by taking the normal goto function 
which is not split up. 6 
6Schabes more or less also argues that LC itself can be 
obtained by determinizing TD parsing. (In lieu of TD pars- 
ing he mentions Earley's algorithm, which is its tabular 
realisation.) 
We conclude that we have a family consisting of LC, 
PLR, ELR, and LR parsing, which are increasingly de- 
terministic. In general, the more deterministic an algo- 
rithm is, the more parser states it requires. For exam- 
ple, the LC algorithm requires a number of states (the 
items in I Lc) which is linear in the size of the gram- 
mar. By contrast, the LR algorithm requires a number 
of states (the sets of items) which is exponential in the 
size of the grammar \[2\]. 
The differences in the number of states complicates 
the choice of a tabular algorithm as the one giving op- 
timal behaviour for all grammars. If a grammar is very 
simple, then a sophisticated algorithm such as LR may 
allow completely deterministic parsing, which requires a 
linear number of entries to be added to the parse table, 
measured in the size of the grammar. 
If, on the other hand, the grammar is very ambigu- 
ous such that even LR parsing is very nondeterministic, 
then the tabular realisation may at worst add each state 
to each set Tij, so that the more states there are, the 
more work the parser needs to do. This favours sim- 
ple algorithms such as LC over more sophisticated ones 
such as LR. Furthermore, if more than one state repre- 
sents the same subderivation, then computation of that 
subderivation may be done more than once, which leads 
to parse forests (compact representations of collections 
of parse trees) which are not optimally dense \[1, 12, 7\]. 
Schabes proposes to tune a parser to a grammar, or 
in other words, to use a combination of parsing tech- 
niques in order to find an optimal parser for a certain 
grammar. 7 This idea has until now not been realised. 
However, when we try to find a single parsing algorithm 
which performs well for all grammars, then the tabu- 
lar ELR algorithm we have presented may be a serious 
candidate, for the following reasons: 
• For M1 i, j, and a at most one item of the form 
\[A --, ct\] is added to Tij. Therefore, identical sub- 
derivations are not computed more than once. (This 
is a consequence of our optimization in Algorithm 6.) 
Note that this also holds for the tabular CP algo- 
rithm. 
• ELR parsing guarantees the correct-prefix property, 
contrary to the CP algorithm. This prevents com- 
putation of all subderivations which are useless with 
regard to the already processed input. 
• ELR parsing is more deterministic than LC and PLR 
parsing, because it allows shared processing of all 
common prefixes. It is hard to imagine a practical 
parsing technique more deterministic than ELR pars- 
ing which also satisfies the previous two properties. 
In particular, we argue in \[8\] that refinement of the 
LR technique in such a way that the first property 
above holds whould require an impractically large 
number of LR states. 
7This is reminiscent of the idea of "optimal cover" \[5\]. 
123 
Epsilon rules 
Epsilon rules cause two problems for bottom-up pars- 
ing. The first is non-termination for simple realisations 
of nondeterminism (such as backtrack parsing) caused 
by hidden left recursion \[7\]. The second problem occurs 
when we optimize TD filtering e.g. using the sets Si: it 
is no longer possible to completely construct a set Si be- 
fore it is used, because the computation of a derivation 
deriving the empty string requires Si for TD filtering 
but at the same time its result causes new elements to 
be added to S~. Both problems can be overcome \[8\]. 
Conclusions 
We have discussed a range of different parsing algo- 
rithms, which have their roots in compiler construction, 
expression parsing, and natural language processing. 
We have shown that these algorithms can be described 
in a common framework. 
We further discussed tabular realisations of these al- 
gorithms, and concluded that we have found an opti- 
mal algorithm, which in most cases leads to parse tables 
containing fewer entries than for other algorithms, but 
which avoids computing identical subderivations more 
than once. 
Acknowledgements 
The author acknowledges valuable correspondence with 
Klaas Sikkel, Ran6 Leermakers, Franqois Barth61emy, 
Giorgio Satta, Yves Schabes, and Fr6d@ric Voisin. 

References 
\[1\] S. Billot and B. Lang. The structure of shared 
forests in ambiguous parsing. In 27th Annual Meet- 
ing of the ACL, 143-151, 1989. 
\[2\] M. Johnson. The computational complexity of 
GLR parsing. In M. Tomita, editor, Generalized 
LR Parsing, chapter 3, 35-42. Kluwer Academic 
Publishers, 1991. 
\[3\] B. Lang. Complete evaluation of Horn clauses: 
An automata theoretic approach. Rapport de 
Recherche 913, Institut National de Recherche en 
Informatique et en Automatique, Rocquencourt, 
France, November 1988. 
\[4\] M. Lankhorst. An empirical comparison of gener- 
alized LR tables. In R. Heemels, A. Nijholt, and 
K. Sikkel, editors, Tomita's Algorithm: Extensions 
and Applications, Proc. of the first Twente Work- 
shop on Language Technology, 87-93. University of 
Twente, September 1991. Memoranda Informatica 
91-68. 
\[5\] R. Leermakers. How to cover a grammar. In 27th 
Annual Meeting of the ACL, 135-142, 1989. 
\[6\] R. Leermakers. A recursive ascent Earley 
parser. Information Processing Letters, 41(2):87- 
91, February 1992. 
\[7\] M.J. Nederhof. Generalized left-corner parsing. In 
Sixth Conference of the European Chapter of the 
ACL, 305-314, 1993. 
\[8\] M.J. Nederhof. A multidisciplinary approach to 
a parsing algorithm. In K. Sikkel and A. Ni- 
jholt, editors, Natural Language Parsing: Methods 
and Formalisms, Proc. of the sixth Twente Work- 
shop on Language Technology, 85-98. University 
of Twente, 1993. 
\[9\] M.J. Nederhof and G. Satta. An extended theory 
of head-driven parsing. In this proceedings. 
\[10\] P. Oude Luttighuis and K. Sikkel. Generalized LR 
parsing and attribute evaluation. In Third Inter- 
national Workshop on Parsing Technologies, 219- 
233, Tilburg (The Netherlands) and Durbuy (Bel- 
gium), August 1993. 
\[11\] P.W. Purdom, Jr. and C.A. Brown. Parsing 
extended LR(k) grammars. Acta Informatica, 
15:115-127, 1981. 
\[12\] J. Rekers. Parser Generation for Interactive Envi- 
ronments. PhD thesis, University of Amsterdam, 
1992. 
\[13\] D.J. Rosenkrantz and P.M. Lewis II. Deterministic 
left corner parsing. In IEEE Conference Record 
of the 11th Annual Symposium on Switching and 
Automata Theory, 139-152, 1970. 
\[14\] Y. Schabes. Polynomial time and space shift- 
reduce parsing of arbitrary context-free grammars. 
In 29th Annual Meeting of the ACL, 106-113, 1991. 
\[15\] K. Sikkel and M. Lankhorst. A parallel bottom- 
up Tomita parser. In 1. Konferenz "Verarbeitung 
Natiirlicher Sprache", 238-247, Nfirnberg, October 
1992. Springer-Verlag. 
\[16\] S. Sippu and E. Soisalon-Soininen. Parsing The- 
ory, Vol. H: LR(k) and LL(k) Parsing, EATCS 
Monographs on Theoretical Computer Science, 
volume 20. Springer-Verlag, 1990. 
\[17\] E. Soisalon-Soininen and E. Ukkonen. A method 
for transforming grammars into LL(k) form. Acta 
Informatica, 12:339-369, 1979. 
\[18\] M. Tomita. Efficient Parsing for Natural Lan- 
guage. Kluwer Academic Publishers, 1986. 
\[19\] F. Voisin. CIGALE: A tool for interactive grammar 
construction and expression parsing. Science of 
Computer Programming, 7:61-86, 1986. 
\[20\] F. Voisin. A bottom-up adaptation of Earley's 
parsing algorithm. In Programming Languages 
Implementation and Logic Programming, Interna- 
tional Workshop, LNCS 348, 146-160, Orl@ans, 
France, May 1988. Springer-Verlag. 
\[21\] F. Voisin and J.-C. Raoult. A new, bottom-up, 
general parsing algorithm. BIGRE, 70:221-235, 
September 1990. 
