# Q3A · Top-down parsing

Subject: Natural Language Processing

Exam: M2

Reader: https://deep-learning-study-room.vercel.app/nlp/#m2/papers/reexam-2026/reexam-2026-q3a

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/m2/papers/reexam-2026--reexam-2026-q3a/

M2-relevant questions from an actual TEE paper · original marks retained for longer practice

Question. In the context of natural language processing, explain the concept of top-down and bottom-up parsing approaches. Apply top-down syntax parsing approach to the sentence “The tall boy saw a girl in the park.” and draw a parse tree using the CFG grammar rules:  
S → NP VP; NP → Det Adj N | Det N; VP → V NP | VP PP; PP → P NP.  
Lexicon: Det → {the | a}; Adj → {tall}; N → {boy | girl | park}; V → {saw}; P → {in}. [10 marks]

### Answer

| Aspect | Top-down | Bottom-up |
| --- | --- | --- |
| Start | The start symbol S | The input words |
| Operation | Expand a nonterminal using grammar productions | Combine words and constituents using productions in reverse |
| Success | Leaves match the complete input | All input is reduced to S |
| Possible difficulty | Naive recursive descent can loop on left recursion or need backtracking | A naive shift-reduce parser may face shift/reduce conflicts |

### Given

The sentence contains the tokens the / tall / boy / saw / a / girl / in / the / park. Lowercase the initial “The” to match the lexicon. The full stop is punctuation outside the listed grammar.

### To find

A derivation beginning at S and a parse tree matching the whole sentence.

### Rule: which one and why

A context-free production replaces one nonterminal with its right-hand sequence. A top-down derivation begins at S and expands the desired structure. The supplied grammar attaches the PP through VP → VP PP; it does not provide NP → NP PP.

### Step 1. Expand the sentence

S ⇒ NP VP. Choose NP → Det Adj N for “the tall boy”.

### Step 2. Match the subject words

Det ⇒ the, Adj ⇒ tall, N ⇒ boy. The remaining material must be generated by VP.

### Step 3. Allow a verb phrase followed by a PP

Expand the outer VP using VP → VP PP. Then expand the inner VP using VP → V NP. This finite derivation selects the recursive rule once.

### Step 4. Match the verb and object

V ⇒ saw. Choose NP → Det N, then Det ⇒ a and N ⇒ girl.

### Step 5. Expand the prepositional phrase

PP ⇒ P NP. P ⇒ in. NP ⇒ Det N, with Det ⇒ the and N ⇒ park.

### Step 6. Check the complete leaf order

The leaves read “the tall boy saw a girl in the park”, exactly the normalized input. The PP “in the park” attaches to the VP under this supplied grammar.

SNPVPDetAdjNVPPPVNPPNPDetNDetNThetallboysawagirlinthepark

Top-down parse tree showing the PP attached to VP.

### Complete derivation

S ⇒ NP VP ⇒ Det Adj N VP ⇒ the tall boy VP ⇒ the tall boy VP PP ⇒ the tall boy V NP PP ⇒ the tall boy saw Det N PP ⇒ the tall boy saw a girl P NP ⇒ the tall boy saw a girl in Det N ⇒ the tall boy saw a girl in the park.

**Implementation caution:** VP → VP PP is left-recursive. A naive recursive-descent implementation may loop; it must transform or otherwise handle the grammar. A valid finite top-down derivation, as shown above, still exists.

**Yaad rakho:** Rule jo diya hai wahi use karo: yahan “in the park” VP ka part hai.