Spoken Language Parsing with Robustness and Incrementality

Yoshihide Kato , Shigeki Matsubara , Katsuhiko
Toyama andyYasuyoshi InagakiyGraduate School of Engineering, Nagoya University

Faculty of Language and Culture, Nagoya University z

Center for Integrated Acoustic Information Research, Nagoya University x
Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japanyosihide@inagaki.nuie.nagoya-u.ac.jp

Abstract

This paper describes a method of incremental parsing for grammatically ill-formed sentences. The
method consists of incremental chart parsing anderror correcting, which are executed synchronously.
The error correction at an early stage enables theparser to construct a syntactic structure of an initial fragment of a grammatically ill-formed sentence
whenever a word is inputed. The parser has two features: One is to utilize the syntactic constraints suchas reachability and connectability, and the other is toassign a cost, which represents degrees of error corrections, to every syntactic structure. Therefore, theparser, at any time, adopts the syntactic structureof the well-formed sentence which is most similar to
the input sentence as a parsing result.

1 Introduction

It is important for a speech dialogue system to interact with a user naturally and smoothly. Such system is required to possess the capability of immediate response to the user, so that the user can recognize the degree of the system's understanding at any
time. To satisfy this requirement, the spontaneous
speech dialogue system should be able to interpret
spoken language at least incrementally (Milward andCooper, 1994; Inagaki and Matsubara, 1995). Incremental interpretation means to process an input
sentence from left to right and extract semantic information from the initial fragment of it.
Another problem on the spontaneous speech dialogue system is whether it can deal with grammatical
ill-formedness since grammatically ill-formed expressions appear frequently in spoken language. Most of
the systems which have been developed so far, however, assume that input sentences are grammaticallywell-formed. To solve the problem, some techniques
for processing grammatically ill-formed sentences
have been proposed. For example, uni cation-based
framework (Douglas and Dale, 1992; Imaichi andMatsumoto, 1995) deals with the ill-formedness suchas constraint violations. Partial parsing (Jensen etal., 1983; McDonald, 1992) extracts the informationfrom the partial structures constructed in the pars-ing process. Extended parsing algorithms (Saito andTomita, 1988; Mellish, 1989; Kato, 1994; Lee et al.,1995) deal with the syntactic ill-formedness such as
deletion, insertion and mutation of words. Little attention, however, has been given to the viewpoint of
incrementality in these literatures.
This paper describes a method of incremental
parsing for grammatically ill-formed sentences. The
method consists of incremental chart parsing (Matsubara et al., 1997) and error correcting, which are
executed synchronously. The error correcting, at
any time, processes syntactic errors such as deletion,
insertion and mutation of words. The error correction at an early stage enables the parser to constructa syntactic structure of an initial fragment of a grammatically ill-formed sentence whenever a word is inputed. The parser has two features: the rst one is
to utilize the syntactic constraints such as reachability and connectability so that it can correct theerrors eciently. The second one is to assign a cost,which represents degrees of error corrections, to every syntactic structure. The parser adopts the syntactic structure of the well-formed sentence which ismost similar to the input sentence as a parsing result. In addition, in order to increase eciency ofparsing, the parser deletes the structures which do
not contribute to the construction of the complete
structure with a minimum cost.
This paper is organized as follows: The next section is a summary of incremental chart parsing. In
section 3, we describe the error correcting method.
Reports of an eciency evaluation of our parsing
system are given in section 4. In section 5, we makea comparison with related works.

2 Incremental Chart Parsing

