21BME276T

Natural Language Processing

for Health Care Applications

UNIT 2 : SYNTAX ANALYSIS

■ Context Free Grammars

■ Grammar Rules for English
■ Top-Down Parsing
■ Bottom-Up Parsing
■ Ambiguity in Parsing
■ CKY Parsing
■ Dependency Parsing
■ Earley Parsing
■ Probabilistic Context-Free Grammars (PCFG)

Study Material | MCQs | 8-Mark Q&A; | 12-Mark Q&A;

Based on Jurafsky & Martin, Manning & Schutze
 SECTION 1: DETAILED NOTES

1. Context-Free Grammars (CFG)

A Context-Free Grammar (CFG) is a formal system used in computational linguistics to describe the syntactic
structure of natural languages. It is also called a Phrase Structure Grammar. CFGs are widely used in NLP
parsers to represent sentence structure.

Formal Definition: A CFG is a 4-tuple G = (N, T, P, S) where:

Symbol Meaning Example

N Set of Non-terminal symbols (variables) S, NP, VP, PP, Det, N, V

T Set of Terminal symbols (words) dog, runs, the, in, park
P Set of Production rules (rewrite rules) S → NP VP
S Start symbol S (Sentence)

Key Properties of CFG:

● Rules are of the form A → α, where A is a single non-terminal and α is a string of
terminals/non-terminals.
● CFGs can model recursive structures (e.g., nested clauses).
● They are more powerful than Regular Grammars but less than Context-Sensitive Grammars.
● Parse trees (derivation trees) represent the hierarchical structure of a sentence.
● CFGs generate a language: the set of all terminal strings derivable from S.

Example CFG for a simple English sentence:

S → NP VP
NP → Det N | Det N PP | Pronoun
VP → V NP | V NP PP | V
PP → Prep NP
Det → the | a | an
N → dog | cat | park | park | man
V → sees | chases | runs
Prep → in | on | with
Pronoun → he | she | it

Parse Tree Example: "The dog sees a man"

S
/\
NP VP
/\/\
Det N V NP
|||/\
The dog sees Det N
||
a man

2. Grammar Rules for English

English grammar rules in NLP specify how phrases are formed from words. These rules must handle noun
phrases, verb phrases, prepositional phrases, subordinate clauses and many other constructions.

Common Phrase Structure Rules:

Rule Expansion Meaning

S → NP VP Sentence A sentence = Noun Phrase + Verb Phrase

NP → Det N Noun Phrase NP can be a Determiner + Noun
NP → Det Adj N Noun Phrase Determiner + Adjective + Noun
VP → V NP Verb Phrase Transitive verb + object NP
VP → V NP PP Verb Phrase Verb + object + Prepositional Phrase
PP → Prep NP Prepositional Phrase Preposition + Noun Phrase
S → S conj S Coordination Two sentences joined by conjunction
NP → NP PP Attachment NP with prepositional modifier

Lexical Rules (Pre-terminal rules):

Lexical rules map parts of speech to actual words. For example:
Det → the | a | this | that | every
Noun → flight | meal | money | Dallas
Verb → is | prefer | like | need | want
Adj → cheapest | nonstop | first | available
Prep → from | to | on | in | through

Handling English Complexities:

● Agreement: NP must agree with VP in number (The dog runs / The dogs run).
● Subcategorization: Verbs can be intransitive (run), transitive (see + NP), or ditransitive (give + NP +
NP).
● Long-distance dependencies: 'What did you eat?' — 'what' is the object of 'eat' but appears at the
beginning.
● Coordination: Multiple NPs or VPs can be conjoined using 'and', 'or', 'but'.

3. Top-Down Parsing
Top-Down parsing starts with the start symbol S and attempts to derive the input sentence by successively
applying grammar rules. It works from the root of the parse tree downwards toward the leaves (words).

Algorithm: Recursive Descent Parsing

The most common top-down parser is the Recursive Descent Parser.

Steps:
1. Start with the start symbol S.
2. Predict: Select a grammar rule that expands the leftmost non-terminal.
3. Match: Compare predicted terminals against actual input words.
4. Backtrack: If a rule fails, undo and try the next rule.
5. Accept: If all input is matched with no non-terminals remaining.

Flowchart – Top-Down Parsing:

 START
|
v
Push Start Symbol S onto Stack
|
v
Is Top of Stack a Non-Terminal? --YES--> Expand using grammar rule
||
NO Push RHS onto stack
||
v [Loop back]
Top is Terminal -- Match with input word?
YES --> Pop stack, advance input
NO --> Backtrack, try next rule
|
v
Stack empty AND Input exhausted? --> ACCEPT
--> else REJECT

Advantages of Top-Down Parsing:

✓ Simple and intuitive to implement.
✓ Directly follows grammar rules.
✓ Well-suited for LL(1) grammars.

Disadvantages of Top-Down Parsing:

✗ Cannot handle left-recursive grammars (e.g., NP → NP PP leads to infinite loop).
✗ Backtracking makes it inefficient (exponential in worst case).
✗ Reparsed substrings multiple times (no memoization).
✗ Hypothesizes structures not supported by input.

4. Bottom-Up Parsing
Bottom-Up parsing starts from the input words (leaves) and applies grammar rules in reverse to reduce
substrings to non-terminals, eventually reducing everything to the start symbol S. This approach is also
called Shift-Reduce parsing.

Shift-Reduce Parsing Algorithm:

Two main operations:
1. SHIFT: Push the next input token onto the stack.
2. REDUCE: When the top of the stack matches the RHS of some rule A → α,
pop those symbols and push A.

Example: Parsing "The dog sees"

