Constituency and Dependency Parsing › Limitations and Impact

Each method has a scope. Unpruned compact CNF Viterbi CKY is exact for its model and uses cubic sentence-length time and quadratic chart memory for a fixed grammar. Pruning can change exactness, and explicitly storing every tree can require much more memory. A bare PCFG's structural rule probabilities do not directly condition on lexical heads. Greedy arc-standard decisions are irreversible and can affect later configurations; beam search retains alternatives, while SWAP extensions have a different worst-case action count. Unrestricted graph decoding permits nonprojective trees, but arc-factored objectives omit explicit sibling and grandparent factors. Neural representations change the scores and features; decoder restrictions, domain shift, tokenization and annotation compatibility still matter.

The choice of formalism also has consequences. The continuous constituency trees used here group contiguous spans. Ordinary head-percolation conversion from such a tree yields projective dependencies; representing nonprojective analyses requires a different treatment, such as discontinuous constituents or an enriched representation. This is a restriction of the representation and conversion, not a claim that every constituency formalism is continuous. Dependency treebanks can directly annotate crossing arcs, but annotation conventions still matter: a parser trained with one label set or tokenization scheme may not transfer cleanly to another, even within one language.

Syntactic structure has been used in information and relation extraction, semantic role labeling, coreference resolution, machine translation, question answering, and knowledge graph construction. Whether a parse helps a particular system is an empirical question; a parser's errors can also propagate downstream. Pretrained parsers such as those in spaCy, Stanza, and SuPar let you obtain dependency analyses without training a parser from scratch. Throughput depends on the encoder, implementation, hardware and batching, so the decoder's asymptotic bound alone is not a capacity estimate. The next chapter takes up structured prediction and evaluation, including how to compare predicted trees with an annotation target.

Generating a parse string with an LLM does not remove the representation and evaluation requirements. Invalid or unfaithful trees have been observed in LLM constituency-parsing studies. Public test material can also create a contamination risk when pretraining data are unavailable for inspection; that risk is not proof that a particular model saw a particular treebank. Report the model and prompt, preserve the input units, and distinguish well-formedness from gold-annotation accuracy. A dedicated constrained decoder provides specified structural guarantees, while the quality of either approach still requires evaluation.