Constituency and Dependency Parsing › Summary

Parsing predicts syntactic structure over supplied input units. Constituency parsing builds nested phrase trees; dependency parsing builds labeled head-dependent trees. The candidate families counted here rapidly outgrow enumeration, although a restricted grammar can admit few analyses and a general cyclic grammar can admit infinitely many finite derivations of one sentence.

Unpruned Viterbi CKY is exact for its specified CNF PCFG and has cubic sentence-length time for a fixed grammar. Earley handles general CFGs with grammar-dependent bounds. Ordinary greedy arc-standard decoding builds projective trees in (2n) actions and is linear under fixed-cost scoring and operations, excluding encoding; SWAP extensions can require quadratically many actions. Chu-Liu/Edmonds exactly solves nonprojective arc-factored arborescence decoding, with an adaptation needed for our single-ROOT-child convention. Eisner-style decoding exactly optimizes the projective arc-factored family with matching ROOT constraints. Neural encoders and scorers supply learned representations and scores to these inference procedures, or generate encoded trees with a sequence model.

The central trade-offs are exact versus approximate search, projective versus non-projective structure, local versus global decisions, and speed versus accuracy. The best choice depends on the annotation scheme, the language, the latency budget, and the downstream task. In the next chapter we will connect these decoders to structured prediction and to the evaluation metrics used to compare their outputs with gold annotations.