🪜 Parsing

About 16 minutes to read · every paper named here has its own page in this library

What it is

A sentence has a shape that the string of words does not show. In "The cat chased a mouse", a reader sees at once that "the cat" forms a unit, that the cat does the chasing, and that "a mouse" is what is chased. Parsing makes this hidden shape explicit. A parser takes a sentence and returns a structure that says how its words combine. It is one of the oldest problems in natural language processing and computational linguistics. The word is shared with compilers, which parse program text against the grammar of a programming language.

Two representations of syntax dominate. A constituency, or phrase-structure, tree groups words into nested phrases with category labels such as noun phrase (NP) and verb phrase (VP), in the way a context-free grammar licenses them. A dependency tree links each word to the one word it modifies, called its head, and labels each link with a grammatical relation. Building such trees is dependency parsing. For the example sentence:

Constituency:   (S (NP (DT The) (NN cat))
                   (VP (VBD chased)
                       (NP (DT a) (NN mouse))))

Dependency:     ROOT   → chased
                chased → cat    (nsubj)
                cat    → The    (det)
                chased → mouse  (obj)
                mouse  → a      (det)

In the constituency tree, DT, NN and VBD are tags of the kind assigned in part-of-speech tagging, and S, NP and VP are phrase labels. In the dependency analysis, each line is an arc from a head to its dependent. The labels mark the subject (nsubj), the object (obj) and the determiners (det), and "chased" hangs from an artificial ROOT. Here the two analyses carry nearly the same information. One makes phrases explicit; the other makes word-to-word relations explicit.

The central difficulty is ambiguity. A wide-coverage grammar can license a large number of analyses even for a short sentence, so a practical parser has to rank candidates rather than merely list them (Collins 2003). Parses matter because applications need predicate–argument structure: who did what to whom (Collins 1997). In semantic role labeling, for instance, full syntactic parses help most at the stage that prunes argument candidates (Punyakanok et al. 2008). The term has also widened. Semantic parsing maps sentences to executable meaning, and "parsing" now also names the recovery of discourse, argument and table structure.

How it works

Dynamic programming over a chart

The classic algorithm for a context-free grammar in Chomsky normal form, where every rule rewrites a nonterminal either as two nonterminals or as a single word, is CKY. It is named after Cocke, Kasami and Younger (1960s). It fills a triangular chart from short spans to long ones. For a probabilistic context-free grammar (PCFG), the Viterbi version is:

β(i, i+1, A) = P(A → wᵢ₊₁)
β(i, j, A)   = max over rules A → B C and split points i < k < j of
               P(A → B C) · β(i, k, B) · β(k, j, C)

β(i, j, A) is the probability of the best subtree of category A that covers words i+1 through j. A, B and C are nonterminals, k is the point where the span splits into two children, P(A → B C) is a rule probability, and wᵢ₊₁ is a word of the sentence. Back-pointers stored with each cell recover the best tree. Replacing max with a sum gives the inside probability, which training by expectation–maximisation (EM) needs. The run time grows with the cube of sentence length times the grammar size.

Chart parsing generalises this idea. The chart stores partial constituents, so no sub-analysis is built twice. Earley's algorithm (Earley, 1970) works left to right with "dotted" rules through three operations: predict, scan and complete. It handles any context-free grammar without binarisation. Its probabilistic form yields prefix probabilities. Hale used Stolcke's probabilistic Earley parser to compute surprisal, the log-ratio of successive prefix probabilities, as a measure of word-by-word processing load. He showed that it predicts garden-path effects in reduced relatives and the extra difficulty of object relatives (Hale 2001). This made parsing a tool of psycholinguistics.

Transition-based (shift-reduce) parsing

A transition-based parser does not search the space of trees. It reads the sentence once, keeps a stack of partly processed words and a buffer of unread words, and applies one action at a time. Nivre's deterministic algorithm, the arc-eager system, uses four actions (Left-Arc, Right-Arc, Reduce, Shift). It runs in time linear in sentence length and always produces a projective, acyclic graph (Nivre 2003). MaltParser turned this into a parser generator. It offers arc-eager and arc-standard variants, and a trained classifier picks the next action from features of the current state (Nivre et al. 2006). The arc-standard system has no Reduce action. With an artificial ROOT kept at the bottom of the stack, it builds the example tree in ten steps, two per word:

