Ckylark: A More Robust PCFG-LA Parser
Yusuke Oda

Graham Neubig
Sakriani Sakti
Tomoki Toda
Satoshi Nakamura
Graduate School of Information ScienceNara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0192, Japan{oda.yusuke.on9, neubig, ssakti, tomoki, s-nakamura}@is.naist.jp

Abstract
This paper describes Ckylark, a PCFG-LA
style phrase structure parser that is more robust than other parsers in the genre. PCFG-LA
parsers are known to achieve highly competitive performance, but sometimes the parsing
process fails completely, and no parses can begenerated. Ckylark introduces three new techniques that prevent possible causes for parsing
failure: outputting intermediate results whencoarse-to-fine analysis fails, smoothing lexicon probabilities, and scaling probabilities toavoid underflow. An experiment shows that
this allows millions of sentences can be parsed
without any failures, in contrast to other publicly available PCFG-LA parsers. Ckylark is
implemented in C++, and is available opensource under the LGPL license.11

Introduction

Parsing accuracy is important. Parsing accuracy hasbeen shown to have a significant effect on downstream applications such as textual entailment (Yuretet al., 2010) and machine translation (Neubig andDuh, 2014), and most work on parsing evaluates accuracy to some extent. However, one element that isequally, or perhaps even more, important from theview of downstream applications is parser robustness, or the ability to return at least some parse regardless of the input. Every failed parse is a sentence for which downstream applications have nochance of even performing processing in the normal way, and application developers must perform1http://github.com/odashi/ckylark

special checks that detect these sentences and either
give up entirely, or fall back to some alternative processing scheme.
Among the various methods for phrase-structure
parsing, the probabilistic context free grammar withlatent annotations (PCFG-LA, (Matsuzaki et al.,2005; Petrov et al., 2006)) framework is among themost popular for several reasons. The first is that it
boasts competitive accuracy, both in intrisinic measures such as F1-score on the Penn Treebank (Marcus et al., 1993), and extrinsic measures (it achieved
the highest textual entailment and machine translation accuracy in the papers cited above). The second
is the availablity of easy-to-use tools, most notably
the Berkeley Parser,2 but also including Egret,3 andBUBS Parser.4
However, from the point of view of robustness,
existing tools for PCFG-LA parsing leave something
to be desired; to our knowledge, all existing tools
produce a certain number of failed parses when run
on large data sets. In this paper, we introduce Ckylark, a new PCFG-LA parser specifically designedfor robustness. Specifically, Ckylark makes the following contributions:• Based on our analysis of three reasons why
conventional PCFG-LA parsing models fail(Section 2), Ckylark implements three improvements over the conventional PCFG-LA
parsing method to remedy these problems (Section 3).
2

https://code.google.com/p/berkeleyparser/
https://code.google.com/p/egret-parser/
4
https://code.google.com/p/bubs-parser/
3• An experimental evaluation (Section 4) showsthat Ckylark achieves competitive accuracy
with other PCFG-LA parsers, and can robustly
parse large datasets where other parsers fail.
• Ckylark is implemented in C++, and released
under the LGPL license, allowing for free research or commercial use. It is also available
in library format, which means that it can beincorporated directly into other programs.

2

Failure of PCFG-LA Parsing

The basic idea behind PCFG-LA parsing is that traditional tags in the Penn Treebank are too coarse,
and more accurate grammars can be achieved byautomatically splitting tags into finer latent classes.
For example, the English words “a” and “the” areclassified as determiners (DT), but these words areused in different contexts, so can be assigned different latent classes. The most widely used method todiscover these classes uses the EM algorithm to estimate latent classes in stages (Petrov et al., 2006).
This method generates hierarchical grammars including relationships between each latent class in atree structure, and the number of latent classes increases exponentially for each level of the grammar.
The standard search method for PCFG grammars isbased on the CKY algorithm. However, simply applying CKY directly to the “finest” grammar is notrealistic, as the complexity of CKY is propotional
to the polynomial of the number of latent classes.
To avoid this problem, Petrov et al. (2006) start
the analysis with the “coarse” grammar and apply
pruning to reduce the amount of computation. Thismethod is called coarse-to-fine analysis. However,this method is not guaranteed to successfully returna parse tree. We describe three reasons why PCFGLA parsing fails below.
Failure of pruning in coarse-to-fine analysis
Coarse-to-fine analysis prunes away candidate
paths in the parse graph when their probability
is less than a specific threshold ϵ. This pruning
can cause problems in the case that all possible
paths are pruned and the parser cannot generate
any parse tree at the next step.
Inconsistency between model and target If weparse sentences with syntax that diverges fromthe training data, the parser may fail because
the parser needs rules which are not includedin the grammar. For example, symbols “(”and “)” become a part of phrase “PRN” only
if both of them and some phrase “X” exist
with the order “( X ).” One approach for thisproblem is to use smoothed grammars (Petrovet al., 2006), but this increases the size ofthe probability table needed to save such agrammar.
Underflow of probabilities Parsers calculate joint
probabilities of each parse tree, and this value
decreases exponentially according to the lengthof the input sequence. As a result, numerical
underflow sometimes occurs if the parser tries
to parse longer sentences. Using calculations inlogarithmic space is one approach to avoid underflow. However, this approach requires log
and exponent operations, which are more computationally expensive than sums or products.
The failure of pruning is a unique problem for
PCFG-LA, and the others are general problems ofparsing methods based on PCFG. In the next section, we describe three improvements over the basic
PCFG-LA method that Ckylark uses to avoid theseproblems.

