Incremental CFG Parsing with
Statistical Lexical Dependencies
Takahisa Murase†, Shigeki Matsubara‡, Yoshihide Kato†and Yasuyoshi Inagaki†
Graduate School of Engineering, Nagoya University †Faculty of Language and Culture, Nagoya University ‡Furo-cho, Chikusa-ku, Nagoya, 464-8603 Japan{murase,matu,yosihide,inagaki}@inagaki.nuie.nagoya-u.ac.jp
Abstract
Incremental parsing with a context
free grammar produces partial syntactic structures for an initial fragment on
the word-by-word basis. Owing to thesyntactic ambiguity, however, too many
structures are produced, and therefore
its parsing speed becomes very slow.
This paper describes a technique for efﬁcient incremental parsing using lexicalinformation. The probability concerning dependencies between words, as thelexical information, is automatically acquired from a large-scale corpus withsyntactic structures. A process for discarding syntactic structures which will
not be likely has been integrated into
the incremental chart parsing. That is,partial syntactic structures whose dependency probabilities are not high will
be removed from the chart. Our technique proposed in this paper can also be
considered as a kind of practical methods of incremental disambiguation. An
experiment using Penn Treebank has
shown our technique to be feasible andeﬃcient.

1

Introduction

With the advances of speech processing technologies in recent years, it has been tried to develop
systems which understand speech simultaneouslywith it (Ehsani et al., 1994; Matsubara et al.,
1999; Nakano et al., 1999). An incremental parsing is one of essential techniques for such the systems, because it is useful for the system to get
syntax-relations of input sentences at an earlystage of the input. Several techniques for incremental parsing have been proposed so far (Akiba
and Tanaka, 1992; Matsubara et al., 1997; Milward, 1995; Steedman, 1987). However, producing the syntactic structures word-by-word makes
the parsing process ineﬃcient in comparing withthe usual parsing method which has only to produce the structures for one sentence.

In order to overcome this problem, several
works have been done. Akiba et al. proposeda technique referring obligatory case information(Akiba et al., 1993), and Haddock studied a technique examining consistency between the conversational situation and the input content (Haddock, 1987). We can consider that the former uses
a semantic information and the latter a contextual one to solve the syntactic ambiguity incrementally. However, it is not easy to acquire suchthe advanced linguistic knowledge.
On the other hand, many researches have used
the statistical information to increase the eﬃciency of parsing (Charniak, 1997; Collins, 1996;
Magerman, 1995; Ratnaparkhi, 1997; Stolcke,
1995). The common idea of (Charniak, 1997;
Collins, 1996; Magerman, 1995) is to assign aprobability to every syntactic structure for one
sentence, and to ﬁnd the most likely one. In contrast, Imaichi et al., and Watanabe have proposeda technique to avoid producing unlikely syntactic structures by using statistical lexical dependency information (Imaichi et al., 1998; Watanabe, 1999). What needs to be noted is that all ofthese techniques mentioned here are intended forparsing of a whole sentence, not a partial one.
This paper proposes an eﬃcient incremental
parsing technique by using statistical lexical information. Our technique is based on the incremental chart parsing method, and it determines dependency probabilities of partial syntactic structures which will be produced on the way of incremental parsing, and it statistically evaluates thesemantical likelihood of them. The statistical information of the lexical dependency relation for
initial fragments is useful to attain a more eﬃcient incremental parsing. We have used the Penn
Treebank (Marcus et al., 1993) to make an experiment. This has shown our technique to be feasible
and eﬃcient.
This paper is organized as follows: Section 2
explains the incremental chart parsing. Section 3
describes the parsing method using statistical dependency information. Section 4 reports the experimental results.

2

Incremental Parsing

2.1 Incremental chart parsing
The incremental chart parsing (Matsubara et al.,1997), which is one of the syntax analysis techniques using a context free grammar, expresses
the result in progress as the graph called chart(Kay, 1980). The node labeled the number exists between words in an input sentence, and theedge stretched between nodes is labeled a syntactic
structure called term. The term [?] X is called an
undecided term and represents that the part has
not been produced yet. The leftmost occurrenceof an undecided term in a term is called a leftmost undecided term. If an edge is labeled a term
which includes an undecided term, it is called active, otherwise inactive.
The incremental chart parsing starts on thechart in which the edge labeled term [?] S wasstretched from the node 0 to itself. When i-thword wi is produced, the following procedures are
performed in order:

Table 1: Grammar rules and dictionary
grammar rules dictionarys → np vp
prp → I
np → prp
vbp → need
vp → vbp np pp
dt → anp → dt nn
nn → flight
pp → p np
p → from
np → nnp pp
nnp → Atlanta
np → np pp
p → tonp → nnp
nnp → Charlotte
vp → vbp np

