CYK, PCFG, and Shift-reduce Parsing
On this page
CYK, PCFG, and Shift-reduce Parsing
Recall first
Which parser fills a span chart, which assigns probabilities to productions, and which keeps a stack plus an input buffer? What common problem do all three solve?
First principles
CYK (Cocke–Younger–Kasami) is bottom-up dynamic programming for CFGs in Chomsky Normal Form (CNF): binary rules A → BC and lexical rules A → word (with preprocessing for other forms). Let chart[i,j] contain nonterminals spanning tokens i…j. For every split k, if B ∈ chart[i,k] and C ∈ chart[k+1,j] and A → BC, add A to chart[i,j]. The recurrence reuses shorter spans, giving the classic cubic dependence on sentence length (plus grammar factors). It is exhaustive for the grammar and can recover a tree with backpointers, but CNF conversion can make trees less intuitive.
PCFG attaches a probability to each CFG rule, with probabilities of alternative rules for a left-hand side normally summing to one. A parse-tree probability is the product of its rule probabilities; a Viterbi/inside chart can choose the most probable parse. PCFGs rank structural alternatives but make independence assumptions: rule choice depends mainly on the parent/nonterminal, not all lexical context.
Shift-reduce parsing uses a stack and remaining input. SHIFT moves the next token onto the stack; REDUCE A→β replaces a matching stack sequence β with A; ACCEPT succeeds when the stack contains S and input is exhausted. It is incremental and can be linear with a good decision policy, but shift/reduce and reduce/reduce conflicts require a grammar, oracle, or learned disambiguator.
Worked CYK trace. Grammar S→NP VP, NP→Det N | N, VP→V NP; input the dog sees cats. Length-1 cells contain Det(the), N(dog), V(sees), N(cats). Span the dog combines Det N → NP; span sees cats combines V NP only after cats has an NP analysis (add NP→N or use a CNF-compatible lexical rule). Finally [the…cats] combines NP VP → S. Because NP→N is a unit production, a plain CNF CYK implementation must eliminate it (for example, by folding N’s lexical rules into NP) or handle unit-closure; otherwise cats never enters an NP cell. This illustrates why the grammar must actually license every phrase.
Exercise — reveal after answering
Why must plain CYK require CNF (or an equivalent binarized grammar)?
Answer: Its recurrence combines two subspans at a time. Rules with three or more symbols, epsilon, or unit forms must be transformed or handled by extra closure steps.
Exam lens
Write the CYK span/split recurrence, state CNF and complexity, define PCFG rule/tree probabilities, then list SHIFT/REDUCE/ACCEPT and conflict risk. Do not confuse CYK (chart DP) with shift-reduce (stack control).
Rapid revision checklist
- Define
chart[i,j]and splitk. - Explain CNF and cubic chart filling.
- Compute PCFG tree probability as a product.
- Trace SHIFT and REDUCE.
Key takeaways
- CYK systematically reuses bottom-up spans.
- PCFG scores grammatical alternatives but uses simplifying assumptions.
- Shift-reduce is incremental; its hard problem is action selection/conflicts.