# Q4a · Top-down syntax tree

Subject: Natural Language Processing

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/papers/legacy-f24/q4a

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/papers/legacy-f24--q4a/

Previous examination · complete worked answers

**Question. Explain the need for syntax parsing; compare top-down and bottom-up parsing. Parse “the cat chased the dog” using S→NP VP, NP→Det N, VP→V NP, Det→the, N→cat|dog, V→chased|saw.** [10 marks]

### Answer

**Top-down parsing** starts at the grammar's start symbol S and expands nonterminals until the leaves match the input words in order. **Recursive descent** commonly implements each nonterminal as a procedure that tries its productions. It builds from the root toward the leaves.

Start with S

→

Choose an allowed S production

→

Expand its next nonterminal

→

Match the resulting terminal to the input

→

Continue, or backtrack if the choice fails

**Algorithm.** Start with S as the current goal. Choose a production for the leftmost unexpanded nonterminal. Replace that nonterminal by the production's right side. If a terminal appears, compare it with the next input token. If it matches, consume the token; if it does not, reject that branch and try another production. Accept only when the complete input is consumed and all grammar goals are satisfied.

A **leftmost derivation** always expands the leftmost remaining nonterminal first. Top-down parsing can make guesses that the actual words cannot support, so it may need backtracking. A naive recursive-descent parser can loop on left-recursive rules such as NP→NP PP unless the grammar or algorithm is changed. Predictive LL(1) parsing chooses productions using one lookahead token when the grammar permits; not every English CFG is LL(1).

| Approach | Begins with | Direction | Common difficulty |
| --- | --- | --- | --- |
| Top-down | Start symbol S | Root to word leaves | Predictions that do not match input; left recursion |
| Bottom-up | Actual input tokens | Leaves to root S | Reductions that cannot contribute to a complete sentence |

**Yaad rakho:** Top-down: sentence ka structure pehle, words tak neeche aao.

**Bottom-up parsing** starts from the input tokens and combines them into larger constituents until the start symbol is reached. A **shift-reduce parser** maintains a stack of recognized material and a list of remaining input tokens.

| Action | Exact operation | Example |
| --- | --- | --- |
| Shift | Move the next input token onto the stack | Stack: the; remaining input: dog runs |
| Reduce | Replace a suffix of the stack matching a rule's RHS with its LHS | Det N becomes NP using NP→Det N |
| Accept | Stack is S and input is exhausted | Stack: S; input: empty |
| Fail/backtrack | Chosen reductions cannot complete a parse | A noun reading of book blocks an imperative parse |

Reduction uses a production in reverse: the grammar NP→Det N expands an NP top-down, but reduces Det N into NP bottom-up. The stack's **rightmost item is its top** in the traces below. Each row shows the state **after** the listed action, avoiding an off-by-one mismatch between actions and stack contents.

A lexical reduction such as N→dog still counts as a reduction. Do not skip the sequence from word to category to phrase when the question asks for a complete trace. Backtracking means returning to an earlier choice and trying another applicable rule, not changing the original input.

**Yaad rakho:** Shift = input se stack. Reduce = chhote pieces se bada grammatical unit.

### Exact top-down derivation

1. S
2. NP VP
3. Det N VP
4. the N VP
5. the cat VP
6. the cat V NP
7. the cat chased NP
8. the cat chased Det N
9. the cat chased the N
10. the cat chased the dog

SNPDettheNcatVPVchasedNPDettheNdog

[S [NP [Det the] [N cat]] [VP [V chased] [NP [Det the] [N dog]]]]

Parsing assigns constituent structure and grammatical relationships for extraction, translation and ambiguity resolution. Top-down expands from S toward input; bottom-up combines observed tokens toward S. This derivation uses only supplied rules.