In this section, we summarize incremental chartparsing (Matsubara et al., 1997).
The incremental chart parsing records parsing results in a graph called a chart. The edge is labeled
a syntactic structure called a term which is denotedby an expression [ ]x , where x is a category and is
a list of terms, a word or a special symbol `?'. The
term [?]x is called an undecided term. The leftmost

1 1 1 wn

input: w1 w2
output: chart

chart := f(0; 0; [?]s )g;for i = 1 to n begin

1)consulting dictionary:if category of w is x then add (i 1; i; [w ] ) to chart2)applying grammar rule:for each (i 1; i; [ ] 1 ) chart andeach grammar rule ax2 y zif x1 = x2
then add (i 1; i; [[ ] 1 [?][?] ] ) to chart3)replacing term:
for each (0; i 1;  ); (i 1; i; [ ] ) chart
if the category of lut( ) is x
then add (0; i; rep(; [ ] )) to chart
end

0

i

0

111 x 2! 111
0111 x y 111 z a
0
0 111 x 2
111 x

ix

Figure 1: Algorithm of incremental chart parsing
s
np
np
np
np

! np vp! pron! det n! gi pp
!n

vp
vp
vp
pp

! vt s! vi pp! be adj! p np

pron
det
n
gi
p

!I
! the
! train! going
! by

vt
vi
be
adj

! think! think! is! bestFigure 2: Example of Grammar
occurrence of an undecided term in a term  is calleda leftmost undecided term in  , which is denoted bylut(). If an edge is labeled the term which includes
an undecided term, it is said to be active, otherwise
inactive.
The incremental parsing algorithm is shown in
Figure 1. Here, the edge with label  between thenodes j and k is denoted by (j; k;  ). The result of
replacing the leftmost undecided term in  with  isdenoted by rep(;  ). The incremental chart parsing introduces two new operations to the standard
bottom-up chart parsing (Kay, 1980). One is the application of grammar rules to an active edge and theother is the replacement of the leftmost undecided
term with the term of an active edge. The operations
enable the parser to construct a syntactic structureof the initial fragment of an input sentence.
As an example, let us consider the parse of thefollowing sentence by using the grammar shown in
Figure 2:
I think going by train is best.

(2.1)

When \think" is inputed after the input of\I", the standard bottom-up chart parser constructs terms [[[I ]pron ]np [?]vp ]s , [[think]vi [?]pp ]vp and[[think ]vt [?]s ]vp . On the other hand, the incremental
chart parser also constructs terms:[[[I ]pron ]np [[think]vt [?]s ]vp ]s(2.2)[[[I ]pron ]np [[think ]vi [?]pp ]vp ]s(2.3)
These terms, at least, represent the relation that \I"is the subject of the verb \think" which can be acquired from the initial fragment \ I think". Thisshows that the incremental chart parsing has capability of constructing a syntactic structure of an initial fragment at an early stage.

3 Incremental Parsing of Ill-formed
Sentences

This study deals with three kinds of syntactic errors
such as deletion, insertion and mutation of words. In
this section, we extend the incremental chart parsing
to process grammatically ill-formed sentences which
include errors with keeping high degree of incrementality.

3.1 Structure Construction for Ill-formed
Sentences

Our purpose is to develop a method of constructing
a syntactic structure of the initial fragment of thesentence including errors at any time. This is accomplished easily by the following operations: insertinga word (for a deletion error), skipping a word (for an
insertion error) and replacing a word with anotherone (for a mutation error).
Let us consider the following sentence:
I think by train is best.

(3.1)

It might be suspected that (3.1) includes one of thefollowing errors:
1. deletion of \going" in the sentence \I think going by train is best."
2. insertion of \by" in the sentence \I think train
is best."
3. mutation of \the" into \by" in the sentence \Ithink the train is best."
In the rst case, the error can be corrected byinserting a gerund \going". Actually, if the parser
adds the edge labeled the term [going ]gi to the chart
and applies grammar rules to it, the parser constructs a term (3.2).
[[[going ]gi [?]pp ]np [?]vp ]s(3.2)

The parser replaces the leftmost undecided term [?]sin (2.2) with (3.2) so that constructs a term[[[I ]pron ]np [[think ]vt [[[going ]gi [?]pp ]np [?]vp ]s ]vp ]sfor the initial fragment \I think".
In the second case, the error can be corrected byskipping \by" so that the parser constructs a term[[[I ]pron ]np [[think ]vt [[[train]n ]np [?]vp ]s ]vp ]sfor the initial fragment \I think by train".
Finally, in the third case, the error can be corrected by replacing \by" with a determiner \the".
Then, the parser constructs a term:[[[I ]pron ]np [[think ]vt [[[the]det [?]n ]np [?]vp ]s ]vp ]sThe above examples show that the incremental chartparser can construct syntactic structures of the initial fragments of ill-formed sentences by the above
three operations at an early stage.

3.2 Error Detection

The previous section has illustrated the structure
construction for a grammatically ill-formed sentence.
The operations, however, do not always enable theparser to construct a syntactic structure. For example, if \train" is skipped in (3.1), no syntactic
structure can be constructed.
From the viewpoint of eciency, the parser should
not execute such operations. Thus, error detecting
technique is required. What is important is that error detecting should be executed as soon as possible.
For this purpose, the parser detects errors by utilizing the information included in the parsing result
and a lookahead word. Since such information canbe extracted easily from the initial fragment which
has been already inputed, high degree of incrementality can be achieved.

3.2.1 Reachability and Connectablity

To formalize the information which is used for theerror detection, we de ne two relations between
syntactic categories: reachability and connectability.
Let and be any sequences of categories and let
a, x, y and z be any categories.

De nition(Reachability) x is reachable to y if x
and y satisfy one of the following conditions:
1. x = y .
2. A grammar rule y ! x exists.
3. For some z , x is reachable to z and z is reachable
to y .
2
The relation that x is reachable to y means that a
structure whose root is y has the leftmost descendant
x. We write x ; y if x is reachable to y.
De nition(connectability) x is connectable to y if
x and y satisfy the following condition 1. or 2.:
1. A grammar rule a ! xz exists and y ; z .
2. A grammar rule a ! x exists and a is connectable to y .
2
The relation that x is connectable to y means thata category sequence xy is allowed by the grammar.
We write x_ y if x is connectable to y .
3.2.2 Error Correction Procedures

In our method, the parser corrects errors whenevera word is inputed. The procedures for error corrections are shown in Figure 3. Here, we use a special
symbol `3' for the result of insertion or replacementof a word by error correction. The reachability relation is utilized for the error detecting using the information included in the parsing results. The connectability relation is utilized for the error detecting
using a lookahead word.

