Natural Language Processing · TEE · papers

Q3a · Top-down restaurant parse

2024-02-12 · re-exam · recovered AI paper

Previous examination · complete worked answers

Question. Draw a top-down parse of “A restaurant serves dosas” using the printed grammar: S→NP VP | Aux NP VP | VP; NP→Pronoun | Proper-Noun | Det Nominal; Nominal→Noun | Nominal Noun | Nominal PP; VP→Verb | Verb NP | VP PP; PP→Prep NP. Lexicon: Det=A; Noun=restaurant,dosas; Verb=serves. [10 marks]

Answer

As printed, this grammar cannot derive the complete sentence. The object dosas is a Noun, but NP has no rule for a bare Nominal/Noun. NP→Det Nominal would require a determiner before dosas that is absent.

Clearly stated minimal repair

Add NP→Nominal. The repaired top-down derivation is:

StepSentential form
1S
2NP VP
3Det Nominal VP
4A Noun VP
5A restaurant Verb NP
6A restaurant serves Nominal
7A restaurant serves Noun
8A restaurant serves dosas
SNPDetANominalNounrestaurantVPVerbservesNPNominalNoundosas
[S [NP [Det A] [Nominal [Noun restaurant]]] [VP [Verb serves] [NP [Nominal [Noun dosas]]]]]

This tree uses the added rule only for the object. Do not silently pretend it is derivable under the original rule set. Left-recursive Nominal/VP alternatives require a terminating parser strategy; the displayed successful derivation chooses the needed finite branches.

Source / convention note. Original CFG is incomplete for the given bare-plural object. Exact failure and explicit repaired derivation are both shown.