Parsing comparison across grammar
formalisms using strongly equivalent
grammarsComparison of LTAG and HPSG parsers: A case study
Naoki Yoshinaga* — Yusuke Miyao* — Kentaro Torisawa**
Jun’ichi Tsujii*,**** University of Tokyo

7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-0033, Japan{yoshinag, yusuke, tsujii}@is.s.u-tokyo.ac.jp** Japan Advanced Institute of Science and Technology

1-1 Asahidai, Tatsunokuchi, Ishikawa, 923-1292, Japan
torisawa@jaist.ac.jp*** CREST, JST (Japan Science and Technology Agency)

4-1-8 Honcho, Kawaguchi-shi, Saitama, 332-0012, Japan
ABSTRACT. This article presents a novel approach to empirical comparison between parsers fordifferent grammar formalisms such as LTAG and HPSG. The key idea of our approach is touse strongly equivalent grammars obtained by grammar conversion, which generate equivalent parse results for the same input. We validate our approach by giving a formal proof ofstrong equivalence for an existing grammar conversion from LTAG to HPSG-style grammar.
Experimental results using two pairs of LTAG and HPSG parsers with dynamic programmingand CFG filtering reveal that the different ways of using the parsing techniques cause significant
performance differences, and also suggest a definite way of improving these parsing techniques.
RÉSUMÉ. Nous présentons une approche nouvelle pour comparer de manière empirique des analyseurs syntaxiques pour des formalismes grammaticaux comme LTAG et HPSG. L’idée centraleconsiste à utiliser des grammaires fortement équivalentes obtenues par conversion et produisant des analyses équivalentes pour la même chaîne d’entrée. Nous validons cette approche enfournissant une preuve formelle d’équivalence forte pour le mécanisme de conversion de grammaires de LTAG vers HPSG. Les résultats expérimentaux obtenus avec deux paires d’analyseurs
syntaxiques LTAG et HPSG en utilisant la programmation dynamique et le filtrage CFG ont
montré que les différences de performance résultent des différence d’adaptation des techniquesd’analyse, suggérant une piste solide pour améliorer celles-ci.
KEYWORDS: parsing, dynamic programming, CFG filtering, LTAG, HPSG.
MOTS-CLÉS : analyse syntaxique, programmation dynamique, filtrage CFG, LTAG, HPSG.

TAL. Volume 44 - n◦ 3/2003, pages 15 to 39

16

TAL. Volume 44 - n◦ 3/2003

1. Introduction
Over the past two decades, a wide range of parsers have been developed for lexicalized grammars such as Lexicalized Tree Adjoining Grammar (LTAG) [SCH 88] andHead-Driven Phrase Structure Grammar (HPSG) [POL 94a]. Parsers that have been
proposed independently of one another often share the same parsing techniques thatare claimed to be independent of individual grammar formalisms. Examples of suchgeneric techniques are dynamic programming [YOU 67, EAR 70, VIJ 85, HAA 87],
left-to-right parsing [TOM 86, BRI 93, NED 98], and two-phase parsing [MAX 93,
TOR 95, YOS 99] including CFG filtering [TOR 96, TOR 00, KIE 00]. However, as
mentioned in [CAR 94], while these techniques are generic in the sense that they canbe used for efficient implementation of parsers for any grammar formalism, their impact often varies from one formalism to another [SCH 95, YOS 99]. It seems thatgeneric techniques actually interact with the characteristics of individual grammar
formalisms.
To assess the true effect of algorithmic techniques such as those derived from dynamic programming, CFG filtering, etc., we need a means of abstracting away the‘surface’ differences between grammar formalisms. Such abstraction should also be
useful for adapting techniques found that have been efficient with parsers based on
one formalism to parsers based on another.
In this article, we propose grammar conversion as a means of abstracting away
the surface differences between grammar formalisms. That is, we show that, by constructing a “strongly equivalent” grammar1 in a particular formalism from one given
in another formalism and by measuring the performance of parsers based on the original grammar and ones based on the newly-constructed grammar, one can gain a deeper
insight into generic parsing techniques and share techniques developed for parsers fordifferent grammar formalisms. Strongly equivalent grammars obtained by grammar
conversion allow us to carry out a meaningful comparison among parsers for different
grammar formalisms regardless of their surface differences, because the parsers handle equivalent grammatical constraints (which are preserved by the grammar conversion) and thus produce equivalent parse results for the same input. Strongly equivalent
grammars are also very helpful for incorporating techniques that have been found tobe efficient from parsers based on one formalism to parsers based on another, because
the grammar conversion defines a clear correspondence between those grammars, i.e.,a correspondence which enables us to observe how parsers for one formalism handle
a grammar in another formalism.
We focus on two generic parsing techniques in this article, namely dynamic
programming [SAR 00a, HAA 87] and CFG filtering [HAR 90, POL 94b, TOR 96,
1. Chomsky [CHO 63] first introduced the notion of strong equivalence between grammars,
where both grammars generate the same set of structural descriptions (e.g., parse trees). Kornai
and Pullum [KOR 90] and Miller [MIL 99] used the notion of isomorphism between sets ofstructural descriptions to provide the notion of strong equivalence across grammar formalisms,
which we have adopted in this research.

Parsing comparison across formalisms

*

α1 

anchorfoot node
substitution nodesubstitution

α2 

we

 β1

adjunction






can

 *

run
α1, α2, β1: elementary trees

17

derived tree

derivation tree



α1






α2





we can

β1

run

Figure 1. Lexicalized Tree Adjoining Grammar: basic structures (elementary trees)and compose operations (substitution and adjunction)
POL 98, TOR 00, KIE 00]. We first see how these techniques have been employed inparsers for two particular grammar formalisms, LTAG and HPSG. Since dynamic programming forms the basis of most current parsing techniques, a comparison of parsers
using it allows us to roughly grasp the difference between the performance of LTAG
and HPSG parsers. Since the impact of CFG filtering for LTAG is quite different fromthat for HPSG, a comparison of parsers using it can demonstrate the utility of our
methods. Next, we show that grammar conversion yielding an HPSG-style grammarfrom a given LTAG grammar reveals the true nature of these generic parsing techniques, and results in parsers for LTAG that are more efficient than those implemented
for the original LTAG grammar, even though they use the same generic techniques.
To validate our approach, we give a formal proof of strong equivalence for an existing grammar conversion from LTAG to HPSG-style grammar [YOS 02], and use
it to obtain strongly equivalent grammars. Empirical comparisons of parser performance were then conducted using two LTAG grammars and their equivalent HPSGstyle grammars. One is the XTAG English grammar [XTA 01], which is a large-scale
handcrafted Feature-Based LTAG (FB-LTAG) [VIJ 87, VIJ 88], and the other is an
LTAG grammar that was automatically extracted from the Penn Treebank [MAR 93].

2. Grammar formalisms and parsing techniques
2.1. Grammar formalisms
2.1.1. Lexicalized Tree Adjoining Grammar
An LTAG [SCH 88] is defined by a set of elementary trees that are composed by
two operations called substitution and adjunction. These are shown on the left-handside of Figure 1. An elementary tree has at least one leaf node that is labeled with aterminal symbol (i.e., word) called an anchor (marked with ). Elementary trees areclassified as either initial trees (α1 and α2) or auxiliary trees (β1). The label of one
leaf node of an auxiliary tree is identical to that of its root node, and this is speciallymarked (here, with ∗) as a foot node. In an elementary tree, leaf nodes other than

18

TAL. Volume 44 - n◦ 3/2003