I#1c) Replacement of terms: Let [?] X be the leftmost undecided term of the term σ of theedge stretched between nodes 0 and i − 1 ina chart. If the category of the term τ of theedge stretched between i − 1 and i is X, theedge labeled the term produced by replacing
the leftmost undecided term of σ with τ isadded between nodes 0 and i in a chart.
That is, the incremental chart parsing introduces two new operations into the standard
bottom-up chart parsing. One is the applicationof grammar rules to an active edge and the otheris the replacement of the leftmost undecided termwith the term of an active edge. The operations
enable the parsing to necessarily construct syntactic structures for initial fragments of grammatical input sentences. But, the amount of calculation increases in comparing with the usual parsing
method. Therefore, it takes much time for parsing.
2.2 The process of incremental parsing
In the incremental chart parsing, new structures
are produced word-by-word through the replacement operation. As an example, let us consider

#2

a
#3

flight#5

from#7

Atlanta
#9

#11

to

Charlotte
#15

#12
#4

a) Consultation of a dictionary: If the category of a word wi is A, the edge labeled term[wi ]A is stretched between nodes i − 1 and iin a chart.
b) Application of grammar rules:
If the term of the edge stretched between
nodes i − 1 and i in a chart is [· · ·]A1 and agrammar rule A → A1 A2 · · · An exists, theedge labeled term [[· · ·]A1 [?] A2 · · · [?] An ]A is
added between nodes i − 1 and i in a chart.
As much as possible, this operation is repeated.

need

#6

#8

#10

#13
#14

#17
#18

#16

#19
#20

Figure 1: Process of incremental parsing

incremental chart parsing for an English sentence:
I need a flight from Atlanta to Charlotte. (1)using the grammar and dictionary in Table 1. Its
parsing process is shown in Table 2. Each line
corresponds to the edge in a chart, the number ofthe columns of # corresponds to the production
order of the edge, the loc expresses the positionof the edge, and the term expresses the syntactic
structure. For example, by replacing the leftmost
undecided term of a term [[[I]prp]np [?] vp ]s for “I”
with a term [[need]vbp [?] np]vp for “need”, a term[[[I]prp]np [[need]vbp[?] np ]vp ]s for a word sequence“I need” is produced. Figure 1 expresses the relation between the produced terms as a graph. Thisgraph can be regarded as a kind of the search trees
in which a node corresponds to a term (Kato et al.,2000). The node in the search tree is derived fromits parent node by adding the information about
the input word to the syntactic structure of theparent node. That is, incremental chart parsing
makes the tree grow up word-by-word, and pruning the tree makes the parsing process eﬃcient.

3

Incremental Parsing with Lexical
Dependency Information

In this section, we propose a technique for pruning the search tree discussed in the previous section, that is, for avoiding the production of unlikely syntactic structures by using the dependency information between words in incremental

Table 2: parsing process for “I need a ﬂight from Atlanta to Charlotte”
word
I
need
a

# loc term
1
2
3
4
5
6

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