LEFT-ARC makes the top of the stack the head of the word beneath it and pops the dependent. RIGHT-ARC does the opposite. Greedy decisions are fast, but an early mistake cannot be undone. Two fixes have been studied. Non-monotonic systems let the parser repair earlier attachments (Honnibal & Johnson 2015). Beam search with globally normalised training scores whole action sequences rather than single steps (Andor et al. 2016).

Graph-based parsing

Graph-based parsers score every possible head–dependent arc and then search for the best tree as a whole:

s(y) = Σ over arcs (h, m) in y of  w · f(h, m, x)
ŷ    = argmax over trees y of sentence x of  s(y)

Here x is the sentence, y a candidate tree, (h, m) an arc from head h to modifier m, f a feature vector describing that arc, and w the learned weights. Because the score splits into a sum over arcs, the best tree is a maximum spanning tree (MST) of the directed graph over the words. Eisner gave an O(n³) dynamic programme for projective trees, where n is sentence length (Eisner 1996). McDonald, Crammer and Pereira trained arc weights on top of it with the online large-margin method MIRA (Margin Infused Relaxed Algorithm) (McDonald et al. 2005). McDonald, Pereira, Ribarov and Hajič then showed that non-projective trees, whose arcs cross, can be found exactly with the Chu–Liu–Edmonds algorithm in O(n²) (McDonald et al. 2005). Richer scores break this exactness. With second-order features, projective parsing stays cubic, but non-projective parsing becomes NP-hard and needs approximate search (McDonald & Pereira 2006).

History

Early broad-coverage systems relied on hand-written grammars. Statistics entered through shallow analysis. Church's 1988 tagger chose tag sequences by dynamic programming over trigram statistics from the tagged Brown Corpus, and it also bracketed simple noun phrases (Church 1988). The turning point was the Penn Treebank. It covers over 4.5 million words of American English. All of it is tagged for part of speech and more than half is bracketed for syntax. It soon became the standard training and test material for English (Marcus et al. 1993).

Learned parsers followed. Magerman's SPATTER learned every parsing choice with decision trees and outperformed a long-developed grammar-based IBM parser (Magerman 1995). Collins' head-driven generative models (Collins 1997) and Charniak's maximum-entropy-inspired parser (Charniak 2000) defined the lexicalised era. Klein and Manning then narrowed the gap with unlexicalised grammars (Klein & Manning 2003), and Petrov and colleagues automated their annotation (Petrov et al. 2006). Discriminative rerankers (Collins & Koo 2005; Charniak & Johnson 2005) and self-training on unlabelled news (McClosky et al. 2006) pushed treebank accuracy further.

Dependency parsing grew alongside. After Eisner's algorithm (Eisner 1996) came Nivre's linear-time parser (Nivre 2003) and McDonald's spanning-tree parsers (McDonald et al. 2005). The CoNLL-X shared task of 2006 and its 2007 successor gave dependency parsers common multilingual benchmarks (Buchholz & Marsi 2006; Nivre et al. 2007). A harmonised cross-lingual annotation followed in 2013 (McDonald et al. 2013) and grew into Universal Dependencies.

The neural turn began when Chen and Manning replaced sparse feature templates with dense embeddings in a small feed-forward network (Chen & Manning 2014). Recurrent encoders (Dyer et al. 2015; Kiperwasser & Goldberg 2016), biaffine scoring (Dozat & Manning 2016) and self-attention (Kitaev & Klein 2018) came next. Semantic parsing, meanwhile, scaled training from question–answer pairs alone, with logical forms left latent, to a large knowledge base, Freebase (Berant et al. 2013).

Methods

Probabilistic and lexicalised grammars

A plain PCFG read off a treebank parses poorly, because its independence assumptions ignore which words fill a phrase. Collins lexicalised each nonterminal with a head word and tag and generated trees top-down, outward from each head. Model 1 conditions modifiers on a distance measure. Model 2 adds complements and subcategorisation frames. Model 3 adds traces of wh-movement (Collins 1997). The journal version reported 88.3% precision and 88.0% recall for Models 2 and 3 on Wall Street Journal (WSJ) section 23, counting sentences of up to 100 words (Collins 2003). Charniak's parser predicts each constituent's head tag, then its head word, then its expansion. It conditions these probabilities through products of ratios borrowed from log-linear modelling, and it cut errors by 13% relative to Collins (Charniak 2000).