anchors and the foot node are called substitution nodes (marked with ↓). The lefthand side of Figure 1 also illustrates the two operations. In substitution, a leaf node(substitution node) is replaced by an initial tree, while in adjunction, an auxiliary treewith the root node and a foot node labeled x is grafted onto a node with the same
symbol x. The results of analysis are described not only by derived trees (i.e., parsetrees) but also by derivation trees (the right-hand side of Figure 1). The derivation
trees represent the history of combinations of trees.
FB-LTAG [VIJ 87, VIJ 88] is an extension of the LTAG formalism in which eachnode in the elementary trees has a feature structure, which contains a set of grammatical constraints on the node. The constraints are to be satisfied through unification
during adjunction and substitution.
2.1.2. Head-Driven Phrase Structure Grammar
We define an HPSG-style grammar according to the computational architecture of
HPSG [POL 94a]. It consists of lexical entries and Immediate Dominance (ID) grammar rules, each of which is described with typed feature structures [CAR 92]. The
greater generative power of the underlying architecture of HPSG allows us to obtaina trivial encoding of LTAG in the typed feature structure, as described by [KEL 94,
pp. 144–151]. However, such a conversion cannot meet our needs because the resulting grammar is far from the one defined in [POL 94a]. Hence, we restrict the formof an HPSG-style grammar to one that follows the HPSG formalism in the following
ways. A lexical entry for a word must express the characteristics of the word, suchas its subcategorization frame and grammatical category. An ID grammar rule must
represent the constraints on the configuration of immediate constituency and not be aconstruction-specific rule defined by lexical characteristics. These restrictions enable
us not only to define a formal link between computational architectures that underlies LTAG and HPSG, but also to clarify the relationships between linguistic accounts
given using LTAG and HPSG by comparing the HPSG-style grammar converted fromLTAG with HPSG. The interested reader may refer to the discussion in [YOS 02].
Note that Pollard and Sag [POL 94a] provide detailed linguistic specifications forthe form of feature structures and adopt principles, such as the Immediate DominancePrinciple, to express linguistic concepts, for example projection. In our definition,
we assume that principles are implicitly encoded in ID grammar rules and when weconvert an LTAG grammar to an HPSG-style grammar we do not attempt to translate
linguistic specifications in the LTAG into the corresponding HPSG principles.

2.2. Conventional parsers
The LTAG and HPSG parsers with dynamic programming used in our experiments [NOO 94, HAA 87] perform factoring, a common-sense parsing technique thatavoids generating duplicate equivalent partial parse trees. In the following sections,
we briefly describe how factoring is accomplished in parsers for the two formalisms.

Parsing comparison across formalisms

S1: runα1 S3: run
α1 




S5: can run
α1 

S7: we can run
α1 

S8: we can run
α1 





















run

run

run

run

19



run

Accept
β1 

can
S4-1:

β1 
*



*

can
S4-2: can

α2 

α2 





We
We
S6-1: we S6-2: weFigure 2. Example of head-corner parsing for an LTAG grammar

2.2.1. Head-corner parser for LTAG
One of the LTAG parsers used in our experiments, which we call the “conventional” LTAG parser, is a head-corner LTAG parser [SAR 00a]. Its parsing algorithm
is a chart-based variant of van Noord’s [NOO 94]. The parser uses a data structure
called an agenda. The agenda stores states to be processed. A state is represented bya quadruplet consisting of an elementary tree, a root node, a processing node, and aspan over the input, which denote the processed and unprocessed parts of the tree.
Figure 2 depicts the process of head-corner parsing for the sentence “we can run.”In the figure, nodes in bold face, arrows in states, arrows between states, and strings
followed by the state number S# respectively indicate processing nodes, directionsof processing, relations between the states, and spans over the input string. In headcorner parsing, the parser traverses a tree from one leaf node called the head-corner tothe root node. This tree traversal is called head-corner traversal. During head-cornertraversal, the parser recognizes the siblings of the processing node and possible adjunctions at this node. In Figure 2, the parser first predicts an initial tree α2 whoseroot node matches the symbol S corresponding to the sentence (state S1 in Figure 2).
The parser proceeds in a bottom-up manner from the head-corner “run” to S. Aftermoving up to the node VP in α2 (S3), the parser recognizes the adjunction at theprocessing node VP and introduces a new state S4-1 for the adjoining tree β1. After
recognizing β1 (S4-2), the parser tries to recognize the sibling of VP (S5). To recognize the sibling NP, the parser introduces a new state S6-1 for α1. Then, the parser
proceeds to the root S of α2 (S8). Since there is no state to be processed in the agenda,
parsing of “we can run” ends.
The parser performs factoring when it generates a new state. That is, it pushes astate in the agenda only when an equivalent state does not exist in the agenda. Notethat equivalent states are those which have the same elements in the quadruplet.

TAL. Volume 44 - n◦ 3/2003

20

Grammar rule SymǱ ŗ

Arg Ǳ řE5
Grammar rule SymǱ ŗ

Arg Ǳ řSymǱ ŗ
Arg Ǳ ŘE1
Sym: 
Arg :

we

E2

unify

SymǱ ŘE4

SymǱ Ř
Arg Ǳ řE3SymǱȱ ŗArg Ǳ Ř

unify

unify

SymǱȱȱ
Arg Ǳ

ř

unify

SymǱȱ Arg ǱȱȱȱSymǱȱ Arg ǱȱȱȱSymǱȱ Arg ǱȱȱȱSymǱȱ Arg Ǳȱȱȱ

Sym: 
Arg :SymǱȱ Arg ǱȱȱȱSymǱȱ Arg Ǳȱȱȱ

Sym: 
Arg :SymǱȱ Arg ǱȱȱȱSymǱȱ Arg Ǳȱȱȱ

can

run

we

can

run

we

can

run

Figure 3. Example of CKY-style parsing for an HPSG grammar
2.2.2. CKY-style HPSG parser
One of the HPSG parsers used in our experiments, which we call the “conventional” HPSG parser, is a CKY-style HPSG parser [HAA 87]. The parser uses a data
structure called a triangular table. The triangular table stores edges, which correspond to partial parse trees. An edge is described with a tuple consisting of a feature
structure that represents the root node of a partial parse tree and a span over the input.
Figure 3 illustrates an example of the CKY-style parsing for an HPSG grammar.
First, lexical entries for “we,” “can,” and “run” are stored as edges E1, E2, and E3 in
the triangular table. Next, E2 and E3 are each unified with the daughter feature structures of an ID grammar rule. The feature structure of the mother node is determined
as a result of this unification and is stored in the triangular table as a new edge E4. An
ID grammar rule is then applied to E1 and E4, and a new edge E5 is generated. Since
the parse tree spans the whole input string, parsing of “we can run” ends.
The parser performs factoring when it generates a new edge. That is, it storesan edge in the triangular table unless an equivalent edge exists in the cell. Note thatequivalent edges are those which have the same elements in the tuple.

2.3. CFG filtering techniques
CFG filtering is a parsing scheme that predicts possible parse trees by using a CFG
extracted from a given grammar. An initial offline step of CFG filtering is performed toapproximate a given grammar with a CFG, in other words, to extract a CFG backbone
from a given grammar (Context-Free (CF) approximation). The resulting CFG is used
as an efficient device for computing the necessary conditions for parse trees.
After the initial step, CFG filtering generally comprises two phases. In phase 1, theparser first constructs possible parse trees by using the CFG obtained in the initial offline step, and then filters out CFG edges unreachable by top-down traversal startingfrom roots of successful context-free derivations. In phase 2, it eliminates invalid
parse trees by using full constraints in the given grammar. We call the remaining CFG
edges that are used for phase 2 essential edges.

Parsing comparison across formalisms
Tree 5: 

5.ε

5.1 5.2

Tree 9:  ȱ

 

9.ε

5.ε
9.ε

9.1  9.2

5.2.1  5.2.2

 9.2.1

love

think

21



 9.2.2

5.1
9.1

5.2
9.2





5.2.1

5.2





9.2.1

9.2

5.2.2



9.2.2

Figure 4. Extraction of CFG from LTAGa) ok-flag is propagated to a node otherthan a root of auxiliary treeb) ok-flag is propagated to a root of auxiliary tree

C

C
B
B
2. Check the node
number equality

Ay

1. Find a supernodeA x okAy

2. Find a foot node

1. Find a supernodeA*A x ok
4. Check the node
number equality

