Grammar conversion from LTAG to HPSG
Naoki Yoshinaga Yusuke Miyao
Department of Information Science, Graduate School of Science
University of Tokyo
yoshinag@is.s.u-tokyo.ac.jp yusuke@is.s.u-tokyo.ac.jp
Abstract
We propose an algorithm for the conversion of grammars from an arbitrary FB-LTAG
grammar into a strongly equivalent HPSG-style grammar. Our algorithm converts LTAG
elementary trees into HPSG feature structures by encoding the tree structures in stacks. A
set of pre-determined rules manipulate the stack to emulate substitution and adjunction. We
have used our algorithm to obtain HPSG-style grammars from existing LTAG grammars. We
apply this algorithm to the XTAG English grammar and report some of our findings.

1

Introduction

Recent applications of NLP (Kay et al. 1994; Carroll et al. 1998) have taken advantage ofcomputationally and linguistically motivated approaches to the formalization of grammars, suchas the Feature-Based Lexicalized Tree Adjoining Grammar (FB-LTAG1 : Vijay-Shanker 1987;
Vijay-Shanker and Joshi 1988) and the Head-Driven Phrase Structure Grammar (HPSG: Pollard and Sag 1994). Discussion of the correspondences between the two formalisms has accompanied their development; i.e., their linguistic relationships and differences have been investigated (Abeillé 1993; Kasper 1998), as has conversion between two grammars in the twoformalisms (Kasper et al. 1995; Tateisi et al. 1998; Becker and Lopez 2000). These ongoing
efforts towards collaboration have contributed greatly to the development of the two formalisms,
and we believe that it is worth continuing in this direction.
This research is thus intended to provide a basis for further collaboration between the communities, and is built around a proposed method of conversion from LTAG to HPSG. This differsfrom previous methods of conversion in that it guarantees strong equivalence2 ; that is, the resultsof parsing (derivation trees) by an LTAG grammar can be derived from those of the obtained
1

Unless otherwise noted, we use the term LTAG to refer to FB-LTAG in this paper.
Chomsky first introduced the notion of strong equivalence between grammars, where both grammars generate
the same set of structural descriptions (e.g., parse trees: Chomsky (1963)). Kornai and Pullum (1990) and Miller(1999) used the notion of isomorphism between sets of structural descriptions to provide the notion of a strong
equivalence across grammar formalisms which we have adopted in this research.
2

1

HPSG-style grammar and vice versa. Having strongly equivalent grammars based on different formalisms is valuable for both communities from practical, computational, and theoreticalpoints of view in the following way (Becker and Lopez 2000):
Sharing of resources HPSG-based applications can make use of LTAG resources (lexicons andgrammars) such as the large-scale English (Doran et al. 2000) and French (Abeillé andCandito 2000) grammars that have been developed. Our method of conversion can reducethe considerable workload involved in developing large-scale resources from scratch. In
this paper, we report on the conversion of a large-scale LTAG grammar.
Parsing comparison Having strongly equivalent grammars allows us to compare two parsers
based on two different formalisms. Although most researchers believe that the HPSG
parsers are inefficient as compared to LTAG parsers from the viewpoint of the theoreticalbounds of worst time complexity, no results have been reported for empirical comparisonsof the respective levels of time complexity. This is because a comparison can only bemeaningful if it is based on strongly equivalent grammars, which had not been available.
Linguistic correspondence We are also able to explore the linguistic correspondences between
formalisms. Since the HPSG-style grammar obtained by our method has both the computational architecture that underlies HPSG and the linguistic specifications that were givenin the original LTAG, their difference will be made apparent by comparing the obtained
grammar with existing HPSG grammars (Kay et al. 1994; Flickinger 2000).
We used the conversion algorithm which we implemented to successfully convert the latest
version of the XTAG English grammar (The XTAG Research Group 2001), which is a large-scale
FB-LTAG grammar, into an HPSG-style grammar. Strong equivalence between the original andobtained grammars was empirically attested to by the fact that parsing with these grammars
generated equivalent results. Strong equivalence of grammars allows the fair comparison of
LTAG and HPSG parsers. As an aside, Yoshinaga et al. (2001) have reported on an efficient
HPSG parser that achieved a significantly higher speed of parsing than an existing LTAG parser.
In this paper, we investigated the types of linguistic phenomena covered by the XTAG English
grammar, and the correspondence to their analysis in the HPSG formalism.
The existing works do not have the above three advantages, which are only attainable whenstrong equivalence is preserved. Tateisi et al. (1998) have translated the same LTAG into an
HPSG. However, their method depended on a translator’s intuitive analysis of the original grammar, and the translation was thus manual and grammar dependent. The manual translation demanded considerable efforts on the part of the translator, and this obscures the existence or nonexistence of strong equivalence between the original and obtained grammars. Other work has
involved the conversion of HPSG into LTAG (Kasper et al. 1995; Becker and Lopez 2000).
However, given the greater generative power of HPSG, the conversion required that some restrictions be placed on the input HPSG to suppress its generative capacity. Moreover, Becker
and Lopez discussed that there was overgeneration and undergeneration of the LTAG grammars.
Thus the results of conversion do not have strong equivalence.
2α1anchor* foot node