3 Improvements of the Parsing Method
3.1 Early Stopping in Coarse-to-fine Analysis
While coarse-to-fine analysis generally uses theparsing result of the finest grammar as output, intermediate grammars also can generate parse trees.
Thus, we can use these intermediate results insteadof the finest result when parsing fails at later stages.
Algorithm 1 shows this “stopping” approach. Thisapproach can avoid all errors due to coarse-to-fine
pruning, except in the case of failure during the parsing with the first grammar due to problems of themodel itself.
3.2 Lexicon Smoothing
Next, we introduce lexicon smoothing using theprobabilities of unknown words at parsing time.
This approach not only reduces the size of the grammar, but also allows for treatment of any word asAlgorithm 1 Stopping coarse-to-fine analysis
Require: w: input sentence
Require: G0 , · · · , GL : coarse-to-fine grammars
T−1 ← nilP0 ← {}▷ pruned pathesfor l ← 0 .. L doTl , Pl+1 ← parse and prune(w; Gl , Pl )if Tl = nil then▷ parsing failed
return Tl−1 ▷ return intermediate result
end ifend forreturn TL▷ parsing succeeded“unknown” if the word appears in an unknown syntactic content. Equation (1) shows the smoothed lexicon probability:

TypeWSJ-train/dev
WSJ-test
NTCIR#sent
41.5 k
2.42 k3.08 M#word
990 k
56.7 k
99.0 M

Equation (5):sl (w) ≡ exp∑P (X) log P ′ (X → w), (5)Xand sg is the scaling factor of binary rules defined as
the geometric mean of all binary rules in the grammar P (X → Y Z) as in Equation (6):sg ≡ exp
H(X) ≡P ′ (X → w) ≡ (1 − λ)P (X → w) +λP (X → wunk ),Table 1: Dataset Summaries.

∑∑

P (X)H(X),(6)

X

P (X → Y Z) log P (X → Y Z). (7)Y,Z(1)where X is any pre-terminal (part-of-speech) symbol in the grammar, w is any word, and wunk is
the unknown word. λ is an interpolation factor between w and wunk , and should be small enough tocause no effect when the parser can generate the result without interpolation. Our implementation uses
λ = 10−10 .
3.3 Probability Scaling
To solve the problem of underflow, we modify
model probabilities as Equations (2) to (4) to avoid
underflow without other expensive operations:

Calculating P (X) is not trivial, but we can retrievethese values using the graph propagation algorithm
proposed by Petrov and Klein (2007).

4 Experiments
We evaluated parsing accuracies of our parser Ckylark and conventional PCFG-LA parsers: Berkeley Parser and Egret. Berkeley Parser is a conventional PCFG-LA parser written in Java with some
additional optimization techniques. Egret is also aconventional PCFG-LA parser in C++ which cangenerate a parsing forest that can be used in downstream application such forest based machine translation (Mi et al., 2008).

Q(X → w) ≡ P ′ (X → w)/sl (w),(2)

4.1 Dataset and Tools

Q(X → Y ) ≡ P (X → Y ),(3)Table 1 shows summaries of each dataset.
We used GrammarTrainer in the Berkeley Parser
to train a PCFG-LA grammar with the Penn Treebank WSJ dataset section 2 to 22 (WSJ-train/dev).
Egret and Ckylark can use the same model as theBerkeley Parser so we can evaluate only the performance of the parsers using the same grammar. Eachparser is run on a Debian 7.1 machine with an Intel
Core i7 CPU (3.40GHz, 4 cores, 8MB caches) and4GB RAM.
We chose 2 datasets to evaluate the performancesof each parser. First, WSJ-test, the Penn Treebank WSJ dataset section 23, is a standard dataset

Q(X → Y Z) ≡ P (X → Y Z)/sg ,(4)where X, Y, Z are any non-terminal symbols (including pre-terminals) in the grammar, and w is anyword. The result of parsing using Q is guaranteed tobe the same as using original probabilities P and P ′ ,because Q maintains the same ordering of P and P ′despite the fact that Q is not a probability. Valuesof Q are closer to 1 than the original values, reducing the risk of underflow. sl (w) is a scaling factor
of a word w defined as the geometric mean of lexicon probabilities that generate w, P ′ (X → w), as inTable 2: Bracketing F1 scores of each parser.

