Typing as a means for validating feature structures 

Anoop Sarkar (University of Pennsylvania) 
Shuly Wintner (University of Pennsylvania) 

The XTAG grammar development system makes limited use of feature
structures which can be attached to nodes in the trees that make up a
grammar. The system allows the user to define path equations that are
interpreted as specifying feature structures. Feature structure
specifications can refer to lexical items, tree families or specific
trees, and are declared in three different formats and three different
files. This organization leaves room for several kinds of errors,
inconsistencies and typos in feature structure manipulation: undefined
features can be referenced, paths can be assigned undefined values,
incompatible features can be equated, etc.

We present a method for validating the consistency of feature
structure specifications by imposing a type discipline. A typed system
facilitates a great number of compile-time checks: many possible
errors can be detected before the grammar is used for parsing. We have
constructed a type signature for an existing broad-coverage grammar of
English, and implemented a type inference algorithm that operates on
the feature structure specifications in the grammar. The algorithm
reports occurrences of incompatibility with the type signature. We
have detected a large number of errors in the grammar; four types of
errors will be discussed.

While the method we suggest was tested on an XTAG grammar, it is in
principle applicable to any linguistic formalism that uses untyped
feature structures (in particular, LFG). Additional advantages are
possible in the future: typed feature structures provide means for
better linguistic generalizations to be made, and usually lead to more
efficient processing.