Constituency and Dependency Parsing

In "the man saw the dog with a telescope", who had the telescope? Attach the final phrase to "saw", and the man used it to see the dog. Attach it to "dog", and the dog had it. The words alone permit both readings. Parsing turns a flat sequence of tokens into a syntactic structure; the algorithms in this chapter search the possible structures and choose an analysis under a scoring model. The previous chapters introduced the tokens and annotations that these algorithms take as input.

This chapter uses two representations of syntax:

• Constituency parsing groups words into nested phrases such as noun phrases, verb phrases, and sentences.
• Dependency parsing links each word to a syntactic head and labels the relation, such as subject, object, or modifier.

Constituency structure represents phrase boundaries and nested clauses. Dependency structure represents word-to-word relations, including relations used in information extraction. Choosing between them depends on the annotation scheme and the task. For the prediction problem studied here, a parser combines a scoring model with a decoder that searches the candidate trees.

The candidate set can grow rapidly with sentence length. Under a scoring model, choosing between the telescope readings means ranking the available analyses. The ranking depends on the grammar, lexical preferences, context and annotation scheme. Scalable decoders seek a best or approximately best tree without enumerating the full candidate set. We will also use explicit enumeration to check tiny examples.

This chapter covers four families of parsing methods:

• Chart parsing, which uses dynamic programming over spans.
• Transition-based parsing, which treats parsing as a sequence of actions.
• Arc-factored graph-based parsing, which scores possible arcs and finds a highest-scoring permitted tree with a spanning-tree decoder.
• Neural parsing, which learns structural scores or a conditional model for generating an encoded tree.

These families overlap. Neural chart, transition and graph parsers supply learned scores to their respective search procedures. A sequence-to-sequence parser instead generates an encoding of the analysis through successive output decisions. Separating the scoring assumptions from the inference procedure helps identify the source of a parsing error.

For each method, ask what it scores, how it searches, which structures it permits, and what the search costs. These questions separate exact from approximate search and expose the conditions behind linear or cubic decoding bounds.