3. Find a subnode of a foot nodeA z okFigure 5. Ok-propagation from an essential edge to another
The parsers with CFG filtering for LTAG and HPSG follow the above parsing strategy, but differ in their ways of approximating a grammar with CFG and eliminating
impossible parse trees in phase 2. In the following sections, we briefly describe theCF approximation and the elimination of impossible parse trees for each formalism.
2.3.1. CF approximation of LTAG
In the CFG filtering techniques for LTAG [HAR 90, POL 98], every branching ofelementary trees in a given grammar is extracted as a CFG rule as shown in Figure 4.
Because the obtained CFG can reflect only local constraints given in each local
structure of the elementary trees, it generates invalid parse trees that connect local
trees extracted from different elementary trees. To eliminate such illegal parse trees, alink between branchings is preserved as a node number which records a unique nodeaddress (a subscript attached to each node in Figure 4). As depicted in Figure 5, we
can eliminate such parse trees by traversing essential edges in a bottom-up mannerand recursively propagating an ok-flag from node number x to node number y when aconnection between x and y is allowed in the LTAG grammar. We call this propagation
ok-propagation [POL 94b].
2.3.2. CF approximation of HPSGIn the CFG filtering techniques for HPSG [TOR 96, TOR 00, KIE 00], a CFG isextracted from a given HPSG grammar by recursively instantiating daughters of agrammar rule with lexical entries and generated feature structures, as shown in Fig-

22

TAL. Volume 44 - n◦ 3/2003

phrasalSYNSEM …

Grammar rulesign

SYNSEM …

sign

SYNSEM …

Grammar rulesign

SYNSEM …

sign

SYNSEM …

phrasalSYNSEM …

sign

SYNSEM …

phrasalSYNSEM …

 ȱ
ȱ
ȱ



phrasalSYNSEM …

sign

SYNSEM …

lexicalSYNSEM …



Figure 6. Extraction of CFG from HPSG
ure 6. This procedure stops when new feature structures are not generated. We must
impose restrictions on the features (i.e., ignore them) or on the number of rule instantiations or both in order to guarantee termination of the rule instantiation. A CFG is
obtained by regarding the initial and the generated feature structures as nonterminals
and bottom-up derivation relationships as CFG rules.
Although the resulting CFG reflects the local and global constraints of the whole
structure of lexical entries, it generates invalid parse trees that do not reflect the constraints given by the features that were ignored in the CFG. These parse trees are
eliminated in phase 2 by applying HPSG grammar rules that correspond to the applied
CFG rules. We call this rule application rule-application.

3. Grammar conversion
This section describes an algorithm for converting from LTAG to a strongly equivalent HPSG-style grammar [YOS 02]. The conversion algorithm consists of two phasesof conversion: i) a conversion from LTAG into canonical LTAG, LTAG which consists
only of canonical elementary trees, and ii) a conversion from the canonical LTAG into
an HPSG-style grammar. Substitution and adjunction are emulated by pre-determined
ID grammar rules.2 This algorithm can easily handle an FB-LTAG grammar by merely
extending the grammar rules to execute the feature structure unification in the same
way as in FB-LTAG. We give a formal proof of strong equivalence for the above twophases of conversion in Appendices A.2 and A.3, respectively.
We define canonical elementary trees, which have one-to-one correspondenceswith HPSG lexical entries. Canonical elementary trees are elementary trees which
2. In this article, we assume that elementary trees consist of binary branching structures. A
unary branching can be regarded as a binary branching in which one daughter is the empty
category, and n-ary (n ≥ 3) branchings can similarly be converted into binary branchings. This
conversion guarantees strong equivalence by virtue of being a one-to-one mapping.

Parsing comparison across formalisms
Canonical elementary tree

Non-canonical elementary treesa) Violation of Condition 1 b) Violation of Condition 2
Tree with non-anchored subtreesMulti-anchored tree



*

23












think
look










give



Non-anchored subtree

for

Figure 7. A canonical elementary tree and non-canonical elementary trees

Sym : ŗArg : Ř



think

*

Sym: 
Sym : Sym : think :
, Leaf : 
Arg: Leaf : 
Dir :  Dir : Foot?: +Foot?:

Sym : řArg :substitution node

Arg :Sym : ŗArg : ŘSym : ŗLeaf : ř
Dir : Foot? :
trunk node

Left substitution ruleŘ

Sym : řArg : Śfoot node

Arg :

Ś

Sym : ŗLeaf : ř
Dir : Foot? : +trunk nodeŘLeft adjunction ruleFigure 8. Conversion of LTAG elementary trees into HPSG lexical entries (left) andthe grammar rules: the substitution rule (center) and the adjunction rule (right)
satisfy two conditions. Condition 1: A tree has only one anchor, and Condition 2:
Every branching structure in a tree contains trunk nodes. Trunk nodes (nodes in bold
face in Figure 7) are nodes on a trunk (thick branches in Figure 7), which is a pathfrom an anchor to a root node other than the anchor [KAS 95]. Condition 1 guarantees
that a canonical elementary tree has only one trunk, while Condition 2 guarantees thateach branching consists of a trunk node, a leaf node, and their mother, as seen in theexample on the left-hand side of Figure 7. The right-hand side of Figure 7 shows noncanonical trees. We call a subtree of depth n (n ≥ 1) that includes no anchor a nonanchored subtree. Non-canonical elementary trees are first converted into canonicaltrees, and then converted into HPSG lexical entries.

3.1. Conversion of canonical elementary trees
The left-hand side of Figure 8 depicts an example of conversion of canonical elementary trees. A canonical elementary tree is converted into an HPSG lexical entry byregarding leaf nodes as arguments of the anchor and storing them in a stack (the Arg
feature in the left-hand side of Figure 8) where each leaf node is expressed by a triplet
consisting of the symbol, the direction against the trunk, and the type (the Leaf, Dir,TAL. Volume 44 - n◦ 3/2003

24

Sym : ŗ 
Arg :

α1






α2




β1





what



*


loves

α3




α4

α2





he

think


you

LTAG derivation

Arg :Sym : ŗ 
Leaf : Ř ȱ
Dir : Foot? :

ś

what

α4

Sym : Ŝ ȱ
Arg :

you
Sym : think: Arg :α1
β1

Sym : ř 

Sym : Ř ȱ
Arg :

…C

Sym : ŝ 
Sym : ř 
Arg : Ş Leaf : Ŝ ȱ
Dir : Foot? :

Sym : ŝ 
Leaf : Ś ȱDir : 
Foot? : ƸśSym : ŗ 
Leaf : Ř ȱ
Dir : Foot? :

Sym : Ś 

Sym : ř : Ŝ ȱ, Ş Leaf
Dir : Arg :Foot? :
Sym : ş ȱ
Arg :

α3
he

…B

Sym : loves:Arg :Sym : ŗ 
ś Leaf : Ř ȱ
Dir : Foot? :

Sym : Ś 
Leaf : ş 
Dir : Foot? :

…A

Sym : ŗ : Ř ȱ, ś Leaf
Dir : Foot? :HPSG rule applications

Figure 9. LTAG and HPSG parsing of the phrase “what you think he loves”
and Foot? features in the left-hand side of Figure 8, respectively). The trunk symbol
is stored as the Sym feature in order to explicitly determine the symbol of the mothernode in the rule applications.
Substitution and adjunction are emulated by grammar rules such as those shownin the center and the right-hand side of Figure 8, respectively. A co-indexing box nindicates that two sub-feature structures share their values with each other. Both rules
pop an element in the value of the Arg feature of a node and let the node subcategorize
for a node unifiable with the popped element. A substitution rule requires that the Arg
feature of the node to be subcategorized should be an empty stack, while an adjunction
rule concatenates the values of the Arg features of both daughters.
Figure 9 shows examples of rule application. The solid lines indicate the adjoinedtree (α1) and the dotted lines indicate the adjoining tree (β1). The adjunction rule isapplied in order to construct the branching marked with , where “think” takes as its
argument the node having the Sym feature’s value of S. By applying the adjunction
rule, the Arg feature of the mother node B becomes a concatenated stack of the Arg
features of both β1, ‘ 8 ’, and α1, ‘ 5 .’ Note that when the construction of β1 has
been completed, the Arg feature of the trunk node C will return to its former state (A).
We can continue constructing α1 in the same way as for the case where no adjunction
rules have been applied.

3.2. Conversion of non-canonical elementary trees
Non-canonical elementary trees are initially divided into multiple subtrees, eachof which has at most one anchor, by a procedure called tree division, as shown in Fig-

Parsing comparison across formalisms
Multi-anchored tree

Canonical trees
cut off





25






look




identifierlook_forlook_for

tree division
look





