Tree Grafting

Once a particular set of lexicalized trees for the sentence have been selected, XTAG uses an Earley-style predictive left-to-right parsing algorithm for LTAGs ([#!schabesjoshi88!#,#!schabes90!#]) to find all derivations for the sentence. The derivation trees and the associated derived trees can be viewed using the X-interface (see Table 3.1). The X-interface can also be used to save particular derivations to disk. The output of the parser for the sentence I had a map yesterday is illustrated in Figure 3.2. The parse tree^3.3 represents the surface constituent structure, while the derivation tree represents the derivation history of the parse. The nodes of the derivation tree are the tree names anchored by the lexical items^3.4. The composition operation is indicated by the nature of the arcs: a dashed line is used for substitution and a bold line for adjunction. The number beside each tree name is the address of the node at which the operation took place. The derivation tree can also be interpreted as a dependency graph with unlabeled arcs between words of the sentence.

  

Figure 3.2: Output Structures from the Parser

Parse Tree	Derivation Tree

 

Table 3.3: XTAG tagset

Part of Speech	Description
A	Adjective
Ad	Adverb
Comp	Complementizer
D	Determiner
G	Genitive Noun
I	Interjection
N	Noun
P	Preposition
PL	Particle
Punct	Punctuation
V	Verb