Syntax and Parsing

Introduction and Context

Natural language is not merely a sequence of words. Words combine into phrases, clauses, and larger constructions, and the way they combine determines meaning. In The analyst reviewed the report, for example, the analyst functions as a noun phrase and the report as an object noun phrase. A syntactic parser attempts to recover such structure from a sentence.

Syntax is important because many NLP applications require more than lexical recognition. Information extraction uses syntactic relations to identify who did what to whom; question answering uses clause structure to align questions with answers; machine translation uses syntactic correspondences; speech and writing assistants use syntax for grammatical analysis; and semantic role labeling uses predicates and their arguments. Parsing is therefore a central interface between surface language and meaning.

This chapter develops two complementary views of syntax: constituency grammar, which represents nested phrases, and dependency grammar, which represents relations between individual words. It then examines context-free grammars, probabilistic parsing, classical algorithms, transition-based and graph-based dependency parsing, neural parsers, evaluation, and practical limitations.

Learning Objectives

By the end of this chapter, a learner should be able to:

1. Explain the distinction between constituency and dependency representations.
2. Construct and interpret context-free grammar rules and parse trees.
3. Describe ambiguity and compare strategies for resolving it.
4. Apply the CKY dynamic-programming algorithm under its standard assumptions.
5. Explain probabilistic context-free grammars and the Viterbi parsing objective.
6. Compare transition-based, graph-based, and neural dependency parsers.
7. Evaluate parses using constituent and dependency metrics.
8. Design a syntactic parsing solution while recognizing domain, data, and ethical limitations.

1. What a Parser Represents

A parser maps a tokenized sentence to one or more structural analyses. Let a sentence be a sequence of tokens w₁, w₂, ..., w_n. A constituency parse is a labeled tree whose leaves are tokens and whose internal nodes are phrases such as NP (noun phrase) and VP (verb phrase). A dependency parse is usually a directed tree in which each word, except the root, has a head and a labeled relation such as nsubj (nominal subject), obj (object), or amod (adjectival modifier).

Consider the sentence “Researchers tested the model.” A constituency analysis is:

[S
  [NP Researchers]
  [VP [V tested] [NP the model]]]

A dependency analysis identifies tested as the root, Researchers as its nominal subject, and model as its object; the modifies model as a determiner. The two representations emphasize different information. Constituency captures hierarchical grouping and phrase boundaries. Dependency structure captures predicate–argument relations and is often compact for languages with relatively free word order.

A parser must also cope with linguistic ambiguity. In “I saw the person with a telescope,” the prepositional phrase may modify saw—the instrument used—or person—the person carrying the telescope. Both analyses may be structurally possible. A grammar generates candidates; a statistical or neural model ranks them using contextual evidence.

2. Constituency Grammar

2.1 Phrase-structure concepts

Constituency grammar assumes that sentences are organized into constituents: contiguous groups of words that behave as units. Common categories include:

Constituents can be diagnosed through substitution, movement, coordination, and question-answer behavior, although no single diagnostic is perfect. In “The experienced team won,” the experienced team can be replaced by they, suggesting that it forms an NP. Constituency is hierarchical: an NP may contain an adjective phrase, and a VP may contain an NP and a PP.

2.2 Context-free grammars

A context-free grammar (CFG) is defined by the tuple G = (N, Σ, P, S), where N is a finite set of nonterminal symbols, Σ is a finite set of terminals, P is a set of productions, and S is the start symbol. A production has a single nonterminal on its left-hand side, such as NP → Det N.

A small grammar might contain:

S  → NP VP
NP → Det N
NP → Name
VP → V NP
VP → V
Det → the | a
N  → analyst | report
V  → reviewed | arrived
Name → Maya

A derivation for “the analyst reviewed a report” is:

S ⇒ NP VP
  ⇒ Det N VP
  ⇒ the analyst VP
  ⇒ the analyst V NP
  ⇒ the analyst reviewed Det N
  ⇒ the analyst reviewed a report

The grammar is context-free because expanding a nonterminal does not depend on neighboring symbols. This assumption supports efficient algorithms, but natural language contains phenomena that are difficult to model with a simple CFG, including long-distance agreement, cross-serial dependencies, discourse context, and lexical idiosyncrasy. CFGs nevertheless provide a useful abstraction and a foundation for more expressive formalisms.