ParserBerkeley Parser
Egret
Ckylark (10−5 )Ckylark (10−7 )F1 (all)
89.98
89.05
89.44
89.85

F1 (|w| ≤ 40)
90.54
89.70
90.07
90.39

Table 3: Tagging accuracies of each parser.

ParserBerkeley Parser
Egret
Ckylark (10−5 )Ckylark (10−7 )Acc (all)
97.39
97.33
97.37
97.39

Acc (|w| ≤ 40)
97.37
97.28
97.35
97.38

to evaluate parsing accuracy including about 2000
sentences. Second, we use NTCIR, a large English
corpus including more than 3 million sentences, extracted from the NTCIR-8 patent translation task
(Yamamoto and Shimohata, 2010).
Input sentences of each parser must be tokenizedin advance, so we used a tokenization algorithm
equivalent to the Stanford Tokenizer5 for tokenizing
the NTCIR dataset.
4.2 Results
Table 2 shows the bracketing F1 scores6 of parsetrees for each parser on the WSJ-test dataset and Table 3 also shows the part-of-speech tagging accuracies. We show 2 results for Ckylark with pruningthreshold ϵ as 10−5 and 10−7 . These tables showthat the result of Ckylark with ϵ = 10−7 achieves
nearly the same parsing accuracy as the BerkeleyParser.
Table 4 shows calculation times of each parser on
the WSJ-test dataset. When the pruning threshold ϵ
is smaller, parsing takes longer, but in all cases Ckylark is faster than Egret while achieving higher accuracy. Berkeley Parser is the fastest of all parsers, aresult of optimizations not included in the standard
PCFG-LA parsing algorithm. Incorporating thesetechniques into Ckylark is future work.
Table 5 shows the number of parsing failures ofeach parser. All parsers generate no failure in theWSJ-test dataset, however, in the NTCIR dataset,
56

Table 4: Calculation times of each parser.

http://nlp.stanford.edu/software/tokenizer.shtml
http://nlp.cs.nyu.edu/evalb/

ParserBerkeley Parser
Egret
Ckylark (10−5 )Ckylark (10−7 )Time [s]27833789232157

Table 5: Frequencies of parsing failure of each parser.

ParserBerkeley Parser
Egret
Ckylark (10−5 )WSJ-test(#) (%)
000000Failure
NTCIR(#)(%)
419 0.0136
17287
0.561
00

Table 6: Number of failures of each coarse-to-fine level.

Smoothλ=0
λ = 10−10Failure level01 2 3 4 561741 135 24 11 5 57 1405
0 130 19 8 4 51 1389

0.01% and 0.5% of sentences could not be parsedwith the Berkeley Parser and Egret respectively. In
contrast, our parser does not fail a single time.
Table 6 shows the number of failures of Ckylark
with ϵ = 10−5 and without the stopping approach; if
the parser failed at the level l analysis then it returns
the result of the l − 1 level. Thus, the stopping approach will never generate any failure, unless failure
occurs at the initial level. The reason for failure at
the initial level is only due to model mismatch, as
no pruning has been performed. These errors can beprevented by lexicon smoothing at parsing time asshown in the case of level 0 with λ = 10−10 in thetable.

5 Conclusion
In this paper, we introduce Ckylark, a parser thatmakes three improvements over standard PCFG-LAstyle parsing to prevent parsing failure. Experiments
show that Ckylark can parse robustly where other
PCFG-LA style parsers (Berkeley Parser and Egret)fail. In the future, we plan to further speed up Ckylark, support forest output, and create interfaces toother programming languages.

Acknowledgement
Part of this work was supported by JSPS’s Research
Fellowship for Young Scientists.

References
Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of english: The Penn Treebank. Computationallinguistics, 19(2).
Takuya Matsuzaki, Yusuke Miyao, and Jun’ichi Tsujii.
2005. Probabilistic CFG with latent annotations. InProc. ACL.
Haitao Mi, Liang Huang, and Qun Liu. 2008. Forestbased translation. In Proc. ACL-HLT.
Graham Neubig and Kevin Duh. 2014. On the elementsof an accurate tree-to-string machine translation system. In Proc. ACL.
Slav Petrov and Dan Klein. 2007. Improved inference
for unlexicalized parsing. In Proc. NAACL-HLT.
Slav Petrov, Leon Barrett, Romain Thibaux, and DanKlein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proc. COLING-ACL.
Atsushi Fujii Masao Utiyama Mikio Yamamoto and Sayori Shimohata. 2010. Overview of the patent translation task at the NTCIR-8 workshop. In Proc. NTCIR8.
Deniz Yuret, Aydin Han, and Zehra Turgut. 2010.
Semeval-2010 task 12: Parser evaluation using textualentailments. In Proc. SemEval.