Parsers: Top-down, Bottom-up, and Constituency
On this page
Parsers: Top-down, Bottom-up, and Constituency
Recall first
In a parse tree for The dog sleeps, what does the NP constituent contain? Which strategy starts from S, and which starts from input words?
First principles
A parser maps a token sequence to one or more syntactic structures. A constituency parse represents nested phrases as nodes: a CFG might derive S → NP VP, NP → Det N, and VP → V. Terminals are words/tokens; nonterminals are categories; a parse tree records which productions built each span. A sentence can have multiple trees, so a parser may return a forest, ranked alternatives, or one best tree.
Top-down parsing begins with the start symbol S and predicts productions until its frontier can match the input. It is goal-directed: it avoids structures that cannot derive S, but can predict many alternatives, loop with left-recursive grammars, or backtrack.
Bottom-up parsing begins with input tokens and combines them into larger constituents until reaching S. It is data-directed and can reuse recognized spans, but may build constituents that cannot participate in a complete sentence.
Worked derivation. For The dog sleeps, S ⇒ NP VP ⇒ Det N VP ⇒ The dog VP ⇒ The dog V ⇒ The dog sleeps is a leftmost top-down derivation. A bottom-up reducer first recognizes The as Det, dog as N, reduces Det N to NP, recognizes sleeps as V, then reduces NP V to S under the toy grammar. The strategies use the same grammar but schedule hypotheses differently.
Constituency is useful for phrase boundaries, recursion, coordination, and grammar-based interpretation. It differs from dependency parsing, which links heads and dependents rather than grouping spans; neither is automatically “the meaning” of a sentence. Ambiguous grammars need disambiguation, often with PCFG probabilities or discriminative scores.
Exercise — reveal after answering
Why can a bottom-up parser waste work on a constituent that no complete sentence uses?
Answer: It starts from local input evidence without the top-down goal, so it may build a valid local phrase that cannot attach to any derivation of S.
Exam lens
Define CFG constituents, then compare top-down and bottom-up by starting point, benefit, and failure mode. Include one derivation and mention ambiguity/PCFG ranking.
Rapid revision checklist
- Define constituency parse, terminal, nonterminal, span.
- State top-down vs bottom-up start points.
- Trace a short derivation.
- Contrast constituency with dependency.
Key takeaways
- Parsing searches grammar derivations that cover the input.
- Top-down is goal-directed; bottom-up is input-directed.
- The grammar can generate multiple structures; scoring selects among them.