2.3 Normal forms and binarization

The CKY algorithm is commonly presented for grammars in Chomsky Normal Form (CNF), in which binary rules have the form A → B C and lexical rules have the form A → a. A rule such as VP → V NP PP can be binarized, for example as VP → VP* PP and VP* → V NP. Binarization changes the internal representation but preserves the language when handled carefully. Unary rules and empty productions require additional treatment or preprocessing.

CNF is an algorithmic convenience, not a claim that natural language literally has only binary branching. Grammar engineering must preserve labels and recover the intended tree after parsing.

3. Dependency Grammar

Dependency grammar represents syntax as relations between lexical heads and dependents. In “The analyst reviewed the report,” the verb reviewed is the root. analyst depends on it as nsubj, report as obj, and the depends on report as det.

A dependency tree normally satisfies these conditions:

• There is one designated root.
• Every other token has one syntactic head.
• The structure is connected and acyclic.

Dependency trees are often constrained to be projective: the words dominated by a node form a contiguous span. A crossing dependency violates projectivity. Natural languages such as Czech, Dutch, German, and Japanese exhibit non-projective patterns, so practical parsers may permit non-projective trees.

Dependency labels express grammatical functions rather than phrase categories. Universal Dependencies, for example, uses labels such as nsubj, obj, iobj, obl, amod, advmod, conj, and mark. Annotation schemes differ, so models trained under one scheme should not be assumed to be directly compatible with another.

Constituency and dependency compared

Neither representation is universally superior. Constituency is natural for theories that emphasize phrases; dependency is convenient for semantic interfaces and multilingual processing. Conversion between representations is possible but not always lossless because annotation schemes encode different decisions.

4. Ambiguity and Grammar-Based Analysis

A grammar is ambiguous if a sentence has more than one parse tree. “I saw the man with a telescope” illustrates attachment ambiguity. “Old men and women” may have different adjective scopes. Lexical ambiguity occurs when a word has multiple categories or subcategorization frames; flies can be a noun or a verb.

A parser should distinguish syntactic ambiguity from uncertainty caused by incomplete or noisy input. In real applications, the best analysis may not be certain. A system can retain a packed forest—a compact representation of many trees—or return an n-best list rather than a single parse.

Grammar rules alone cannot generally select the intended interpretation. Lexicalized grammars associate preferences with particular heads, while probabilistic grammars assign weights to alternatives. Contextual neural models add information from the entire sentence and, when available, surrounding discourse.

5. Probabilistic Context-Free Grammars

A probabilistic context-free grammar (PCFG) attaches a probability to each production. For every nonterminal A, the alternatives expanding A must satisfy:

Here P(α | A) is the probability of production A → α, and the sum is over all productions with left-hand side A. The PCFG independence assumption is that the probability of a derivation is the product of the probabilities of its rule applications:

where T is a parse tree and r ranges over its production applications. For a sentence w_1:n, the Viterbi parser seeks:

Under a grammar that generates the observed words, this is commonly implemented as maximizing P(T) among trees yielding the sentence. If comparing analyses of the same sentence, maximizing the joint probability and the conditional probability P(T | w_1:n) are equivalent because the sentence probability is constant across candidate trees. A PCFG’s independence assumptions are strong: rule probabilities conditioned only on the parent category cannot represent all lexical and structural preferences. Lexicalized and neural scoring models relax this limitation.

6. Dynamic-Programming Parsing

6.1 The CKY algorithm

CKY (also called CYK) exploits the fact that a binary constituent spanning positions i through j can be split at a position k. For a CNF grammar, a chart entry records whether or how nonterminal [[MATH[A]] spans tokens [[MATH[w_i, ..., w_{j-1}]]]. The recurrence is:

For recognition rather than probabilistic parsing, the multiplication and maximization are replaced by logical existence. Here C[A,i,j] is the best score for category A over the span, k is a split point, and the rule probability is included only for a PCFG. The usual indexing treats a sentence of length [[MATH[n]]] as positions from 0 to [[MATH[n]]].

The algorithm first fills length-one cells using lexical rules, then progressively larger spans. Backpointers store the best split and child categories so that the tree can be reconstructed. With a fixed grammar in binary form, CKY requires [[MATH[O(n^3 |P|)]] time in a straightforward implementation and [[MATH[O(n^2 |N|)]] chart space, where [[MATH[n]]]] is sentence length, [[MATH[|P|]]]] is the number of productions, and [[MATH[|N|]]]] is the number of nonterminals. Grammar indexing and sparse charts can reduce practical cost. The cubic time bound follows from considering span starts, span ends, and split points; it is not a universal bound for every parsing formalism.

