Incremental Tree Substitution Grammar for Parsing and Sentence Prediction

Federico Sangati, Frank Keller

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)111-124
Number of pages14
JournalTransactions of the Association for Computational Linguistics
Publication statusPublished - May 2013


Dive into the research topics of 'Incremental Tree Substitution Grammar for Parsing and Sentence Prediction'. Together they form a unique fingerprint.

Cite this