We will describe an Earley-type parser for Tree Adjoining Grammars (TAGs). Although a CKYtype parser for TAGs has been developed earlier (Vijay-Shanker and :Icshi, 1985), this is the first practical parser for TAGs because as is well known for CFGs, the average behavior of Earley-type parsers is superior to that of CKY-type parsers. The core of the algorithm is described. Then we discuss modifications of the parsing algorithm that can parse extensions of TAGs such as constraints on adjunction, substitution, and feature structures for TAGs. We show how with the use of substitution in TAGs the system is able.
