Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 63 ยท Sequences and Structure

Syntactic Parsing

Understand syntactic parsing: constituency vs dependency trees, context-free grammars, a CKY parser written from scratch, and reading dependency trees in Python.

"I saw the man with the telescope." Who has the telescope, you or the man? The words are the same under both readings; only the structure differs. Syntactic parsing is the task of recovering that structure: which words group into phrases, which phrase modifies which, who did what to whom. Parsers are the engine behind grammar checkers, question answering over text, relation extraction and, in classic machine translation, reordering.

There are two main kinds of structure, and you will meet both. This lesson explains them, builds a small constituency parser (the CKY algorithm) from scratch to see how ambiguity arises, and then works with dependency trees, which are what modern libraries such as spaCy produce.

Two views of structure

Constituency trees

Phrases inside phrases Words group into NP, VP, PP and finally S.
Labeled brackets (S (NP I) (VP saw (NP the man)))
Grammar rules S becomes NP VP.

Great for seeing how a sentence is built.

1 / 2

A constituency (phrase-structure) tree groups words into nested phrases: a noun phrase (NP) such as the man, a verb phrase (VP) such as saw the man, a prepositional phrase (PP) such as with the telescope. Rules of a context-free grammar (CFG) describe how phrases are built from smaller parts, for example S -> NP VP (a sentence is a noun phrase followed by a verb phrase) and NP -> Det N.

A dependency tree has no phrase nodes. Every word, except one root, has exactly one head, and the arc is labeled with the grammatical relation: in She gave the dog a bone, She is the nsubj (subject) of gave, and bone is its obj (object). Dependency trees are smaller, closer to meaning and easier to use in code, which is why the Universal Dependencies project and most libraries prefer them.

A tiny grammar and the CKY algorithm

To parse with a CFG, you must decide for each span of words which phrase labels it could have. CKY (named after Cocke, Kasami and Younger) does it bottom-up with dynamic programming. It requires the grammar in Chomsky normal form: every rule is either A -> B C (two symbols) or A -> word. Any CFG can be converted to this form.

The algorithm fills a triangular chart. Cell (i, j) holds the labels that can cover words i to j. First fill single words from the lexicon. Then, for each longer span, try every split point k: if cell (i, k) holds B and cell (k, j) holds C and the grammar has A -> B C, then A goes into cell (i, j). The sentence is grammatical if the start symbol S ends up in the cell that covers all the words.

Python A CKY recognizer: reading the chart

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The chart reads like a story. The one-word cells come from the lexicon. the dog becomes an NP and a man another NP; saw a man becomes a VP, because V and NP sit next to each other; and the whole span is an S. The scrambled dog the saw gets no S at all, so the grammar rejects it. A recognizer only says yes or no. To get the actual trees we keep, for each label in each cell, a list of the ways it was built.

Ambiguity

Now store the trees instead of only the labels. Each entry in a cell becomes a tuple (label, left_tree, right_tree). When two different splits lead to the same label, the cell holds two trees: the sentence is ambiguous.

Python CKY with parse trees and ambiguity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first sentence has exactly one parse. The second has two, and they are exactly the two meanings from the beginning of the lesson. In the first tree, with the telescope is a PP inside the noun phrase the man with the telescope: the man has the telescope. In the second tree, the PP attaches to the VP saw the man: you used the telescope to see him. This is prepositional-phrase attachment ambiguity, one of the best-known problems in parsing. A real grammar with thousands of rules can give hundreds of parses for a single sentence, so practical parsers use a probabilistic CFG, which attaches a probability to each rule and returns the most likely tree. CKY then keeps the best-scoring tree per cell instead of all of them, and the idea is the same as the Viterbi algorithm in part-of-speech tagging.

CKY takes time proportional to the cube of the sentence length (three nested loops over i, j and k), times the grammar size. That is fine for sentences, and the reason syntactic parsers work sentence by sentence; see sentence segmentation.

Working with dependency trees

Dependency trees are simple data: for each word, store the index of its head and a relation label. That is exactly the form spaCy gives you (token.head, token.dep_). With just those two arrays we can print the tree, walk to the root and pull out facts. The example below also checks projectivity: a tree is projective when no arcs cross when drawn above the sentence. Most English sentences are projective, but a few, such as A hearing is scheduled on the issue today, are not, because on the issue belongs to hearing while today belongs to scheduled.

Python Dependency trees as head arrays

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed tree shows gave at the top with three children (subject, indirect object and object), and each noun with its determiner below. The path from a to the root is a -> bone -> gave, which says "a belongs to bone, which belongs to gave". The triple extraction is the seed of relation extraction: because we look at relations (nsubj, obj) instead of word positions, the same code would still find the subject and object if a parser labeled The tired girl quickly gave the dog a bone, however many words sit between them. Finally, the first sentence is projective and the second is not, as promised.

Parsers in practice

Modern dependency parsers are neural. A transition-based parser reads the sentence left to right and chooses actions (shift a word, or draw an arc between words on its stack), and a graph-based parser scores every possible arc and picks the best tree. Both reach about 90 to 95% of arcs correct on news text; results fall on social media, speech and other domains unlike the training data. Accuracy is reported as UAS (unlabeled attachment score: the share of words with the correct head) and LAS (labeled attachment score: correct head and correct relation).

Using spaCy is two lines. The snippet is read-only because the model download is too large for the browser.

Python
import spacy

nlp = spacy.load("en_core_web_sm")
doc = nlp("I saw the man with the telescope")
for token in doc:
    print(f"{token.text:10s} {token.dep_:8s} head={token.head.text}")

# spaCy returns one dependency tree per sentence. For phrases use doc.noun_chunks.
# Which attachment of "with the telescope" you get depends on the statistics of the model.

For constituency trees, NLTK offers nltk.ChartParser for hand-written grammars like ours (and Tree.pretty_print() to draw the result), while treebank-trained constituency parsers are available in research toolkits.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the main difference between constituency and dependency trees?

    A constituency tree has phrase nodes (NP, VP, PP). A dependency tree has only words, each pointing to a head with a labeled relation.
  2. 2. Why does CKY require a grammar in Chomsky normal form?

    With binary rules A -> B C, each cell can be filled by combining two smaller cells at a split point, which is what makes the chart algorithm simple and cubic.
  3. 3. Why does "I saw the man with the telescope" get two parses?

    Both rules NP -> NP PP and VP -> VP PP are legal, so with the telescope can modify the man or the act of seeing.
  4. 4. What does a probabilistic CFG add to a plain CFG?

    Most real sentences have many legal parses. Rule probabilities rank them, and CKY keeps the best-scoring tree per cell.
  5. 5. What does LAS measure?

    UAS counts only correct heads; LAS also requires the right relation label such as nsubj or obj.

Summary

  • Parsing recovers sentence structure. Constituency trees nest phrases (NP, VP, PP); dependency trees link each word to a head with a labeled relation.
  • A CFG describes how phrases are built; in Chomsky normal form it can be parsed with the CKY chart algorithm in time proportional to the cube of the sentence length.
  • Ambiguity is normal: prepositional-phrase attachment gives two trees for one sentence, and probabilistic grammars or neural scoring pick the likeliest one.
  • Dependency trees are simple head arrays, and relations such as nsubj and obj make fact extraction easy; projective trees have no crossing arcs.
  • Parsers are evaluated with UAS and LAS, and modern ones are neural (spaCy and others).

Next, learn how to build feature-based taggers in Sequence Labeling with CRFs and Features.