6.2 Worked example

Suppose the grammar contains:

S  → NP VP
NP → Det N
VP → V NP
Det → the
N → analyst | report
V → reviewed

For “the analyst reviewed the report,” lexical entries populate spans for the, analyst, reviewed, the, and report. The first the and analyst combine to form NP; the second the and report form another NP. The verb and object NP form VP. Finally, the subject NP and VP form S. The chart avoids rebuilding the object NP when considering larger constituents: once a subproblem is solved, its result is reused. This reuse is the central advantage of dynamic programming.

6.3 Other classical algorithms

Earley parsing handles arbitrary CFGs and can process left-recursive grammars; its worst-case complexity is cubic, although it can be faster for many grammars and inputs. Left-corner parsing combines properties of top-down and bottom-up strategies. Shift-reduce parsing constructs a tree incrementally using actions such as SHIFT, REDUCE, and ACCEPT. Chart parsers are attractive for exhaustive ambiguity management, whereas deterministic shift-reduce parsers can be faster and easier to deploy.

7. Dependency Parsing Algorithms

7.1 Transition-based parsing

A transition-based parser maintains a configuration consisting of a stack, a buffer of unread tokens, and a set of dependency arcs. In an arc-standard system, common actions include:

• SHIFT: move the next buffer token to the stack.
• LEFT-ARC(label): create an arc from the top stack item to the next item and remove the dependent.
• RIGHT-ARC(label): create an arc from the next stack item to the top item and remove the dependent.

Exact arc direction and preconditions depend on the chosen transition system. A classifier or neural policy selects the next legal action. The method is efficient—often close to linear in sentence length for one action per token-dependent operation—but early errors may propagate because an incorrect action changes later configurations. Beam search can retain several partial analyses and reduce, though not eliminate, this problem.

7.2 Graph-based parsing

A graph-based parser scores possible arcs or larger structures and searches for the highest-scoring well-formed tree. A first-order model commonly assigns a score to each head–dependent pair. For a candidate tree [[MATH[T]]]:

Here [[MATH[h]]] is a head, [[MATH[m]]] a dependent, [[MATH[ℓ]]] a dependency label, and [[MATH[s(h,m,ℓ)]]]] the learned local score. The maximum spanning tree algorithm can find the best non-projective unlabeled or labeled tree under suitable scoring assumptions. Projective graph parsing can use dynamic programming. Higher-order models score sibling, grandparent, or other configurations but generally increase computational cost.

Transition-based methods make local sequential decisions; graph-based methods optimize a global tree objective. Neural systems often combine both ideas or use reranking to obtain the advantages of each.

8. Neural and Modern Parsers

Neural parsers replace manually designed feature templates with learned representations. A typical pipeline uses a pretrained Transformer encoder to produce contextual token vectors. Separate scoring layers may predict constituent spans, dependency arcs, labels, or parsing actions.

For dependency parsing, an encoder produces representations [[MATH[h]]] and [[MATH[m]]] for candidate head and dependent tokens. A biaffine scorer can estimate an arc score in the general form:

Here [[MATH[h]]] and [[MATH[m]]] are learned vectors, [[MATH[U]]] is a learned bilinear parameter matrix, [[MATH[W]]] is a learned linear parameter matrix, [[MATH[h;m]]] denotes concatenation, and [[MATH[b]]] is a bias. Implementations may use separate parameters for labels and arcs. The equation describes a scoring function, not a probability; probabilities require a normalization or an appropriate training objective.

Common architectures include:

• BiLSTM and feed-forward parsers: contextual sequence encoders with span or arc classifiers.
• Biaffine graph parsers: independently score heads, dependents, and labels, then decode a tree.
• Transition-based neural parsers: predict actions from representations of the current configuration.
• Span-based constituency parsers: score candidate labeled spans and decode a compatible tree.
• Transformer-based parsers: exploit pretrained multilingual or domain-adapted representations.