Unlexicalised and latent-annotation grammars

Klein and Manning attributed much of the benefit of lexicalisation to structural context. Parent annotation, head-outward markovisation and hand-picked splits, such as separating finite from non-finite VPs, lifted an unsmoothed treebank grammar to about 86.3 F1 on short sentences (Klein & Manning 2003). Petrov, Barrett, Thibaux and Klein learned such splits automatically. Each symbol is split in two, the subsymbols are trained with EM over the known trees, and splits that add little likelihood are merged back. The resulting grammar of 1043 symbols outperformed fully lexicalised parsers, and its subcategories remained readable to linguists (Petrov et al. 2006). These grammars were slow, so Petrov and Klein pruned with the coarser grammars of earlier splitting rounds. Parsing ran up to 100 times faster with no loss of accuracy, and the method carried over to German and Chinese without tuning (Petrov & Klein 2007).

Discriminative training, reranking and semi-supervision

Generative models limit which features can be used. A reranker escapes this limit by rescoring a parser's n-best list with arbitrary global features (Collins & Koo 2005). Charniak and Johnson paired coarse-to-fine n-best parsing with a maximum-entropy reranker (Charniak & Johnson 2005). Collins and Roark trained an incremental parser with the perceptron (Collins & Roark 2004). Self-training was long thought useless for parsers. McClosky, Charniak and Johnson made it work by retraining the first-stage parser on reranker-selected parses of unlabelled news (McClosky et al. 2006). For dependencies, Brown word clusters learned from raw text roughly halved the annotated data needed to reach a given accuracy (Koo et al. 2008). Bohnet showed that most of the run time of a feature-rich graph-based parser went to looking up feature weights. Hashing features straight to weight positions made his parser both faster and more accurate (Bohnet 2010).

Lexicalised grammar formalisms

Richer formalisms put most of the grammar in the lexicon. In Lexicalised Tree-Adjoining Grammar, each word selects an elementary tree, or supertag. Choosing supertags by statistical tagging leaves an "almost parse" that a light step completes, and disambiguation accuracy rose from 68% to 92% (Bangalore & Joshi 1999). Clark and Curran combined Combinatory Categorial Grammar (CCG) with log-linear models to build a wide-coverage and efficient statistical parser (Clark & Curran 2007).

Neural parsers

Chen and Manning embedded the words, tags and arc labels found at selected stack and buffer positions. A single hidden layer with a cube activation, g(x) = x³, captures products of three inputs, and a softmax then chooses the next transition. The parser was more accurate than sparse-feature greedy baselines and processed over 1000 sentences per second (Chen & Manning 2014). Dyer and colleagues introduced the stack LSTM. It is a long short-term memory (LSTM) network that supports push and pop while keeping a vector summary of the whole stack. With it, the parser could encode its full state, including the buffer and the history of actions (Dyer et al. 2015).

Kiperwasser and Goldberg showed that a few bidirectional LSTM (BiLSTM) vectors per decision can replace large feature sets in both transition-based and graph-based parsers. They trained the encoder jointly with a structured loss (Kiperwasser & Goldberg 2016). Dozat and Manning added biaffine attention:

s(h, d) = r_hᵀ U r_d + r_hᵀ u

r_h and r_d are the outputs of two small feed-forward layers that view a BiLSTM state as a potential head and as a potential dependent. U is a weight matrix, and u is a weight vector. The first term scores how well a particular head–dependent pair fits. The second scores how readily word h takes dependents at all. A second biaffine classifier assigns labels, and an MST decoder guarantees a well-formed tree (Dozat & Manning 2016).

For constituency, Kitaev and Klein replaced the LSTM encoder of a chart-based span parser with self-attention adapted from the Transformer. They found that keeping content and position in separate channels raised accuracy (Kitaev & Klein 2018). The biaffine scorer has itself been reused outside syntax. It treats nested named entity recognition as scoring start–end token pairs (Yu et al. 2020).

Semantic parsing

A semantic parser maps an utterance to a logical form or query whose execution gives an answer. Berant and colleagues trained a Freebase parser from question–answer pairs and treated the logical forms as latent. A lexicon aligned from web text and a "bridging" operation connected phrases to predicates (Berant et al. 2013). Berant and Liang later recast the task as paraphrasing. Candidate logical forms are turned into canonical sentences, and a paraphrase model picks the closest one (Berant & Liang 2014). Yih and colleagues built query graphs in stages. They start from a topic entity and then add a relation chain, constraints and aggregation, so that the knowledge graph prunes the search early (Yih et al. 2015).