deletion correction:for each (0; i 1;  ); (i 1; i;  ) chart andeach category x
if x
 and x  then add (i 1; i 1; [ ] ) to chart
insertion correction:for each (0; i 2;  ) chart and each category x of w
if x
 then add (i 2; i 1; ") to chart
mutation correction:for each (0; i 2;  ); (i 1; i;  ) chart andeach category x
if x
 and x  then add (i 2; i 1; [ ] ) to chart

;

;

;

0

0

0

0

_

2

_

0
0

2
0

0 3x

0

2
0

i

0 3x

Figure 3: Procedures for error correction
For example, as Figure 4 (a), let us consider deletion correction for the sentence (3.1) when \by"isinputed. The categories of the leftmost undecided
terms in the terms (2.2) and (2.3) are s and pp, respectively. The categories which are reachable to s
or pp are gi, n, p and pron. Moreover, the only gi
in these categories is connectable to the category p
of \by". Therefore, the parser inserts a word whose
category is gi. The parser corrects the other errors
in the same way as Figure 4 (b) and (c) show.

3.3 Cost of Error Correction

In order to keep high degree of incrementality, theparser executes the error correcting at any time.
Thus, it may execute the error correcting where errors do not occur actually and construct syntactic
structures of the sentence which is not similar to
the input sentence. Such structures should be eliminated from the parsing results. For this purpose, thecost which represents degrees of error corrections is
assigned to every syntactic structure and the parser
adopts the structures with a minimum cost as a parsing result. The calculation of the cost value is asfollows:
1. Assigning a cost to every error correction.
2. If the parser constructs a structure by error correction, add the cost of the error correction to
the cost of the structure.
For example, when \I" is inputed, a term[[[I ]pron ]np [?]vp ]s(3.3)

is constructed in the parsing phase. Next, when\think" is inputed, a term[[[3]n ]np [?]vp ]s(3.4)

is constructed in the error correcting phase. The
cost value of the term (3.3) is less than that of (3.4)
since (3.3) is with no error correction and (3.4) iswith mutation error correction. Consequently, theparser adopts (3.3) as a parsing result.
From the viewpoint of eciency, the error correcting may increase the number of edges in the chart
so that the parsing becomes inecient. To improveeciency of the parsing, the parser should delete theError detection

Error correction

Reachability

Edge

Connectablitysnp

1 think 2

Invt vi padj beI think
0pron dets

pron vi(a) Deletion correctionpron det
n gi

vp

gi

gi
p

by 3

0

I

1 think 2

by 3

0

I

1 think 2

by 3spron det
n gi

vp

np
pron vi

vt vi padj beI think0

1 think 2Ipron dets(b) Mutation correctionby 3 train 4

0

I

det

gi

n

n

1 think 2

by 3 train 40I

1 think 2

by 3 train 4

s
vp

np
pron vis(c) Insertion correctionεI think0

ReachabilityIn

1 think 2

0

by 3 train 4

Connectability

Active edge

Inactive edgeI

1 think 2

by 3 train 4edge by error correction

Figure 4: Examples of error corrections
edge deletion:for each (0; i;  ); (0; i;  ) chart
if cs( ) = cs( ) and cost( ) < cost( )then delete (0; i;  ) from chart

2

Figure 5: Procedure of edge deletionssσ:cost = 0 np vp
cost = c’ np vp
pron
pron
cost = c’replacing term
I
I
s
s
τ:
np vp
np vp
cost = c ncost = c+c’ ncost = c’**Figure 6: Comparison between the costs of syntactic
structures
structures which do not contribute to the construction of the complete structure with a minimum cost.
Therefore, the parser executes edge deletion shownin Figure 5. Here, the cost value of a term  is denoted by cost( ) and a sequence of categories of theundecided terms which occur in a term  is denotedby cs( ).
Let us consider an example of edge deletion. The
term  in Figure 6 is constructed when \I" is inputed. The term  in Figure 6 is constructed bymutation correction when \think" is inputed. cs( )and cs( ) are vp. We know cost( ) < cost( ) since is with no error correction and  is with mutation
correction. Thus, the edge (0; 1;  ) is deleted.

3.4 An Example of Parsing

This section gives an example of incremental parsing of grammatically ill-formed sentences. Table 1

shows the chart construction process for the sentence(3.1). We assume that the cost value of every error
correction is 1.
When \by" is inputed, a gerund is inserted bydeletion correction and the edge #6 is constructed.
When \train" is inputed, \by" is skipped by insertion correction and the edge #11 is constructed.
Next, \by" is replaced with a determiner by mutation correction and the edge #12 is constructed.
The edges #3, #10, #15, #18 and #19, which areconstructed in error correcting phase, are deleted
by edge deletion. The example illustrates that theparser can construct syntactic structures of initial
fragments of the grammatically ill-formed sentence(3.1) whenever a word is inputed. The edges which
are constructed nally are #23, #24 and #25, andeach edge is constructed by deletion, insertion or
mutation correction, respectively.

4 Evaluation of Eciency

We have made an experiment to evaluate eciencyof the method proposed in this paper. The experiment has been made under the following conditions: The parser has been implemented in GNU Common Lisp on UltraSPARC-II (Main memory
512MB, CPU 248MHz)
 The grammar consists of 74 rules and 54 categories.
 The cost value of any error correction is 1 regardless of the kind of an error.
 60 grammatically ill-formed sentences are generated at random in the following way: First, 20
well-formed sentences are generated at random

Table 1: Incremental parsing process of \I think by train is best."

chart
edge
word # loc term
cost deletion
1 0-0 [?]s0I
2 0-1 [[[I ]pron ]np [?]vp ]s0think 3 0-1 [[[3]n ]np[?]vp ]s
1 deleted
4 0-2 [[[I ]pron ]np [[think]vt [?]s ]vp ]s0
5 0-2 [[[I ]pron ]np [[think]vi [?]pp ]vp ]s0by
6 0-2 [[[I ]pron ]np [[think]vt [[[3]gi[[?]pp ]np[?]vp ]s ]vp ]s1
7 0-3 [[[I ]pron ]np [[think]vi [[by]p [?]np ]pp ]vp ]s0
8 0-3 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [?]np]pp ]np [?]vp ]s ]vp ]s1
train 9 0-3 [[[I ]pron ]np [[think]vi [[by]p [[3]det [?]n]np ]pp ]vp ]s1
10 0-3 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [[3]det [?]n ]np ]pp ]np [?]vp ]s ]vp ]s
2 deleted
11 0-3 [[[I ]pron ]np [[think]vt [?]s ]vp ]s1
12 0-3 [[[I ]pron ]np [[think]vt [[[3]det [?]n]np[?]vp ]s ]vp ]s1
13 0-4 [[[I ]pron ]np [[think]vi [[by]p [[train]n]np]pp ]vp ]s0
14 0-4 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [[train]n]np ]pp ]np[?]vp ]s ]vp ]s1
15 0-4 [[[I ]pron ]np [[think]vi [[by]p [[3]det [train]n ]np ]pp ]vp ]s
1 deleted
16 0-4 [[[I ]pron ]np [[think]vt [[[train]n ]np [?]vp ]s ]vp ]s1
17 0-4 [[[I ]pron ]np [[think]vt [[[3]det [train]n]np [?]vp ]s ]]vp ]s1
is
18 0-4 [[[I ]pron ]np [[think]vi [[by]p [[[3]pron ]np]pp ]vp ]s
1 deleted
19 0-4 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [[3]pron ]np]pp ]np [?]vp ]s ]]vp ]s
2 deleted
20 0-5 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [[train]n]np ]pp ]np[[is]be [?]adj ]vp ]s ]]vp ]s 1
21 0-5 [[[I ]pron ]np [[think]vt [[[train]n ]np [[is]be[?]adj ]vp ]s ]]vp ]s1
22 0-5 [[[I ]pron ]np [[think]vt [[[3]det [train]n]np [[is]be [?]adj ]vp ]s ]vp ]s1
best 23 0-6 [[[I ]pron ]np [[think]vt [[[3]gi[[by]p [[train]n]np ]pp ]np[[is]be [best]adj ]vp ]s ]vp ]s 1
24 0-6 [[[I ]pron ]np [[think]vt [[[train]n ]np [[is]be[best]adj ]vp ]s ]vp ]s1
25 0-6 [[[I ]pron ]np [[think]vt [[[3]det [train]n]np [[is]be [best]adj ]vp ]s ]vp ]s1
from the grammar (the length of the sentence
is 4, 6, 8 or 10 and the number of the sentences
is 5 for each length). Second, random occurrences of speci c types of errors are introduced
into these sentences.
We measured the worst processing time per word in
the following cases:
 the parsing with both error detection and edge