Stack | Input Remaining | Action
-------------------------------------------
[ ] | The dog sees | SHIFT
[ The ] | dog sees | SHIFT
[ The dog ] | sees | REDUCE: Det→The, N→dog
[ Det N ] | sees | REDUCE: NP→Det N
 [ NP ] | sees | SHIFT
[ NP sees ] | (end) | REDUCE: V→sees, VP→V
[ NP VP ] | (end) | REDUCE: S→NP VP
[ S ] | (end) | ACCEPT

Advantages of Bottom-Up Parsing:

✓ Handles a broader class of grammars.
✓ Never pursues analyses inconsistent with input words.
✓ Left-recursive grammars do not cause infinite loops.

Disadvantages:
✗ Shift-Reduce and Reduce-Reduce conflicts can arise.
✗ Harder to implement than top-down parsing.
✗ May build constituents inconsistent with the overall grammar.

5. Ambiguity in Parsing
Ambiguity occurs when a sentence or phrase can have more than one parse tree under a given grammar.
Ambiguity is extremely common in natural language and is one of the central challenges of NLP.

Types of Ambiguity:
Type Description Example

Lexical Ambiguity A word has multiple POS or meanings "bank" (river bank / financial bank)
Structural Ambiguity Sentence has multiple parse trees "I saw the man with a telescope"
PP Attachment Prepositional phrase can attach to different"She
constituents
ate pizza with a fork" vs "with mushrooms"
Coordination Scope of conjunction is ambiguous "old men and women" = old (men+women) or (old men)+w
Noun-Phrase Multiple NP boundaries "American history teacher" = American (history teacher) or

PP-Attachment Ambiguity Example (Jurafsky & Martin):

Sentence: "I shot an elephant in my pajamas"

Parse 1: [VP [V shot] [NP an elephant] [PP in my pajamas]]

→ The elephant is in my pajamas (unlikely!)

Parse 2: [VP [V shot] [NP [NP an elephant] [PP in my pajamas]]]

→ I was in my pajamas when I shot the elephant (intended)

Resolving PP-attachment is a key challenge in NLP. PCFGs and neural models help choose the most probable
parse.

Solutions to Ambiguity:
● Use Probabilistic Context-Free Grammars (PCFG) to assign probabilities to parses.
● Use lexical information (collocations, selectional preferences).
● Machine learning models trained on treebanks (Penn Treebank).
● Neural parsers use contextual embeddings to disambiguate.
6. CKY (Cocke-Kasami-Younger) Parsing
CKY is a bottom-up dynamic programming parsing algorithm for context-free grammars in Chomsky Normal
Form (CNF). It efficiently finds all possible parse trees by storing partial results in a 2D table.

Chomsky Normal Form (CNF) Requirements:

All grammar rules must be in ONE of these two forms:
1. A → B C (non-terminal produces exactly two non-terminals)
2. A → a (non-terminal produces exactly one terminal)

Any CFG can be converted to CNF without changing the language it generates.

CKY Algorithm:
Given: Input sentence w = w1 w2 ... wn and grammar G in CNF

Step 1: Initialize diagonal (span length = 1)

For each word wi, table[i][i] = {A | A → wi in P}

Step 2: Fill table for longer spans

For span length l = 2 to n:
For each start i, end j = i+l-1:
For each split point k (i to j-1):
For each rule A → B C:
If B in table[i][k] AND C in table[k+1][j]:
Add A to table[i][j]

Step 3: Accept if S in table[1][n], else Reject.

CKY Example: Parsing "She eats fish"

Grammar (CNF):
S → NP VP
VP → V NP
NP → She | fish
V → eats

Table (i,j) notation:

(1,1)=NP (She), (2,2)=V (eats), (3,3)=NP (fish)
(2,3): VP → V NP → VP is in (2,3)
(1,3): S → NP VP → S is in (1,3) ✓ ACCEPT

Properties of CKY:
● Time Complexity: O(n³ |G|) where n=sentence length, |G|=grammar size
● Space Complexity: O(n² |N|) for the parse table
● Completeness: Guaranteed to find ALL parses that exist
● Deterministic: No backtracking needed (dynamic programming)

7. Dependency Parsing
Dependency Parsing represents the grammatical structure of a sentence as a set of binary asymmetric
relations (dependencies) between words, called a dependency tree. Unlike phrase structure parsing, there
are no phrasal nodes — only word-to-word relationships.

Key Concepts:
● Head: The dominant word in a dependency relation (governs the dependent).
● Dependent: The word that modifies or completes the head.
● Dependency Relation: Typed arc from head to dependent (e.g., nsubj, dobj, det).
● Root: The head of the entire sentence (usually the main verb).

Universal Dependency Relations (UD):

Relation Full Name Example

nsubj Nominal Subject "Dogs bark" → bark ←nsubj— Dogs

dobj Direct Object "She eats fish" → eats ←dobj— fish
det Determiner "the dog" → dog ←det— the
amod Adjectival Modifier "big dog" → dog ←amod— big
prep Prepositional Modifier "ate in park" → ate ←prep— in
advmod Adverb Modifier "runs quickly" → runs ←advmod— quickly

Dependency Tree Example: "The doctor examines the patient"

examines (ROOT)
■■■ doctor (nsubj)
■ ■■■ The (det)
■■■ patient (dobj)
■■■ the (det)

Arcs: examines → doctor (nsubj), examines → patient (dobj),

doctor → The (det), patient → the (det)

Dependency Parsing Algorithms:

● Graph-based: Find the maximum spanning tree (MST) of the dependency graph (Eisner algorithm).
● Transition-based: Use a sequence of shift/reduce actions (Arc-Standard, Arc-Eager algorithms).
● Neural Dependency Parsers: Use LSTM or transformer encoders to predict arcs and labels.