adjunction

S

VP

β1

derived tree

derivation tree
α1S

substitution node

NP

VP

V

V

can

VP *

substitution

α2

NP
V

VP

We can

V

N

NP

α2

VP

β1

run
N

run

We

Figure 1: Tree Adjoining Grammar: basic structures and the compose operations used to them

2 Grammar formalisms
2.1 Feature-Based Lexicalized Tree Adjoining Grammar (FB-LTAG)
LTAG (Schabes et al. 1988), an input of our algorithm, provides syntactic analysis of a sentence
by using two operations, called substitution and adjunction, to compose elementary trees. Thisis shown on the left-hand side of Figure 1. An elementary tree has at least one leaf node that islabeled with a terminal symbol (i.e., word) called an anchor (marked with ). Elementary trees
are classified into two types, initial trees (α1 and α2) and auxiliary trees (β1). The label of one
leaf node of an auxiliary tree is identical to that of its root node and this is specially marked (here,with ∗) as a foot node. In an elementary tree, leaf nodes other than anchors and a foot node arecalled substitution nodes (marked with ↓).
The left-hand side of Figure 1 illustrates the two operations. In substitution, a leaf node(substitution node) is replaced by an initial tree, while in adjunction, an auxiliary tree with theroot node and a foot node labeled x is grafted onto a node with the same symbol x. The resultsof analysis are described not only by derived trees (i.e., parse trees) but also by derivation trees(the right-hand side of Figure 1). Derivation trees represent the history of combinations of trees
and are the upper-level structural descriptions of LTAG.
FB-LTAG (Vijay-Shanker 1987; Vijay-Shanker and Joshi 1988) is an extension of the LTAG
formalism in which each node in the elementary trees has a feature structure, which contains theset of grammatical constraints on that node.

2.2

Head-Driven Phrase Structure Grammar (HPSG)

We define an HPSG-style grammar, the form of the output of our algorithm, according to thecomputational architecture which underlies HPSG (Pollard and Sag 1994). It consists of lexical
entries and ID grammar rules, each of which is described with typed feature structures (Carpenter 1992). The greater generative power of the underlying architecture of HPSG allows us toobtain a trivial encoding of an LTAG in HPSG, as described by Keller (1994). However, such a3

ID grammar rule

ID grammar rule
Arg :

Arg :

Arg :

2

3

Arg : 1 | 2

unify
Arg :

2

Sym :
Arg :

Arg :

2
3

unify

unify

Sym :
Arg :

Arg :

NP

NP

1

unify

Sym : NPArg :Sym : VP
Arg : VP

Sym : VP
Arg : NPSym : NPArg :Sym : VP
Arg : VP

Sym : VP
Arg : NPSym : NPArg :Sym : VP
Arg : VP

Sym : VP
Arg : NP

we

can

run

we

can

run

we

can

run

Figure 2: Parsing with an HPSG grammar
conversion cannot answer our purpose because the obtained grammar is far from the one definedby Pollard and Sag (1994). Hence, we restrict the form of an HPSG-style grammar to one which
follows the HPSG formalism in its lexicalist framework in the following way. A lexical entry
for a word must express the characteristics of the word, such as its subcategorization frame andgrammatical category. An ID grammar rule must represent the constraints on the configurationof immediate constituency, and not be a construction-specific rule specified by lexical characteristics. For example, in Figure 2, the boxed numericals ‘ n ’ called tags express the sharingof common values between the two sub-feature structures. Note that Pollard and Sag (1994)
provide detailed linguistic specifications for the form of feature structures and adopt principles,such as the Head Feature Principle, to depict linguistic properties. In our definition, we assume
that such principles are encoded in ID grammar rules, and do not give further linguistic specifications. The above restrictions enable us to not only define a formal link between an LTAG and an
HPSG-style grammar, both of which are lexicalist frameworks, but also clarify the relationships
between an HPSG-style grammar and HPSG. We will address this point later, in Section 3.7.
Figure 2 illustrates an example of bottom-up parsing with an HPSG-style grammar. In the
HPSG approach, as we can see in this example, a parse tree is generated by incrementally applying ID grammar rules to lexical entries and constructing each of the branching structures one
by one. Thus, the key points in the conversion are 1) how to encode the tree structure of anelementary tree as an HPSG lexical entry, and 2) how to emulate substitution and adjunction by
ID grammar rules. Note that there is no one-to-one correspondence between an elementary tree
and an HPSG lexical entry because one elementary tree can have multiple anchors (i.e., words)
to represent compound expressions.

3 The algorithm
This section describes our conversion algorithm in detail. As noted in Section 2, the tree structures of LTAG elementary trees should be encoded in HPSG lexical entries, and substitution andadjunction should be emulated by ID grammar rules. Thus, we propose a conversion algorithm
which consists of: 1) the conversion of elementary trees into HPSG lexical entries and 2) the4