cut-off nodes

for

for

Figure 10. Conversion of multi-anchored trees into multiple canonical trees
canonical treesTree with non-anchoredsubtrees










cut offtree division

give






givegive
non-anchoredsubtreesgiveTrees without non-anchored
all candidate canonicalsubtrees
trees for substitution treegivegive
substitution



on




next

substitution,…
next to







on
break points





,…

next tonext

Figure 11. Conversion of a tree with non-anchored subtrees into canonical trees andtrees without non-anchored subtrees
ures 10 and 11. Nodes that mark the separation of one tree into two are called cut-off
nodes. A cut-off node is marked by an identifier to preserve the co-occurrence relation
among the multiple anchors. The tree division converts multi-anchored trees, which
only violate Condition 1, into canonical trees (Figure 10), while it converts trees with
non-anchored subtrees into canonical trees and non-anchored subtrees (Figure 11).
A procedure called tree substitution converts the non-anchored subtrees into anchored trees. It causes a substitution at one substitution node on every deepest branching by every candidate tree for substitution, as shown in Figure 11. We should mention
that the substituted nodes are marked as break points to remember that the resulting
trees are obtained by substituting other trees at those nodes. The candidate trees for
substitution are selected from among all the canonical elementary trees and the ones
obtained by the conversion given in the previous paragraph. Because the candidate
trees for substitution include neither non-anchored subtrees nor auxiliary trees whoseroot nodes do not originate from the root nodes of initial trees, the trees obtained bythis process will satisfy Condition 2. When they take substitution at one substitution node, they also satisfy Condition 1 and are canonical trees; otherwise, they are
multi-anchored trees and will be converted into canonical trees by the tree division.

26

TAL. Volume 44 - n◦ 3/2003

Table 1. Classification of elementary trees in the XTAG English grammar (LTAG) andlexical entries converted from them (HPSG)
Grammar
LTAG
HPSG

A
326
326

B
C
763
54
1,989 1,083

DTotal
50 1,193
2,474 5,872

Table 2. Parsing performance with the XTAG English grammar for the ATIS corpus
ParserNaive
lemParse time (sec.)
1.54
20.76

4. Comparison of LTAG and HPSG parsers
4.1. Comparison of dynamic programming techniques
We compared a pair of dynamic programming techniques for LTAG [NOO 94] and
HPSG [HAA 87] described in Sections 2.2.1 and 2.2.2. Henceforth, lem refers to the
LTAG parser [SAR 00a], ANSI C implementation of the head-corner parsing.3 Naiverefers to C++ implementation of the CKY-style HPSG parser.
We converted the latest version of the XTAG English grammar [XTA 01], which
is a large-scale FB-LTAG grammar, into a strongly equivalent grammar by using thegrammar conversion described in Section 3.1. Table 1 shows a classification of theelementary trees4 of the XTAG English grammar according to the conditions describedin Section 3.1.5 In the table, A shows the number of canonical elementary trees, while
B, C, and D respectively show the number of trees that violate only Condition 1, only
Condition 2, and both conditions. The second row indicates the number of HPSG
lexical entries converted from the LTAG elementary trees.
Table 2 shows the parsing speed results for 452 sentences from the ATIS corpus [MAR 93]6 (average sentence length: 6.32 words). The machine used in the following experiments was a 1.26 GHz Pentium III with 4 GB memory. The results showthat the HPSG parser achieved a speed-up of a factor of 13. Figure 12 shows parsetime plotted against sentence length, where both axes use logarithmic scales. Since
the increase in parse time versus sentence length plotted on logarithmic scales is equal
3. The LTAG parser is available at: ftp://ftp.cis.upenn.edu/pub/xtag/lem/lem-0.14.0.tgz
4. These elementary trees should more strictly be called elementary tree templates. That is, elementary trees are abstracted from lexicalized trees, and one elementary tree template is definedfor one syntactic construction, which is assigned to a number of words.
5. We eliminated 33 elementary trees because the LTAG parser could not produce correct
derivation trees with them; adjunction of these trees was sometimes not performed by the parser.
6. We eliminated 56 sentences because of parser time-outs, and 69 sentences because the LTAG
parser had bugs in its preprocessor preventing it from producing correct derivation trees.

Parsing comparison across formalisms

1e+07
log (time) in milliseconds

log (time) in milliseconds

1e+07

27

1e+06
100000
10000
1000
100
10

1e+06
100000
10000
1000
100
10

1

1
1

5
10 15
log (sentence length) in words

1

5
10 15
log (sentence length) in words

lem

Naive

Figure 12. Parsing performance with the XTAG English grammar for the ATIS corpus
Edges are equivalent and factored out

States are not equivalent and not factored out















felt






felt







felt








Sym: VP
Sym : Arg: Leaf : 
Dir : Foot?:

felt

duplicated equivalent grammatical construction

LTAG

HPSG

Figure 13. Difference between factoring schemes in LTAG and HPSG

to the degree of polynomial order of the empirical time complexity, the graphs showthat the order of the empirical time complexity of lem is higher than that of Naive.
As noted in Section 2.2, both parsers have an architecture that supports factoring, but the ways in which they perform factoring differ. Remember that a state in
the LTAG parser is a quadruplet consisting of an elementary tree, a root node, a processing node, and a span over an input, while an edge in the HPSG parser is a tuple
consisting of a feature structure and a span over an input. By considering how the
HPSG parser handles the HPSG-style grammar converted from the LTAG, we see thatthe HPSG parser treats a branching as its minimal component and performs factoringof edges when the edges’ feature structures are equivalent (the right-hand side of Figure 13). On the other hand, the LTAG parser treats an elementary tree as its minimalcomponent and performs factoring of states when the elementary trees of the states
have equivalent root nodes (the left-hand side of Figure 13). Since the root node corresponds to a feature structure whose Arg feature is an empty stack in HPSG, thisdifference means that the HPSG parser factors out more partial parse trees than does
the LTAG parser. As illustrated in Figure 13, the LTAG parser cannot avoid duplicating equivalent grammatical constructions corresponding to fragments of elementary

28

TAL. Volume 44 - n◦ 3/2003

100000log (the numbr of edges)log (the numbr of edges)

100000
10000
1000
100
10

10000
1000
100
10

1

5
10 15
log (sentence length) in words

Naiverf1

5
10 15
log (sentence length) in words

Naive

Figure 14. Number of edges of a variant of Naive (Naiverf ) which performs factoring
only when the factoring can be performed in lem (left) and Naive (right)
trees. This difference in factoring schemes leads to the difference in the empiricaltime complexity.
To verify the above argument, we conducted a parsing experiment on the same
corpus by using a variant of Naive (hereafter Naiverf ) which performs factoring only
when the factoring could be performed by the LTAG parser.7 Since edges and states
generated by the LTAG and HPSG parsers represent partial parse trees, their numbers
are reliable indicators of empirical time complexity. Figure 14 shows the number ofedges plotted against sentence length, where both axes use logarithmic scales.8 The
increase in the number of edges of Naiverf was higher than that of Naive. Since theparsing scheme of Naiverf mimics that of lem, the difference in parse time between
lem and Naive and the difference in the number of edges between Naiverf and Naive
confirm that the difference in the factoring scheme is the major cause of difference inthe empirical time complexity.9
At first glance, these results are inconsistent with the fact that the theoretical boundof worst time complexity for HPSG parsing is exponential, while LTAG parsing requires O(n6 ) for an input of length n. However, Carroll [CAR 94] demonstrated thattheoretical bounds of time complexity with respect to grammar size and input length
have little impact on performance for some unification-based parsing algorithms, andattributed the reason to the specification of grammars (i.e., variations in grammar rules,etc.). Sarkar et al. [SAR 00b] studied LTAG grammars extracted from the Penn Treebank and reported that the theoretical bound of computational complexity does not
significantly affect parsing performance and that the most dominant factor is syntactic
lexical ambiguity, i.e., ambiguity of lexical entries for the same words. Our results are
7. We did not compare the states of lem with the edges of Naive because an edge of Naive does
not have a one-to-one correspondence with a state of lem.
8. Naive and Naiverf in fact duplicate a part of auxiliary trees when they adjoin to different trees.
Although lem can avoid this duplication, it has no serious effect on our conclusion.
9. lem and Naive also differ in their ways of handling linguistic features. However, we supposethat their impact on parsing performance is mild compared to one by the difference in factoring.

