Natural Language Processing · TEE · papers
Q3A · Ambiguity and bottom-up parsing
Solved final paper · December 2025
Actual final examination · 2 December 2025 · 100 marks · 3 hours
ii. Compare top-down and bottom-up parsing and apply bottom-up syntax parsing approach to the sentence “A cat chased the mouse” and draw a parse tree using the grammar rules:
S → NP 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, the}; Noun → {cat, mouse}; Verb → {chased}. [10 marks]
Answer
i. Types of ambiguity
Ambiguity exists when the same language expression permits more than one interpretation. The correct interpretation usually requires grammatical, semantic or contextual evidence.
| Type | Meaning | Example and readings |
|---|---|---|
| Lexical | One word has multiple meanings | “She visited the bank”: financial institution or riverbank |
| Syntactic | The sentence permits different structural attachments | “I saw the man with a telescope”: I used the telescope, or the man had it |
| Semantic / scope | A structured sentence permits different interpretations | “Every student read a book”: one shared book, or possibly a different book per student |
| Referential | A referring expression has more than one candidate referent | “Asha told Riya that she won”: she could refer to Asha or Riya |
| Pragmatic | Intention depends on the situation | “Can you open the door?” can ask about ability or request an action |
ii. Parsing approaches
| 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 five tokens are A / cat / chased / the / mouse. The supplied grammar permits determiner + nominal noun phrases and a verb + noun phrase verb phrase.
To find
A bottom-up sequence of reductions and a parse tree whose root is S and whose leaves preserve the input order.
Rule: which one and why
A production A → B C permits B C to be reduced to A. Bottom-up parsing begins with the words; lexical rules assign their categories, and phrase rules combine those categories.
Step 1. Assign lexical categories
A → Det; cat → Noun; chased → Verb; the → Det; mouse → Noun.
Step 2. Build the first noun phrase
cat is Noun. Reduce Noun to Nominal using Nominal → Noun. Then reduce Det Nominal, representing “A cat”, to NP.
Step 3. Build the object noun phrase
mouse is Noun. Reduce it to Nominal. Reduce “the” + “mouse”, now Det Nominal, to NP.
Step 4. Build the verb phrase
“chased” is Verb and “the mouse” is NP. Reduce Verb NP to VP.
Step 5. Build the sentence
The remaining constituents are NP (“A cat”) and VP (“chased the mouse”). Apply S → NP VP in reverse to obtain S. Every input token is used exactly once.
Final answer: [S [NP [Det A] [Nominal [Noun cat]]] [VP [Verb chased] [NP [Det the] [Nominal [Noun mouse]]]]].
Yaad rakho: Bottom-up: words se phrases, phrases se S. Top-down: S se words.