Advantage over Phrase Structure:

Dependency trees are language-universal and handle free word-order languages (like Hindi, Turkish) better
than CFG-based phrase structures. They are also more directly useful for information extraction and clinical
NLP tasks.

8. Earley Parsing
Earley's algorithm is a chart-based top-down parsing algorithm that can handle any CFG including
ambiguous and left-recursive grammars. It uses dynamic programming to store intermediate results in a chart
(set of Earley items).

Earley Item:
An Earley item is written as: [A → α • β, i]
Where:
A → αβ is a grammar rule
 • (dot) marks how far parsing has proceeded
i is the start position in the input

Example: [VP → V • NP, 2] means:

We are parsing a VP, we have matched V starting from position 2,
and we still expect an NP.

Three Operations of Earley Parsing:

● PREDICTOR: If the next expected symbol (after •) is a non-terminal A, add new items for all rules A →
•α beginning at current position.
● SCANNER: If the next expected symbol (after •) is a terminal matching the current input word, advance
the dot.
● COMPLETER: If an item is complete (dot at end), look for items that were waiting for this non-terminal
and advance their dots.

Properties of Earley Algorithm:

● Time Complexity: O(n³) for ambiguous grammars, O(n²) for unambiguous, O(n) for LR grammars
● Left Recursion: Handles left-recursive grammars without infinite loops
● Coverage: Works for ALL CFGs (no CNF conversion needed)
● Chart: Avoids redundant computation via dynamic programming

9. Probabilistic Context-Free Grammars (PCFG)

A Probabilistic CFG (PCFG) extends a CFG by assigning a probability to each production rule. PCFGs allow
us to rank multiple parses and select the most likely (most probable) parse for an ambiguous sentence.

Formal Definition:
A PCFG is a 5-tuple: G = (N, T, P, S, D) where D is a probability distribution over rules.

For each non-terminal A, the probabilities of rules expanding A must sum to 1:

Σ P(A → α) = 1 for all rules with A on left-hand side

Example:
VP → V NP [P = 0.70]
VP → V NP PP [P = 0.20]
VP → V [P = 0.10]
Total = 1.00 ✓

Probability of a Parse Tree:

The probability of a parse tree T for sentence S is the product of probabilities of all rules used:

P(T, S) = ∏ P(rule i)

The most probable parse tree T* is selected:

T* = argmax P(T|S)

Estimating PCFG Probabilities from a Treebank:

Given a treebank (corpus of annotated parse trees), the maximum likelihood estimate is:
 P(A → β) = Count(A → β) / Count(A)

Example from Penn Treebank:

If NP appears 10,000 times and NP → Det N occurs 4,000 times:
P(NP → Det N) = 4000/10000 = 0.40

Probabilistic CKY (Inside Algorithm):

CKY can be extended for PCFGs using the Viterbi algorithm:

π[i][j][A] = maximum probability of any parse of wi...wj spanning [i,j] as A

Recurrence:
π[i][j][A] = max over (A→BC, i<k<j) of P(A→BC) * π[i][k][B] * π[k+1][j][C]

Limitations of PCFG:
✗ PCFGs are lexically unaware — the probability of NP-expansion does not depend on specific words.
✗ They do not capture structural preferences like close attachment or right attachment.
✗ Lexicalized PCFGs (Collins, Charniak) address these issues by conditioning on head words.
 SECTION 2: MULTIPLE CHOICE QUESTIONS (MCQs)
All Conceptual Questions — Unit 2: Syntax Analysis

Q1. A Context-Free Grammar is formally defined as a 4-tuple (N, T, P, S). What does 'P' represent?
A) A set of probability distributions
B) A set of production/rewrite rules
C) A set of parse trees
D) A set of programmatic tokens
■ Answer: (B) Explanation: In CFG, P denotes the set of production rules of the form A → α,
where A is a non-terminal.

Q2. Which of the following is NOT a required form in Chomsky Normal Form (CNF)?
A) A → BC
B) A → a
C) A → BCD
D) A → a (terminal)
■ Answer: (C) Explanation: CNF only allows binary branching (A → BC) or terminal production (A
→ a). Rules with three or more symbols on the RHS are not permitted.

Q3. Top-Down parsing begins with which symbol?

A) The last word of the sentence
B) The start symbol S
C) The first terminal of the grammar
D) The lowest-frequency word
■ Answer: (B) Explanation: Top-Down parsing begins with the start symbol S and tries to derive
the sentence by expanding rules.

Q4. Which problem specifically affects Top-Down parsers with left-recursive grammars?
A) Shift-Reduce conflict
B) Infinite loop
C) Stack overflow only in CNF
D) Reduce-Reduce conflict
■ Answer: (B) Explanation: Left-recursive rules like NP → NP PP cause the top-down parser to
recursively expand NP infinitely without consuming any input.

Q5. In Shift-Reduce parsing, what happens during a REDUCE action?

A) The next input token is pushed onto the stack
B) The top of the stack is compared to a terminal
C) Symbols matching the RHS of a rule are popped and replaced with the LHS non-terminal
D) The parser restarts from the start symbol
■ Answer: (C) Explanation: REDUCE pops symbols matching the RHS of a grammar rule and
replaces them with the LHS non-terminal, effectively building the tree bottom-up.

Q6. What is the time complexity of the CKY parsing algorithm?

A) O(n²)
B) O(n³|G|)
C) O(n log n)
 D) O(|G|²)
■ Answer: (B) Explanation: CKY has time complexity O(n³|G|) where n is the sentence length and
|G| is the grammar size, due to the three nested loops.