[?]s
[[[I]prp ]np [?]vp ]s[[[I]prp ]np [[need]vbp [?]np [?]pp ]vp ]s[[[I]prp ]np [[need]vbp [?]np ]vp ]s[[[I]prp ]np [[need]vbp [[a]dt [?]nn ]np [?]pp ]vp ]s[[[I]prp ]np [[need]vbp [[[a]dt [?]nn ]np [?]pp ]np ]np

α

α

X
Y1

Yi
…

β1

X

δ
Yj

Z*

βj

?
γ

Z

Y1

…

βi

Yi
…

β1

…

βi

(A)

δ
Z*

Yj

Yj

…
?
γ

βh

(B)

wβ1 … wβi … wβjwδ

wβ1 … wβi … wβh… wδ

Figure 3: Case 1: leftmost undecided term γ isthe head term of α

Figure 4: Case 2: leftmost undecided term γ islocated on the right of the head term of αthat of whj . djhj is the distance between wj andwhj . cjhj is the number of the commas between
wj and whj .
3.3

Dependency probability for partial
syntactic structure
Collins’ probabilistic model should be modiﬁed
to be used for incremental parsing, because themodel cannot estimate the dependency probability in the case where the head word or the dependent is “?” as shown in Figure 2. In this paper,
we regard the probability of such a dependency as
1. That is, for an initial fragment W (= w1 · · · wi )and a partial syntactic structure T , we deﬁne theconditional probability P (T |W ) as follows:
P (T |W ) =

i


rel

P̂ (wj → whj |W )

(5)

j=1
rel

P̂ (wj → whj |W ) =
1(if hj > i)(6)rel
P (wj → whj |W ) (otherwise)
When the input is completed, the probability
P (T |W ) is the same as the one in Collins’ model.
3.4 Pruning
We take the method of ﬁnding the syntactic structures which have a low cost rather than that ofcomparing the score between syntactic structures.
In our technique, we use the following thresholdΘ which is dynamically varied dependently on thenumber of input words, i.e. i.
Θ = θi (0 ≤ θ ≤ 1)

(7)

Here, θ is the threshold for a dependency probability of a pair of words. If P (T |W ) ≤ Θ, thesyntactic structure is judged to be unlikely.
3.5 Utilizing dependency probability
In this section, we describe the technique forcontrolling the replacement operation of terms in

α
X
Y1

Yi
…

β1

δ
Yj

…

βi

Z*

Yj

…
?
γ

?
βh

(C)

wβ1 … wβi … wδ … ?
Figure 5: Case 3: leftmost undecided term γ islocated on the left of the head term of α

incremental chart parsing by using the probabilistic model mentioned in section 3.3 and avoiding
the production of unlikely syntactic structures.
In incremental chart parsing, replacing terms isequivalent to forming a new dependency relation
between words. If the dependency formed newly
by replacement operation can be gotten, the likelihood of the syntactic structure can be examined.
The replacement operation of terms can be classiﬁed into three cases based on the formation of
the dependency. Figure 3 shows the ﬁrst case.
When the leftmost undecided term γ of a term
α is replaced with a term δ, the dependency (A)will be formed (wβi is the head-word of a term βi ,and wδ is that of δ.). In Figure 3, since γ is thehead term, it is newly formed that wβi (1 ≤ i ≤ j)is the dependent on wδ . Figure 4 shows the second case. When γ is replaced with δ, the dependency (B) will be formed. In Figure 4, since γ
is located on the right of the head term βh , it is
newly formed that wδ is the dependent on wβh .
Figure 5 shows the third case. The dependency(C) will be formed in this case. Since γ is locatedon the left of βh , the dependency containing “?”is newly formed. Moreover, not concerned withthese cases, when the head-word of δ is “?”, therelation that δ depends on “?” is formed. By clas-

σ

Table 3: Grammar rules and dictionary
grammar rules dictionarys → np vp∗
prp → I
np → prp∗
vbp → need
vp → vbp∗ np pp
dt → anp → dt nn∗
nn → flight
pp → p∗ np
p → from
np → nnp∗ pp
nnp → Atlanta
np → np∗ pp
p → tonp → nnp∗
nnp → Charlotte
vp → vbp∗ np

s
np

vp*

prp*

vbp*

I

need

4

Experiment

In order to evaluate the eﬀectiveness of thetechnique proposed in this paper, we have madean experiment using Penn Treebank. We implemented it in GNU Common Lisp 2.3.6 on a Linux
workstation (CPU: Intel Pentium Xeon III 1GHz,
Memory: 1024MB).
4.1 Outline of the experiment
We used 52 sentences of a spoken language corpus,
ATIS corpus as the open test data. The average
length is 8.4 words. Figure 7 shows the relationship between the sentence length and the numberof sentences. The grammar and lexical rules has
been acquired from the sentences with the syntactic structures in ATIS corpus. For the purpose of the parsing speed, we used the grammar

p*

np

?

from

?

dt

nn*

p*

np

a

flight from

?

dt

nn*

a

flight

σ’
np

vp*
vbp*

I

need

np’

pp

Figure 6: Example of calculating the probabilityof a syntactic structure
87Number of sentences

3.6 Example
The parsing of an English sentence (1) is as follows: The grammar and dictionary shown in Table
3 are used.
Let us consider the replacement shown in Figure 6. The dependency between the head-words“need” of the term [need]vbp∗ and “from” of[[from]in∗ [?] np ]pp will be formed in case 2 mentioned above. If let the dependency probabilityrel
P (from → need | I need a flight from) be−6
3.60 × 10 , and the probability for σ be 0.98,
then the probability for the new term σ  is calculated like 0.98 × 3.60 × 10−6 = 3.52 × 10−6 . If thethreshold is Θ = 0.25 , then 0.25 > 3.52 ×10−6. By
preventing the replacement of terms, the syntactic
structure #9 in Table 2 is not produced.

pp

pp

s

prp*

sifying replacement operation into three cases, it
can be turn out what dependencies will be formed.
Let us consider replacing the leftmost undecided term of σ with the term τ . Let the probability for σ be Pσ . The probability for the newterm is calculated by the product of Pσ and theprobability of the dependency which will be newly
formed. If the probability for the new term islower than the threshold, the replacement of terms
is prevented.

τ

np’

6
5
4
3
2
1
0

0

2

4

6
8
10
Sentence length

12

14

16

Figure 7: Sentence length distribution of our test
data from ATIS corpus

rules which are transformed according to a grammar transfer technique (Johnson, 1998). Every
non-terminal symbol included in syntactic structures in the corpus is copied the parent node onto.
Thus, we used 508 grammar rules and 363 lexical
rules. We have measured the number of the syntactic structures and the parsing time word-byword in both the conventional incremental chartparsing and our technique. We set 0, . . ., 0.3 as θof the threshold (7).
As the training data, we used both 520 sentences of ATIS corpus, and in addition, 38,438
sentences of WSJ corpus to compensate the sparse
data.
4.2

Experimental result

Figure 8 shows the relation between the sentence length and the average number of syntactic
structures. The longer the sentences are, the more
syntactic structures are produced in the incremental chart parsing. As compared with it, it is in-100

conventional method
θ= 0
θ= 0.1
θ= 0.2
θ= 0.3

40000
35000

Average processing time (sec)

Average number of syntactic structures

45000

30000
25000
20000
15000
10000
5000
0

0

2

4
6
8
Number of input words

10

conventional method
θ= 0
θ= 0.1
θ= 0.2
θ= 0.3

10

1

0.1

12

0

Figure 8: Average number of syntactic structures

2

4
6
8
Number of input words

10

12

10

12

Figure 9: Average processing time
1
0.9
0.8

θ= 0
θ= 0.1
θ= 0.2
θ= 0.3

98
96

0.7

Ratio

Ratio of correct analysis (%)

100

94

0.6
0.5
0.4

92

0.3
90

0.2

88

0.1

86

0

84

0

2

4
6
8
Number of input words

10

0

2

4
6
8
Number of input words

12

Figure 11: Ratio of the average number of dependencies containing “?” to the number ofall possible dependencies

Figure 10: Recall of syntactic structures

dicated that our technique is useful for reducing
the syntactic structures. This fact brings an eﬀect
on the processing speed. Figure 9 shows the relation between the sentence length and the average
processing time of parsing one word. As Figure
9 shows, even if it takes much time to parsing aword in the incremental parsing, it may not be
so in our technique. Moreover, the recall of thecorrect syntactic structures is shown in Figure 10.
This result indicates that many correct structures
were judged to be likely. From the experimental
result, we have conﬁrmed the eﬀectiveness of ourtechnique.
In our technique, however, there is a problem tobe pointed out here. Figure 9 indicates that thetechnique using the lexical dependency may not be
eﬃcient for the short initial fragment. In an earlystep of the input, many dependencies mappedfrom syntactic structures contain the words which
has not been produced yet. We deﬁned the probability of such the dependencies as 1. So many
syntactic structures are judged to be likely semantically. Figure 11 shows the ratio of the average

number of dependencies which contain a “?” tothe number of input words. The longer the fragments are, the smaller the ratio becomes.
Moreover, as the evaluation criteria, we used
the PARSEVAL measures (Black et al., 1991)
for complete syntactic structures which were produced for an input sentence by our technique. Table 4 shows the results. We give results using six
measures: the percentage of sentences for which
a syntactic structure was produced, LR (labeledrecall), LP (labeled precision), CBs (the average
number of crossing brackets per sentence), 0CBs(the percentage of sentences with 0 crossing brackets), ≤2CBs (the percentage of sentences with ≤2crossing brackets). We can then additionally evaluate the parser’s performance to the maximum
likelihood syntactic structure (MLS). As we cansee, our technique is a viable broad-coverage statistical one.

5

Conclusion

In this paper, we have proposed the technique foreﬃcient incremental parsing using the statistical

θ
0
0.1
0.2
0.3

Per. of
Sen.
96.2%
92.3%
90.4%
82.7%

LR
59.5%
71.2%
76.4%
79.2%

Table 4: Evaluation on ATIS corpus
All Produced Structures
LP
CBs 0CBs ≤2CBs
LR
LP
49.9% 1.84 37.2% 71.7% 92.9% 90.8%
63.7% 1.16 54.4% 82.0% 93.2% 90.8%
69.5% 0.75 65.6% 90.2% 93.1% 90.6%
72.4% 0.62 74.4% 91.1% 95.1% 92.6%

lexical dependency information. Utilizing the dependency between words enables the technique toget out of producing semantically unlikely syntactic structures. An experimental result has demonstrated that the parsing time becomes shorter because of the reduction of the number of syntactic
structures.

Acknowledgment
The authors would like to thank all members of
Nagoya University Corpus Project for their helpful suggestions. This research has been supported
in part by Kayamori Foundation of Information
Science Advancement.

References
T. Akiba and H. Tanaka. 1992. A Method
for Incremental Parsing using Extended Partial
Trees. The 45th National Convention of Information Processing Society of Japan, 3:175–176.
(in Japanese)
T. Akiba, K. Itou, M. Okumura, and H. Tanaka.
1993. A Japanese Analysis based on Incremental Disambiguation Model. Computer Software,
10(1):29–40. (in Japanese)
E. Black et al. 1991. A Procedure for Quantitatively Comparing the Syntactic Coverage ofEnglish Grammars. Proceedings of the February 1991 DARPA Speech and Natural Language
Workshop.
E. Charniak. 1997. Statistical Parsing witha Context-free Grammar and Word Statistics.
Proceedings of the 14th AAAI, pages 598–603.
M. J. Collins. 1996. A New Statistical Parser
Based on Bigram Lexical Dependencies. Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics, pages
184–191.
F. Ehsani, K. Hatazaki, J. Noguchi, andT. Watanabe. 1994. Interactive Speech Dialogue System Using Simultaneous Understanding. Proceedings of the 3rd International Conference on Spoken Language Processing, 2:879–
882.
J. Haddock. 1987. Incremental Interpretation andCombinatory Categorial Grammar. Proceed-

MLS
CBs
0.26
0.27
0.28
0.14

0CBs
94.0%
93.8%
93.6%
97.7%

≤2CBs
96.0%
95.8%
95.7%
97.7%

ings of the 10th International Joint Conferenceon Artificial Intelligence, pages 661–663.
O. Imaichi, Y. Matsumoto, and M. Fujio.
1998. An Integrated Parsing Method using
Stochastic Information and Grammatical Constraints. Journal of Natural Language Processing, 5(3):67–83. (in Japanese)
M. Johnson. 1998. PCFG models of linguistic
tree representations. Computational Linguistics, 24:617–636.
Y. Kato, S. Matsubara, K. Toyama, and Y. Inagaki. 2000. Spoken Language Parsing basedon Incremental Disambiguation. Proceedingsof the 6th International Conference on Spoken
Language Processing, 2:999–1002.
M. Kay. 1980. Algorithm Schemata and Data
Structures in Syntactic Processing. Technical
Report CSL-80-12.
D. Magerman. 1995. Statistical Decision-Tree
Models for Parsing. Proceedings of the 33rd
Annual Meetings of the Association for Computational Linguistics, pages 276–283.
M. Marcus, B. Santorini, and M. Marcinkiewicz.
1993. Building a Large Annotated Corpus ofEnglish: the Penn Treebank. Computational
Linguistics, 19(2):313–330.
S. Matsubara, S. Asai, K. Toyama, and Y. Inagaki. 1997. Chart-based Parsing and Transfer
in Incremental Spoken Language Translation.
Proceedings of the 4th Natural Language Processing Pacific Rim Symposium, pages 521–524.
S. Matsubara, K. Toyama, and Y. Inagaki. 1999.
Sync/Trans: Simultaneous Machine Interpretation between English and Japanese. N. Foo(Ed.): Advanced Topics in Artificial Intelligence, Lecture Note in Artificial Intelligence
1747:134–143.
D. Milward. 1995. Incremental Interpretation of
Categorial Grammar. Proceedings of the 7th
European Association for Computational Linguistics, pages 119–126.
M. Nakano, N. Miyazaki, and J. Hirasawa. 1999.
Understanding Unsegmented User Utterancesin Real-Time Spoken Dialogue Systems. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, pages
200–207.

A. Ratnaparkhi. 1997. A Linear Observed Time
Statistical Parser Based on Maximum Entropy
Models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing.
J. Steedman. 1987. Combinatory Grammarand Human Sentence Processing. Modurality in Knowledge Representation and Natural
language Understanding, pages 187–205. MIT
Press.
A. Stolcke. 1995. An Eﬃcient Probabilistic
Contex-Free Parsing Algorithm that Computes
Preﬁx Probabilities. Computational Linguistics, 21(2):165–201.
H. Watanabe. 1999. A Pruning Method of
CFG-Parsing Using Dependency Information.
The 59th National Convention of Information
Processing Society of Japan, 2:345–346. (inJapanese)