deletion
 the parsing without error detection and withedge deletion
 the parsing with error detection and withoutedge deletion
Table 2 shows averages of the worst processing
time per word. The time in the parsing withoutedge deletion was a great deal longer than that withedge deletion. The time in the parsing without error
detection was longer than that with error detection.
This result demonstrates that our proposed method
is useful for increasing eciency of the parsing.

5 Related WorksFirst, we compares our work with related works fromthe viewpoint of incrementality, i.e., the timing oferror correcting and the construction of syntactic
structures on the way.
Mellish (Mellish, 1989) and Kato (Kato, 1994)
have proposed a method based on chart parsing.
The method is divided into the bottom-up phaseand the top-down phase. The bottom-up phase
constructs structures of an input sentence in thebottom-up chart parsing manner. If it failed toconstruct a complete structure, the top-down phaseis started to detect errors. The bottom-up chartparsing cannot construct a structure of the initial
fragment of a sentence and, consequently, Mellish's
and Kato's parser also cannot construct it. In addition, it is not until the bottom-up phase is nished that the error detection process is invoked.
Moreover, error correcting needs all of the partial
syntactic structures constructed in the bottom-up
chart parsing. Thereby, the method cannot executeparsing and error correcting synchronously. Saito's
method is on basis of Generalized LR parsing (Saito
and Tomita, 1988). The method executes parsing
and error correcting synchronously as ours. Saito's
parser, however, cannot construct a structure of theinitial fragment of a sentence, because the method isbased on Generalized LR parser. Lee extended Earley Algorithm to deal with grammatically ill-formed
sentences (Lee et al., 1995). Their parser performs
parsing and error correcting synchronously. The algorithm cannot construct a syntactic structure whileparsing is performed.
On the other hand, our proposed parser can process grammatically ill-formed sentences incrementally since it executes parsing and error correcting
synchronously. In addition, the parser can construct