Parsing comparison across formalisms

29

therefore convincing because factoring handles ambiguity in partial parse trees, which
is mostly caused by the syntactic lexical ambiguity.
We should note that there is other work that aims at avoiding the ambiguity causedby syntactic lexical ambiguity. Evans and Weir [EVA 98] have asserted that the compaction of substructures in elementary trees has a great impact on parsing performance. In their research, several elementary trees for each word were converted into
finite-state automata, and merged into a single finite-state automaton. Chen and VijayShanker [CHE 97] use underspecified tree descriptions to allow ambiguous node labels in elementary trees. In the conventional HPSG parser, some of this compaction
is dynamically executed by factoring. Furthermore, the factoring method enables another kind of compaction that merges equivalent edges headed by different words.
Existing methods cannot perform this kind of compaction, since these techniques areapplied separately to the elementary trees for each word. Shaumyan et al. [SHA 02]
evaluated an automaton-based parser with an LTAG grammar extracted by a method
proposed by Xia [XIA 99], and showed results similar to ours. However, the grammar
they used had far less syntactic lexical ambiguity than the XTAG English grammar.
Our results with the XTAG English grammar are a strong indication of the importanceof compaction of substructures in elementary trees.
It should be noted that the above investigation also suggests another way of factoring in LTAG. We can merge two states which have equivalent unprocessed parts,
as depicted in Figure 13, into a single state when they cover the same span of input.
This kind of factoring that merges edges with equivalent unprocessed parts has been
proposed for CFG by Leermakers [LEE 92]. In his parser, the edges in Earley parsing
are merged if their rules have a common unprocessed suffix. As exemplified by theapplication of Naive to an HPSG-style grammar converted from LTAG, this kind offactoring is applicable to LTAG parsing. Our study empirically attested to its effectiveness in LTAG parsing, not by implementing complex parsing algorithms, but by
simply applying the existing HPSG parser potentially equipped with such a functionality to the grammar converted from LTAG.

4.2. Comparison of CFG filtering techniques
Following on from the comparison of dynamic programming techniques, we
compared a pair of CFG filtering techniques for LTAG [HAR 90, POL 98] and
HPSG [TOR 00, KIE 00] described in Sections 2.3.1 and 2.3.2. We chose the filtering technique of Poller and Becker [POL 98] because it is the most sophisticatedalgorithm for CFG filtering for LTAG. Hereafter, we refer to its C++ implementation
as PB. The other filtering technique for HPSG was TNT [TOR 00]. We modified the
CF approximation of the original TNT by instantiating both daughters and restricting
the number of rule instantiations, as shown in [KIE 00], to approximate the obtained
HPSG-style grammar with CFG. In phase 1, PB and TNT performed Earley [EAR 70]
and CKY [YOU 67] parsing, respectively. Note that the CFG filtering techniques for
LTAG used the same CF approximation, as did the CFG filtering techniques for HPSG,

30

TAL. Volume 44 - n◦ 3/2003

Table 3. Size of extracted LTAGs (elementary trees) and CFGs approximated fromthem (above: the number of nonterminals; below: the number of rules)
GrammarLTAG
CFGPB
CFGTNT

G2
1,488
65
716
1,989
18,323

G2-4
2,412
66
954
3,118
35,541

G2-6
3,139
66
1,090
4,009
50,115

G2-8
3,536
66
1,158
4,468
58,356

G2-10
3,999
67
1,229
5,034
68,239

G2-21
6,085
67
1,552
7,454
118,464

G2-10
34.2
0.224

G2-21
124.3
0.542

Table 4. Parsing performance (sec.) for Section 2 of WSJ
Parser
PB
TNT

G2
1.4
0.044

G2-4
9.1
0.097

G2-6
17.4
0.144

G2-8
24.0
0.182

Table 5. Number of essential edges generated in parsing of Section 02 of WSJ
Parser
PB
TNT

G2
791
63

G2-4
1,435
121

G2-6
1,924
174

G2-8
2,192
218

G2-10
2,566
265

G2-21
3,976
536

as described in Sections 2.3.1 and 2.3.2. Comparison of PB and TNT thus suffices toinvestigate the effect of the CF approximations for LTAG and HPSG.
We acquired LTAGs by the method proposed in [MIY 03] from Sections 2-21 of
the Wall Street Journal (WSJ) in the Penn Treebank [MAR 93] and their subsets.10 We
converted them into strongly equivalent HPSG-style grammars by using the grammar
conversion described in Section 3.1. Table 3 shows the size of CFGs approximatedfrom the strongly equivalent grammars. Gx , CFGPB , and CFGTNT henceforth referto the LTAG extracted from Section x of WSJ and the CFGs approximated from Gx
by PB and TNT, respectively. CFGTNT is much larger than CFGPB . By investigating parsing performance using these CFGs as filters, we conclude that larger size of
CFGTNT caused the better parsing performance.
Table 4 shows the parse time for 254 sentences of length n (n ≤10) from Section
2 of WSJ (average sentence length: 6.72 words).11 This result shows not only that
TNT was much faster than PB, but also that the performance difference between themincreased when the larger grammars were used.
To estimate the degree of CF approximation, we measured the number of essential(inactive) edges of phase 1. Table 5 shows the number of essential edges. PB produces
10. The elementary trees in the LTAGs are binarized.
11. We used a subset of the training corpus to avoid using default lexical entries for unknown
words, because there are various ways to assign default entries for automatically extracted grammars and this would have an uncontrolled effect on parsing performance.

Parsing comparison across formalisms

31

Table 6. Success rate (%) of phase 2 operations
Operations
ok-propagation (PB)
rule-application (TNT)

G2
38.5
100

G2-4
34.3
100

G2-6
33.1
100

G2-8
32.3
100

G2-10
31.7
100

: 
 Sym
Arg :


Grammar rule

Sym : ŗArg : ŘSym : ř
Arg :

Arg :

: ȱ
 Sym
Arg :

Sym : ŗLeaf : ř
Dir : Foot? :

Sym : Arg :Grammar rule

Arg :

love:

Arg :

Leaf : 
Dir : 
Foot? :

,





Ř

Sym : Leaf : ȱDir : Foot? :







love

Sym : ŗArg : ŘSym : ŗLeaf : ř
Dir : Foot? :

 Sym :  Sym : 

G2-21
31.0
100

Ř

Sym : Leaf : ȱDir : Foot? :

Sym : řArg : ȱ
Sym : ȱ
Arg :






ȱ
ȱ

Figure 15. CF approximation of an HPSG-style grammar converted from LTAGa much greater number of essential edges than TNT. We then investigated the effectof different numbers of essential edges on phase 2. Table 6 shows the success rates of
ok-propagation and rule-application. The success rate of rule-application (for TNT) is
100%, while that of ok-propagation (for PB) is quite low.12 These results indicate that
CFGTNT is superior to CFGPB with respect to the degree of CF approximation.
We can work out the reason for this difference by investigating how the CF approximation of HPSG approximates HPSG-style grammars converted from LTAGs.
As described in Section 3.1, the grammar conversion preserves the whole structure ofeach elementary tree (precisely, a canonical elementary tree) in a stack, and grammar
rules manipulate the top element of the stack. A generated feature structure in theapproximation process thus corresponds to the whole unprocessed parts of a canonical elementary tree, as shown in Figure 15. This implies that successful context-free
derivations obtained by CFGTNT basically involve elementary trees in which all substitution and adjunction have succeeded. However, as mentioned in Section 2.3.1,
CFGPB (as well as a CFG produced by another work [HAR 90]) cannot avoid generating invalid parse trees that connect two local structures where adjunction takes place
12. This means that the extracted LTAGs should be compatible with CFG and were completely
approximated with CFGs. Preliminary experiments with the XTAG English grammar [XTA 01]
without features were 15.3(parse time (sec.))/30.6(success rate (%)) for PB and 0.606/71.2 for
TNT, for the same sentences.

32

TAL. Volume 44 - n◦ 3/2003