Canonical elementary tree

Non-canonical elementary treesa) Violation of Condition 1

S

Multi-anchored tree
Sb) Violation of Condition 2
Tree with non-anchored subtrees
S

VP

NP

NP

V
think

NP

VP

S*

V
look

PP
P

NP

for

VP

N V

VP

it is V

PP

ε P

S
NP

Non-anchored subtree

Figure 3: A canonical elementary tree and non-canonical elementary trees
emulation of substitution and adjunction by pre-determined ID grammar rules.
In the following description, we start by defining canonical elementary trees, which have a
one-to-one correspondence with HPSG lexical entries.3
Definition 3.1 (Canonical elementary tree) Canonical elementary trees are elementary trees
which satisfy the conditions below:
Condition 1: A tree has only one anchor.
Condition 2: Every branching structure in a tree contains trunk nodes.
Trunk nodes are nodes on a trunk which is a path from an anchor to the root node (the thicklines in Figure 3) other than the anchor (Kasper et al. 1995). Conditions 1 and 2 respectively
guarantee that a canonical elementary tree has only one trunk and that each branching consistsof a trunk node, a leaf node, and their mother which is also a trunk node, as seen in the example
on the left-hand side of Figure 3. The right-hand side of Figure 3 shows non-canonical trees. We
call a subtree of depth n(≥ 1) that includes no anchor a non-anchored subtree. Non-canonicalelementary trees are converted to canonical trees before conversion into HPSG lexical entries by
the algorithm in the next section.

3.1

Conversion of canonical elementary trees

We can directly convert canonical elementary trees to HPSG lexical entries in the way shownin Figure 4. The procedure convert tree into lexical entry in Figure 4 presents an algorithm for converting a canonical elementary tree T into an HPSG lexical entry L. In thealgorithm, arg is a stack of branchings bi as described by a quadruplet hni−1 , li , di , ti i along thetrunk. The parameter ni−1 represents the mother node of the trunk node ni . The parameters li , di3
In this paper, we discuss the conversion of elementary trees which consist of binary branching structures. A
unary branching can be regarded as a binary branching whose sibling is the empty category, and n-ary (n ≥ 3)
branchings can be converted into binary branchings. Strong equivalence before and after the conversion is guaranteed, because the conversion are according to a one-to-one (i.e., isomorphic) mapping.

5

anchorprocedure convert tree into lexical entry(T )begin
arg := []for i := 1 to depth(T )−1
ni−1 := trunk(T , i − 1)
li := leaf(T , i)di := direct(T , i)ti := type(T , i)bi := hni−1 , li , di , ti iarg := [bi ] ⊕ arg
end for
L := (ndepth(T)−1 , arg)
return L;
endS* foot node
substitution node

NP

VP
V

S*

think
Sym: VSym : VP
Sym : S
think : Arg: Leaf : S, Leaf : NP
Dir : right Dir : right
Foot?: +Foot?:

Sym: symbol of a trunk nodeLeaf: symbol of a leaf nodeDir: the direction of a leaf node

depth: returns the depth of the anchor.
trunk: returns the symbol of the trunk node.
leaf: returns the symbol of the leaf node at depth i
direct: returns the side of the trunk node
for the leaf node at depth i
type: returns the type of the leaf node at depth i

relative to the trunk
Foot?: the type of a leaf node

Figure 4: An algorithm for converting a canonical elementary tree T to an HPSG lexical entry L
Sym : 1
Arg : 2

Sym : 3Arg :substitution node

Arg :Sym : 1
Arg : 2

Sym : 1
Leaf : 3
Dir: leftFoot? :

Sym : 3
Arg : 42

foot node

trunk node

Arg :

4

Sym : 1
Leaf : 3
Dir: leftFoot? : +2

trunk node

Left adjunction rule

Left substitution ruleFigure 5: Grammar rules: the substitution rule and adjunction ruleand ti represent the leaf node at a depth i; respectively, they represent the non-terminal symbol,
the direction (the side of the trunk node ni on which the leaf node is), and the type (whether thenode is a foot node or a substitution node). We call this stack arguments of the word. Finally,
the converted lexical entry L is described by the arguments arg and the mother of the anchor,
namely, ndepth(T)−1 where depth(T) is the depth of the tree T . In the left-hand side of Figure 4,
the value of the Sym feature is the symbol ndepth(T )−1 and the value of the Arg feature contains thearguments in arg, as a stack of feature structures with the four features Sym, Leaf, Dir and Foot?,which correspond to ni−1 , li , di and ti , respectively. In the recognition process, the parser pops anelement from the Arg feature to select a node that is unifiable with that element. It follows thatthe node with an empty stack as its Arg feature corresponds to the root node of the initial tree.

3.2

Definition of grammar rules

In this section, we provide the definition of the grammar rules which emulate substitution andadjunction respectively and are thus called substitution rules and adjunction rules (in Figure 5).
6Sym : 1 S
Arg :

α1

α1
β1

NP
Sym : 2 NP
Arg :

