Abstract
Incremental Tree Substitution Grammar for Parsing and Word Prediction
In this talk I will be presenting the first incremental parser for Tree Substitution Grammars (TSGs). A TSG allows arbitrarily large syntactic fragments to be combined into complete trees; I will show how constraints (including lexicalization) can be imposed on the shape of the TSG fragments to enable incremental processing. I will then illustrate an efficient Earley-based algorithm for incremental TSG parsing which obtains competitive results when compared with other incremental parsers. In addition to whole-sentence F-score, the parser is also evaluated on the partial trees that it constructs for sentence prefixes; partial trees play an important role in incremental interpretation, language modeling, and psycholinguistics. Unlike existing parsers, the incremental TSG parser can generate partial trees that include predictions about the upcoming words in a sentence. I will compare these predictions with the ones obtained from a standard n-gram model.