Training normally uses gold treebanks. A supervised objective may be negative log-likelihood:

where [[MATH[x_i]]] is an input sentence, [[MATH[y_i]]] its gold parse, [[MATH[θ]]] model parameters, [[MATH[N]]] the number of training examples, [[MATH[R(θ)]]] a regularization term, and [[MATH[λ ≥ 0]]] its weight. The exact factorization of [[MATH[P_θ]]]] depends on whether the model predicts actions, arcs, labels, spans, or complete trees. Regularization, dropout, early stopping, and validation data help control overfitting.

Pretraining improves performance when the target domain resembles training data, but it does not remove the need for annotation-aware evaluation. Domain adaptation may involve continued pretraining, supervised fine-tuning on in-domain treebanks, parameter-efficient adaptation, or self-training with confidence filtering.

9. Evaluation and Error Analysis

Constituency parsing is commonly evaluated with labeled precision, labeled recall, and labeled F1 over predicted constituents, usually excluding trivial sentence-level brackets. If [[MATH[P]]] is the set of predicted labeled constituents and [[MATH[G]]] the gold set:

The formulas assume that predicted and gold constituents use the same tokenization and label scheme. Dependency parsing often reports unlabeled attachment score (UAS), the proportion of tokens whose predicted head is correct, and labeled attachment score (LAS), the proportion whose head and dependency label are both correct. Punctuation treatment, multiword tokens, empty nodes, and enhanced dependencies must be specified because they affect comparability.

Exact sentence match is stringent but informative: it is the proportion of sentences for which the entire predicted structure is correct. Error analysis should separate tokenization errors, part-of-speech errors, attachment errors, label errors, coordination, long-distance dependencies, rare constructions, and out-of-domain language. Aggregate scores can conceal systematic weaknesses affecting particular communities or genres.

10. Applied Case: Parsing for Contract-Clause Information Extraction

The following is an illustrative case, not a report of a particular organization.

Background

A legal-technology team wants to extract obligations from procurement contracts. The target fields are the obligated party, action, object, deadline, and conditional trigger. A clause such as “The supplier shall deliver the equipment within thirty days after acceptance” requires identification of supplier as the subject, deliver as the action, equipment as the object, and the temporal phrase as a deadline.

Problem

A keyword system retrieves supplier, deliver, and thirty days but cannot reliably determine whether the supplier or the buyer is responsible. Legal clauses contain long noun phrases, passive constructions, coordination, enumerations, defined terms, and unusual punctuation. General news-trained parsers may also encounter vocabulary and syntax absent from their treebank.

Analysis and approach

The team first defines an annotation scheme and creates a representative, access-controlled sample of contracts. It normalizes document layout without destroying section boundaries, performs domain-aware tokenization, and fine-tunes a pretrained dependency parser on manually reviewed examples. Constituency parses are retained for identifying clause and phrase spans, while dependencies provide subject, object, modifier, and auxiliary relations.

The extraction system combines parser output with a rule-and-model layer. For active clauses it searches for nominal subjects and objects attached to a deontic predicate such as shall deliver. For passive clauses it uses passive-subject and agent relations, while preserving uncertainty when an agent is omitted. A confidence threshold routes difficult clauses to human review. Evaluation uses document-level splits rather than random sentence splits so that nearly identical clauses do not appear in both training and test data.

Outcome

The principal benefit is not merely a higher parsing score. The structured representation makes extraction errors diagnosable: a missed agent, an incorrect attachment of a deadline, and a coordination error can be distinguished. Reviewers can inspect the source sentence and the dependency arcs before accepting a generated obligation. The system is deployed as decision support, not as an autonomous legal authority.

Learning points

1. Parsing quality must be measured on the target genre.
2. Annotation decisions determine what “correct” means.
3. Constituency and dependency outputs can be complementary.
4. Confidence estimates and human escalation are important in high-impact settings.
5. Data governance is part of system design, not an afterthought.

11. Challenges, Limitations, and Responsible Use

Linguistic limitations