Q7. In Earley parsing, the PREDICTOR operation adds new chart entries for which type of symbols
after the dot?
A) Terminal symbols
B) Non-terminal symbols
C) Both terminals and non-terminals
D) Only verbs
■ Answer: (B) Explanation: PREDICTOR fires when the next expected symbol (after the dot) is a
non-terminal, adding all rules expanding that non-terminal.

Q8. In a PCFG, the probabilities of all rules expanding a particular non-terminal must:
A) Be equal
B) Sum to 1
C) Be greater than 0.5 each
D) Sum to the number of rules
■ Answer: (B) Explanation: For each non-terminal A, ΣP(A → α) = 1, making it a valid probability
distribution over expansions of A.

Q9. Which parsing approach is used by the CKY algorithm?

A) Top-Down with backtracking
B) Left-to-Right Top-Down
C) Bottom-Up Dynamic Programming
D) Random search with pruning
■ Answer: (C) Explanation: CKY is a bottom-up dynamic programming algorithm that fills a
triangular table, avoiding redundant recomputation.

Q10. Which type of ambiguity is exemplified by 'I saw the man with the telescope'?
A) Lexical ambiguity
B) Morphological ambiguity
C) Prepositional Phrase attachment ambiguity
D) Agreement ambiguity
■ Answer: (C) Explanation: PP attachment ambiguity: 'with the telescope' can modify 'saw' (I
used a telescope) or 'man' (the man had a telescope).

Q11. Dependency parsing differs from constituency parsing in that it:

A) Requires the grammar to be in CNF
B) Represents structure as word-to-word relations without phrasal nodes
C) Always produces a unique parse
D) Uses only context-sensitive grammars
■ Answer: (B) Explanation: Dependency trees show head-dependent binary relationships
between words directly, without hierarchical phrase nodes.

Q12. Which operation in Earley parsing fires when an item is complete (dot at the end)?
A) SCANNER
B) PREDICTOR
C) COMPLETER
 D) REDUCER
■ Answer: (C) Explanation: COMPLETER fires when an item's dot has reached the end of the
rule, advancing the dot in other items that were waiting for this completed constituent.

Q13. The grammar rule S → S conj S demonstrates which property of English grammar?
A) Subcategorization
B) Agreement
C) Coordination
D) Morphological derivation
■ Answer: (C) Explanation: The rule S → S conj S captures sentence coordination where two
sentences are joined by a conjunction like 'and', 'or', or 'but'.

Q14. Which algorithm is most appropriate to find ALL parses of an ambiguous sentence efficiently?
A) Recursive Descent
B) Shift-Reduce
C) CKY
D) Left-corner
■ Answer: (C) Explanation: CKY (via dynamic programming) is guaranteed to find all parses,
whereas recursive descent backtracks and shift-reduce may have conflicts.

Q15. In a dependency parse, what is the 'nsubj' label?

A) Noun subject relation — marks the nominal subject of a predicate
B) Nested subject clause
C) Nominal object relation
D) Non-standard subject marker
■ Answer: (A) Explanation: nsubj (nominal subject) is a Universal Dependency relation marking
the noun phrase that acts as the grammatical subject of the verb.

Q16. Which of the following best describes Earley's algorithm?

A) It is only applicable to CNF grammars
B) It uses top-down prediction with bottom-up recognition, based on chart parsing
C) It only works for unambiguous grammars
D) It uses beam search to prune improbable parses
■ Answer: (B) Explanation: Earley combines top-down prediction (PREDICTOR) and bottom-up
recognition (COMPLETER/SCANNER) in a chart to handle all CFGs efficiently.

Q17. Probabilistic CKY (Viterbi parse) selects the parse tree that:
A) Uses the fewest grammar rules
B) Maximizes the product of rule probabilities
C) Has the minimum depth
D) Matches the most frequent words
■ Answer: (B) Explanation: The probability of a parse tree is the product of the probabilities of all
rules used; Viterbi/PCKY finds the parse with maximum product.

Q18. What is a 'treebank' in the context of PCFG training?

A) A database of binary trees
B) A corpus of sentences annotated with parse trees
C) A collection of grammar rules only
D) A software tool for parsing
 ■ Answer: (B) Explanation: A treebank (e.g., Penn Treebank) is a linguistically annotated corpus
where sentences have been manually parsed to provide training data for PCFGs.

Q19. In CKY parsing, what must be true of the grammar before the algorithm can be applied?
A) All rules must be unary
B) Grammar must be in Chomsky Normal Form (CNF)
C) Grammar must have no epsilon rules only
D) Grammar must be right-recursive
■ Answer: (B) Explanation: CKY requires grammar rules to be in CNF (A→BC or A→a). Any CFG
can be converted to CNF before applying CKY.

Q20. Which of the following is an advantage of Dependency Parsing over Phrase-Structure Parsing
for healthcare NLP?
A) Requires larger training data
B) Directly captures semantic relationships between words, useful for extracting clinical facts
C) Only works for English
D) Does not require any training
■ Answer: (B) Explanation: Dependency parses directly show which words relate to which (e.g.,
drug→dosage, symptom→patient), making clinical information extraction more straightforward.
 SECTION 3: 8-MARK QUESTIONS WITH ANSWERS

Question 1 (8 Marks)
1. Define Context-Free Grammar (CFG). Explain its components with a suitable example and
draw a parse tree for the sentence 'The cat eats fish'.

Answer:
Definition:
A Context-Free Grammar (CFG) is a formal grammar G = (N, T, P, S) where:
• N = Non-terminals (e.g., S, NP, VP)
• T = Terminals (actual words like 'cat', 'eats')
• P = Production rules of the form A → α
• S = Start symbol (the sentence symbol)