NP

α2

S

α2

NP

NP

β1

N

NP

NP

what

Arg :

4 S
Sym : 1 S
5 Leaf : 2 NP
Dir
: leftFoot? :

…C

what

V
loves

α3

S

Sym :

Sym : 6 NP
Arg :

Sym :
Arg :

7 VP
Sym : 3 S
8 Leaf : 6 NP
Dir
: leftFoot? :

Sym : 7 VP
Leaf : 4 S
Dir: right
Foot? : +Sym : 3 S
Leaf : 6 NP
Dir
: leftFoot? :

α45

Sym : 1 S
Leaf : 2 NP
Dir
: leftFoot? :

…B

you

S
N
V

α4

S*

Sym : Vhethink: Arg :

think

NP

Sym :

N

, 8

Sym : 9 NP
Arg :

…A

Sym : Vloves:

α3

you

Arg :

4 S
Sym : 1 S
5 Leaf : 2 NP
Dir
: leftFoot? :Arg :Sym : 4 S
Leaf : 9 NP
Dir
: leftFoot? :

Sym : 1 S
: 2 NP, 5 LeafDir: leftFoot? :he

LTAG derivation

HPSG rule applications

Figure 6: LTAG derivation and HPSG rule applications for the phrase “what you think he loves”
In the figure, we give rules for the case where right-hand daughters correspond to the trunk nodes.
Of course, there are symmetric rules for the left-hand case. These rules are independent of the
input LTAG because they do not specify any given characteristics for the LTAG.
Substitution rule: The Sym feature of the node to which is applied substitution must be identical to the Leaf feature ‘ 3 ’ of the trunk node. The substitution rule percolates the tail elements‘ 2 ’ of the Arg feature of the trunk node to the mother in order to continue constructing the tree.
The value of the Arg feature of the node for substitution must be an empty stack h i, because thisnode must be unified only with the node that corresponds to the root node of the initial tree. The
value “−” or “+” of the Foot? feature explicitly determines whether the next rule to be appliedis the substitution rule or the adjunction rule.
Adjunction rule: The Sym feature of a foot node must be identical to the Leaf feature ‘ 3 ’ of
the trunk node. The value of the Arg feature of the mother node is a concatenated stack of the Arg
features, ‘ 2 ’ and ‘ 4 ’, of both of its daughters. This allows the parser to construct the tree whichcorresponds to the adjoining tree and then to continue constructing the tree which corresponds
to the adjoined tree.
Figure 6 shows examples of rule application. The thick lines indicate the adjoined tree (α1)
and the dashed lines indicate the adjoining tree (β1). The adjunction rule is applied to construct7

procedure divide tree into subtrees(MT )begin
if (number(MT ) = 0)
return {MT }else
A := select(MT )hCT, T i := divtree(MT , A)foreach T (T )SST := divide tree into subtrees(T )ST := SST ∪ ST
end foreach
ST := ST ∪ {CT }return ST ;end

S
cut off

VP

NP
V

PP

look

P

NP

for

S
NP

identifier

VP
PP look_for

V

PP look_for
look
cut-off nodes P
forNP

procedure divtree(MT , A)begin
T := φfor i := 1 to depth(MT , A)-1
if (nonleaf(arg(trunk(i))))hMT 0 , T i := cut(MT , arg(trunk(i)))
address(trunk(i), Address)
mark(Address, MT 0 , T )T = T ∪T
MT := MT 0
end ifend forCT := MT
return hCT, T i
end· · · (1)· · · (2)· · · (3)returns one of anchors (default: the left-most one).
returns the depth of the anchor.
returns the trunk node at depth i
returns the sibling node of the trunk node.
cuts off the tree at the sibling node of the trunk node andreturns a subtree whose root node is the sibling node.
nonleaf: returns true if not a leaf node.
address: returns address in the elementary tree.
mark:marks an address for each cut-off node.
select:depth:
trunk:
arg:
cut:

Figure 7: An algorithm for dividing a non-canonical elementary tree MT into a set of subtree
ST , each of which has at most one anchor.
the branching marked with ?, where “think” takes as its argument the node whose Sym feature’s
value is S . By applying the adjunction rule, the Arg feature of the mother node B becomesa concatenated stack of the Arg features of both β1, ‘ 8 ’, and α1, ‘ 5 .’ Note that when theconstruction of β1 is 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 had
been applied.

3.3

Division of multi-anchored trees

Non-canonical elementary trees are initially divided into multiple subtrees, each of which has at
most one anchor, as is shown in Figure 7. We call the cutting nodes in the divided trees cut-off
nodes. Note that a cut-off node is marked by an identifier to preserve the co-occurrence relation
among the multiple anchors.
The procedure divide tree into subtrees in Figure 7 represents an algorithm for dividing a non-canonical elementary tree MT into a set of subtrees ST . It starts by selecting one
anchor A, and the single-anchored tree CT of that anchor A, which consists of the trunk nodes
8non-anchoredsubtrees

P

P

PP
P

all candidate subtrees
for substitution