between them. We used G2-21 to calculate the percentage of ok-propagations that were
between two node numbers that take adjunction (the right-hand side of Figure 5) andthe success rate for this percentage. 87% of the total number of ok-propagations wereof this type but their success rate was only 22%. These results suggest that the global
constraints in a given grammar are essential to obtaining an effective CFG filter.
It should be noted that the above investigation also suggests another way of making a CF approximation for LTAG. We first define a unique mode of tree traversal,
such as head-corner traversal [NOO 94] described in Section 2.2.1, on which we cansequentially apply substitution and adjunction. We then recursively apply substitution
and adjunction on that traversal to elementary trees and generated tree structures. Because the processed parts of the generated tree structures are not used again, we regard
the unprocessed parts of the tree structures as nonterminals of a CFG. We can thereby
perform another type of CFG filtering for LTAG by combining this CFG filter with ahead-corner LTAG parsing algorithm [NOO 94] that uses the same tree traversal.

5. Conclusion
This article presented an approach for comparing parsers for different grammar
formalisms, making use of strongly equivalent grammars obtained by grammar conversion. We showed that a parsing comparison between LTAG and HPSG is possible by giving a formal proof of strong equivalence for the grammar conversion procedure [YOS 02] and using this conversion to obtain strongly equivalent grammars.
As an application of our approach, we empirically compared two pairs of LTAG and
HPSG parsers based on dynamic programming and CFG filtering. We first obtained
strongly equivalent grammars by converting the XTAG English grammar and LTAG
grammars extracted from the Penn Treebank into HPSG-style grammars. Experiments
comparing parsers using dynamic programming showed that the different implementations of the factoring scheme caused a difference in the empirical time complexityof the parsers. This result suggests that for LTAG parsing we can achieve a drastic
speed-up by merging two states whose elementary trees have the same unprocessedparts. Another experiment comparing parsers with CFG filtering showed that the CF
approximation of HPSG produced a more effective filter than that of LTAG. This result
also suggests that we can obtain an effective CFG filter for LTAG by approximating
the LTAG with a CFG by applying substitution and adjunction along tree traversal andregarding unprocessed parts of generated tree structures as nonterminals of the CFG.

Acknowledgements
The authors wish to thank Anoop Sarkar for his help in applying his parser andYousuke Sakao for his help in profiling the TNT parser. The authors are also indebted
to John Carroll and the anonymous reviewers for their valuable comments. The firstauthor was supported in part by JSPS Research Fellowships for Young Scientists.

Parsing comparison across formalisms

33

6. References[BRI 93] B RISCOE E., C ARROLL J., “Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars”, Computational Linguistics, vol. 19,
num. 1, 1993, p. 25-60.
[CAR 92] C ARPENTER B., The Logic of Typed Feature Structures, Cambridge University
Press, 1992.
[CAR 94] C ARROLL J., “Relating complexity to practical performance in parsing with widecoverage unification grammars”, Proc. of the 32nd ACL, 1994, p. 287–294.
[CHE 97] C HEN J., V IJAY-S HANKER K., “Towards a reduced-commitment D-theory style
TAG parser”, Proc. of the fifth IWPT, 1997, p. 18–29.
[CHO 63] C HOMSKY N., “Formal properties of grammar”, L UCE R. D., B USH R. R.,
G ALANTER E., Eds., Handbook of Mathematical Psychology, vol. II, p. 323–418, John
Wiley and Sons, Inc., 1963.
[EAR 70] E ARLEY J., “An efficient context-free parsing algorithm”, Communications of theACM, vol. 6, num. 8, 1970, p. 451–455.
[EVA 98] E VANS R., W EIR D., “A structure-sharing parser for lexicalized grammars”, Proc.
of COLING–ACL, 1998, p. 372–378.
[HAA 87] H AAS A. R., “Parallel parsing for unification grammars”, Proc. of the 14th IJCAI,
1987, p. 615–618.
[HAR 90] H ARBUSCH K., “An efficient parsing algorithm for Tree Adjoining Grammars”,
Proc. of the 28th ACL, 1990, p. 284–291.
[KAS 95] K ASPER R., K IEFER B., N ETTER K., V IJAY-S HANKER K., “Compilation of HPSG
to TAG”, Proc. of the 33rd ACL, 1995, p. 92–99.
[KEL 94] K ELLER B., Feature Logics, Infinitary Descriptions and Grammars, CSLI publications, 1994.
[KIE 00] K IEFER B., K RIEGER H.-U., “A context-free approximation of Head-Driven Phrase
Structure Grammar”, Proc. of the sixth IWPT, 2000, p. 135–146.
[KOR 90] KORNAI A., P ULLUM G. K., “The X-bar theory of phrase structure”, Language,
vol. 66, 1990, p. 24–50.
[LEE 92] L EERMAKERS R., “A recursive ascent Earley parser”, Information Processing Letters, vol. 41, num. 2, 1992, p. 87–91.
[MAR 93] M ARCUS M., S ANTORINI B., M ARCINKIEWICZ M. A., “Building a large annotated corpus of English: the Penn Treebank”, Computational Linguistics, vol. 19, num. 2,
1993, p. 313–330.
[MAX 93] M AXWELL III J. T., K APLAN R. M., “The interface between phrasal and functional constraints”, Computational Linguistics, vol. 19, num. 4, 1993, p. 571–590.
[MIL 99] M ILLER P. H., Strong Generative Capacity, CSLI publications, 1999.
[MIY 03] M IYAO Y., N INOMIYA T., T SUJII J., “Lexicalized grammar acquisition”, Proc. of
the 10th EACL companion volume, 2003, p. 127–130.
[NED 98] N EDERHOF M.-J., “An alternative LR algorithm for TAGs”, Proc. of COLING–
ACL, 1998, p. 946–952.
[NOO 94] VAN N OORD G., “Head corner parsing for TAG”, Computational Intelligence,
vol. 10, num. 4, 1994, p. 525-534.

34

TAL. Volume 44 - n◦ 3/2003[POL 94a] P OLLARD C., S AG I. A., Head-Driven Phrase Structure Grammar, University of
Chicago Press and CSLI Publications, 1994.
[POL 94b] P OLLER P., “Incremental parsing with LD/TLP-TAGs”, Computational Intelligence, vol. 10, num. 4, 1994, p. 549–562.
[POL 98] P OLLER P., B ECKER T., “Two-step TAG parsing revisited”, Proc. of TAG+4, 1998,
p. 143–146.
[SAR 00a] S ARKAR A., “Practical experiments in parsing using Tree Adjoining Grammars”,
Proc. of TAG+5, 2000, p. 193–198.
[SAR 00b] S ARKAR A., X IA F., J OSHI A., “Some experiments on indicators of parsing complexity for lexicalized grammars”, Proc. of the 18th COLING workshop, 2000, p. 37–42.
[SCH 88] S CHABES Y., A BEILLÉ A., J OSHI A. K., “Parsing strategies with ‘lexicalized’grammars: application to Tree Adjoining Grammars.”, Proc. of the 12th COLING, 1988,
p. 578–583.
[SCH 95] S CHABES Y., WATERS R. C., “Tree Insertion Grammar: A cubic-time parsable formalism that lexicalizes context-free grammar without changing the tree produced”, Computational Linguistics, vol. 21, num. 4, 1995, p. 479–513.
[SHA 02] S HAUMYAN O., C ARROLL J., W EIR D., “Evaluation of LTAG parsing with supertag compaction”, Proc. of TAG+6, 2002, p. 201–205.
[TOM 86] T OMITA M., Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publisher, 1986.
[TOR 95] T ORISAWA K., T SUJII J., “Compiling HPSG-style grammar to object-oriented language”, Proc. of the NLPRS, 1995, p. 320–325.
[TOR 96] T ORISAWA K., T SUJII J., “Computing phrasal-signs in HPSG prior to parsing”,
Proc. of the 16th COLING, 1996, p. 949–955.
[TOR 00] T ORISAWA K., N ISHIDA K., M IYAO Y., T SUJII J., “An HPSG parser with CFG
filtering”, Natural Language Engineering, vol. 6, num. 1, 2000, p. 63–80.
[VIJ 85] V IJAY-S HANKER K., J OSHI A. K., “Some computational properties of Tree Adjoining Grammars”, Proc. of the 23rd ACL, 1985, p. 82–93.
[VIJ 87] V IJAY-S HANKER K., “A study of Tree Adjoining Grammars”, PhD thesis, Department of Computer & Information Science, University of Pennsylvania, 1987.
[VIJ 88] V IJAY-S HANKER K., J OSHI A. K., “Feature structures based Tree Adjoining Grammars”, Proc. of the 12th COLING, 1988, p. 714–719.
[XIA 99] X IA F., “Extracting Tree Adjoining Grammars from bracketed corpora”, Proc. of
the fifth NLPRS, 1999, p. 398–403.
[XTA 01] XTAG R ESEARCH G ROUP, “A lexicalized Tree Adjoining Grammar for English”,
report num. IRCS-01-03, 2001, IRCS, University of Pennsylvania.
[YOS 99] YOSHIDA M., N INOMIYA T., T ORISAWA K., M AKINO T., T SUJII J., “Efficient
FB-LTAG Parser and its Parallelization”, Proc. of PACLING, 1999, p. 90–103.
[YOS 02] YOSHINAGA N., M IYAO Y., “Grammar conversion from LTAG to HPSG”, The
European Student Journal on Language and Speech, , 2002, available at
http://hltheses.elsnet.org/eventpapers/essliproceed.htm.
[YOU 67] YOUNGER D. H., “Recognition and parsing of context-free languages in time n3 ”,
Information and Control, vol. 2, num. 10, 1967, p. 189–208.