Treebanks encode one annotation policy and cannot represent every theoretical analysis. Spoken language includes repairs, fragments, overlaps, and prosodic cues missing from ordinary text. Social-media text contains abbreviations, code-switching, emojis, and nonstandard orthography. Morphologically rich and low-resource languages may require segmentation and multilingual modeling strategies. Free word order and non-projective dependencies challenge algorithms designed for projective structures.

Statistical and neural limitations

Parser confidence can be poorly calibrated, especially under domain shift. Neural models may exploit superficial correlations, inherit biases from pretraining data, and fail on rare constructions. A high average LAS does not guarantee reliable extraction of legally, medically, or financially important relations. Long sentences, nested coordination, and implicit arguments remain frequent sources of error.

Governance and ethics

Parsing may expose confidential contracts, medical notes, or private communications. Organizations should minimize data collection, control access, encrypt stored annotations, document retention, and assess whether data may legally be used for training. Annotators need clear guidelines, fair compensation, and procedures for handling sensitive content. Systems used in consequential decisions should provide traceable evidence, communicate uncertainty, permit human correction, and undergo subgroup and domain audits. A parser should support professional judgment rather than disguise an uncertain inference as fact.

12. Best Practices and Contemporary Directions

A robust parsing project begins with a clearly specified representation and annotation standard. It should establish tokenization policy, treatment of punctuation and multiword expressions, label inventory, train–development–test separation, and domain coverage. Baselines using a deterministic or pretrained parser are valuable before adding complexity. Evaluation should report both aggregate metrics and targeted challenge sets.

Practical recommendations include:

• Inspect parses qualitatively; scores alone do not reveal systematic errors.
• Use domain-adaptive training and test on temporally and stylistically realistic data.
• Preserve n-best analyses or confidence values when downstream decisions are sensitive.
• Use constrained decoding when the application requires valid trees or known terminology.
• Compare constituency and dependency outputs against the needs of the downstream task.
• Version data, annotation guidelines, models, and evaluation scripts.
• Record computational cost, latency, memory, and licensing constraints.

Current research explores multilingual and cross-lingual parsing, efficient adaptation of large language models, structured prediction with differentiable or constrained decoding, retrieval of domain examples, and joint modeling of syntax with semantics, discourse, and information extraction. Large language models can produce plausible trees, but plausibility is not equivalent to structural validity or calibrated correctness. Hybrid systems that combine pretrained representations, explicit structural constraints, specialized treebanks, and human evaluation remain important.

Chapter Summary

Syntax describes how words combine into meaningful structures. Constituency grammar represents recursive phrases, while dependency grammar represents head–dependent relations. Context-free grammars formalize phrase generation and enable dynamic-programming methods such as CKY under binary-grammar assumptions. Probabilistic CFGs rank alternative trees, although their independence assumptions are limited. Dependency parsing can be transition-based, making local actions, or graph-based, optimizing a global tree; neural encoders and biaffine or span-based scorers now support both families. Evaluation requires carefully defined constituent or dependency metrics and consistent annotation policies. In professional NLP, parser selection must account for domain shift, ambiguity, computational cost, privacy, fairness, uncertainty, and human oversight. The most useful parser is not simply the one with the highest benchmark score, but the one whose representation and errors are appropriate for the downstream task.

Key Terms

Constituent: A group of words functioning as a syntactic unit.

Constituency grammar: A grammar that represents sentences as hierarchically nested phrases.

Dependency grammar: A grammar that represents relations between lexical heads and dependents.

Context-free grammar (CFG): A grammar whose productions have one nonterminal on the left-hand side.

Nonterminal: A grammar symbol representing a syntactic category such as NP or VP.

Terminal: A symbol corresponding to an observed word or token.

Ambiguity: The existence of multiple valid structural analyses for an input.

Chomsky Normal Form: A binary CFG form using rules such as A → B C and A → a.

CKY algorithm: A dynamic-programming parser for suitably binarized CFGs.

Probabilistic CFG: A CFG whose productions have conditional probabilities.

Viterbi parse: The highest-scoring parse under a specified model.

Projectivity: The property that a dependency subtree occupies a contiguous word span.

Transition-based parser: A parser that builds structure through actions on a configuration.

Graph-based parser: A parser that scores possible structures and selects the best valid tree.