NP

,…

Ad

on

P next to

next
substitution

multi-anchored trees
PP
P

PP

NP

P
Ad

on
breaking points

next

NP
Pnext toprocedure expand tree into anchored tree(NT )begin
BR := na br(NT )MT := {NT }foreach BR (BR)S := select(BR)IT := initial(S )MMT := φforeach MT (MT )T MT := substitute(MT , S , IT )mark(S)
MMT := T MT ∩ MMT
end foreach
MT := MMT
end foreach
return MTend· · · (1)· · · (2)returns the deepest branchings, whosedaughters do not consist of an anchor.
initial:returns all candidate trees whose root node is thesame as the leaf node.
select:returns one of leaf nodes (default: the left-most one).
substitute: causes substitution to the leaf node andreturns a set of resulting multi-anchored trees.
mark:marks the substituted nodena br:,…

Figure 8: An algorithm for converting a non-anchored subtree NT to a set of multi-anchoredtrees MTand their sibling nodes, is then picked up ((1) in Figure 7). We traverse the path from the root
node to the anchor A, cut off the sibling node4 arg(trunk(i)) if it is not a leaf node, and store
the address of the elementary tree in the cut-off node as an identifier ((2) and (3) in Figure 7).
Using this algorithm, multi-anchored elementary trees which only violates Condition 1 areconverted into canonical trees, while trees with non-anchored subtrees are converted into canonical trees and non-anchored subtrees, which violate Condition 2. Non-anchored subtrees areconverted into canonical trees by the algorithm given in the next section.

3.4

Substitution in non-anchored subtrees

The non-canonical elementary trees which violate Condition 2 have non-anchored subtrees.
These non-anchored subtrees are first extracted by the algorithm in the previous section, andare then converted into multi-anchored trees by substituting a substitution node on the deepest
branching by every candidate tree for substitution. The candidate trees for the application of thisprocess are selected from among the all canonical elementary trees and the ones obtained by thealgorithm in the previous section. Substituted nodes are marked as breaking points to record
the origination of these nodes. Note that non-anchored subtrees are not selected as candidates
for substitution, because their root nodes originate from internal nodes of the elementary trees.
This guarantees that the multi-anchored trees obtained by this process will satisfy Condition 2.
4

We should mention that the path from the foot node to the root node (spine: Kasper et al. 1995) in an auxiliary
tree must not be cut because the spine represents the chain of head signs between the root node and the foot node,
which are unified with the same internal node in the other trees.

9These trees can be converted into single-anchored trees, to which we can apply the algorithm in
Section 3.1, by the algorithm in the previous section.
The procedure expand tree into anchored tree in Figure 8 represents an algorithm forconverting a non-anchored subtree NT into multi-anchored trees MT . For each branching structure that consists of substitution nodes or foot nodes, one substitution node S is selected ((1) in
Figure 8). The function substitute applies a substitution to the node S of every candidate tree
which is substitutable for S ((2) in Figure 8).

3.5Strong equivalence

In this section, we discuss how our algorithm guarantees strong equivalence between the grammar it obtains and the original grammar. In the obtained grammar, the grammar rules are applied
only to those feature structures which correspond to nodes which are substitutable for/adjoinablewith the canonical elementary trees of the original LTAG because the branchings encoded in therespective values of Arg specify the nodes to be subcategorized next. Strong equivalence also
holds for the conversion of non-canonical elementary trees. For trees that violate Condition 1, we
can distinguish the cut-off nodes from substitution nodes thanks to the identifiers, which allow
recovery of the co-occurrence relation between the divided trees. For trees that violate Condition
2, we can identify those nodes to which substitution is to be applied in a combined tree because
they are marked as breaking points, and thus consider the combined tree as two trees in the LTAG
derivation. We can thus avoid overgeneration by having the identifiers checked in the substitution
rules, and avoid undergeneration by substituting all candidate trees for substitution nodes in thealgorithm in Section 3.4.
Strong equivalence enables us to recover an LTAG derivation tree from an HPSG parse tree
by following the history of rule applications and mapping each of them to substitution or adjunction. Let us take the case of Figure 6 as an example. We start by following the trunk node when
the substitution rule was applied, or the foot node when the adjunction rule was applied. We thenreach “love,” and recognize it as the anchor of an elementary tree whose root node is identicalto that of the parse tree. We then follow the path from the anchor to the root node to recognize
α1 and combinations between α1 and other elementary trees. Since we start by finding an application of the substitution rule, we can map it to the substitution of α3 to α1 by recognizing thesibling node of the trunk node as the root node of α3 and by recursively recovering the partial
derivation from the sibling subtree. Then, the next rule is the adjunction rule (marked with ?),and we find that the node A takes adjunction. We thus remember the length of the value of the
Arg feature of the node A, and follow the trunk with handling rule applications as ones for theadjoining tree β1 until the length of the Arg feature is equal to that for the node A. This is thecase at the node C. This implies that the construction of the adjoining tree β1 is completed at thenode C. We restart the recognition of α1. After handling another application of the substitution
rule, we reach the root node S , and complete the recognition of α1 and thus the whole derivation
tree.