Parsing comparison across formalisms

35

A. Formal proof of strong equivalence for the grammar conversion from LTAG
to HPSG-style grammar
The proof comprises two parts. Part one proves that strong equivalence is guaranteed for the conversion from LTAG G to canonical LTAG G by the tree divisionand the tree substitution. Part two proves that strong equivalence is guaranteed for theconversion from canonical LTAG G to an HPSG-style grammar G .
A.1. Definitions
Definition A.1 (Lexicalized Tree Adjoining Grammar (LTAG)) A lexicalized tree
adjoining grammar G is a quintuplet (Σ, NT , S, I, A) where Σ and NT are a finite
set of terminal symbols and a finite set of nonterminal symbols, respectively, S is adistinguished nonterminal symbol called the start symbol, and I and A are a finite setof initial trees and a finite set of auxiliary trees, respectively.13
Here, an elementary tree γ ∈ A ∪ I is a tree whose leaf nodes are labeled by
X ∈ NT ∪ S or x ∈ Σ, and whose internal nodes are labeled by X ∈ NT ∪ S. The
symbol of one leaf node in an auxiliary tree β ∈ A is identical to that of its root node,and is specially marked as a foot node. Note that more than one leaf node, calledanchors, in an elementary tree γ are labeled with x ∈ Σ, and leaf nodes other thananchors and the foot node are marked as substitution nodes.
We hereafter use the notion of an address of a node in a tree. An address of a tree
is a symbol that indicates a unique node in the tree.
Next, we define a derivation for an elementary tree γ. Let us denote a tree thatis derived from an elementary tree γ by having substitution and adjunction into γ asγ  . When we produce γ  from an elementary tree γ by applying substitutions and adjunctions of several trees γ1 , γ2 , . . . , γk to γ at k distinct addresses a1 , a2 , . . . , ak , theproduction is denoted by γ  → γ[a1 , γ1 ][a2 , γ2 ] . . . [ak , γk ] where k ≥ 1, and [ai , γi ]indicates substitution at ai of γi if ai is a substitution node, or indicates adjunction
at ai of γi if ai is an internal node. This production is called a derivation for γ if
a1 , a2 , . . . , ak include all addresses of the substitution nodes in γ. A derivation forγ without substitution and adjunction is denoted as γ  → . The set of all possible
derivations DG for LTAG G = (Σ, NT , S, I, A) is then denoted as follows:
DG = {γi →  | 1 ≤ i ≤ m, γi ∈ A ∪ I, γi includes no substitution node.}∪ {γi → γi [a1 , γi1 ][a2 , γi2 ] . . . [ak , γik ] | k ≥ j ≥ 1, i > m, γi , γij ∈ A ∪ I,
a1 , a2 , . . . , ak include all addresses of the substitution nodes in γi }We use the above notations to define a derivation tree, which represents the history of
combinations of trees and is a structural description of LTAG.
13. The LTAG definition follows the definition of TAG given by Vijay-Shanker [VIJ 87]. Due
to limitations of space, we omit the notion of adjoining constraints and the proof including thenotion in this article, and then assume all internal nodes take selective adjoining constraints.

36

TAL. Volume 44 - n◦ 3/2003

Definition A.2 (derivation tree) A derivation tree for LTAG G = (Σ, NT , S, I, A),
ΥG , is formed from any subset of the set of all derivations DG by uniquely relabeling
identical elementary trees in the derivations of the subset. A derivation tree ΥG mustsatisfy the following conditions:– Because γi can be adjoined or substituted once, γi can appear once respectively
in the left-hand side and the right-hand side of derivations in ΥG except for the one
distinguished elementary tree γS , which is the root of the derivation tree ΥG . The
condition implies that trees cannot be substituted or adjoined to more than one node.
– γS can appear once in the left-hand side of the derivation.
– The inequality i > ij ≥ 1 is necessary to avoid cyclic applications of substitution and adjunction among elementary trees.
Next, we give the definition of strong equivalence between two grammars G1 andG2 . Strong equivalence is intuitively that the two grammars generate equivalent structural descriptions, which are the most informative data structures given by G; examples of structural descriptions are parse trees by CFG and derivation trees by LTAG.
The following definition follows from the one by Miller [MIL 99, p. 7].
Definition A.3 (strong equivalence) Let the set of all possible structural descriptions given by two given grammars G1 and G2 be TD (G1 ) and TD (G2 ). The two given
grammars G1 and G2 are strongly equivalent if and only if there is a bijective (i.e.,
one-to-one and onto) mapping from a structural description of G1 , ΥG1 ∈ TD (G1 ),to a structural description of G2 , ΥG2 ∈ TD (G2 ).
In what follows, we assume that structural descriptions of LTAG are derivation
trees in which the root node of γS is labeled by the start symbol S in the definition A.2.
A.2. Proof of strong equivalence for the tree division and the tree substitution
The tree substitution of Section 3.2 is exactly the same as the one that Schabes andWaters [SCH 95, pp. 494–495] defined and proved in their procedure of strong lexicalization of CFG. We briefly give a proof sketch that strong equivalence is guaranteed
for grammars before and after the tree division.
For the tree division of Section 3.2, we can readily construct a bijective mapping
between derivation trees by LTAG G and canonical LTAG G converted from G by thetree division. Assume that an elementary tree of G, γ, is converted by the tree division
into a supertree γ u and a subtree γ v , both of which are elementary trees of G . We canthen map any derivation tree by G one-to-one onto a unique derivation tree by G byreplacing every occurrence of γ u which takes a substitution of γ v in derivations withγ and vice versa. Note that γ v must accompany γ u because γ v can be substituted only
into γ u and cannot be the root of a derivation tree.

Parsing comparison across formalisms

37