Key Properties:
• Each rule has a single non-terminal on the left-hand side.
• The grammar generates sentences by repeatedly replacing non-terminals with the corresponding RHS.
• CFGs are closed under union, concatenation, and Kleene star.
• They generate Context-Free Languages (CFL), more powerful than Regular Languages.

Example Grammar:
S → NP VP
NP → Det N | Pronoun
VP → V NP
Det → the | a
N → cat | dog | fish
V → eats | chases

Derivation of 'The cat eats fish':

S ■ NP VP
■ Det N VP
■ The N VP
■ The cat VP
■ The cat V NP
■ The cat eats NP
■ The cat eats N
■ The cat eats fish

Parse Tree:
S
/\
NP VP
/\/\
Det N V NP
||||
The cat eats fish
 Significance: The parse tree makes the hierarchical syntactic structure explicit, showing that 'The cat' is
the subject (NP) and 'eats fish' is the predicate (VP). CFGs are the backbone of all syntax-based NLP
systems.

Question 2 (8 Marks)
2. Explain Top-Down and Bottom-Up Parsing. Compare them with advantages and
disadvantages.

Answer:
TOP-DOWN PARSING:
Top-Down parsing starts from the start symbol S and tries to derive the input sentence by expanding
grammar rules.

Algorithm (Recursive Descent):

1. Initialize with start symbol S.
2. Pick the leftmost non-terminal and apply a rule.
3. If the predicted terminal matches the input word, advance.
4. If not, backtrack and try the next applicable rule.
5. Accept when all input is consumed and the stack is empty.

Example: Parsing "The dog runs"

• Expand S → NP VP
• Expand NP → Det N; predict Det = "The" ✓, N = "dog" ✓
• Expand VP → V; predict V = "runs" ✓ → ACCEPT

BOTTOM-UP PARSING (Shift-Reduce):

Bottom-Up parsing starts from the input words and reduces them step by step to the start symbol S.

Operations:
• SHIFT: Push next input word onto stack.
• REDUCE: When stack top matches RHS of a rule, pop and replace with LHS.

Example: Parsing "The dog runs"

[The] → [Det] → [Det dog] → [Det N] → [NP] → [NP runs] → [NP V] → [NP VP] → [S] ✓

Comparison Table:
Aspect | Top-Down | Bottom-Up
Direction | Root → Leaves | Leaves → Root
Start Point | Start symbol S | Input words
Left Recursion | Problematic (loops) | Handles well
Backtracking | Required | Less needed
Efficiency | Exponential worst case| More efficient generally
Grammar Class | LL(k) grammars | LR(k) grammars
Conflicts | Left-recursion issues | Shift-Reduce conflicts
 Conclusion: Bottom-up parsers are preferred in practice (e.g., LALR parsers in compilers). For NLP,
chart-based parsers like CKY (bottom-up dynamic programming) are most efficient.

Question 3 (8 Marks)
3. Explain Ambiguity in natural language parsing. Discuss structural ambiguity and
PP-attachment ambiguity with examples and methods to resolve them.

Answer:
Ambiguity in NLP:
A sentence is ambiguous if it can be assigned more than one syntactic structure (parse tree) under a given
grammar. Ambiguity is pervasive in natural language and is fundamentally different from programming
languages.

Types of Ambiguity:
1. Lexical Ambiguity: A word has multiple meanings or POS tags.
Example: "She saw the bank." (financial bank or river bank?)

2. Structural/Syntactic Ambiguity: The same sequence of words can be organized into different phrase
structures.
Example: "old men and women" can mean:
• (old men) and (women) — only men are old
• old (men and women) — both are old

3. PP-Attachment Ambiguity (Most Common):

A prepositional phrase can attach to a verb or a noun.

Sentence: "The doctor examined the patient with a stethoscope"

Parse 1 (VP attachment):
VP → V NP PP: The doctor used a stethoscope to examine.

Parse 2 (NP attachment):

NP → NP PP: The patient had a stethoscope.

Both are syntactically valid; world knowledge favors Parse 1.

Another Classic Example (Marx Brothers):

"I shot an elephant in my pajamas"
• Intended: I was wearing pajamas when I shot the elephant.
• Humorous: The elephant was in my pajamas.

Methods to Resolve Ambiguity:

1. Probabilistic Context-Free Grammars (PCFG): Assign probabilities to grammar rules and select the
most probable parse. P(T) = product of all rule probabilities used.
 2. Lexicalized PCFGs: Condition probabilities on head words (Collins Parser). The probability of PP
attachment depends on the specific verb and noun involved.

3. Corpus Statistics: Learn from treebanks which attachments are more common for specific
verb-noun-preposition triples.

4. Neural Parsers: Use contextual word embeddings (BERT) which encode semantic meaning, allowing
models to prefer semantically coherent parses.

5. Selectional Preferences: Verbs prefer arguments of certain semantic types (e.g., "eat" prefers food
objects).

Significance in Healthcare NLP: Resolving ambiguity is critical for clinical text mining — "the patient with
diabetes and hypertension" must correctly identify comorbidities.

Question 4 (8 Marks)
4. Describe the CKY parsing algorithm. Illustrate with an example for the sentence 'She eats
fresh fish'. Show the parse table.

Answer:
CKY (Cocke-Kasami-Younger) Parsing:
CKY is a bottom-up dynamic programming algorithm that parses sentences in O(n³|G|) time using a
triangular chart table. It requires the grammar to be in Chomsky Normal Form (CNF).

CNF Requirements:
All rules must be either: A → BC or A → a

Example Grammar (CNF):

S → NP VP [0.9]
VP → V NP [0.8]
VP → VP PP [0.2]
NP → Det N [0.5]
NP → NP PP [0.2]
NP → Adj N [0.3]
Det → She, N → fish, V → eats, Adj → fresh