Pasupat and Liang moved to Wikipedia tables never seen in training (Pasupat & Liang 2015). Artzi and Zettlemoyer learned a weighted CCG parser for navigation instructions, using only the success of executing them as supervision (Artzi & Zettlemoyer 2013). Text-to-SQL work, the branch that reaches into code and programming, centres on unseen database schemas. RAT-SQL encodes schema relations and links between question words and columns inside relation-aware self-attention (Wang et al. 2020).

Parsing in the age of language models

Pretrained encoders have changed the input representations of parsers, while the decoding algorithms survive. In the strongest systems, CKY, MST and transition decoders are fed contextual vectors from a language model. ELMo (Embeddings from Language Models) inputs lifted the self-attentive constituency parser in this way (Kitaev & Klein 2018), and BERT (Bidirectional Encoder Representations from Transformers) lifted RAT-SQL (Wang et al. 2020). Some tasks drop explicit structure entirely. TaPas answers table questions by selecting cells and an aggregation operator with a BERT-style encoder, with no logical form at all (Herzig et al. 2020). Pipelines such as UDPipe, meanwhile, made tokenisation, tagging, lemmatisation and dependency parsing a trainable commodity for dozens of languages (Straka & Straková 2017). Structure prediction above the sentence follows the same pattern. Examples are discourse trees built from syntactic cues (Soricut & Marcu 2003) and argument structure in essays, recovered with joint integer linear programming (ILP) inference (Stab & Gurevych 2017). This work connects parsing to discourse analysis.

Datasets and benchmarks

Evaluation measures

Constituency parsers are scored with the PARSEVAL bracket measures (Black et al., 1991): precision, recall and F1. These are usually computed with the EVALB tool, as in the latent-annotation experiments (Petrov et al. 2006). Dependency parsers are scored by the attachment measures UAS and LAS:

P   = correct labelled brackets / brackets in the parser's tree
R   = correct labelled brackets / brackets in the gold tree
F1  = 2 · P · R / (P + R)
UAS = tokens with the correct head / scored tokens
LAS = tokens with the correct head and relation label / scored tokens

A bracket is a constituent identified by its label and the span of words it covers. It counts as correct when the gold tree has the same bracket. P is precision, R recall, and F1 their harmonic mean. UAS and LAS are the unlabelled and labelled attachment scores. Conventions differ, and the differences matter. CoNLL-X made LAS its official metric and left punctuation out (Buchholz & Marsi 2006). CoNLL 2007 counted every token, punctuation included (Nivre et al. 2007). Constituency results are often reported separately for sentences of at most 40 words and for longer limits (Charniak 2000). Semantic parsers are scored by denotation accuracy, F1 over answers, or exact match of the produced query.

Treebanks and shared tasks

The WSJ part of the Penn Treebank anchors English parsing (Marcus et al. 1993). Its usual split trains on sections 2–21 and tests on section 23 (Klein & Manning 2003). Some representative results on that test set follow. Their conditions differ, so they are not strictly comparable.

The same trees, converted to Stanford dependencies, serve as the main English dependency benchmark:

The Prague Dependency Treebank is the classic test of non-projective parsing. On Czech, the spanning-tree parser beat its projective counterpart, with the largest gains on sentences that contain crossing arcs (McDonald et al. 2005).

Shared tasks built the multilingual landscape. In CoNLL-X, 19 groups parsed 13 languages, and scores ranged from 37.8% LAS on Turkish to 91.7% on Japanese (Buchholz & Marsi 2006). CoNLL 2007 covered ten languages and a domain adaptation track (Nivre et al. 2007). CoNLL 2008 joined syntactic dependencies with PropBank and NomBank roles (Surdeanu et al. 2008). The CoNLL 2017 task parsed raw text with Universal Dependencies annotation. Systems trained on 64 treebanks in 45 languages and were evaluated on 81 test sets, some of them for surprise languages with almost no training data. The winning system came from Stanford (Zeman et al. 2017). Shared tasks like these are the main reference points for evaluation and benchmarks in parsing, alongside the treebanks behind them.