A.3. Proof of strong equivalence for the conversion from canonical LTAG to an
HPSG-style grammar
We prove that strong equivalence is guaranteed for a conversion from canonical
LTAG G to an HPSG-style grammar G . We first define an HPSG parse, which is a
structural description of an HPSG-style grammar. We then prove strong equivalenceby giving a bijective mapping from a derivation tree by G to an HPSG parse by G .
Definition A.4 (HPSG-style grammar converted from LTAG) Givencanonical
LTAG G = (Σ, NT , S, I, A), an HPSG-style grammar G converted from G isdenoted by a sextuplet (Σ, NT , S, ∆I , ∆A , R) where δi ∈ ∆I and δj ∈ ∆A are
lexical entries converted from γi ∈ I and γj ∈ A, respectively, and R denotes thesubstitution and adjunction rules. δi is denoted as follows: δi = (s0 , (s1 , l1 , d1 , t1 ),. . ., (sk , lk , dk , tk )) where k ≥ 1, s0 ∈ Σ ∪ NT is the symbol of the mother node of
the anchor in γi , and sj ∈ Σ ∪ NT , lj ∈ Σ ∪ NT , dj ∈ {right, left}, tj ∈ {+, −}are values of Sym, Leaf, Dir, and Foot? features in the j-th element of the Arg featurein δi . When the length of the Arg feature of δi is 0, δi is denoted as δi = (s0 , φ).
First, we introduce the notion of origination for the Sym and Leaf features in
HPSG lexical entries in order to define an HPSG parse, which represents the histories
of rule applications to lexical entries and is a structural description of an HPSG-style
grammar. We hereafter assume that each HPSG lexical entry δi is converted from acanonical elementary tree γi . We define the origination of the feature in δi as p, γi ,which indicates that the value of the feature originates from the symbol of a node withaddress p in γi .
Next, we define a rule history for δi , which is a history of rule applications to alexical entry δi . Since the grammar rule must pop the value of the Arg feature of one
daughter, we assign each rule application to δi as an element of the sequence of rule
applications for δi if and only if the applied rule pops an element that originates froman element of the Arg feature in δi . Assume that δi is denoted as the one given in
definition A.4. When the origination of lj and sij unified with lj in the grammar rule
are aj , γi and b, γij , respectively, a sequence of rule applications for δi is denoted
as follows:
δi → δi [xi1 , yi1 ][xi2 , yi2 ] . . . [xik , yik ],where k ≥ j ≥ 1, (xij , yij ) is (ai , δij ) if tj = − or (b, δij ) if th = +. Whenxi1 , xi2 , . . . xik include b where k ≥ h ≥ 1 and th = + or aj where k ≥ j ≥ 1
and tj = − in the sequence of rule applications for δi , we call the sequence of rule
applications a rule history for δi . When the length of the Arg feature of δi is 0, a rule
history for δi is denoted by δi → .
Lemma A.1 Given an HPSG-style grammar G = (Σ, NT , S, ∆I , ∆A , R), a rule
history for δi ∈ ∆I ∪ ∆A must be the following form.
i) When the length of the Arg feature of δi is 0, δi → 

38

TAL. Volume 44 - n◦ 3/2003

ii) When the length of the Arg feature of δi is not 0 and δi ∈ ∆I , δi →δi [a1 , δi1 ][a2 , δi2 ] . . . [ak , δik ].
iii) When the length of the Arg feature of δi is not 0 and δi ∈ ∆A , δi →δi [a1 , δi1 ] . . . [ah−1 , δih−1 ][b, δih ][ah+1 , δih+1 ] . . . [ak , δik ] where th = +.
Proof
When the length of the Arg feature of δi is 0, no rule application is assigned
as a rule application for δi because it is defined according to elements in the Arg
feature. The rule history for δi is thus denoted as δi → .
When δi ∈ ∆I , the elements in the Arg feature of δi keep their order until thegrammar rules consume all the elements. This is because both substitution and adjunction rules do not change the order of the Arg feature, and also do not remove anelement of the Arg feature without unifying it with another node. The rule history forδi is thus denoted as δi → δi [a1 , δi1 ][a2 , δi2 ] . . . [ak , δik ].
When δi ∈ ∆A , the elements in the Arg feature of δi keep their order until thegrammar rules consume all the elements as in the case where δi ∈ ∆I . One differenceis that it includes exactly one element lh when th = +. The rule history for δ is thendenoted by δi → δi [a1 , δi1 ] . . . [ah−1 , δih−1 ][b, δih ][ah+1 , δih+1 ] . . . [ak , δik ] where th= +.
By using lemma A.1, we can define the set of rule histories by G = (Σ, NT , S,
∆I , ∆A , R) as follows:
DG = {δi →  | 1 ≤ i ≤ m, γi ∈ I, the length of the Arg feature of δi is 0 }∪ {δi → δi [a1 , δi1 ] . . . [ak , δik ] | m < i ≤ n, k ≥ j ≥ 1, δi , δij ∈ ∆I }∪ {δi → δi [a1 , δi1 ] . . . [ah−1 , δih−1 ][b, δih ][ah+1 , δih+1 ] . . . [ak , δik ]| n < i, k ≥ h ≥ 1, k ≥ j ≥ 1, th = +, δi ∈ ∆A , δij ∈ ∆I }We use the above notations to define an HPSG parse, 14 which represents the historyof rule applications and is a structural description of an HPSG-style grammar.
Definition A.5 (HPSG parse) Given an HPSG-style grammar G = (Σ, NT , S, ∆I ,
∆A , R) converted from G, an HPSG parse ΨG is formed from any subset of the setof all rule histories DG by renaming identical lexical entries in the rule histories ofthe subset uniquely. An HPSG parse ΨG must satisfy the following conditions:– δi where δi ∈ ∆I can appear once respectively in the left-hand side and theright-hand side of rule histories except for the one distinguished lexical entry δS whereδS appears once in the left-hand side of the rule history for δS .
– δi where δi ∈ ∆A must appear only once in the left-hand side of the rule historyfor δi .
– 1 ≤ ij < i for the rule history for δi ∈ ∆I .
14. Due to limitations of space, we omit the proof showing that an HPSG parse by G corresponds to a unique parse tree derived by G.

Parsing comparison across formalisms

39– 1 ≤ ij < i where j = h, and ih > i, for the rule history for δi ∈ ∆A .
The third and fourth conditions are necessary to avoid cyclic applications of grammar
rules to lexical entries.
Lemma A.2 Let G = (Σ, NT , S, I, A) be canonical LTAG and G = (Σ, NT , S, ∆I ,
∆A , R) be an HPSG-style grammar converted from G. Then, we can map a derivation
tree ΥG by G one-to-one onto to an HPSG parse ΨG by G .
Proof
We first show a mapping from ΨG to a set of derivations ΥG , and thenshow that ΥG is a valid derivation by G. Suppose an HPSG parse satisfying definition A.5. We can map it one-to-one onto a set of derivations ΥG with the following
procedure. For each δi where δi ∈ ∆A , we eliminate [b, δih ], which corresponds toan application of the adjunction rule, and add the element [b, δi ] to the right-hand sideof the rule history for δih . Then, we obtain a set of derivations ΥG by replacing δij
and δij with γij and γij in the rule history for δi and by regarding it as the derivationfor γi in ΥG . This mapping is one-to-one because the operation pair of eliminating[b, δih ] and adding [b, δi ] is a one-to-one mapping.
Following the definition A.2, we show that ΥG is a valid derivation tree by G.
First, every substitution and adjunction in the derivations in ΥG must be valid in
G. Since the substitution and adjunction rules preserve the order of the elements in
the Arg feature of δi , substitution rules always unify the symbol of the substitution
node with the symbol of the root node of γij . This unification represents the same
constraint as the one imposed by substitution. We can give an analogous argument foran adjunction rule. The substitution and adjunction in the derivations in ΥG are thenvalid in G. Second, all addresses in the substitution nodes of γi must be included in
the derivation for γi . This is apparently guaranteed by definition of the rule historyfor δi . Third, γi can appear only once respectively in the right-hand side and the lefthand side of the derivations. This is apparently guaranteed for γi where γi ∈ I by
definition A.5, and is guaranteed for γi where γi ∈ A because δi does not appear in
the right-hand side of rule histories, [b, δih ] appears only once in the rule history for
δi , and the elimination of [b, δih ] accompanies the addition of [b, γi ] once to the righthand side of the derivation for γih . Fourth, the elements in the right-hand side of thederivation for γi must be [aj , γij ] where ij < i. This is apparently guaranteed for γiwhere γi ∈ I by definition A.5, and is guaranteed for γi where γi ∈ A because theaddition of [b, γi ] for the derivation for γih satisfies ih > i from definition A.5.
The frontier string is preserved before and after this mapping from ΨG to ΥG ,because δi stores the same linear precedence constraints between δi and δj for i = j
as the constraints between γi and γj . Thus, an HPSG parse ΨG by G is mapped
one-to-one onto a derivation tree ΥG that is valid in G.
We can construct a mapping from ΥG onto an HPSG parse ΨG by inverting theprocedure for the above mapping from ΨG onto ΥG . The obtained ΨG is a valid
HPSG parse by G because we can give an analogous argument for the validity of therule histories in ΨG .