Input Sentence: She(1) eats(2) fresh(3) fish(4)

Algorithm Steps:
Step 1 — Fill diagonal (single words):
table[1,1] = {NP} (She is a Pronoun → treated as NP)
table[2,2] = {V} (eats)
table[3,3] = {Adj} (fresh)
table[4,4] = {N, NP} (fish can be N)
 Step 2 — Spans of length 2:
table[1,2]: NP(1,1) + V(2,2) → no matching rule
table[2,3]: V(2,2) + Adj(3,3) → no match
table[3,4]: Adj(3,3) + N(4,4) → NP via NP → Adj N ✓

Step 3 — Spans of length 3:

table[2,4]: V(2,2) + NP(3,4) → VP via VP → V NP ✓
table[1,3]: NP(1,1) + V+Adj → no valid NP/VP combo

Step 4 — Full span [1,4]:

table[1,4]: NP(1,1) + VP(2,4) → S via S → NP VP ✓ ACCEPT!

Parse Table Summary:

| She | eats | fresh | fish
She | NP | - | - | S
eats | --- | V | - | VP
fresh| --- | --- | Adj | NP
fish | --- | --- | --- | N

Result: S is in table[1,4] → Sentence is grammatical.

Parse: S → NP(She) + VP(eats + NP(fresh fish))

Key Properties:
• Guaranteed complete: finds ALL valid parses
• Handles ambiguity: multiple entries per cell represent alternative analyses
• No backtracking needed: dynamic programming stores sub-results

Question 5 (8 Marks)
5. Explain Dependency Parsing. Illustrate with a dependency tree for a medical sentence
and describe at least four dependency relations.

Answer:
Dependency Parsing:
Dependency parsing analyzes the grammatical structure of a sentence by identifying word-to-word
dependency relations rather than hierarchical phrase structures. The result is a dependency tree where:
• Nodes are words
• Directed arcs represent dependency relations from head to dependent
• One word (usually the main verb) is the root

Formal Properties:
• Each word has exactly one head (except the root)
• The structure forms a tree (connected, acyclic)
• Relations are typed (labeled arcs)

Universal Dependency Relations (Examples):

1. nsubj (Nominal Subject): The word that is the grammatical subject.
"The patient takes medication" → takes ←nsubj— patient

2. dobj (Direct Object): The direct object of the verb.

"The doctor prescribed antibiotics" → prescribed ←dobj— antibiotics

3. det (Determiner): Article or demonstrative modifying a noun.

"the medication" → medication ←det— the

4. amod (Adjectival Modifier): Adjective modifying a noun.

"severe headache" → headache ←amod— severe

5. nmod (Nominal Modifier): A noun modifying another noun.

"chest pain" → pain ←nmod— chest

6. advmod (Adverbial Modifier): An adverb modifying the verb.

"chronically ill" → ill ←advmod— chronically

Medical Example Sentence:

"The elderly patient was prescribed high-dose aspirin for chest pain."

Dependency Tree:
prescribed (ROOT)
■■■ patient (nsubjpass)
■ ■■■ The (det)
■ ■■■ elderly (amod)
■■■ aspirin (dobj)
■ ■■■ high-dose (amod)
■■■ pain (nmod:for)
■■■ chest (compound)

Dependency Arcs:
• prescribed → patient (nsubjpass): patient is the passive subject
• prescribed → aspirin (dobj): aspirin is the medication prescribed
• aspirin → high-dose (amod): high-dose modifies aspirin
• prescribed → pain (nmod): chest pain is the indication

Applications in Healthcare NLP:

• Extracting drug-disease relationships from EHRs
• Identifying who prescribed what and to whom
• Clinical information extraction: symptom-body part associations
• Coreference resolution in clinical notes
SECTION 4: 12-MARK QUESTIONS WITH DETAILED ANSWERS

Question 1 (12 Marks)

1. Explain Probabilistic Context-Free Grammars (PCFGs) in detail. Describe how
probabilities are assigned and estimated, how the most probable parse is computed, and
discuss the limitations of PCFGs. (12 Marks)

Detailed Answer:
PROBABILISTIC CONTEXT-FREE GRAMMARS (PCFG)

1. Motivation:
Plain CFGs accept or reject sentences but cannot rank multiple valid parses of an ambiguous sentence.
PCFGs solve this by attaching probabilities to production rules, enabling selection of the most likely parse.

2. Formal Definition:
A PCFG is a 5-tuple: G = (N, T, P, S, D) where:
• N = Non-terminals, T = Terminals, P = Production rules, S = Start symbol
• D = Probability distribution: each rule A → α has probability P(A → α)
• Constraint: For every non-terminal A: Σ P(A → α) = 1

3. Example PCFG:
S → NP VP [1.0]
NP → Det N [0.5]
NP → Pronoun [0.3]
NP → NP PP [0.2]
VP → V NP [0.7]
VP → V NP PP [0.2]
VP → V [0.1]
PP → Prep NP [1.0]
Det → the [0.6] | a [0.4]
N → man [0.3] | dog [0.3] | park [0.4]
V → saw [0.5] | chased [0.5]
Prep → in [0.6] | with [0.4]

4. Probability of a Parse Tree:

P(T, S) = Π P(A → α) for all rules used in T

Example: For parse tree of "the dog saw a man":

P = P(S→NPVP) × P(NP→DetN) × P(Det→the) × P(N→dog)
× P(VP→VNP) × P(V→saw) × P(NP→DetN) × P(Det→a) × P(N→man)
= 1.0 × 0.5 × 0.6 × 0.3 × 0.7 × 0.5 × 0.5 × 0.4 × 0.3
= 0.00189