Semantic parsing benchmarks

Free917 and WebQuestions test parsing over Freebase (Berant et al. 2013). WikiTableQuestions contains 22,033 questions over 2,108 Wikipedia tables (Pasupat & Liang 2015). Spider pairs 10,181 questions with 5,693 SQL queries over 200 databases. When it appeared, the best model reached only 9.7% exact match on the split whose test databases are unseen (Yu et al. 2018). Two years later, RAT-SQL reached 65.6% on the Spider test set with BERT (Wang et al. 2020).

People and institutions

Joakim Nivre, now at Uppsala University and RISE Research Institutes of Sweden, wrote the linear-time deterministic dependency parser (Nivre 2003) and co-built MaltParser (Nivre et al. 2006). He also co-organised the CoNLL shared tasks (Nivre et al. 2007) and helped found universal dependency annotation (McDonald et al. 2013). Christopher D. Manning of Stanford University co-authored unlexicalised PCFG parsing (Klein & Manning 2003), an influential early neural dependency parser (Chen & Manning 2014) and biaffine parsing (Dozat & Manning 2016). Dan Klein, of the University of California, Berkeley, worked on latent-annotation grammars (Petrov et al. 2006; Petrov & Klein 2007) and self-attentive parsing (Kitaev & Klein 2018).

Michael Collins defined head-driven lexicalised parsing (Collins 1997) and discriminative reranking (Collins & Koo 2005). Eugene Charniak and Mark Johnson built the Brown reranking parser and showed that self-training works (Charniak & Johnson 2005; McClosky et al. 2006). Johnson also co-designed a non-monotonic transition system (Honnibal & Johnson 2015). Ryan McDonald introduced spanning-tree dependency parsing (McDonald et al. 2005; McDonald & Pereira 2006).

Yoav Goldberg, at Bar-Ilan University and the Allen Institute for Artificial Intelligence, co-authored BiLSTM feature parsing (Kiperwasser & Goldberg 2016). Noah A. Smith, also at the Allen Institute for Artificial Intelligence, co-developed the stack-LSTM parser (Dyer et al. 2015). Luke Zettlemoyer, at the University of Washington and Meta, led work on CCG semantic parsing from weak supervision (Artzi & Zettlemoyer 2013). Daniel Zeman of Charles University organised the raw-text UD shared task (Zeman et al. 2017). His co-organisers include Nizar Habash, now at New York University Abu Dhabi. Stephen Clark developed wide-coverage CCG parsing (Clark & Curran 2007). At Google, researchers built SyntaxNet (Andor et al. 2016) and TaPas (Herzig et al. 2020).

Open questions

Is explicit syntax still needed? Pretrained encoders raise parser accuracy (Kitaev & Klein 2018), and end-to-end models can answer structured questions without producing any structure (Herzig et al. 2020). It remains unsettled when an explicit tree helps a downstream system and when it only adds a source of errors. Some studies have asked where syntax pays off, such as the analysis of where full parses help in role labelling (Punyakanok et al. 2008). Such studies have not yet been repeated systematically for current models. A related question is what attention-based parsers actually rely on. Kitaev and Klein found that their encoder leaned mostly on word position rather than word content (Kitaev & Klein 2018), which links parsing to interpretability.

Robustness beyond newswire is the second gap. In CoNLL 2007, the best LAS on chemical abstracts was 81.06, against 89.01 for the same team on in-domain English (Nivre et al. 2007). In 2017, the top LAS reached only about 29 on Kazakh and about 32 on Buryat, languages with almost no training data (Zeman et al. 2017). Cross-lingual transfer from harmonised treebanks helps (McDonald et al. 2013). Even so, parsing low-resource languages and languages with rich morphology is still far from English accuracy.

Third, exact search remains a constraint. Non-projective parsing with rich features is intractable to do exactly (McDonald & Pereira 2006). Global normalisation narrowed the trade-off between local greedy decisions and global search (Andor et al. 2016), but it has not disappeared.

For semantic parsing, generalising to unseen schemas remains hard (Yu et al. 2018). Exact-match metrics also misjudge queries that are equivalent but written differently (Wang et al. 2020). Finally, surprisal-based parsing once served as a model of human comprehension (Hale 2001). It is open whether parsers can do so again, now that the strongest systems no longer compute explicit prefix probabilities over a grammar.

The library in figures