10

3.6 Extension to FB-LTAG
The above algorithms produce the conversion of an LTAG, and are easily extensible to handle
an FB-LTAG grammar by merely storing a feature structure for each node, together with thesymbol, in the Sym feature and Leaf feature. The grammar rules are also extended to executethe feature structure unification done in FB-LTAG.

3.7 Correspondence between an HPSG-style grammar and HPSG
The above algorithms provide a formal link between HPSG and LTAG via an HPSG-style grammar. In this section, we discuss the linguistic correspondence between an HPSG-style grammarand HPSG according to the syntactic head, which is a central notion in HPSG. In the following
discussion, we assume that the reader is familiar with HPSG (Pollard and Sag 1994).
In order to derive HPSG from an HPSG-style grammar that we have obtained, we must elaborate on the sign of the HPSG-style grammar. HPSG provides a modular specification of linguistic
generalization by using principles and rule schemata in the context of the lexicalist framework.5
On the other hand, our HPSG-style grammar implicitly captures some of the principles and
ID schemata of the definition in Section 2.2 in the following way. The Immediate DominancePrinciple is satisfied by the use of the ID grammar rules. In the ID grammar rules, the Subcategorization Principle is expressed by the structure-sharing of the Sym and Leaf features whichcorrespond to the HEAD feature in HPSG. We should notice that a non-empty value for the
Arg feature of the foot node in the adjunction rules roughly corresponds to the SLASH featurein HPSG, which supports the Nonlocal Feature Principle. The Arg feature thus corresponds
to concatenation of the SUBCAT and SLASH features of HPSG. Other principles, such as the
Head Feature Principle, are implicitly encoded in the original FB-LTAG. We will extract suchprinciples in the LTAG context and subdivide the ID grammar rules into HPSG rule schemata by
analyzing feature percolation (Tateisi et al. 1998). We should mention the following two issues
in order to elaborate an HPSG-style grammar.
The distinction between predicative and modifier auxiliary trees We should mention that
auxiliary trees in LTAG are of a predicative or a modifier type (Kroch 1989; Schabes and Shieber
1994). The former introduces a predicate that subcategorizes for a phrase of the category of its
foot node, while the latter introduces a modifying, dislocated phrase, or a complement. Thisdistinction is, in rough terms, made by determining which daughter is the head, a foot nodeor a trunk node. Tateisi et al. (1998) distinguished these trees by manually analyzing feature
percolation in auxiliary trees and by assigning HPSG rule schemata separately to each auxiliary
tree. In this paper, we consider that all trunk nodes are heads, that is, treat all auxiliary trees aspredicative trees, but we can manually or semi-automatically determine the above categories by
providing some linguistic cues or by analyzing feature percolation.
5Note that HPSG-specific linguistic theories such as binding theory must be implemented in the obtained HPSGstyle grammar by defining additional features or special mechanisms.

11

Table 1: The classification of elementary trees in the XTAG English grammar (LTAG) and lexical
entries converted from (HPSG): A: canonical elementary trees, B: trees that are non-canonicalonly because they violate Condition 1, C: violate Condition 2, D: trees that violate both conditions
Grammar

A

B

C

LTAG
HPSG

326
326

764
1,992

54
1,083

D

Total

50 1,1942,474 5,875

Head selection How we should implement the function select in Figure 7 that selects the anchor A is not entirely clear. Since most multi-anchored trees represent compound expressions oridioms, such as “in front of ” and “kick the bucket,” this problem can be replaced with the problemof which word of a phrase is the syntactic/semantic head. We must also consider a similar issue
to do with how we should implement the function select in Figure 8 that selects the leaf node
S to be substituted. Since elementary trees with non-anchored subtrees represent constructions
that require a specification beyond immediate dominance, such as it-clefts and equative be, thisproblem may be rephrased as one of finding which leaf node takes the dominant syntactic roleand should be substituted in carrying out HPSG analysis. We currently simply select an anchor
or a substitution node from the left-most node, though we can solve these problems by using
linguistic ideas such as projection.

4 Experiments
We applied the algorithm to the latest version of the XTAG English grammar (The XTAG Research Group 2001),6 a large-scale FB-LTAG grammar for English. We successfully converted
all elementary trees7 in the XTAG English grammar to HPSG lexical entries. Table 1 shows theclassification of the elementary trees of the XTAG English grammar according to the conditions
we introduced in Section 3. The table also shows the number of corresponding HPSG lexical
entries.
In the experiment with the parsing of 457 sentences from the ATIS corpus8 (Marcus et al.
1994: the average length is 6.32 words), we acquired exactly the same number of derivation
trees by using the original and obtained grammars. This result is empirical attestation of thestrong equivalence of our algorithm. We had thus made the XTAG English grammar available
6