5. Estimating Probabilities from a Treebank:

Maximum Likelihood Estimation (MLE):
P(A → β) = Count(A → β) / Count(A)

Penn Treebank Example:

If VP appears 15,000 times and VP → V NP occurs 10,500 times:
P(VP → V NP) = 10,500 / 15,000 = 0.70

6. Finding the Most Probable Parse — Viterbi CKY:

The probabilistic CKY (Inside-Viterbi) algorithm finds T* = argmax P(T|S):

Initialization: π[i,i,A] = P(A → wi) for each word wi

Recurrence (for span [i,j]):

π[i,j,A] = max over (A→BC, i≤k<j) of:
P(A→BC) × π[i,k,B] × π[k+1,j,C]

Backpointers: Store argmax choices to reconstruct the best parse tree.

Final Answer: T* = parse corresponding to π[1,n,S]

7. Inside Algorithm (Computing Probability of Sentence):

α[i,j,A] = Σ P(A→BC) × α[i,k,B] × α[k+1,j,C] (sum over ALL parses, not max)
P(S | Grammar) = α[1,n,S]

8. Limitations of PCFGs:

(a) Lexical Insensitivity:

PCFG rule probabilities do not depend on specific words. The probability of NP → NP PP is the same
regardless of whether the head noun is "telescope" or "banana". Lexicalized PCFGs (Collins, 1997) fix this
by conditioning on head words.

(b) Independence Assumption:

Rule probabilities are assumed independent — the expansion of a non-terminal doesn't depend on the
surrounding context. This ignores important structural preferences.

(c) Structural Preferences Not Captured:

English has a right-attachment preference for PPs and a preference for shorter dependencies. Basic
PCFGs ignore these tendencies.

(d) Treebank Bias:

Estimated probabilities depend heavily on the treebank domain. A grammar trained on Wall Street Journal
text performs poorly on medical text (domain mismatch).

(e) Solutions and Extensions:

