Questions: Computational Parsing Algorithms and Complexity

Question 1

An NLP team replaces a CKY chart parser with a neural parser because the neural model scores higher on a benchmark of standard news text. Months later, the system fails badly on technical documents with unusual syntactic constructions. What does this failure most directly illustrate?

• A. CKY is always more accurate than neural parsers because it uses explicit grammar rules that generalize better
• B. Neural parsers are O(n³) on technical text, causing them to time out on long sentences
• C. Benchmark accuracy and out-of-distribution robustness are different properties; a faster, higher-scoring parser can still fail in ways a grammar-based parser would not
• D. The team should have used an Earley parser, which handles arbitrary context-free grammars and therefore generalizes to any text

Answer: (C)

Efficiency and accuracy are separate from robustness to unusual inputs. A neural parser trained on news text may score very highly on that benchmark while failing on constructions outside its training distribution — confidently producing plausible-looking but wrong parses. A chart parser like CKY, by contrast, is theoretically complete for its grammar: if the grammar covers a construction, the parser will find it. The benchmark result measures performance on typical text, not on tail cases. Choosing a parser means understanding which failure modes matter for your application.

Question 2

A shift-reduce parser, processing the sentence 'The horse raced past the barn fell,' successfully reduces 'the horse raced past the barn' as a complete verb phrase before encountering 'fell' — and then cannot recover. Why does this happen?

• A. Shift-reduce requires Chomsky Normal Form, and this sentence contains a reduced relative clause that violates CNF
• B. The O(n³) complexity of shift-reduce causes it to time out on garden-path constructions
• C. Shift-reduce makes early, irrevocable commitments — once it reduces 'raced past the barn' as a main verb, it cannot reanalyze it as a relative clause modifier
• D. Shift-reduce processes input right-to-left and therefore misses the main verb 'fell' at the end

Answer: (C)

Shift-reduce parsing is a greedy left-to-right algorithm: at each step it either shifts the next word onto a stack or reduces the top of the stack using a grammar rule, with no backtracking. When it reduces 'the horse raced past the barn' as a complete clause, it commits to that analysis and has no mechanism to revise it when 'fell' arrives. Chart parsers (CKY, Earley) avoid this by maintaining all possible analyses simultaneously until the full sentence is processed. The garden-path effect is not a bug in shift-reduce — it mirrors aspects of how human incremental processing also makes early commitments.

Question 3

CKY can parse any context-free grammar as long as the sentence is unambiguous.

• T. True
• F. False

Answer: False

CKY requires the grammar to be in Chomsky Normal Form (CNF), where every rule is either A → BC or A → word. This is not a restriction on ambiguity but on rule structure. Any context-free grammar can be converted to CNF, but CKY cannot directly process arbitrary CFGs — the grammar must be preprocessed into CNF first. Earley parsing, by contrast, handles arbitrary context-free grammars directly without CNF conversion, and also handles ambiguous sentences by returning all possible parse trees.

Question 4

An O(n) neural parser will generally be less accurate than an O(n³) chart parser, because higher time complexity reflects more thorough examination of the input.

• T. True
• F. False

Answer: False

Efficiency (time complexity) and accuracy are independent properties. An O(n) neural parser can outperform an O(n³) chart parser on typical benchmark text — it has learned patterns from large training corpora that let it make accurate predictions quickly. Complexity bounds describe how computation scales with input length, not how well the output matches the correct parse. In practice, modern neural parsers achieve state-of-the-art accuracy on standard benchmarks despite their speed. However, they fail differently: they are less robust to unusual constructions outside their training distribution, whereas a complete chart parser is bounded by its grammar coverage.

Question 5

Explain the core tradeoff between shift-reduce and chart parsing approaches like CKY or Earley. Why is shift-reduce faster, and what does it sacrifice?

Model answer: Shift-reduce is fast because it processes the input greedily from left to right with a single pass, making immediate reduce/shift decisions without revisiting earlier choices. It sacrifices completeness: once it commits to a reduction, it cannot backtrack if that analysis turns out to be wrong when more input arrives. Chart parsers (CKY, Earley) sacrifice speed for completeness: they maintain a chart of all possible partial analyses and never discard alternatives until the full input is seen, guaranteeing they find all valid parses (at O(n³) cost). The tradeoff is early commitment (fast but error-prone on ambiguous/garden-path sentences) versus delayed commitment (thorough but slower).

This tradeoff mirrors the accuracy/efficiency tradeoff more broadly. Shift-reduce is used in many production NLP systems because it's fast enough and usually correct on typical input. But it embodies a design choice: trade theoretical guarantees for practical speed. Chart parsers are theoretically attractive but computationally heavier. Neural parsers reframe the tradeoff entirely — they learn heuristics from data rather than implementing an explicit algorithm, achieving high speed and accuracy on typical text while failing differently on atypical input.