Table 2: Worst processing time per word

Kind of Length of with both error detection without error detection with error detection
Error
Sentence and edge deletion
and with edge deletion and without edge deletion
50.028 sec
0.048 sec
0.044 sec
70.158 sec
0.372 sec
0.548 sec
insertion ofa word90.390 sec
0.600 sec
2.964 sec
11
1.014 sec
1.282 sec
61.948 sec
40.064 sec
0.038 sec
0.060 secmutation of
6
0.026 sec
0.034 sec
0.030 sec
80.600 sec
0.830 sec
4.514 seca word101.390 sec
2.030 sec
56.000 sec
3
0.018 sec
0.088 sec
0.024 sec
50.070 sec
0.142 sec
0.146 secdeletion of
7
0.334 sec
0.420 sec
1.160 seca word90.888 sec
1.304 sec
6.926 sec
structures of the initial fragments of grammatically
ill-formed sentences since it is based on the incremental chart parsing.
Next, our works is compared with Saito's andLee's from the viewpoint of eciency of the error
detecting.
Saito's parser utilizes LR parsing table which predicts what word is the next input in order to detect
errors. In Lee's method, the parser predicts the next
constituent by utilizing the parsing results. Saito'sand Lee's error detecting are identical to the error
detecting which utilizes the reachability relation.
On the other hand, the error detecting which havebeen proposed in this paper is more ecient since
the error detecting utilizes not only the reachability
relation but also the connectability relation.

