The 4th Natural Language Processing Paci c Rim Symposium (NLPRS'97)

Chart-based Parsing and Transfer inIncremental Spoken Language Translation

Shigeki MATSUBARA, Satoru ASAI, Katsuhiko TOYAMAand Yasuyoshi INAGAKI
Department of Computational Science and Engineering,
Nagoya University
Furo-cho, Chikusa-ku, Nagoya, 464-01 Japanfmatu,asai,toyama,inagakig@inagaki.nuie.nagoya-u.ac.jp

Abstract
This paper describes a method of implementing the incremental EnglishJapanese spoken language translation
which the authors have proposed sofar. To satisfy the requirement thateach module in translation has to work
synchronously, incremental parsing andtransfer are designed on the basis of achart processing paradigm. Whenever a
spoken word is inputed, the parsing module constructs a chart and the transfer iscarried out using one of the structures
constituting the chart. Some techniques
introduced into the incremental parsing
could be used for spoken language processing systems with high interactivity.

1 Introduction
In order to develop a system behaving like a simultaneous interpreter, a technique for translating
spoken language incrementally and synchronously
is essential (Menzel 94). However, it is dicult toincrementally translate between languages which
are di erent in word-order. In fact, both EnglishJapanese simultaneous interpretation (Kitano 90)
and incremental German-English machine translation (Amtrup 95) do not achieve high degreeof incrementality and synchronicity owing to suchthe reason.
To overcome this diculty, we have proposed
an idea of utilizing grammatically ill-formed expressions as the results of English-Japanese translation (Matsubara and Inagaki 97). That is, thesystem outputs Japanese speech including expres-sions such as repetitions, inversions, ellipses, errors, repairs and hesitations (Matsubara et al.
97). Since these expressions appear frequently inhuman dialogues, it seems to be quite all rightfor speech-to-speech systems to produce grammatically ill-formed sentences.
The purpose of this paper is to provide amethod of implementing the incremental spoken
language translation system. Many of machinetranslation systems on a sentence-by-sentence basis have adopted an approach called structuraltransfer. They commonly consist of three stages:
parsing, transfer and generation, which work sequentially (Landsbergen and Jong 94). On theother hand, since the incremental translation system needs to output the target language synchronously with the input of the source language,
each stage has to work incrementally and synchronously.
This paper concentrates on the stages of the incremental English-Japanese spoken language system. To satisfy the above requirement and makethe process of the system clear, the system mainly
consists of two stages: parsing and transfer which
work synchronously. The transfer stage directly transforms the source language structure into
the target language. For the purpose of processing partially inputed sentences halfway throughspeech, we have adopted a chart processing technique (Kay 80). A chart is a graph in which eachlabel represents an incomplete phrase structure.
It is used not only for the parsing but also for thetransfer. To put it concretely, each stage works asfollowing:(1) Whenever a spoken word is inputed, theparsing module constructs a chart consistingof the structures of the sentence which has

function

English Speaker

L chart := f g;
temp := f g;

English Speech
Speech Recognition
ParsingRules

step 1

Consulting Dictionary:

2 Catw = and ; G chart then
L chart := L chart [ f[w] g;for each

English Wordif

Incremental Parser

Edges

GlobalChart

Dictionary

Incremental Transfer
TransferRules

Chart Parsing(G chart; w)

begin

step 2Edge

Speech Synthesis
Japanese Speech

step 3

Japanese Listener

Figure 1 shows the con guration of the incremental English-Japanese spoken language translation
system. The system is composed of eight components: speech recognition, speech synthesis, incremental parsing, incremental transfer, parsing
rules, transfer rules, a dictionary and a globalchart. Both incremental parsing and transfer are
based on a chart processing technique (Kay 80).
The global chart, which will be explained in thefollowing section, is the data which represents
the source language structures formed halfway
through the input.
Whenever an English word is inputed, the system executes (1)-(4) sequentially.
(1) Recognition of an English input word
(2) Construction of a global chart(3) Transformation of a term into Japanese(4) Production of the Japanese speech
These processes (1)-(4) are executed in the stagesof speech recognition, incremental parsing, incremental transfer and speech synthesis respectively.
The next section describes the incremental parsing stage in detail and the incremental transfer
stage is illustrated with an example in Section 4.

Replacing Terms:

for each
if 9Figure 1: Con guration of the system

2 An Overview

 2 L chart and1 2 1 1 1 n 2 Parsing rules
if  = 1 and; G chart then
L chart :=L chart [ f[[?] 2 1 1 1 [?] n ] g;!

Japanesebeen inputed up to the point of time.
(2) Whenever a new chart is constructed, thetransfer module selects a structure from thechart and produces a target expression by applying transfer rules to the structure.

Applicating Rules:

for each 2 G chart and= lut() ^ =2 L chart
thenbeginreplace lut() with ;temp := temp [ fg;end;
G chart := temp;
if G chart = f g thenerror
else

Chart Parsing:= G chart;

end.

fmaingG chart := f[?]S g;i := 1 to lastforbegin

wi :=input word;
G chart :=Chart Parsing(G chart; wi );i := i + 1;

end.

Figure 2: Algorithm of incremental chart parsing

3 Incremental Chart Parsing

3.1 Global Chart and Local Chart

This study introduces the chart (Kay 80) 1 into
representing parsing results. Since the chart canrepresent a partial sentence structure as an activeedge, it is e ective to utilize charts for incremental
parsing. The chart parsing is carried out apply1 Let us complement the small explanation of the chartparsing method. The chart is de ned as a labeled directedgraph. The label means a phrase structure called a term.
For example, the term for a word \met" whose category isv can be represented as [[met]v [?]np ]vp using an undecidedterm [?]np . The edge whose term includes an undecided
term is called active.

inputword

Kenmetheraunt

Table 1: Incremental parsing process of (3.1)

# loc
(2)
(3)
(5)
(6)
(8)
(9)
(10)
(13)

0-1
0-1
1-2
1-2
2-3
2-3
2-3
3-4

local chart
termuse[Ken]np[[Ken]np [?]vp ]s (2)[met]v[[met]v [?]np ]vp (5)[her]np[her]da[[her]da [?]n ]np (9)[aunt]nglobal chart# loc term
(1) 0-0 [?]suse(4) 0-1 [[Ken]np[?]vp ]s(1)(3)(7) 0-2 [[Ken]np[[met]v [?]np]vp ]s(11) 0-3 [[Ken]np[[met]v [[her]np]vp ]s(4)(6)(7)(8)(12) 0-3 [[Ken]np[[met]v [[her]da [?]n ]np ]vp ]s(7)(10)(14) 0-4 [[Ken]np[[met]v [[her]da [aunt]n ]np ]vp ]s (12)(13)

ing to edges two main rules: bottom-up rule andfundamental rule. According to our chart parsing algorithm which will be given in the following
subsection, the edge formed by a fundamental rule
could be used for the transfer processing and theone formed by a bottom-up rule is not. To distinguish between them, we call the chart consistingof the formers global and the one consisting of thelatters local.

(2)
Ken0(10)

(5)
met
1(9)
her
2

(8)

(13)
aunt
3

4

Figure 3: Local chart
(14)
(12)
(7)

3.2 Algorithm

Incremental chart parsing is initialized as a graphconsisting of a node labeled 0 and an edge labeled
a term [?]s . Figure 2 shows the algorithm of theincremental chart parsing. Let us here introduce
a few notations. Let ; be categories and ; ;be terms. The notation ; G chart denotesthat is reachable for the category of the leftmost
undecided term of at least one term in G chart.
lut() denotes the leftmost undecided term of .
To illustrate the parsing mechanism, let us consider the following simple sentence:(3.1) Ken met her aunt.
Table 1 shows the parsing process of (3.1). The
rows in the local chart and the global chart correspond to the edges. \#" means the order ofconstructing edges. The parser constructs a new
global chart by executing the replacement operation. Since at least one edge is added to the globalchart whenever a word is inputed, the transfer canbe carried out using the edge. The nal resultsof the local chart and the global chart are given in
Figure 3 and 4 respectively. We can see from thegures that the local chart consists of the edges
whose length is 1 and the global chart consists ofthe edges whose initial node is labeled 0.

(6)

(3)

(4)
(1)
Ken0

met
1

her
2

aunt
3

4

(11)

Figure 4: Global chart

3.3 Discussion
This method is a kind of the so-called mixed mode
left-corner chart parsing method based on reachability relations. However, the method di ers fromthe others in the point that the operations of applying a parsing rule to an active edge and replacing the leftmost undecided term in an activeedge with the term of another active edge are introduced. The latter operation is just corresponding to applying a composition rule of combinatory
categorial grammar (Steedman 87) which is wellknown as a framework of incremental parsing. Since introducing the operation makes it possible
to construct a new global chart whenever a word
is inputed, the system can carry out both synchronous and incremental transfer processing.

4 Incremental Transfer
The system utilizes repairs positively (Matsubaraet al. 97). Since we do not have enough space todescribe many of the incremental transfer stage,
we will explain only a method of producing repairs
with an example. The forthcoming literature of
the authors will be available for the details.
The system outputs the following Japanese:(4.1) ken-wa (Ken) atta (met). kanojo-ni (her)kanojo-no oba-ni (her aunt) atta (met).
synchronously with the input of (3.1). Note thatan error \kanojo-ni" is corrected by producing\kanojo-no" afterward. The reason why the system makes the error is that it selected (11) fromtwo edges (11) and (12) in Table 1. In general, it
is dicult to select the correct edge because it is
not clear what the next word is. Selecting a variant of (11), [[!]np [[!]v [her]np ]vp ]s 2 , the transfer
module produces the error \kanojo-ni". For thenext word \aunt", [[!]np [[!]v [[her]da [aunt]n ]np ]vp ]sis newly formed. The transfer result is the repair
expression \kanojo-no oba-ni". Thus, the system
can produces repairs with no extra processing.
5 Concluding Remarks
This paper has described a method of implementing an incremental English-Japanese spoken language translation system. A new method of chartparsing has been introduced for translating spoken language incrementally. The parser behaves
like combinatory categorial grammar (Steedman87) which is known as a framework for incremental parsing. We have discussed that the global
chart plays a key role in the incremental parsingand transfer. The technique for making repairs
has been showed with an example.
We have implemented a prototype system in
Common Lisp. The small scale experiment has
showed the system to be available for spoken language translation with highly real-time nature(Matsubara et al. 97). Currently, we are developing a large scale system for interpreting spontaneous speech. However, the serious problem thatthe structural ambiguities on the way of processing may explode would arises on the system. Since
active edges include the prospects of the forthcoming words, too many edges could be formed. It isthus no longer easy for the transfer stage to select
2 The symbol ! means the inputed English word has al-

ready been translated into Japanese.

an appropriate edge. The technique for disambiguating semantically as early as possible seems
to be worthwhile subject to investigate.

Acknowledgements
The rst author has been supported in part by
Support Center for Advanced Telecommunications Technology Research, Foundation (SCAT).
References
Amtrup J.W. 1995. Chart-based Incremental
Transfer in Machine Translation. Proc. of 6thInt. Conf. of Theoretical and Methodological Is-, 188-195.
Ehara T., Inoue N., Kohyama H., Hasegawa T.,
Shohyama F. and Morimoto T. 1990. Contents of the ATR Dialogue Database. Technical
Report TR-I-0186, ATR Interpreting Telephony
Research Laboratories. (In Japanese)
Kay M. 1980. Algorithm Schemata and Data
Structures in Syntactic Processing. Technical
Report CSL-80-12, Xerox PARC.
Kitano, H. 1990. Incremental Sentence Production with a Parallel Marker-Passing Algorithm.
sues in Machine Translation

Proc. of 13th Int. Conf. on Computationla Lin-, 217{222.
Matsubara S. and Inagaki Y. 1997. Utilizing
Extra-Grammatical Phenomena in Incremental
English-Japanese Machine Translation. Proc.
guistics

of 7th. Int. Conf. on Theoretical and Method-, 138{
145.
Matsubara S., Asai S., Inagaki Y. and Toyama K.
1997. Incremental Spoken Language Translation Utilizing Grammatically Ill-formed Expressions. Proc. of 3rd Conf. of Paci c Association
for Computational Linguistics, 188{194.
Menzel W. 1994. Parsing of Spoken Language
under Time Constraints. Proc. of 11th European
Conf. on Arti cial Intelligence, 560{564.
Landsbergen J. and Jong F. 1994. The translation process. Compositional Translation, Rosseta M. (Ed.), 57{84.
Steedman M. 1987. Combinatory Grammarand Human Sentence Processing. J. Gar eld(ed.), Modurality in Knowledge Representation
and Natural Language Understanding, 187{205,MIT Press.
ological Issues in Machine Translation