Questions: Syntactic Parsing Algorithms and Models

Question 1

The sentence 'The horse raced past the barn fell' causes readers to initially treat 'raced' as the main verb and then struggle to reanalyze. This illustrates a limitation of which parsing strategy?

• A. Chart parsing — it cannot handle reduced relative clauses and fails to find the correct analysis
• B. Shift-reduce parsing — greedy sequential commitment leads to costly reanalysis when later words contradict early decisions
• C. Top-down parsing — it cannot process passive constructions unless given explicit grammar rules for them
• D. CYK parsing — its O(n³) complexity creates processing delays for sentences with embedded clauses

Answer: (B)

Shift-reduce parsers make greedy sequential decisions: at each step, shift the next word onto the stack or reduce. In garden-path sentences like this one, the parser commits to 'raced' as the main verb (a reasonable early decision) and must expensively backtrack when 'fell' appears and makes that analysis impossible. Human readers exhibit the same difficulty, suggesting they use something like shift-reduce processing. Chart parsers avoid this by maintaining all analyses simultaneously, but they are slower.

Question 2

Neural parsers achieve state-of-the-art parsing accuracy without explicit grammatical rules, learning directly from annotated treebanks. What is the most significant limitation this creates?

• A. Neural parsers run slower than chart parsers for sentences longer than approximately 20 words
• B. Without explicit rules, neural parsers cannot generalize to sentences longer or more complex than those in training data
• C. The learned representations are opaque — it is unclear what linguistic knowledge the parser has actually acquired
• D. Neural parsers cannot handle structurally ambiguous sentences because they only output a single parse

Answer: (C)

Neural parsers learn statistical regularities from training data and achieve excellent empirical accuracy, but their representations are distributed and not directly interpretable as linguistic rules. Probing studies try to determine whether hidden states encode phrase structure, syntactic dependencies, or other linguistically meaningful units — and the answers are partial and contested. This opacity is the central limitation: we often cannot explain why a neural parser succeeds or fails on particular inputs, which matters for understanding language and for diagnosing errors.

Question 3

Chart parsing using the CYK algorithm is complete — it finds all valid parses of an ambiguous sentence — but this completeness comes at the cost of potentially generating exponentially many analyses for highly ambiguous inputs.

• T. True
• F. False

Answer: True

CYK runs in O(n³) time, which is polynomial and manageable, but the number of distinct parse trees an ambiguous sentence can have may grow exponentially with sentence length and grammatical ambiguity. For very ambiguous inputs, the chart may fill with exponentially many analyses, making downstream disambiguation and processing expensive. This is the completeness-tractability tradeoff: by exploring all analyses, chart parsers cannot afford to be greedy, and some of the cost is unavoidable.

Question 4

Shift-reduce parsing is preferred when complete enumeration of most possible analyses is required, because its linear time complexity makes it fast enough to evaluate most possible parse.

• T. True
• F. False

Answer: False

Shift-reduce parsing is deterministic and greedy — it commits to one analysis at a time and does not systematically enumerate all analyses. Its linear time complexity comes precisely from not exploring alternatives. If complete enumeration is needed (for disambiguation, statistical ranking of parses, or theoretical completeness), chart parsing or another backtracking approach is required. Shift-reduce is preferred for high-throughput applications where speed matters more than guaranteed correctness on garden-path or highly ambiguous sentences.

Question 5

Explain the fundamental tradeoff between chart parsing and shift-reduce parsing. Under what circumstances would each approach be preferred?

Model answer: Chart parsing uses dynamic programming to store intermediate results and explore all parses simultaneously. It is complete (finds every valid analysis) and avoids recomputing constituents, but runs in O(n³) time and can produce exponentially many analyses for ambiguous sentences. Shift-reduce parsing makes greedy sequential decisions and runs in linear time, but cannot efficiently backtrack and fails on garden-path sentences where early commitments are wrong. Chart parsing is preferred when exhaustive disambiguation and theoretical completeness are required. Shift-reduce is preferred for high-throughput, real-time NLP applications where most sentences are unambiguous and speed is critical.

The tradeoff maps onto a deeper tension between exhaustiveness and efficiency. Psycholinguistic evidence suggests humans use something like shift-reduce processing (garden-path effects), which is efficient but fallible. Computational systems can choose their tradeoff point — and hybrid approaches (like probabilistic chart parsers that prune low-probability analyses early) attempt to capture benefits of both.