Unlabeled Attachment Score: The proportion of tokens with correctly predicted heads.

Labeled Attachment Score: The proportion with both correct heads and dependency labels.

Treebank: A corpus annotated with syntactic structures.

Biaffine scorer: A neural scoring function combining bilinear and affine terms.

Domain shift: A change between the data distribution used for training and that encountered in deployment.

Review Questions

Short Answer Questions

1. What is the principal representational difference between constituency and dependency grammar?
2. Why is binarization useful for CKY parsing?
3. Define syntactic ambiguity and give one example.
4. What do UAS and LAS measure?
5. State two limitations of a simple PCFG.

Long Answer Questions

1. Explain how a CFG derives a sentence and discuss the assumptions that make CFG parsing computationally attractive.
2. Describe the CKY algorithm, including its chart entries, recurrence, backpointers, and standard complexity.
3. Compare transition-based and graph-based dependency parsing in terms of search, efficiency, and error behavior.
4. Explain how neural contextual representations and biaffine scoring are used in modern dependency parsers.
5. Discuss why parser evaluation must consider annotation schemes, domain shift, and downstream application requirements.

Analytical / Application Questions

1. Design a parsing and evaluation plan for a medical information-extraction system. Specify the representation, annotation policy, data split, metrics, and human-safety measures.
2. For the sentence “The manager saw the employee with the badge,” identify two plausible attachment analyses and explain what contextual or lexical evidence could distinguish them.
3. A parser has high overall LAS but performs poorly on passive voice and coordinated clauses in legal contracts. Propose an error-analysis and adaptation strategy, including data, modeling, and governance considerations.

Multiple Choice Questions with Answers

Question 1

Which representation primarily describes phrases such as NP and VP and their recursive nesting?

A. Constituency structure

B. Dependency structure

C. Token frequency table

D. Word embedding space

Correct Answer: A. Constituency structure

Question 2

In a standard dependency tree, what is normally true of every token except the root?

A. It has exactly two labels

B. It has one syntactic head

C. It must be a noun

D. It must begin a phrase

Correct Answer: B. It has one syntactic head

Question 3

Which condition is required by the standard CKY presentation?

A. The grammar must contain only semantic roles

B. The grammar must be represented in a suitable binary form

C. Every sentence must be ambiguous

D. All dependencies must be non-projective

Correct Answer: B. The grammar must be represented in a suitable binary form

Question 4

What does a PCFG attach to each grammar production?

A. A syntactic head word only

B. A conditional probability

C. A vector of token positions

D. A dependency tree depth

Correct Answer: B. A conditional probability

Question 5

In transition-based dependency parsing, what does SHIFT generally do?

A. Moves the next buffer token onto the stack

B. Deletes the root of the tree

C. Reverses every dependency arc

D. Converts a phrase into a probability

Correct Answer: A. Moves the next buffer token onto the stack

Question 6

What does Labeled Attachment Score require for a token to be counted as correct?

A. Correct part of speech only

B. Correct span length only

C. Correct head and dependency label

D. Correct sentence length and punctuation

Correct Answer: C. Correct head and dependency label

Question 7

Which statement best describes a projective dependency tree?

A. Every word has two heads

B. Each subtree occupies a contiguous span of words

C. All relations are semantic rather than syntactic

D. The tree contains no labels

Correct Answer: B. Each subtree occupies a contiguous span of words

Question 8

Why can a neural parser still fail when its benchmark score is high?

A. Neural models cannot process tokens

B. Benchmark data may differ from the deployment domain

C. Parsing never involves ambiguity

D. Dependency trees cannot be evaluated

Correct Answer: B. Benchmark data may differ from the deployment domain

Question 9

In a graph-based parser, a candidate tree is commonly selected by what principle?

A. Choosing the tree with the highest total structural score

B. Choosing the shortest sentence

C. Choosing the tree with the fewest words

D. Choosing actions randomly

Correct Answer: A. Choosing the tree with the highest total structural score

Question 10

Which practice is most appropriate when parsing confidential legal documents?

A. Publish all training documents publicly

B. Ignore annotation and retention policies

C. Use access controls, data minimization, and human review for uncertain cases

D. Replace evaluation with model confidence alone

Correct Answer: C. Use access controls, data minimization, and human review for uncertain cases