Syntactic Analysis & Parsing

Syntax: The Structure of Sentences

Syntax is the set of rules that govern how words combine to form grammatical sentences. Syntactic analysis (parsing) identifies the grammatical structure of a sentence.

Why Syntax Matters for NLP

Syntax is crucial for:

• Information extraction: who did what to whom?
• Machine translation: word order differs across languages
• Relation extraction: "Apple acquired Beats" → subject-verb-object
• Coreference resolution: "The cat chased the dog. It barked." — what is "it"?
• Question answering: understanding what is being asked

Two Parsing Paradigms

	Constituency Parsing	Dependency Parsing
Represents	Phrase structure (nested groups)	Word-to-word grammatical relations
Output	Phrase structure tree (S → NP VP)	Directed graph of dependencies
Grammar formalism	CFG (Context-Free Grammar)	Dependency grammar
Popular tools	Stanford Parser, Berkeley Parser	spaCy, Stanford NLP, UDPipe
Use in NLP	Semantic role labeling, coreference	IE, relation extraction, practical NLP

Constituency Parsing

Context-Free Grammar (CFG)

A CFG consists of:

• Terminal symbols: actual words ("the", "cat", "runs")
• Non-terminal symbols: phrase categories (S, NP, VP, PP, DT, NN...)
• Production rules: NP → DT NN | DT JJ NN | NN
• Start symbol: S (sentence)

Example grammar fragment:

S  → NP VP
NP → DT NN | DT JJ NN | NNP
VP → VB | VB NP | VB NP PP
PP → IN NP
DT → "the" | "a"
NN → "dog" | "cat" | "bone"
VB → "chased" | "saw"
IN → "with" | "near"

For sentence "the dog chased the cat":

         S
        / \
       NP  VP
      / \ / \
     DT NN VB  NP
     |  |  |  / \
    the dog ch DT NN
                |  |
               the cat

Ambiguity in Constituency Parsing

Prepositional phrase attachment ambiguity is the classic problem:

"I saw the man with the telescope"

• Attachment 1: [I saw [the man [with the telescope]]] → the man has the telescope
• Attachment 2: [I [saw [the man] [with the telescope]]] → I used the telescope

The sentence has two valid parse trees. Context and world knowledge are needed to resolve it.

CYK Algorithm

The Cocke-Younger-Kasami (CYK) algorithm parses a sentence of length $n$ in $O(n^3 \cdot |G|)$ time using dynamic programming on a chart (table). Requires Chomsky Normal Form (CNF): every rule is either A → BC or A → a.

Probabilistic CFG (PCFG)

PCFGs assign probabilities to productions, choosing the most likely parse:

$P(\text{parse}) = \prod_{\text{rules used}} P(A \to \alpha | A)$

Modern parsers use neural models (BERT + span labeling) instead of PCFG.

Dependency Parsing

Dependency parsing represents a sentence as a directed graph where:

• Each word has exactly one head (parent)
• Edges are labeled with grammatical relations
• There is one root word with no head

For "The dog chased the cat quickly":

      chased (ROOT)
     /    |     \
   dog   cat    quickly
    |     |
   The   the

Universal Dependency (UD) Relations

The Universal Dependencies project defines cross-lingual dependency relations:

Relation	Abbrev	Example
Nominal subject	nsubj	"The dog chased"
Direct object	obj	"chased the cat"
Modifier adjective	amod	"quick fox"
Adverbial modifier	advmod	"ran quickly"
Determiner	det	"the dog"
Nominal modifier	nmod	"book of John"
Clausal subject	csubj	"Running is fun"
Complement	comp	"I think he left"

Parsing Algorithms

Transition-based parsing (arc-eager, arc-standard):

• Maintains a stack and buffer
• Actions: SHIFT, LEFT-ARC(rel), RIGHT-ARC(rel), REDUCE
• $O(n)$ time — fast, used by spaCy

Graph-based parsing (Eisner algorithm, MST):

