How unit 4 is examined
This unit covers context-free grammars, English phrase-structure rules, parse trees and treebanks, CYK and Earley parsing, and probabilistic CFGs; no topic has been asked recently, so each is kept short but complete.
Grammatical Formalisms: Context Free Grammars
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. ==A context-free grammar is a 4-tuple $G=(N,\Sigma,R,S)$ of non-terminals, terminals, rules $A\to\alpha$ and a start symbol.==
Key points.
- Every rule has a single non-terminal on the left, so it can be applied whatever surrounds it (hence "context-free").
- A derivation starts at $S$ and rewrites non-terminals until only terminals remain; the language is all such strings.
- CFGs are more powerful than regular grammars and can express nested structure such as embedded clauses.
- A sentence with two parse trees is structurally ambiguous.
Example. Take $G$ with $S\to NP\ VP$, $NP\to Det\ N$, $VP\to V\ NP$, $Det\to the$, $N\to dog\mid cat$, $V\to chased$. The derivation is $S\Rightarrow NP\ VP\Rightarrow Det\ N\ VP\Rightarrow the\ N\ VP\Rightarrow the\ dog\ VP\Rightarrow the\ dog\ V\ NP\Rightarrow the\ dog\ chased\ NP\Rightarrow the\ dog\ chased\ the\ cat$. Each step rewrites one non-terminal by one rule, and the last line contains only terminals, so the sentence belongs to $L(G)$.
Additional points. 5. Chomsky's hierarchy places regular grammars below context-free grammars, then context-sensitive, then unrestricted grammars, and natural-language syntax is mostly modelled at the context-free level. 6. A leftmost derivation always rewrites the leftmost non-terminal first and a rightmost derivation rewrites the rightmost, and both correspond to the same parse tree. 7. Chomsky normal form restricts every rule to $A\to BC$ or $A\to a$, and any CFG can be converted to it, which is needed for CYK parsing. 8. A grammar is ambiguous when some sentence has more than one parse tree, as in "I saw the man with the telescope", where the prepositional phrase can attach to the verb or to the noun.
Answer frame. Open with the 4-tuple definition; list the four components with one line each; show the small derivation above; close with ambiguity and Chomsky normal form.
Grammar rules for English
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Phrase-structure rules for English rewrite a phrase into its constituents, for example $S\to NP\ VP$.</mark>
Key points.
- Common rules are $NP\to Det\ N$, $NP\to Det\ Adj\ N$, $VP\to V\ NP$, $VP\to V\ NP\ PP$ and $PP\to P\ NP$.
- A constituent is a group of words that behaves as one unit, such as a noun phrase or verb phrase.
- Lexical rules such as $Det\to the$, $N\to dog$ and $V\to chased$ connect the grammar to words.
- Agreement (subject-verb number) and sub-categorisation (transitive vs intransitive verbs) need extra constraints beyond plain CFG rules.
Example. The sentence "the dog chased the cat" uses $S\to NP\ VP$, $NP\to Det\ N$ (twice), $VP\to V\ NP$ and five lexical rules, and it is exactly these words that must be grouped into two noun phrases and one verb phrase.
Additional points. 5. Verb phrases may contain a noun phrase object, a prepositional phrase or a sentential complement, for example $VP\to V\ S$ in "she said he left". 6. Coordination is written as $NP\to NP\ Conj\ NP$, which lets "the dog and the cat" act as one noun phrase. 7. Questions and relative clauses can be handled with extra rules such as $S\to Aux\ NP\ VP$ for "did the dog chase the cat". 8. Plain CFG rules overgenerate, because "the dogs chases the cat" is accepted unless number features are added to the rules.
Answer frame. Open with the phrase-structure definition; write the rules as a list; give the lexical rules; close by noting agreement and sub-categorisation as limits.
Syntactic parsing: Grammar formalisms and treebanks
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Syntactic parsing assigns a parse tree to a sentence using a grammar; a treebank is a corpus of sentences annotated with such trees.</mark>
Key points.
- A parse tree has $S$ at the root, phrases as internal nodes and words at the leaves.
- Parsing can be top-down (start from $S$) or bottom-up (start from words).
- The Penn Treebank is the standard English treebank, and grammar rules can be read directly off its trees.
- Treebanks provide training data and a gold standard for evaluating parsers.
<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Parse tree for "the dog chased the cat""><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="168" y1="39" x2="80" y2="103"/><line class="e" x1="168" y1="39" x2="256" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="124" y2="167"/><line class="e" x1="256" y1="103" x2="212" y2="167"/><line class="e" x1="256" y1="103" x2="344" y2="167"/><line class="e" x1="344" y1="167" x2="300" y2="231"/><line class="e" x1="344" y1="167" x2="388" y2="231"/><circle class="n" cx="168" cy="39" r="17"/><text class="t" x="168" y="39" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">NP</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">Det</text><circle class="n" cx="124" cy="167" r="17"/><text class="t" x="124" y="167" dy=".35em" text-anchor="middle">N</text><circle class="n" cx="256" cy="103" r="17"/><text class="t" x="256" y="103" dy=".35em" text-anchor="middle">VP</text><circle class="n" cx="212" cy="167" r="17"/><text class="t" x="212" y="167" dy=".35em" text-anchor="middle">V</text><circle class="n" cx="344" cy="167" r="17"/><text class="t" x="344" y="167" dy=".35em" text-anchor="middle">NP</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">Det</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">N</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Parse tree for "the dog chased the cat"</figcaption></figure>
Additional points. 5. Dependency and constituency are the two main grammar formalisms, since constituency trees group words into phrases and dependency trees link each word to its head word. 6. Other formalisms include lexicalised grammars such as CCG and TAG, and feature-based grammars such as HPSG that add agreement information. 7. Treebank sentences are annotated by hand and checked, so a parser trained on them learns real usage rather than hand-written rules. 8. Parsers are scored with precision, recall and F1 on labelled constituents compared with the treebank's gold trees.
Answer frame. Open with the parsing and treebank definitions; draw the parse tree above; then develop top-down against bottom-up parsing; close with the role of the Penn Treebank.
Efficient parsing for context-free grammars (CFGs)
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Efficient CFG parsers such as CYK and Earley use dynamic programming to store partial parses in a table, avoiding repeated work in ambiguous sentences.</mark>
Key points.
- CYK needs the grammar in Chomsky normal form ($A\to BC$ or $A\to a$) and fills a triangular table bottom-up in $O(n^3|G|)$ time.
- A sentence is accepted if $S$ appears in the top cell covering words $1..n$.
- Earley parsing works on any CFG, predicting top-down and completing bottom-up with dotted-rule "states" in a chart.
- Both avoid the exponential backtracking of naive top-down or bottom-up parsing.
Example. Sentence "the dog chased the cat" with CNF rules $S\to NP\ VP$, $VP\to V\ NP$, $NP\to Det\ N$, $Det\to the$, $N\to dog\mid cat$, $V\to chased$. CYK fills the table by span length:
| Span | Words | Cell content |
|---|---|---|
| 1-2 | the dog | NP |
| 2-3 | dog chased | none |
| 3-4 | chased the | none |
| 4-5 | the cat | NP |
| 3-5 | chased the cat | VP (from V and NP) |
| 1-5 | whole sentence | S (from NP 1-2 and VP 3-5) |
Answer. $S$ appears in the cell for span 1-5, so the sentence is grammatical.
Additional points. 5. Naive top-down parsing suffers from left recursion and repeated sub-parses, and naive bottom-up parsing builds many phrases that can never reach $S$. 6. Earley's three operations are predict (add rules for the non-terminal after the dot), scan (match the next word) and complete (advance rules whose right side is finished). 7. CYK is a recogniser that also gives all parses when back-pointers are stored in the cells. 8. Chart parsing stores each sub-parse once, which is why the cost is polynomial although the number of trees can be exponential.
Answer frame. Open with dynamic programming as the idea; state the CNF requirement; draw the CYK table above; then contrast Earley's dotted states; close with $O(n^3)$ time.
Statistical parsing and probabilistic CFGs (PCFGs)
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>A PCFG attaches a probability to every rule so that the probabilities of all rules with the same left side sum to 1.</mark>
Key points.
- The probability of a parse tree is the product of the probabilities of the rules used in it: $P(T)=\prod_i P(A_i\to\alpha_i)$.
- The best parse is $\hat T=\arg\max_T P(T)$, which resolves ambiguity by choosing the most probable tree.
- Rule probabilities are estimated from a treebank: $P(A\to\alpha)=\dfrac{\text{Count}(A\to\alpha)}{\text{Count}(A)}$.
- Probabilistic CYK finds the best parse in $O(n^3)$, but PCFGs assume rules are independent of context, which is a weakness.
Example. Suppose the rule probabilities are $S\to NP\ VP=1.0$, $NP\to Det\ N=0.6$, $VP\to V\ NP=0.7$, $Det\to the=0.8$, $N\to dog=0.3$, $N\to cat=0.2$, $V\to chased=0.5$.
| Rule used | Probability |
|---|---|
| $S\to NP\ VP$ | 1.0 |
| $NP\to Det\ N$ (twice) | $0.6\times0.6$ |
| $VP\to V\ NP$ | 0.7 |
| $Det\to the$ (twice) | $0.8\times0.8$ |
| $N\to dog$, $N\to cat$ | $0.3\times0.2$ |
| $V\to chased$ | 0.5 |
$P(T)=1.0\times0.6\times0.7\times0.6\times0.8\times0.3\times0.8\times0.2\times0.5$
$P(T)=0.0048384$
Additional points. 5. Rules for one non-terminal must sum to 1, for instance $NP\to Det\ N$ at 0.6 plus $NP\to NP\ PP$ at 0.4. 6. For an ambiguous sentence the parser computes each tree's probability and returns the higher one. 7. Weaknesses are the independence assumption and the lack of lexical information, so "eat pizza with a fork" and "eat pizza with anchovies" get the same attachment preference. 8. Lexicalised PCFGs and neural parsers fix this by conditioning on head words.
Answer frame. Open with the PCFG definition; write the tree-probability formula; do the product in a table as above; close with the estimation formula and the independence weakness.
Last-minute revision
- CFG = $(N,\Sigma,R,S)$; each rule has one non-terminal on the left.
- Two trees for one sentence means structural ambiguity.
- Basic English rules: $S\to NP\ VP$, $NP\to Det\ N$, $VP\to V\ NP$, $PP\to P\ NP$.
- A treebank is a corpus annotated with parse trees; Penn Treebank is the standard.
- CYK needs Chomsky normal form and runs in $O(n^3)$.
- Earley handles any CFG using a chart of dotted rules.
- PCFG rule probabilities for the same left side sum to 1.
- Tree probability is the product of its rule probabilities.
- MLE: $P(A\to\alpha)=\text{Count}(A\to\alpha)/\text{Count}(A)$.
Memory hooks
- CYK: "Chomsky Yields K-tables", a triangular table needing CNF.
- Earley: dot moves through the rule, predict, scan, complete.
- PCFG: multiply rules for a tree, add up nothing, pick the max.
- Treebank: a bank of trees that both trains and tests parsers.
Coverage checklist
- Grammatical Formalisms: Context Free Grammars: covered (no past questions).
- Grammar rules for English: covered (no past questions).
- Syntactic parsing: Grammar formalisms and treebanks: covered (no past questions).
- Efficient parsing for context-free grammars (CFGs): covered (no past questions).
- Statistical parsing and probabilistic CFGs (PCFGs): covered (no past questions).