6 Conclusion

This paper has proposed an incremental and robust
parsing method for grammatically ill-formed sentences. The method executes parsing and error correcting synchronously. Correcting errors at any timeenables the parser to construct syntactic structuresof the initial fragments of grammatically ill-formed
sentences whenever a word is inputed. Using our
method, the number of the structures may increase
explosively because the parser constructs them not
only in parsing phase but also in error correcting
phase. In order to decrease it, a cost has been assigned to every error correction.
In future works, we intend to apply the method
proposed in this paper to the incremental spoken
language translation system (Matsubara and Inagaki, 1997).

References

S. Douglas and R. Dale. 1992. Towards Robust
PATR. In Proc. of COLING-92, pages 468{474.
O. Imaichi and Y. Matsumoto. 1995. Integration of
Syntactic, Semantic and Contextual Informationin Processing Grammatically Ill-Formed Inputs.
In Proc. of IJCAI-95, pages 1435{1440.
Y. Inagaki and S. Matsubara. 1995. Models for Incremental Interpretation of Natural Language. In
Proc. of SNLP-95, pages 51{60.
K. Jensen, G. E. Heidorn, L. A. Miller, and
Y. Ravin. 1983. Parse Fitting and Prose Fixing:
Getting a Hold on Ill-Formedness. Computational
Linguistics, 9(3{4):147{160.
T. Kato. 1994. Yet Another Chart-Based Techniquefor Parsing Ill-Formed Input. In Proc. of ANLP94, pages 107{112.
M Kay. 1980. Algorithm Schemata and Data Structures in Syntactic Processing. In Technical Report
CSL-80-12.
K.J. Lee, J.K. Kweon, J. Seo, and G.C. Kim. 1995.
A Robust Parser Based on Syntactic Information.
In Proc. of EACL-95, pages 223{228.
S. Matsubara and Y. Inagaki. 1997. Incremental Transfer in English-Japanease Machine Translation. IEICE Trans. on Inf. & Sys, E80D(11):1122{1129.
S. Matsubara, S. Asai, K. Toyama, and Y. Inagaki.
1997. Chart-based Parsing and Transfer in Incremental Spoken Language Translation. In Proc. of
NLPRS-97, pages 521{524.
D.D. McDonald. 1992. An Ecient Chart-based Algorithm for Partial-Parsing of Unrestricted Texts.
In Proc. of ANLP-92, pages 193{200.
C.S. Mellish. 1989. Some Chart-Based Techniques
for Parsing Ill-Formed Input. In Proc. of ACL-89,
pages 102{109.
D. Milward and R. Cooper. 1994. Incremental Interpretation : Applications, Theory, and Relationship to Dynamic Semantics. In Proc. of COLING94, pages 748{754.
H. Saito and M. Tomita. 1988. Parsing Noizy Sentences. In Proc. of COLING-88, pages 561{566.