Incremental Tree Substitution Grammar for Parsing and Sentence Prediction

In this paper, we present the first incremental
parser for Tree Substitution Grammar (TSG).
A TSG allows arbitrarily large syntactic fragments
to be combined into complete trees;
we show how constraints (including lexicalization)
can be imposed on the shape of the
TSG fragments to enable incremental processing.
We propose an efficient Earley-based algorithm
for incremental TSG parsing and report
an F-score competitive with other incremental
parsers. In addition to whole-sentence
F-score, we also evaluate the partial trees that
the parser constructs for sentence prefixes;
partial trees play an important role in incremental
interpretation, language modeling, and
psycholinguistics. Unlike existing parsers, our
incremental TSG parser can generate partial
trees that include predictions about the upcoming
words in a sentence. We show that
it outperforms an n-gram model in predicting
more than one upcoming word.