• Lexicalized PCFGs: P(A(h) → B(h) C(h')) conditions on head word h
• Parent annotation: Condition rules on the parent non-terminal
 • Neural PCFGs: Use LSTM/Transformer encoders to compute rule probabilities
• Discriminative parsers: Use maximum entropy or SVM instead of generative model

9. Significance in Healthcare NLP:

• PCFGs trained on clinical treebanks (e.g., MiPACQ, i2b2) parse medical text.
• BioBERT-enhanced parsers apply neural PCFGs to biomedical literature.
• Used for clinical trial eligibility extraction, EHR information retrieval.

Question 2 (12 Marks)

2. Explain the Earley parsing algorithm in detail with its three operations. Show how it
processes the sentence 'Dogs chase cats' step by step using an Earley chart. Compare
Earley with CKY parsing. (12 Marks)

Detailed Answer:
EARLEY PARSING ALGORITHM

1. Introduction:
Earley's algorithm (Jay Earley, 1970) is a chart-based, top-down dynamic programming parser that works
for ALL context-free grammars including ambiguous and left-recursive ones. It uses a chart of Earley items
to avoid recomputation.

2. Earley Item:
Format: [A → α • β, j] where:
• A → αβ is a grammar rule
• α = portion already parsed (before dot)
• β = portion yet to parse (after dot)
• j = input position where this constituent began

Example: [VP → V • NP, 2] = "We're parsing VP, matched V starting at position 2, expecting NP next."

3. Three Operations:

PREDICTOR:
When the next expected symbol (after •) is a non-terminal B:
For each rule B → γ in grammar, add item [B → • γ, current_pos] to chart

SCANNER:
When the next expected symbol (after •) is a terminal a:
If current input word = a, add [A → αa •, j] to next chart entry

COMPLETER:
When item [A → α •, j] has dot at end (completed):
Find all items [B → β • Aγ, k] and add [B → βA • γ, k] to current chart
4. Example Grammar:
S → NP VP
NP → N
VP → V NP
N → Dogs | cats
V → chase

5. Step-by-Step Parsing of "Dogs(0) chase(1) cats(2)"

(Positions: 0=before Dogs, 1=between Dogs/chase, 2=between chase/cats, 3=end)

Chart[0] (before any input):

Init: [S → • NP VP, 0] (initial item)
PREDICT S→NP VP: [NP → • N, 0]
PREDICT NP→N: [N → • Dogs, 0]

Chart[1] (after scanning 'Dogs'):

SCAN 'Dogs': [N → Dogs •, 0]
COMPLETE N: [NP → N •, 0]
COMPLETE NP: [S → NP • VP, 0]
PREDICT VP: [VP → • V NP, 0]
PREDICT V: [V → • chase, 0]

Chart[2] (after scanning 'chase'):

SCAN 'chase': [V → chase •, 1]
COMPLETE V: [VP → V • NP, 0]
PREDICT NP: [NP → • N, 2]
PREDICT N: [N → • cats, 2]

Chart[3] (after scanning 'cats'):

SCAN 'cats': [N → cats •, 2]
COMPLETE N: [NP → N •, 2]
COMPLETE NP: [VP → V NP •, 0]
COMPLETE VP: [S → NP VP •, 0] ← COMPLETE PARSE FOUND!

Since [S → NP VP •, 0] is in Chart[3], the sentence is accepted! ✓

6. Earley vs CKY — Comparison:

Feature | Earley | CKY
Grammar Req. | Any CFG | Chomsky Normal Form only
Direction | Top-down with bottom-up recog. | Pure bottom-up
Left Recursion | Handled correctly | Handled (after CNF convert)
Complexity | O(n³) general, O(n²) unamb. | O(n³|G|) always
Chart Structure | 1D array of sets | 2D triangular table
Ambiguity | All parses found | All parses found
Implementation | Complex (3 operations) | Simpler to implement
 Best For | Arbitrary CFGs, online parsing| Fixed CNF grammars, PCFG

7. Properties of Earley Algorithm:

• O(n³) for ambiguous grammars (same as CKY)
• O(n²) for unambiguous grammars
• O(n) for LR(k) grammars (most common English grammars)
• Correct handling of left-recursive rules
• Does not need grammar transformation

8. Application in NLP:
• Used in speech recognition systems (Jelinek-Lafferty integration)
• Foundation for probabilistic chart parsing
• Integrated with PCFGs for medical text parsing in clinical decision support
• Used in question answering and information extraction pipelines

Question 3 (12 Marks)

3. Write a comprehensive essay on Syntax Analysis covering: (a) the role of syntax in NLP,
(b) types of parsing algorithms, (c) handling ambiguity with PCFGs, and (d) applications in
healthcare NLP. (12 Marks)

Detailed Answer:
SYNTAX ANALYSIS IN NATURAL LANGUAGE PROCESSING

(a) Role of Syntax in NLP:

Syntax is the study of the rules governing the arrangement of words to form sentences. In NLP, syntactic
analysis (parsing) is crucial for:
• Understanding sentence structure beyond individual word meanings
• Identifying grammatical relationships: subject, object, modifier
• Enabling downstream tasks: semantic parsing, information extraction, machine translation
• Detecting ill-formed sentences or identifying sentence boundaries

The syntactic structure of "The drug reduces inflammation" is fundamentally different from "Inflammation
reduces the drug" — same words, different meaning. Syntax captures this.

Levels of syntactic structure:

• Word order and constituent structure
• Phrase types: NP, VP, PP, AdjP, AdvP
• Clausal structure: main clause, subordinate clause, relative clause
• Agreement, case, subcategorization

(b) Types of Parsing Algorithms:

1. Recursive Descent (Top-Down):

Starts from S, predicts and matches. Simple but cannot handle left-recursive grammars and requires
backtracking (O(2■) worst case).

2. Shift-Reduce (Bottom-Up):
Builds constituents from words upward. Handles left-recursion but can have shift-reduce conflicts. Used in
LR parsers.

3. CKY (Dynamic Programming):

O(n³|G|) bottom-up chart parser for CNF grammars. Guaranteed complete, no backtracking. Standard for
PCFG parsing.

4. Earley Algorithm:
Top-down prediction + bottom-up recognition. Works for all CFGs. O(n³) general, O(n) for LR grammars.
Most flexible.

5. Dependency Parsing:
Word-to-word relations. Transition-based (Arc-Standard) or graph-based (MST). Particularly useful for free
word-order languages and clinical NLP.

6. Neural Parsers:
Deep learning models (BiLSTM, Transformer) trained on treebanks. Learn representations that capture
syntactic and semantic patterns jointly.

(c) Handling Ambiguity with PCFGs:

Natural language is massively ambiguous. A sentence of 20 words can have billions of parse trees.
PCFGs provide a probabilistic framework for disambiguation.

PCFG Framework:
Each rule A → α has probability P(A → α), and Σ P(A → α) = 1 per non-terminal.
P(T) = Π P(r■) for all rules r■ in T.
Best parse: T* = argmax P(T|sentence)

Estimation from Treebank:

P(A → β) = Count(A → β) / Count(A)
Penn Treebank (1 million words) is the standard resource.

Probabilistic CKY (Viterbi):

π[i,j,A] = max(k, B, C) P(A→BC) × π[i,k,B] × π[k+1,j,C]
Backpointers allow reconstruction of T*.

Advanced PCFG Improvements:

• Lexicalized PCFGs: condition on head words to capture verb-object preferences
• Parent-annotated grammars: NP^S vs NP^VP behave differently
• Neural PCFGs: use BERT embeddings to estimate context-sensitive rule probabilities

(d) Applications in Healthcare NLP:

1. Clinical Information Extraction:
Parsing EHR text to extract structured facts:
• "Patient presents with acute chest pain radiating to left arm"
• Dependency parse identifies: presents←nsubj—Patient, pain←dobj—presents,
radiating←amod—pain, arm←nmod—radiating
• Extracted: Symptom=chest pain, Qualifier=acute, Location=left arm

2. Drug-Disease Relation Extraction:

Syntactic paths in dependency trees between drug and disease entities indicate relations like treats,
causes, contraindicated.
Example: "Metformin reduces blood glucose in diabetic patients"
→ Dependency path: Metformin —nsubj→ reduces ←dobj— glucose

3. Clinical Trial Matching:

Parsing eligibility criteria sentences (complex conditionals, negations) to extract structured
inclusion/exclusion rules using PCFGs.

4. Medical Question Answering:

Parsing medical questions to identify question type, focus, and expected answer type. CFG-based
question parsers transform "What are the side effects of aspirin?" into a structured query.

5. Negation and Uncertainty Detection:

Syntactic scope of negation words (not, no, without, without history of) is determined by parse structure.
"Patient has no fever" — negation scopes over 'fever'. Critical for clinical decision support.

6. Generating Clinical Reports:

Syntax-guided generation models use grammar rules to ensure generated reports are grammatically
well-formed and clinically coherent.

Conclusion:
Syntax analysis forms the backbone of NLP processing pipelines. From classical CFGs to neural
dependency parsers, syntactic knowledge enables machines to understand the structure of human
language and extract meaningful clinical information from unstructured medical text.
21BME276T — Natural Language Processing for Health Care Applications
Unit 2: Syntax Analysis | Study Material Compiled from Jurafsky & Martin, Manning & Schutze