Syntactic Parsing

Overview

Syntactic parsing analyzes the grammatical structure of sentences. Two major formalisms exist: constituency parsing (phrase structure trees) and dependency parsing (head-modifier relations). Both are essential for tasks requiring structural understanding of language.

Constituency Parsing

Constituency parsing decomposes a sentence into nested phrases according to a context-free grammar.

          S
        /   \
      NP      VP
     / \     / \
   DET  N   V   NP
   The cat  sat  on the mat

Context-Free Grammars (CFG)

A CFG G = (N, T, R, S) where:

• N: non-terminal symbols (S, NP, VP, PP, ...)
• T: terminal symbols (words)
• R: production rules (S -> NP VP, NP -> DET N, ...)
• S: start symbol

Chomsky Normal Form (CNF): All rules are either A -> B C (binary) or A -> a (lexical). Any CFG can be converted to CNF.

CKY Algorithm

The Cocke-Kasami-Younger algorithm is the standard dynamic programming parser for CFGs in CNF.

Procedure:

1. Fill a triangular chart bottom-up
2. Cell [i, j] contains all non-terminals that can derive the span from word i to word j
3. For each span, try all split points k and all rules A -> B C where B is in [i, k] and C is in [k+1, j]

Complexity: O(n^3 * |G|) where n is sentence length and |G| is grammar size.

Recognizer vs Parser: The basic algorithm determines if a sentence is grammatical. To recover the tree, store backpointers at each cell.

Probabilistic Context-Free Grammars (PCFG)

Augment each rule with a probability. Probabilities for rules with the same left-hand side sum to 1.

S  -> NP VP      [0.8]
S  -> VP         [0.2]
NP -> DET N      [0.5]
NP -> NP PP      [0.3]
NP -> N          [0.2]

Probabilistic CKY: Same algorithm, but track the probability of each entry (product of rule probabilities). Select the parse with highest probability (Viterbi parse).

Limitations of PCFGs:

• Independence assumption: rule probability is independent of context
• "NP -> PRP" has the same probability whether NP is a subject or object
• Poor modeling of lexical preferences and structural ambiguity

Lexicalized PCFGs

Add head word annotations to non-terminals to capture lexical dependencies.

• VP(sat) -> V(sat) PP(on) is more informative than VP -> V PP
• Dramatically improves parsing accuracy but explodes the grammar size
• Sparse data problem requires smoothing

Neural Constituency Parsers

Chart-based neural parsers (Stern et al., Kitaev & Klein):

1. Encode the sentence with a BiLSTM or Transformer
2. Score each span [i, j] with label L using a neural classifier
3. Find the highest-scoring tree using CKY decoding over span scores
4. Kitaev & Klein (2018): BERT encoder + self-attention + CKY achieves ~96 F1 on Penn Treebank

Transition-based neural parsers:

• Shift-reduce parsing with neural scoring of actions
• Faster (linear time) but slightly less accurate than chart parsers

Sequence-to-sequence parsers:

• Linearize the tree and generate it as a token sequence
• Competitive accuracy with simpler implementation

Dependency Parsing

Dependency parsing represents syntactic structure as directed edges between words. Each word (dependent) is connected to exactly one head (governor), forming a tree rooted at a special ROOT node.

ROOT -> sat
sat -> cat (nsubj)
cat -> The (det)
sat -> on (obl)
on -> mat (nmod)
mat -> the (det)

Dependency Relations

Each edge is labeled with a grammatical relation.

Properties of Dependency Trees

• Single head: each word has exactly one head (except ROOT)
• Connected: all words are reachable from ROOT
• Acyclic: no cycles
• Projectivity: if word A governs word B, then A also governs all words between A and B (in projective trees). Non-projective trees occur in free word-order languages.

Transition-Based Parsing

Processes the sentence left-to-right using a stack, a buffer, and a set of actions.

Arc-standard system:

Properties:

• Linear time O(n) -- exactly 2n transitions for a sentence of length n
• Greedy: each action is predicted independently (no global search)
• Error propagation: early mistakes cascade
• Beam search partially mitigates but increases complexity

Neural scoring (Chen & Manning, 2014):

• Feed-forward network over features from stack and buffer (embeddings of words, POS tags, labels)
• First fast and accurate neural parser
• Later improved with BiLSTM encoders and global training

Graph-Based Parsing

Scores all possible edges independently, then finds the highest-scoring tree globally.

Edge scoring:

• For each pair (head, dependent), compute a score using a biaffine classifier
• s(i, j) = h_i^T W h_j + U^T h_i + V^T h_j + b

Eisner Algorithm:

• Dynamic programming for projective dependency parsing
• O(n^3) complexity
• Builds optimal tree by combining left and right spans
• Analogous to CKY for dependencies

Chu-Liu/Edmonds Algorithm:

• Finds the maximum spanning arborescence (non-projective case)
• O(n^2) or O(n^3) depending on implementation
• Required for free word-order languages (Czech, German, etc.)

Biaffine Parser (Dozat & Manning, 2017)

The current standard architecture for graph-based dependency parsing.

Input -> BERT/BiLSTM -> separate head/dependent MLPs -> Biaffine scoring -> MST decoding

1. Encode sentence with BiLSTM or Transformer
2. Apply separate MLPs to produce head representations and dependent representations
3. Biaffine attention scores all head-dependent pairs
4. Decode with Eisner (projective) or Chu-Liu/Edmonds (non-projective)
5. Separate biaffine classifier for relation labeling

Achieves ~96 UAS / ~94 LAS on Penn Treebank.

Transition-Based vs Graph-Based

Universal Dependencies (UD)

A cross-linguistically consistent framework for dependency annotation.

Design principles:

• Content words are heads (not function words)
• Prioritize cross-linguistic parallelism
• Unified POS tag set (UPOS) and relation set across languages

Scale: UD v2.x covers 150+ languages with 250+ treebanks.

Impact:

• Enables multilingual parser training and evaluation
• Facilitates cross-lingual transfer learning
• Standard benchmark for dependency parsing research

Evaluation Metrics

Constituency vs Dependency

Both formalisms are interconvertible to a degree. Head-finding rules convert constituency trees to dependencies. The Stanford converter and UD tools automate this.

Key Takeaways

• CKY with PCFGs provides exact inference for constituency parsing; neural chart parsers achieve ~96 F1
• Dependency parsing captures head-modifier relations; transition-based is fast, graph-based is globally optimal
• The biaffine parser (graph-based, neural) is the dominant dependency parsing architecture
• Universal Dependencies standardize annotation across 150+ languages
• Modern parsers use pretrained transformers as encoders, achieving near-human performance on English