We used the grammar attached to the latest distribution of the LTAG parser which we used in the parsing
experiment. This parser is available at: ftp://ftp.cis.upenn.edu/pub/xtag/lem/lem-0.13.0.i686.tgz
7Elementary trees should in fact be denoted as elementary tree templates. That is, elementary tree templates are
abstracted from lexicalized trees, which defines one syntactic lexicon.
8
We eliminated 59 sentences because of a time-out of the parsers, and 61 sentences because the LTAG parser
sometimes does not produce correct derivation trees because of bugs in its preprocessor.

12

Table 2: The classification of the non-canonical elementary trees in Table 1: multi-anchoredtrees (corresponding to B) (left), and trees with non-anchored subtrees (corresponding to C ∪ D)
(right)Construction
Compound expressions
Verb with PP
IdiomsOthersTotal# of trees

Construction# of trees

414
194
140
16
764

Verb with PP
It-cleft
Others
Total

85
12
7
104

to the HPSG community by converting the grammar to HPSG-style. In the experimental result,
we see that the efficient HPSG parser (Torisawa et al. 2000) achieved a speed in parsing thatwas higher by a factor of 25.5 than the LTAG parser (Sarkar 2000). We further investigated
the reason for this speed-up in an earlier work (Yoshinaga et al. 2001) where we obtained thefollowing results. Contrary to expectations from the viewpoint of the theoretical bound of worst
time complexity, we showed that the empirical time complexity of the HPSG parser is lower thanthat of the LTAG parser. By inspecting the differences between the algorithms of both parsers,
we finally concluded that suppressing the ambiguity of partial parse trees by the operation calledfactoring is the most important factor in achieving high performance in parsing, and that existing
HPSG parsers are more beneficial than LTAG parsers in this respect.9
The left-hand side of Table 2 shows how multi-anchored elementary trees are used in the
XTAG English grammar. The table shows that they are mainly used for compound expressions
or idioms. Although such expressions seem to be difficult to explain in terms of the HPSG
formalism, the obtained grammar is able to handle them when they are divided into multiple
lexical entries. Another case of multi-anchored trees is the multi-anchor PP complement verb,
whose prepositional node is anchored. Such a case is shown in the center of Figure 3. The
obtained grammar expresses this construction by cut-off nodes to require specified subtrees. In
linguistic specifications in terms of HPSG, on the other hand, such a constraint is expressedby having a PFORM feature, which takes values that represent the type of the corresponding
prepositional phrase. This analysis seems to be consistent with the obtained grammar, that is, the
LTAG analysis.
9

The compaction of substructures in elementary trees has been asserted to have a great impact on performancein parsing (Evans and Weir 1998; Lopez 2000). In this research, several elementary trees for each word wereconverted into finite-state automata, and merged into a single finite-state automaton. In the HPSG parsers, someof this compaction is dynamically executed by factoring. Furthermore, the factoring method enables another kindof compaction which merges the equivalent edges headed by different words. Automaton-based compaction isincapable of performing this kind of compaction, since their techniques are basically closed in elementary trees foreach word.

13

The right-hand side of Table 2 shows the usages represented by elementary trees with nonanchored subtrees. These elementary trees express constructions requiring specifications beyond
immediate dominance. As we can see in Table 1, these trees are expanded to include quite a large
number of lexical entries. This result leads us to expect that these constructions might be difficult
to handle in the HPSG formalism. The major case of such constructions is the PP complement
verb, which has the expanded PP structure (see it-cleft in the right-hand side of Figure 3). This
construction allows the extraction of the object of the preposition, and expresses the verb taking
the object of the preposition as its argument rather than taking the whole PP. In the HPSG
formalism, on the other hand, this NP extraction is explained by using the SLASH feature, andthe predicate-argument relation between the verb and the object of the preposition is expressedby linking the argument in the predicative-argument structure (the CONTENT feature) with theobject of the preposition. This construction is hence explained differently in LTAG and HPSG.
Further case is the it-cleft. It is not clear how to handle this in the HPSG formalism, which might
be a subject worth discussing.

5 Conclusion
We have proposed a method for grammar conversion from an FB-LTAG grammar into an HPSGstyle grammar. Strong equivalence between the original and converted grammars is guaranteed;hence, we can obtain the parsing results of an LTAG grammar from the parsing results of the
HPSG-style grammar obtained by conversion. Our method thus enables the sharing of LTAG
resources with the HPSG community, the application of HPSG parsing techniques to LTAG
grammars, and the clarification of the differences between linguistic analysis according to thetwo grammar formalisms. We implemented this algorithm and obtained the following results.
(1) We used our grammar conversion algorithm to successfully convert the latest version of the
XTAG English grammar; that is, we made the XTAG English grammar available to the HPSG
community. (2) We used the strong equivalence of the grammars to perform the first ever faircomparison of the performance of each of the approaches in parsing, and showed the relative efficiency of an HPSG parser. (3) By analyzing the obtained HPSG-style grammar, we observed thedifference between the two formalisms. We are going to formally prove the strong equivalence
between the two grammars. This will be possible because of the formulation of the conversion
algorithms.
Acknowledgment The authors wish to thank Anoop Sarkar for his help in applying his parser
as part of our experiments. The authors are also indebted to the two anonymous reviewers fortheir valuable comments on and criticisms of this paper. Special thanks to Kristina Striegnitz forher good work since the Sixth ESSLLI Student Session.

