Natural Language Processing · TEE · papers

Q3A · Top-down parsing

Solved re-exam · February 2026

Actual re-examination · 9 February 2026 · 100 marks · 3 hours

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.

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.