• Scores all possible arcs, finds maximum spanning tree
• $O(n^2)$ or $O(n^3)$ — more accurate but slower
• Used by StanfordNLP, Stanza

Projective vs Non-Projective

A parse is projective if no arcs cross. Most English sentences are projective; languages with freer word order (Czech, German) often have non-projective dependencies.

import spacy
import nltk
from nltk import CFG, ChartParser
from nltk.tree import Tree

# ─── 1. CFG Parsing with NLTK ────────────────────────────────
grammar = CFG.fromstring("""
  S  -> NP VP
  NP -> DT NN | DT JJ NN | NNP
  VP -> VB NP | VB NP PP
  PP -> IN NP
  DT -> 'the' | 'a'
  NN -> 'dog' | 'cat' | 'telescope' | 'man'
  NNP -> 'Alice'
  JJ -> 'big' | 'lazy'
  VB -> 'chased' | 'saw'
  IN -> 'with' | 'near'
""")

parser = ChartParser(grammar)

# Ambiguous sentence — should produce 2 parses
sentence = "Alice saw the man with the telescope".lower().split()
parses = list(parser.parse(sentence))
print(f"Number of parses: {len(parses)}")
for i, tree in enumerate(parses):
    print(f"\nParse {i+1}:")
    tree.pretty_print()

# ─── 2. Dependency Parsing with spaCy ────────────────────────
nlp = spacy.load("en_core_web_sm")
doc = nlp("The quick brown fox jumped over the lazy dog near the river bank")

print("\nDependency Parse:")
print(f"{'Token':<15} {'POS':<8} {'Dep':<12} {'Head':<15}")
print("-" * 52)
for token in doc:
    print(f"{token.text:<15} {token.pos_:<8} {token.dep_:<12} {token.head.text:<15}")

# ─── 3. Extract Subject-Verb-Object triples ──────────────────
def extract_svo(doc):
    svo_triples = []
    for token in doc:
        if token.dep_ == "ROOT" and token.pos_ == "VERB":
            subj = [t for t in token.lefts if t.dep_ in ("nsubj", "nsubjpass")]
            obj  = [t for t in token.rights if t.dep_ in ("obj", "dobj", "attr")]
            if subj and obj:
                svo_triples.append((subj[0].text, token.text, obj[0].text))
    return svo_triples

sentences = [
    "Apple acquired Beats in 2014.",
    "Scientists discovered a new species in the Amazon.",
    "The bank approved the loan quickly.",
]
print("\nSVO Triples:")
for sent in sentences:
    doc = nlp(sent)
    triples = extract_svo(doc)
    print(f"  '{sent}' → {triples}")

# ─── 4. Named chunks and noun phrases ────────────────────────
doc2 = nlp("The President of the United States signed the executive order.")
print("\nNoun chunks (constituency-like):")
for chunk in doc2.noun_chunks:
    print(f"  [{chunk.text}] — root: {chunk.root.text}, dep: {chunk.root.dep_}")

# ─── 5. Constituency Parsing with Stanza ────────────────────
# pip install stanza
import stanza
stanza.download('en', processors='tokenize,pos,constituency', quiet=True)
nlp_stanza = stanza.Pipeline('en', processors='tokenize,pos,constituency')
doc3 = nlp_stanza("The cat sat on the mat.")
for sentence in doc3.sentences:
    print(f"\nConstituency tree:\n{sentence.constituency}")

Summary

• Constituency parsing produces nested phrase structure trees using CFG rules; the CYK algorithm solves it in $O(n^3)$
• Dependency parsing produces directed graphs of word-to-word grammatical relations; transition-based (spaCy) runs in $O(n)$
• PP attachment ambiguity is the canonical syntactic challenge — context and semantics are needed to resolve
• Universal Dependencies provides a cross-lingual standard for dependency labels (nsubj, obj, amod, etc.)
• For practical NLP, spaCy's dependency parser is the default choice; Stanza provides constituency trees when needed

Next: Semantic Analysis — understanding the meaning of words and sentences.