14

References
Abeillé, A. (1993). Les nouvelles syntaxes: grammaires d’unification et analyse du français.
Armanda Colin. in French.
Abeillé, A. and M.-H. Candito (2000). FTAG: A Lexicalized Tree Adjoining Grammar for
French. In A. Abeillé and O. Rambow (Eds.), Tree Adjoining Grammars: Formal, Computational and Linguistic Aspects, pp. 305–329. CSLI publications.
Becker, T. and P. Lopez (2000). Adapting HPSG-to-TAG compilation to wide-coverage grammars. In Proc. of TAG+5, pp. 47–54.
Carpenter, B. (1992). The Logic of Typed Feature Structures. Cambridge University Press.
Carroll, J., N. Nicolov, O. Shaumyan, M. Smets, and D. Weir (1998). The LEXSYS project.
In Proc. of TAG+4, pp. 29–33.
Chomsky, N. (1963). Formal properties of grammar. In R. D. Luce, R. R. Bush, and
E. Galanter (Eds.), Handbook of Mathematical Psychology, Volume II, pp. 323–418. John
Wiley and Sons, Inc.
Doran, C., B. A. Hockey, A. Sarkar, B. Srinivas, and F. Xia (2000). Evolution of the XTAG
system. In A. Abeillé and O. Rambow (Eds.), Tree Adjoining Grammars: Formal, Computational and Linguistic Aspects, pp. 371–403. CSLI publications.
Evans, R. and D. Weir (1998). A structure-sharing parser for lexicalized grammars. In Proc.
of COLING–ACL ’98, pp. 372–378.
Flickinger, D. (2000). On building a more efficient grammar by exploiting types. Natural
Language Engineering 6(1), 15–28.
Kasper, R. (1998). TAG and HPSG. Talk given in the tutorial session at TAG+ 4.
Kasper, R., B. Kiefer, K. Netter, and K. Vijay-Shanker (1995). Compilation of HPSG to TAG.
In Proc. of ACL ’95, pp. 92–99.
Kay, M., J. Gawron, and P. Norvig (1994). Verbmobil: A Translation System for Face-to-Face
Dialog. CSLI Publications.
Keller, B. (1994). Feature Logics, Infinitary Descriptions and Grammar. CSLI publications.
Kornai, A. and G. K. Pullum (1990). The X-bar theory of phrase structure. Language 66,
24–50.
Kroch, A. (1989). Asymmetries in long-distance extraction in a Tree-Adjoining Grammar. In
M. Baltin and A. Kroch (Eds.), Alternative Conceptions of Phrase Structure, pp. 66–98.
University of Chicago Press.
Lopez, P. (2000). Extended partial parsing for lexicalized tree grammars. In Proc. of IWPT
2000, pp. 159–170.

15

Marcus, M. P., B. Santorini, and M. A. Marcinkiewicz (1994). Building a large annotatedcorpus of English: the Penn Treebank. Computational Linguistics 19(2), 313–330.
Miller, P. (1999). Strong Generative Capacity: The Semantics of Linguistic Formalism. CSLI
Publications.
Pollard, C. and I. A. Sag (1994). Head-Driven Phrase Structure Grammar. University of
Chicago Press and CSLI Publications.
Sarkar, A. (2000). Practical experiments in parsing using Tree Adjoining Grammars. In Proc.
of TAG+5, pp. 193–198.
Schabes, Y., A. Abeillé, and A. K. Joshi (1988). Parsing strategies with ‘lexicalized’ grammars: Application to Tree Adjoining Grammars. In Proc. of COLING ’92, pp. 578–583.
Schabes, Y. and S. M. Shieber (1994). An alternative conception of tree-adjoining derivation.
Computational Linguistics 20(1), 91–124.
Tateisi, Y., K. Torisawa, Y. Miyao, and J. Tsujii (1998). Translating the XTAG English grammar to HPSG. In Proc. of TAG+4, pp. 172–175.
The XTAG Research Group (2001). A Lexicalized Tree Adjoining Grammar for English.
http://www.cis.upenn.edu/˜xtag/.
Torisawa, K., K. Nishida, Y. Miyao, and J. Tsujii (2000). An HPSG parser with CFG filtering.
Natural Language Engineering 6(1), 63–80.
Vijay-Shanker, K. (1987). A Study of Tree Adjoining Grammars. Ph.D. dissertation, Department of Computer & Information Science, University of Pennsylvania.
Vijay-Shanker, K. and A. K. Joshi (1988). Feature structures based Tree Adjoining Grammars.
In Proc. of COLING ’92, pp. 714–719.
Yoshinaga, N., Y. Miyao, K. Torisawa, and J. Tsujii (2001). Efficient LTAG parsing using
HPSG parsers. In Proc. of PACLING 2001, pp. 342–351.

16