A Bag of Useful Techniques for Efficient and Robust Parsing 
Bernd Kiefer t, Hans-Ulrich Kriegert, John Carroll $, and Rob Malouff 
IGerman Research Center for Artificial Intelligence (DFKI) 
Stuhlsatzenhausweg 3, D-66123 Saarbriicken 
$Cognitive and Computing Sciences, University of Sussex 
Falmer, Brighton BN1 9QH, UK 
*Center for the Study of Language and Information, Stanford University 
Ventura Hall, Stanford, CA 94305-4115, USA 
{kiefer, krieger}@dfki, de, j ohnca@cogs, susx. ac. uk, malouf@csli, stanford, edu 
Abstract 
This paper describes new and improved tech- 
niques which help a unification-based parser to 
process input efficiently and robustly. In com- 
bination these methods result in a speed-up in 
parsing time of more than an order of magni- 
tude. The methods are correct in the sense that 
none of them rule out legal rule applications. 
1 Introduction 
This paper describes several generally- 
applicable techniques which help a unification- 
based parser to process input efficiently and 
robustly. As well as presenting a number of new 
methods, we also report significant improve- 
ments we have made to existing techniques. 
The methods preserve correctness in the sense 
they do not rule out legal rule applications. 
In particular, none of the techniques involve 
statistical or approximate processing. We also 
claim that these methods are independent 
of the concrete parser and neutral with re- 
spect to a given unification-based grammar 
theory/formalism. 
How can we gain reasonable efficiency in pars- 
ing when using large integrated grammars with 
several thousands of huge lexicon entries? Our 
belief is that there is no single method which 
achieves this goal alone. Instead, we have to 
develop and use a set of "cheap" filters which 
are correct in the above sense. As we indicate 
in section 10, combining these methods leads 
to a speed-up in parsing time (and reduction of 
space consumption) of more than an order of 
magnitude when applied to a mature, well en- 
gineered unification-based parsing system. 
We have implemented our methods as exten- 
sions to a HPSG grammar development environ- 
ment (Uszkoreit et al., 1994) which employs a 
sophisticated typed feature formalism (Krieger 
and Sch~ifer, 1994; Krieger and Sch~ifer, 1995) 
and an advanced agenda-based bottom-up chart 
parser (Kiefer and Scherf, 1996). A special- 
ized runtime version of this system is currently 
used in VERBMOBIL as the primary deep anal- 
ysis component. I 
In the next three sections, we report on trans- 
formations we have applied to the knowledge 
base (grammar/lexicon) and on modifications 
in the core formalism (unifier, type system). In 
Section 5-8, we describe how a given parser can 
be extended to filter out possible rule applica- 
tions efficiently before performing "expensive" 
unification. Section 9 shows how to compute 
best partial analyses in order to gain a certain 
level of robustness. Finally, we present empir- 
ical results to demonstrate the efficiency gains, 
and speculate on extensions we intend to work 
on in the near future. Within the different sec- 
tions, we refer to three corpora we have used to 
measure the effects of our methods. The refer- 
ence corpora for English, German, and Japanese 
consist of 1200-5000 samples. 
2 Precompiling the Lexicon 
Lexicon entries in the development system are 
small templates that are loaded and expanded 
on demand by the typed feature structure sys- 
tem. Thereafter, all lexical rules are applied to 
the expanded feature structures. The results of 
these two computations form the input of the 
analysis stage. 
1VERBMOBIL (Wahlster, 1993) deals with the trans- 
lation of spontaneously spoken dialogues, where only a 
minor part consists of "sentences" in a linguistic sense. 
Current languages are English, German, and Japanese. 
Some of the methods were originally developed in the 
context of another HPSG environment, the LKB (Copes- 
take, 1998). This lends support to our claims of their in- 
dependence from a particular parser or grammar engine. 
473 
In order to save space and time in the run- 
time system, the expansion and the application 
of lexical rules is now done off-line. In addi- 
tion, certain parts of the feature structure are 
deleted, since they are only needed to restrict 
the application of lexical rules (see also section 
7 for a similar approach). For each stem, all 
results are stored in compact form as one com- 
piled LISP file, which allows to access and load 
a requested entry rapidly with almost no restric- 
tion on the size of the lexicon. Although load 
time is small (see figure 1), the most frequently 
used entries are cached in main memory, reduc- 
ing effort in the lexicon stage to a minimum. 
We continue to compute morphological infor- 
mation online, due to the significant increase of 
entries (a factor of 10 to 20 for German), which 
is not justifiable considering the minimal com- 
putation time for this operation. 
German English Japanese 
# stems 4269 3754 1875 
space 10.3 KB 10.8 KB 5.4 KB 
entries 6 2.2 2.1 
load time 25.8 msec 29.5 msec 7.5 msec 
Figure 1: Space and time requirements, space, 
entries and load time values are per stem 
3 Improvements in unification 
Unification is the single most expensive oper- 
ation performed in the course of parsing. Up 
to 90% of the CPU time expended in parsing 
a sentence using a large-scale unification based 
grammar can go into feature structure and type 
unification. Therefore, any improvements in the 
efficiency of unification would have direct conse- 
quences for the overall performance of the sys- 
tem. 
One key to reducing the cost of unification is 
to find the simplest set of operations that meet 
the needs of grammar writers but still can be 
efficiently implemented. The unifier which was 
part of the original HPSG grammar develop- 
ment system mentioned in the introduction (de- 
scribed by (Backofen and Krieger, 1993)) pro- 
vided a number of advanced features, including 
distributed (or named) disjunctions (D6rre and 
Eisele, 1990) and support for full backtracking. 
While these operations were sometimes useful, 
they also made the unifier much more complex 
than was really necessary. 
The unification algorithm used by the cur- 
rent system is a modification of Tomabechi's 
(Tomabechi, 1991) "quasi-destructive" unifica- 
tion algorithm. Tomabechi's algorithm is based 
on the insight that unification often fails, and 
copying should only be performed when the uni- 
fication is going to succeed. This makes it par- 
ticularly well suited to chart-based parsing. 
During parsing, each edge must be built with- 
out modifying the edges that contribute to it. 
With a non-backtracking unifier, one option is 
to copy the daughter feature structures before 
performing a destructive unification operation, 
while the other is to use a non-destructive al- 
gorithm that produces a copy of the result up 
to the point a failure occurs. Either approach 
will result in some structures being built in the 
course of an unsuccessful unification, wasting 
space and reducing the overall throughput of 
the system. Tomabechi avoids these problems 
by simulating non-destructiveness without in- 
curring the overhead necessary to support back- 
tracking. First, it performs a destructive (but 
reversible) check that the two structures are 
compatible, and only when that succeeds does 
it produce an output structure. Thus, no out- 
put structures are built until it is certain that 
the unification will ultimately succeed. 
While an improvement over simple destruc- 
tive unification, Tomabechi's approach still suf- 
fers from what Kogure (Kogure, 1990) calls re- 
dundant copying. The new feature structures 
produced in the second phase of unification in- 
clude copies of all the substructures of the in- 
put graphs, even when these structures are un- 
changed. This can be avoided by reusing parts 
of the input structures in the output structure 
(Carroll and Malouf, 1999) without introducing 
significant bookkeeping overhead. 
To keep things as simple and efficient as pos- 
sible, the improved unifier also only supports 
conjunctive feature structures. While disjunc- 
tions can be a convenient descriptive tool for 
writing grammars, they are not absolutely nec- 
essary. When using a typed grammar formal- 
ism, most disjunctions can be easily put into the 
type hierarchy. Any disjunctions which cannot 
be removed by introducing new supertypes can 
be eliminated by translating the grammar into 
474 
disjunctive normal form (DNF). Of course, the 
ratio of the number of rules and lexical entries in 
the original grammar and the DNFed grammar 
depends on the 'style' of the grammar writer, 
the particular grammatical theory used, the 
number of disjunction alternatives, and so on. 
However, context management for distributed 
disjunctions requires enormous overhead when 
compared to simple conjunctive unification, so 
the benefits of using a simplified unifier out- 
weigh the cost of moving to DNF. For the Ger- 
man and Japanese VERBMOBIL grammars, we 
got 1.4-3× more rules and lexical entries, but 
by moving to a sophisticated conjunctive unifier 
we obtained an overall speed-up of 2-5. 
4 Precompiling Type Unification 
After changing the unification engine, type uni- 
fication now became a big factor in processing: 
nearly 50% of the overall unification and copy- 
ing time was taken up by the computation of 
the greatest lower bounds (GLBs). Although 
we have in the past computed GLBs online effi- 
ciently with bit vectors, off-line computation is 
of course superior. 
The feasibility of the latter method depends 
on the number of types T of a grammar. The 
English grammar employs 6000 types which re- 
sults in 36,000,000 possible GLBs. Our exper- 
iments have shown, however, that only 0.5%- 
2% of the type unifications were successful and 
only these GLBs need to be entered into the 
GLB table. In our implementation, accessing 
an arbitrary GLB takes less than 0.002 msec, 
compared to 15 msec of 'expensive' bit vector 
computation (following (A'/t-Kaci et al., 1989)) 
which also produces a lot of memory garbage. 
Our method, however, does not consume any 
memory and works as follows. We first assign 
a unique code (an integer) to every type t E 7-. 
After that, the GLB of s and t is assigned 
the following code (again an integer, in fact a 
fixnum): code(s) × ITI + code(t). This array- 
like encoding guarantees that a specific code is 
given away to a GLB at most once. Finally, this 
code together with the GLB is stored in a hash 
table. Hence, type unification costs are mini- 
mized: two symbol table lookups, one addition, 
one multiplication, and a hash table lookup. 
In order to access a unique maximal lower 
bound (= GLB), we must require that the type 
hierarchy is a lower semilattice (or bounded 
complete partial order). This is often not the 
case, but this deficiency can be overcome either 
by pre-computing the missing types (an efficient 
implementation of this takes approximately 25 
seconds for the English grammar) or by making 
the online table lookup more complex. 
A naive implementation of the off-line compu- 
tation (compute the GLBs for T × T) only works 
for small grammars. Since type unification is 
a commutative operation (glb(s,t) = glb(t, s); 
s,t E 7"), we can improve the algorithm by 
computing only glb(s,t). A second improve- 
ment is due to the following fact: if the GLB 
of s and t is bottom, we do not have to com- 
pute the GLBs of the subtypes of both s and 
t, since they guarantee to fail. Even with these 
improvements, the GLB computation of a spe- 
cific grammar took more than 50 CPU hours, 
due to the special 'topology' of the type hierar- 
chy. However, not even the failing GLBs need 
to be computed (which take much of the time). 
When starting with the leaves of the type hi- 
erarchy, we can compute maximal components 
w.r.t, the supertype relation: by following the 
subsumption links upwards, we obtain sets of 
types, s.t. for a given component C, we can 
guarantee that glb(s,t) ~ _k, for all s,t E C. 
This last technique has helped us to drop the 
off-line computation time to less than one CPU 
hour. 
Overall when using the off-line GLBs, we ob- 
tained a parsing speed-up of 1.5, compared to 
the bit vector computation. 2 
5 Precompiling Rule Filters 
The aim of the methods described in this and 
the next section is to avoid failing unifications 
by applying cheap 'filters' (i.e., methods that 
are cheaper than unification). The first filter 
we want to describe is a rule application filter. 
We have used this method for quite a while, and 
it has proven both efficient and easy to employ. 
Our rule application filter is a function that 
2An alternative approach to improving the speed of 
type unification would be to implement the GLB table 
as a cache, rather than pre-computing the table's con- 
tents exhaustively. Whether this works well in practice 
or not depends on the efficiency of the primitive glb(s, t) 
computation; if the latter were relatively slow then the 
parser itself would run slowly until the cache was suffi- 
ciently full that cache hits became predominant. 
475 
takes two rules and an argument position and 
returns a boolean value that specifies if the sec- 
ond rule can be unified into the given argument 
position of the first rule. 
Take for example the binary filler-head rule 
in the HPSG grammar for German. Since 
this grammar allows not more than one el- 
ement on the SLASH list, the left hand side 
of the rule specifies an empty list as SLASH 
value. In the second (head) argument of the 
rule, SLASH has to be a list of length one. 
Consequently, a passive chart item whose top- 
most rule is a filler-head rule, and so has an 
empty SLASH, can not be a valid second ar- 
gument for another filler-head rule application. 
The filter function, when called with argu- 
ments (filler-head-rule-nr, filler-head-rule-nr, 2 ) 
for mother rule, topmost rule of the daughter 
and argument position respectively, will return 
false and no unification attempt will be made. 
The conjunctive grammars have between 20 
and 120 unary and binary rule schemata. Since 
all rule schemata in our system bear a unique 
number, this filter can be realized as a three di- 
mensional boolean array. Thus, access costs are 
minimized and no additional memory is used at 
run-time. The filters for the three languages are 
computed off-line in less than one minute and 
rule out 50% to 60% of the failing unifications 
during parsing, saving about 45% of the parsing 
time. 
6 Dynamic Unification Filtering 
('Quick Check') 
Our second filter (which we have dubbed the 
'quick check') exploits the fact that unification 
fails more often at certain points in feature 
structures than at others. For example, syn- 
tactic features such as CAW(egory) are very fre- 
quent points of failure, whereas unification al- 
most never fails on semantic features which are 
used merely to accumulate pieces of the logical 
form. Since all substructures are typed, uni- 
fication failure is manifested by a type clash 
when attempting a type unification. The quick 
check is invoked before each unification attempt 
to check the most frequent failure points, each 
stored as a feature path. 
The technique works as follows. First, there 
is an off-line stage, in which a modified unifi- 
cation engine is used that does not return im- 
mediately after a single type unification failure, 
but instead records in a global data structure 
the paths at which all such failures occurred. 
Using this modified system a set of sentences is 
parsed, and the n paths with the highest failure 
counts are saved. It is exactly these paths that 
are used later in filtering. 
During parsing, when an active chart item 
(i.e., a rule schema or a partly instantiated rule 
schema) and a passive chart item (a lexical entry 
or previously-built constituent) are combined, 
the parser has to unify the feature structure of 
the passive item into the substructure of the ac- 
tive item that corresponds to the argument to 
be filled. If either of the two structures has not 
been seen before, the parser associates with it 
a vector of length n containing the types at the 
end of the previously determined paths. The 
first position of the vector contains the type cor- 
responding to the most frequently failing path, 
the second position the second most frequently 
failing path, and so on. Otherwise, the existing 
vectors of types are retrieved. Corresponding 
elements in the vectors are then type-unified, 
and full unification of the feature structures is 
performed only if all the type unifications suc- 
ceed. 
Clearly, when considering the number of 
paths n used for this technique, there is a trade- 
off between the time savings from filtered uni- 
fications and the effort required to create the 
vectors and compare them. The main factors 
involved are the speed of type unification and 
the percentage of unification attempts filtered 
out (the 'filter rate') with a given set of paths. 
The optimum number of paths cannot be de- 
termined analytically. Our English, German 
and Japanese grammars use between 13 to 22 
paths for quick check filtering, the precise num- 
ber having been established by experimenta- 
tion. The paths derived for these grammars are 
somewhat surprising, and in many cases do not 
fit in with the intuitions of the grammar-writers. 
In particular, some of the paths are very long 
(of length ten or more). Optimal sets of paths 
for grammars of this complexity could not be 
produced manually. 
The technique will only be of benefit if type 
unification is computationally cheap--as indeed 
it is in our implementation (section 4)--and if 
the filter rate is high (otherwise the extra work 
476 
performed essentially just duplicates work car- 
ried out later in unification). There is also over- 
lap between the quick check and the rule filter 
(previous section) since they are applied at the 
same point in processing. We have found that 
(given a reasonable number of paths) the quick 
check is the more powerful filter of the two be- 
cause it functions dynamically, taking into ac- 
count feature instantiations that occur during 
the parsing process, but that the rule filter is 
still valuable if executed first since it is a single, 
very fast table lookup. Applying both filters, 
the filter rate ranges from 95% to over 98%. 
Thus almost all failing unifications are avoided. 
Compared to the system with only rule applica- 
tion filtering, parse time is reduced by approxi- 
mately 75% 3 . 
7 Reducing Feature Structure Size 
via Restrictors 
The 'category' information that is attached to 
each chart item of the parser consists of a single 
feature structure. Thus a rule is implemented 
by a feature structure where the daughters have 
to be unified into predetermined substructures. 
Although this implementation is along the lines 
of HPSG, it has the drawback that the tree 
structure that is already present in the chart 
items is duplicated in the feature structures. 
Since HPSG requires all relevant informa- 
tion to be contained in the SYNSEM feature of 
the mother structure, the unnecessary daugh- 
ters only increase the size of the overall feature 
structure without constraining the search space. 
Due to the Locality Principle of HPSG (Pollard 
and Sag, 1987, p. 145ff), they can therefore be 
legally removed in fully instantiated items. The 
situation is different for active chart items since 
daughters can affect their siblings. 
To be independent from a-certain grammati- 
cal theory or implementation, we use restrictors 
similar to (Shieber, 1985) as a flexible and easy- 
to-use specification to perform this deletion. A 
positive restrictor is an automaton describing 
the paths in a feature structure that will re- 
main after restriction (the deletion operation), 
3There are refinements of the technique which we 
have implemented and which in practice produce ad- 
ditional benefits; we will report these in a subsequent 
paper. Briefly, they involve an improvement to th e path 
collection method, and the storage of other information 
besides types in the vectors. 
whereas a negative restrictor specifies the parts 
to be deleted. Both kinds of restrictors can be 
used in our system. 
In addition to the removal of the tree struc- 
ture, the grammar writer can specify the re- 
strictor further to remove features that are only 
used locally and do not play a role in further 
derivation. It is worth noting that this method 
is only correct if the specified restrictor does not 
remove paths that would lead to future unifica- 
tion failures. The reduction in size results in a 
speed-up in unification itself, but also in copy- 
ing and memory management. 
As already mentioned in section 2, there ex- 
ists a second restrictor to get rid of unnecessary 
parts of the lexical entries after lexicon process- 
ing. The speed gain using the restrictors in 
parsing ranges from 30% for the German sys- 
tem to 45% for English. 
8 Limiting the Number of Initial 
Chart Items 
Since the number of lexical entries per stem has 
a direct impact on the number of parsing hy- 
potheses (in the worst case leads to an expo- 
nential increase), it would be a good idea to 
have a cheap mechanism at hand that helps to 
limit these initial items. The technique we have 
implemented is based on the following observa- 
tion: in order to contribute to a reading, certain 
items (concrete lexicon entries, but also classes 
of entries) require the existence of other items 
such that the non-existence of one allows a safe 
deletion of the other (and vice versa). In Ger- 
man, for instance, prefix verbs require the right 
separable prefixes to be present in the chart, but 
also a potential prefix requires its prefix verb. 
Note that such a technique operates in a much 
larger context (in fact, the whole chart) than a 
local rule application filter or the quick-check 
method. The method works as follows. In a 
preprocessing step, we first separate the chart 
items which encode prefix verbs from those 
items which represent separable prefixes. Since 
both specify the morphological form of the pre- 
fix, a set-exclusive-or operation yields exactly 
the items which can be safely deleted from the 
chart. 
Let us give some examples to see the useful- 
ness of this method. In the sentence Ich komme 
mo,'ge,~ (I (will) come tomorrow), komme maps 
477 
onto 97 lexical entries--remember, komme 
might encode prefix verbs such as ankommen 
(arrive), zuriickkommen (come back), etc. al- 
though here, none of the prefix verb readings 
are valid, since a prefix is missing. Using the 
above method, only 8 of 97 lexical entries will 
remain in the chart. The sentence Ich komme 
morgen an (I (will) arrive tomorrow) results in 
8+7 entries for komme (8 entries for the come 
reading together with 7 entries for the arrive 
reading of komme) and 3 prepositional read- 
ings plus 1 prefix entry for an. However in Der 
Mann wartet an der Tiir (The man is waiting 
at the door), only the three prepositional read- 
ings for an come into play, since no prefix verb 
anwartet exists. Although there are no English 
prefix verbs, the method also works for verbs 
requiring certain particles, such as come, come 
along, come back, come up, etc. 
The parsing time for the second example goes 
down by a factor of 2.4; overall savings w.r.t, our 
reference corpus is 17% of the parsing time (i.e., 
speed-up factor of 1.2). 
9 Computing Best Partial Analyses 
Given deficient, ungrammatical, or spontaneous 
input, a traditional parser is not able to de- 
liver a useful result. To overcome this disadvan- 
tage, our approach focuses on partial analyses 
which are combined in a later stage to form to- 
tal analyses without giving up the correctness 
of the overall deep grammar. But what can be 
considered good partial analyses? Obviously a 
(sub)tree licensed by the grammar which covers 
a continuous part of the input (i.e., a passive 
parser edge). But not every passive edge is a 
good candidate since otherwise we would end up 
with perhaps thousands of them. Instead, our 
approach computes an 'optimal' connected se- 
quence of partial analyses which cover the whole 
input. The idea here is to view the set of pas- 
sive edges as a directed graph and to compute 
shortest paths w.r.t, a user-defined estimation 
function. 
Since this graph is acyclic and topologically 
sorted, we have chosen the DAG-shortest-path 
algorithm (Cormen et al., 1990) which runs in 
O(V + E). We have modified this algorithm 
to cope with the needs we have encountered in 
speech parsing: (i) one can use several start and 
~nd vertices (e.g., in case of n-best chains or 
word graphs); (ii) all best shortest paths are 
returned (i.e., we obtain a shortest-path sub- 
graph); (iii) estimation and selection of the best 
edges is done incrementally when parsing n- 
best chains (i.e., only new passive edges entered 
into the chart are estimated and perhaps se- 
lected). This approach has one important prop- 
erty: even if certain parts of the input have not 
undergone at least one rule application, there 
are still lexical edges which help to form a best 
path through the passive edges. This means 
that we can interrupt parsing at any time, but 
still obtain a useful result. 
Let us give an example to see how the estima- 
tion function on edges (-- trees) might look like 
(this estimation is actually used in the German 
grammar): 
• n-ary tree (n > 1) with utterance status 
(e.g., NPs, PPs): value 1 
• lexical items: value 2 
• otherwise: value c~ 
This approach does not always favor paths 
with longest edges as the example in figure 2 
shows--instead it prefers paths containing no 
lexical edges (where this is possible) and there 
might be several such paths having the same 
cost. Longest (sub)paths, however, can be ob- 
tained by employing an exponential estimation 
function. Other properties, such as prosodic 
information or probabilistic scores could also 
be utilized in the estimation function. A de- 
tailed description of the approach can be found 
in (Kasper et al., 1999). 
P R 
S 
Figure 2: Computing best partial analyses. 
Note that the paths PR and QR are chosen, 
but not ST, although S is the longest edge. 
478 
10 Conclusions and Further Work 
The collection of methods described in this pa- 
per has enabled us to unite deep linguistic anal- 
ysis with speech processing. The overall speed- 
up compared to the original system is about a 
factor of 10 up to 25. Below we present some 
absolute timings to give an impression of the 
current systems' performance. 
German English Japanese 
# sentences 5106 1261 1917 
# words 7 6.7 7.2 
# lex. entries 40.9 25.6 69.8 
# chart items 1024 234 565 
# results 5.8 12.4 53.6 
time first 1.46 s 0.24 s 0.9 s 
time overall 4.53 s 1.38 s 4.42 s 
In the table, the last six rows are average val- 
ues per sentence, time first and time overall 
are the mean CPU times to compute the first 
result and the whole search space respectively. 
# lex. entries and # chart items give an im- 
pression of the lexical and syntactic ambiguity 
of the respective grammars 4 
The German and Japanese corpora and half 
of the English corpus consist of transliterations 
of spoken dialogues used in the VEI:tBMOBIL 
project. These dialogues are real world dia- 
logues about appointment scheduling and va- 
cation planning. They contain a variety of syn- 
tactic as well as spontaneous speech phenom- 
ena. The remaining half of the English corpus 
is taken from a manually constructed test suite, 
which may explain some of the differences in 
absolute parse time. 
Most of the methods are corpus independent, 
except for the quick check filter, which requires 
a training corpus, and the use of a purely con- 
junctive grammar, which will do worse in cases 
of great amounts of syntactic ambiguity because 
there is currently no ambiguity packing in the 
parser. For the quick check, we have observed 
that a random subset of the corpora with about 
one to two hundred sentences is enough to ob- 
tain a filter with nearly optimal filter rate. 
Although the actual efficiency gain will vary 
for differently implemented grammars, we are 
4The computations were made using a 300MHz SUN 
Ultrasparc 2 with Solaris 2.5. The whole system is pro- 
grammed in Franz Allegro Common Lisp. 
certain that these techniques will lead to sub- 
stantial improvements in almost every unifica- 
tion based system. It is, for example, quite un- 
likely that unification failures are equally dis- 
tributed over the different nodes of the gram- 
mar's feature structure, which is the most im- 
portant prerequisite for the quick check filter to 
work. Avoiding disjunctions usually requires a 
reworking of the grammar which will pay off in 
the end. 
We have shown that the combination of al- 
gorithmic methods together with some disci- 
pline in grammar writing can lead to a practi- 
cal high performance analysis system even with 
large general grammars for different languages. 
There is, however, room for further improve- 
ments. We intend to generalize to other cases 
the technique for removing unnecessary lexical 
items. A detailed investigation of the quick- 
check method and its interaction with the rule 
application filter is planned for the near future. 
Since almost all failing unifications are avoided 
through the use of filtering techniques, we will 
now focus on methods to reduce the number of 
chart items that do not contribute to any anal- 
ysis; for instance, by computing context-free or 
regular approximations of the HPSG grammars 
(e.g., (Nederhof, 1997)). 
Acknowledgments 
The research described in this paper has greatly 
benefited from a very fruitful collaboration with 
the HPSG group of CSLI at Stanford University. 
This cooperation is part of the deep linguis- 
tic processing effort within the BMBF project 
VERBMOBIL. Special thanks are due to Stefem 
Miiller for discussing the topic of German prefix 
verbs. Thanks to Dan Flickinger who provided 
us with several English phenomena. We also 
want to thank Nicolas Nicolov for reading a ver- 
sion of this paper. Stephan Oepen's and Mark- 
Jan Nederhof's fruitful comments have helped 
us a lot. Finally, we want to thank the anony- 
mous ACL reviewers for their comments. This 
research was supported by the German Federal 
Ministry for Education, Science, Research and 
Technology under grant no. 01 IV 701 V0, and 
by a UK EPSRC Advanced Fellowship to the 
third author, and also is in part based upon 
work supported by the National Science Foun- 
dation under grant number IRL9612682. 
479 

References 
Hassan Ait-Kaci, Robert Boyer, Patrick Lin- 
coln, and Roger Nasr. 1989. Efficient imple- 
mentation of lattice operations. A CM Trans- 
actions on Programming Languages and Sys- 
tems, 11(1):115-146, January. 
Rolf Backofen and Hans-Ulrich Krieger. 1993. 
The TD£///D/A/'e system. In R. Backofen, H.- 
U. Krieger, S.P. Spackman, and H. Uszkor- 
eit, editors, Report of the EAGLES Work- 
shop on Implemented Formalisms at DFKI, 
Saarbriicken, pages 67-74. DFKI Research 
Report D-93-27. 
John Carroll and Robert Malouf. 1999. Effi- 
cient graph unification for parsing feature- 
based grammars. University of Sussex and 
Stanford University. 
Ann Copestake. 1998. The (new) LKB system. 
Ms, Stanford University, 
http ://~n~-csli. stanford, edu/~aac/newdoc, pdf. 
Thomas H. Cormen, Charles E. Leiserson, and 
Ronald L. Rivest. 1990. Introduction to Al- 
gorithms. MIT Press, Cambridge, MA. 
Jochen DSrre and Andreas Eisele. 1990. 
Feature logic with disjunctive unification. 
In Proceedings of the 13th International 
Conference on Computational Linguistics, 
COLING-90, pages Vol. 3, 100-105. 
Walter Kasper, Bernd Kiefer, Hans-Ulrich 
Krieger, C.J. Rupp, and Karsten L. Worm. 
1999. Charting the depths of robust speech 
parsing. In Proceedings of the ACL-99 The- 
matic Session on Robust Sentence-Level In- 
terpretation. 
Bernd Kiefer and Oliver Scherf. 1996. Gimme 
more HQ parsers. The generic parser class of 
DISCO. Unpublished draft. German Research 
Center for Artificial Intelligence (DFKI), 
Saarbr/icken, Germany. 
Kiyoshi Kogure. 1990. Strategic lazy incremen- 
tal copy graph unification. In Proceedings of 
the 13th International Conference on Com- 
putational Linguistics (COLING '90), pages 
223-228, Helsinki. 
Hans-Ulrich Krieger and Ulrich Sch~ifer. 1994. 
7"DE--a type description language for 
constraint-based grammars. In Proceedings 
of the 15th International Conference on 
Computational Linguistics, COLING-94, 
pages 893-899. An enlarged version of this 
paper is available as DFKI Research Report 
RR-94-37. 
Hans-Ulrich Krieger and Ulrich Sch~ifer. 1995. 
Efficient parameterizable type expansion for 
typed feature formalisms. In Proceedings of 
the l~th International Joint Conference on 
Artificial Intelligence, IJCAI-gS, pages 1428- 
1434. DFKI Research Report RR-95-18. 
Mark Jan Nederhof. 1997. Regular approxima- 
tions of cfls: A grammatical view. In Pro- 
ceedings of the 5th International Workshop on 
Parsing Technologies, IWPT'97, pages 159- 
170. 
Carl Pollard and Ivan A. Sag. 1987. 
Information-Based Syntax and Seman- 
tics. Vol. I: Fundamentals. CSLI Lecture 
Notes, Number 13. Center for the Study of 
Language and Information, Stanford. 
Stuart M. Shieber. 1985. Using restriction 
to extend parsing algorithms for complex- 
feature-based formalisms. In Proceedings of 
the 23rd Annual Meeting of the Associa- 
tion for Computational Linguistics, ACL-85, 
pages 145-152. 
Hideto Tomabechi. 1991. Quasi-destructive 
graph unification. In Proceedings of the 29th 
Annual Meeting of the Association for Com- 
putational Linguistics, volume 29, pages 315- 
322. 
Hans Uszkoreit, Rolf Backofen, Stephan Buse- 
mann, Abdel Kader Diagne, Elizabeth A. 
Hinkelman, Walter Kasper, Bernd Kiefer, 
Hans-Ulrich Krieger, Klaus Netter, G/inter 
Neumann, Stephan Oepen, and Stephen P. 
Spackman. 1994. DISCO--an HPSG-based 
NLP system and its application for appoint- 
ment scheduling. In Proceedings of COLING- 
94, pages 436-440. DFKI Research Report 
RR-94-38. 
Wolfgang Wahlster. 1993. VERBMOBIL-- 
translation of face-to-face dialogs. Re- 
search Report RR-93-34, German Research 
Center for Artificial Intelligence (DFKI), 
Saarbr/icken, Germany. Also in Proc. MT 
Summit IV, 127-135, Kobe, Japan, July 
1993. 
