Module 3

SYNTACTIC ANALYSIS : Context-Free Grammars, Grammar rules for English,

Treebanks, Normal Forms for grammar – Dependency Grammar – Syntactic
Parsing, Ambiguity, Dynamic Programming parsing – Shallow parsing –
Probabilistic CFG, Probabilistic CYK, Probabilistic Lexicalized CFGs - Feature
structures, Unification of feature structures.
SYNTACTIC ANALYSIS
Syntactic parsing (or just "parsing") is about figuring out the grammar
structure of a sentence.
Imagine you are trying to understand a sentence not just by knowing the
meaning of individual words, but by looking at how those words are arranged
and related to each other — just like how we learn grammar in school.
Syntax means the rules of sentence structure — like where nouns and verbs
go, what comes before what, and how words form phrases.
Example:
• Sentence: The cat sat on the mat
• Syntax tells us:
o "The cat" is a noun phrase
o "sat on the mat" is a verb phrase
o Together, they form a complete sentence
Syntactic Tree Structure
A tree diagram is used to represent the structure of a sentence.
How does it look?
• The root of the tree is the whole sentence (S).
• Each node (branch point) represents a grammatical unit like a phrase.
• Each leaf (end point) is an individual word.
Example Tree:
nginx
CopyEdit
S
/\
NP VP
/ / \

1
 The V NP
| |
sat on the mat
Here:
• NP = Noun Phrase
• VP = Verb Phrase
• V = Verb
This shows how the sentence is built from phrases and words.
Context-Free Grammars
What is Context-Free Grammar?
Context-Free Grammar (CFG) is a formal system of rules used to describe the
structure of sentences in a language.
Think of it like a set of instructions or blueprints that tell you:
• How sentences can be built from smaller parts like words and phrases
• How to analyze or generate a sentence
Background:
• Introduced by Noam Chomsky in 1957
• Designed to model natural languages like English, and later used in
computer science (like compilers)
A CFG Has Four Components
Let’s understand each part one by one:
i. Non-terminal Symbols (N)
• These are like building blocks.
• They are not actual words, but labels for phrases or categories like:
o S = Sentence
o NP = Noun Phrase
o VP = Verb Phrase
o V = Verb, N = Noun
These symbols help us build the structure of the sentence.
ii. Terminal Symbols (T)
• These are the actual words in the language.

2
 • Examples: "Hena", "reads", "a", "book".

✔ Terminal symbols are the leaves of the tree — the final output (what you
see in a sentence).
iii. Start Symbol (S)
• This is where we start building the sentence.
• Usually, S stands for the whole Sentence.
iv. Production Rules (P)
• These are the grammar rules that show how non-terminals can be
expanded.
• Written in this format:
A→αA
Where A is a non-terminal
o α is a combination of non-terminals and/or terminals
Example Production Rule:
S→NP VPS
Means:
A sentence is made of a Noun Phrase (NP) followed by a Verb Phrase (VP).
These are called phrase structure rules because they define the structure of
phrases.
CFG as a Generator
CFG can be used in two ways:
1. To Generate Sentences
Like saying:
“Let’s build a sentence step by step using grammar rules.”
We start from S (the start symbol), and keep replacing symbols using the rules
until we get an actual sentence.
2. To Analyze (Parse) Sentences
Like saying:
“Here is a sentence. Let’s break it down and figure out its structure.”
We go in reverse — from sentence to structure.
Example: Sentence Generation Using CFG

3
Let’s use this toy grammar (a small sample grammar):

Rule No. Rule

R1 S → NP VP

R2 NP → N

R3 NP → Det N

R4 VP → V NP

R5 V → reads

R6 N → Hena

R7 N → book

R8 Det → a

Let’s generate the sentence:

"Hena reads a book"
Step-by-Step Derivation:
1. Start from S
S → NP VP (R1)
2. Expand NP
NP → N (R2) → N → Hena (R6)
So NP becomes "Hena"
3. Expand VP
VP → V NP (R4)
Now we expand:
o V → reads (R5)
o NP → Det N (R3)
▪ Det → a (R8)
▪ N → book (R7)
4. Putting it all together:
o S → NP VP
o NP → Hena
o VP → reads NP
o NP → a book

4
Final sentence:
Hena reads a book
Parse Tree Representation
We can represent the structure we just built using a tree:
S
/\
NP VP
| / \
Hena V NP
| /\
reads Det N
| |
a book
• The root is S (the sentence)
• The leaves are the actual words
Bracketed Notation
This is a compact way to show the same tree using square brackets:
[S
[NP [N Hena]]
[VP [V reads]
[NP [Det a] [N book]]]]
You read it like nested folders:
• S has two parts: NP and VP
• VP has a verb and another NP
Grammar rules for English:
What Are Grammar Rules?
Grammar rules describe how words and phrases are arranged in English
sentences. They help define:
• What makes a valid sentence
• How to group words into phrases
• What order to use for subjects, verbs, and objects

5
In computational linguistics and NLP, these rules are written using CFG-style
production rules.
Grammar Rule Format:
Each grammar rule is written like:
A→BC
Which means:
The symbol A can be replaced by B C
This is like saying:
A sentence (A) is made of a noun phrase (B) followed by a verb phrase (C)
Basic Grammar Rules for English (CFG Style)
Here’s a set of simplified English grammar rules, explained clearly.
1. Sentence Rule
S → NP VP
A Sentence (S) consists of a:
• Noun Phrase (NP) (who or what the sentence is about)
• Verb Phrase (VP) (what the subject does or what happens to it)
Example:
• "The boy (NP) is playing (VP)"
2. Noun Phrase Rules (NP)
Noun phrases refer to people, things, or ideas. They can be simple or detailed.
Basic structures:
NP → Det N
NP → Det Adj N
NP → N
NP → PN

Symbol Meaning

Det Determiner (the, a, an, some)

Adj Adjective (beautiful, small)

N Common noun (dog, book)

6
Symbol Meaning

PN Proper noun (John, India)

Examples:
• Det N → "The cat"
• Det Adj N → "A small girl"
• PN → "Ram"
3. Verb Phrase Rules (VP)
Verb phrases describe actions or states. They often include a verb and other
parts.
Examples:
VP → V
VP → V NP
VP → V NP PP
VP → V Adj

Symbol Meaning

V Verb (eats, sleeps, plays)

NP Noun Phrase (an apple)

PP Prepositional Phrase (on the table)

Adj Adjective (happy)

Examples:
• VP → V → "sleeps"
• VP → V NP → "ate an apple"
• VP → V NP PP → "placed the book on the table"
• VP → V Adj → "is happy"
4. Prepositional Phrase Rules (PP)
Prepositional phrases give extra information about time, place, or manner.
PP → P NP

Symbol Meaning

P Preposition (on, in, at, with)

7
Symbol Meaning

NP Noun Phrase

Example:
• PP → P NP → "on the table"
5. Determiner Rules (Det)
Det → the | a | an | some | many
These are words that come before nouns.
6. Adjective Rules (Adj)
Adj → small | beautiful | tall | red
These are descriptive words that modify nouns.
7. Verb Rules (V)
V → eats | sleeps | plays | is | likes | gives
These are action or linking verbs.
8. Noun Rules (N)
N → cat | apple | table | girl | boy | book
These are common nouns.
9. Proper Noun Rules (PN)
PN → John | Mary | India | Hena
These are names of people or places.
Example: Full Sentence Derivation
Let's derive this sentence using grammar rules:
"The girl reads a book"
Step-by-step:
1. S → NP VP
2. NP → Det N → "The girl"
o Det → the
o N → girl
3. VP → V NP → "reads a book"
o V → reads
o NP → Det N

8
 ▪ Det → a
▪ N → book
Sentence built: "The girl reads a book"
Parse Tree:
S
/\
NP VP
/\ /\
Det N V NP
| || /\
the girl reads Det N
| |
a book
Why Are These Rules Useful?
• They help computers understand sentence structure
• Allow NLP programs to parse, tag, or translate language correctly
• Used in syntax checkers, machine translation, chatbots, and grammar
correction tools
Summary Table

Rule Type Format Example

Sentence S → NP VP The girl reads a book

Noun Phrase NP → Det N a book

Verb Phrase VP → V NP reads a book

Prepositional Phrase PP → P NP on the table

Determiners `Det → a the`

Verbs `V → eats reads`

Nouns `N → girl book`

Proper Nouns `PN → John Mary`

9
Treebanks
Treebanks: A Data-Driven Approach to Syntax
What is Parsing?
Parsing means analyzing a sentence to understand how words fit together
grammatically.
For example:
Sentence: "The girl eats an apple."
A parser tries to find out:
• What is the subject? (“The girl”)
• What is the verb? (“eats”)
• What is the object? (“an apple”)
But the sentence doesn't say that directly — the parser recovers this hidden
structure.
What Does the Parser Need?
Just the sentence is not enough. The parser needs two things:
1. Grammar rules – How words can combine.
2. Common sentence patterns – Which structures are more likely.
Option 1: Use Grammar Rules (CFGs)
We can write rules like:
S → NP VP
NP → Det N
VP → V NP
These are Context-Free Grammar (CFG) rules.
But natural languages like English, Tamil, Hindi, etc. are too complex to
write all possible CFG rules manually.
Problem: Two Challenges in Syntax Parsing
1. Grammar bottleneck: It's hard to write a complete set of grammar rules
for any language.
2. Ambiguity: For one sentence, there may be many possible grammar
trees. Which one is correct?
Example: "I saw the man with a telescope."
This can mean:

10
 • I used a telescope to see the man.
• I saw a man who had a telescope.
Which is correct? That’s the second challenge.
Treebank: A Better Way (Data-Driven Approach)
What is a Treebank?
A Treebank is a collection of sentences, where:
• Each sentence is labeled with its correct syntax tree.
• A human expert has checked and selected the most likely (plausible)
analysis.
• The entire dataset is consistent and follows annotation guidelines.
Why is Treebank Useful?
Treebank helps with both major problems:

Problem Treebank Solution

Grammar is hard Treebank directly shows syntax trees, no need to write

to write grammar.

Which structure Treebank shows the most plausible structure (chosen by

is best? experts), so machine learning can learn from it.

What Does Treebank Contain?

• Sentences like: “The boy is running.”
• A complete parse tree or dependency structure
• Judged by a linguist/human expert
• No fixed grammar rules listed — but trees reflect the grammar
indirectly.
How Does a Parser Learn from a Treebank?
Using Supervised Machine Learning, a parser can:
• Look at thousands of example sentences
• Learn to score different possible parses
• Predict the best parse for new unseen sentences
Two Types of Tree Structures
1. Phrase Structure Trees (Constituency Grammar)
• Used in English, French

11
 • Shows how words group into phrases (NP, VP, PP, etc.)

🔸 Example:
S
/\
NP VP
| /\
"He" V NP
| |
"ate" "apple"
2. Dependency Trees (Dependency Grammar)
• Shows how words depend on each other
• Used in free word order languages like Czech, Turkish, Hindi, Tamil

🔸 Example:
ate
/ \
He apple
Here, "ate" is the main verb, "He" is the subject, and "apple" is the object.
Difference Between Phrase Structure & Dependency Grammar

Feature Phrase Structure Grammar Dependency Grammar

Shows Phrase groups (NP, VP) Word-to-word links

Languages English, French Hindi, Tamil, Czech

Use Better for complex sentence patterns Better for flexible word order

Related Grammar Concepts

🔸 NLP and Grammar

• NLP = Computers understanding human language.
• Every language has a structure or grammar.
• Grammar defines: what is valid and what is not.

🔸 Word Order in Languages

12
Language Typical Order Example

English SVO (Subject Verb Object) I eat mango

Hindi SOV (Subject Object Verb) मैं आम खाता हूँ (I mango eat)

Three Main Grammar Types in NLP

Type Description

1. Context-Free
Rules like S → NP VP, using non-terminal symbols.
Grammar (CFG)

2. Constituency Uses phrase structures (NP, VP, etc.) — shows how

Grammar phrases group.

3. Dependency Focuses on word-level dependencies (who depends

Grammar on whom) — useful for free word order.

Summary

Concept Meaning

Annotated corpus with correct syntax trees for each

Treebank
sentence

Parsing Finding the grammar structure of a sentence

CFG Rule-based grammar

Phrase Structure
Shows phrases and subphrases
Tree

Dependency Tree Shows direct word-to-word grammatical relations

Machine Learning Learns to parse by analyzing thousands of treebank

Use examples

Normal Forms for grammar

What is a Grammar?
Grammar consists of rules that define how sentences are formed.
Example rule:
S → NP VP
VP → V NP
NP → Det N

13
These are Context-Free Grammar (CFG) rules — they show how to break down
a sentence into parts.
But for parsing algorithms (used by computers), we sometimes need to convert
these rules into a special format, called a normal form.
What is a Normal Form?
A Normal Form is a standard, simplified version of a grammar.
• It makes parsing easier for computers.
• It helps in designing algorithms like CYK parser or PDA (Pushdown
Automata).
• It simplifies the structure of grammar rules.
Two Main Types of Normal Forms in CFG
1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)
1. Chomsky Normal Form (CNF)
What is CNF?
In Chomsky Normal Form, grammar rules follow this format:
1. A → BC
(Two non-terminals on the right-hand side)
2. A → a
(A single terminal)
A, B, C are variables (non-terminal symbols)
a is a terminal (like "dog", "run", "book")
Not Allowed in CNF:
• Rules like A → BCD (more than 2 non-terminals)
• Rules like A → aB (mix of terminal + non-terminal)
• Rules like A → ε (empty string) — unless specially handled
Example: Convert to CNF
Given:
S → NP VP
VP → V NP
NP → Det N
Step-by-step conversion:

14
S → A B (where A = NP, B = VP)
VP → C D (C = V, D = NP)
NP → E F (E = Det, F = N)
All rules now follow: A → BC or A → a
Why CNF is Useful?
• Works well with CYK Parsing algorithm (used in NLP and compilers)
• Easier to process in bottom-up parsing
2. Greibach Normal Form (GNF)
What is GNF?
In Greibach Normal Form, grammar rules follow this format:
A→aα
Where:
• A is a non-terminal
• a is a terminal
• α is a string of non-terminals (can be empty)
Each rule must start with a terminal followed by zero or more non-terminals.
Example: Convert to GNF
Given:
S→aA
A→b
This is already in GNF format:
• First symbol on right is a terminal
• Followed by non-terminals (optional)
Why GNF is Useful?
• Used in designing top-down parsers
• Helps in eliminating left recursion
• Makes recursive descent parsing possible
Comparison: CNF vs GNF

15
Feature Chomsky Normal Form (CNF) Greibach Normal Form (GNF)

Rule Form A → BC or A → a A→aα

Useful for Bottom-up parsing (CYK) Top-down parsing

Terminals At the end or alone At the beginning

Parsing Style Efficient algorithms Recursion-based parsing

Why Convert to Normal Form?

• Makes parsing fast and uniform
• Simplifies grammar analysis
• Ensures that algorithms (like parsers) can be implemented easily
• Used in both NLP and Compiler Design
Summary in Simple Terms

Term Meaning

Grammar Set of rules to form sentences

Normal Form A simplified, standard version of grammar

CNF Rules: A → BC or A → a

GNF Rules: A → a α

Why Needed Makes it easier for computers to parse language

Used In NLP parsing, compilers, formal language theory

Dependency Grammar
1. What is Dependency Grammar?
Dependency Grammar (DG) is a system of grammar that describes sentence
structure by showing how words depend on one another.
It focuses on binary relationships (called dependencies) between a head word
and its dependents.
• Head: A word that controls or governs others (usually a verb or noun).
• Dependent: A word that adds meaning to the head.
Think of it as a “who is linked to whom” model, not “what group/phrase it
belongs to.”
2. Why is it called “Dependency” Grammar?

16
Because:
• The meaning and structure of a sentence come from the dependencies
between words.
• These dependencies form a tree, with one word at the top (root), and all
other words branching from it.
3. Key Concepts

Concept Meaning

Head Central word of a relation. Other words depend on it.

Dependent Word that describes or completes the meaning of the head.

Dependency
A link showing which word depends on which.
Relation

The main word (usually a verb) that does not depend on any
Root
other word.

The full sentence is structured like a tree, where each word

Tree Structure
(except the root) is connected to one parent (the head).

4. Example – Sentence Breakdown

Let’s analyze this sentence using Dependency Grammar:
Sentence: “Hena reads a book.”
Step-by-Step Analysis:

Word Relation Depends on

Hena Subject (nsubj) reads

reads Root — (main verb)

a Determiner (det) book

book Object (obj) reads

5. Dependency Tree Representation

This is how it would look:
reads
/ \
Hena book
|

17
 a
Explanation:
• “reads” is the head of the sentence (main verb → root).
• “Hena” is the subject, connected to “reads”.
• “book” is the object, connected to “reads”.
• “a” is a determiner, connected to “book”.
6. Comparison With Phrase Structure Grammar

Feature Dependency Grammar Phrase Structure Grammar

Units Words Phrases

Based on phrase
Structure Based on word relations
composition

Good for free word order languages Better for fixed word order
Flexibility
(like Hindi, Tamil) (like English)

Tree Head–Dependent Tree Phrase–Subphrase Tree

7. Types of Dependency Relations (with examples)

Relation Description Example

nsubj Nominal subject Hena → reads

obj Object book → reads

det Determiner a → book

amod Adjective modifier sweet → mango

advmod Adverb modifier quickly → ran

compound Compound nouns railway → station

prep Preposition on → table

pobj Prepositional object table → on

8. Sentence With Slightly More Complexity

Sentence: “The small dog barked loudly.”

Word Relation Depends on

The Determiner (det) dog

18
Word Relation Depends on

small Adjective (amod) dog

dog Subject (nsubj) barked

barked Root —

loudly Adverb (advmod) barked

Tree:
barked
/ \
dog loudly
/ \
The small
9. Why is Dependency Grammar useful in NLP?
• It’s more compact and flexible.
• Great for free word order languages like Hindi, Czech, Turkish.
• Useful for:
o Parsing
o Machine Translation
o Question Answering
o Information Extraction
o Grammar correction tools
10. Tools and Frameworks Using Dependency Grammar
• Stanford NLP – Dependency Parser
• spaCy
• Universal Dependencies (UD) – A multilingual resource of dependency-
annotated texts
• SyntaxNet (Google)
11. Dependency Grammar vs Phrase Structure Grammar – Example

19
Structure Sentence: “Hena reads a book.”

Phrase Structure
Breaks into: S → NP VP NP → N VP → V NP
Grammar

Dependency Direct word relations: reads → Hena (subject) reads →

Grammar book (object) book → a (determiner)

Summary:
• Dependency Grammar shows the structure of a sentence by linking
words directly to one another based on who depends on whom.
• It’s simpler and more flexible, especially useful in real-world NLP
applications.
• Words are arranged in a tree, where one word is the root, and every
other word is connected as a dependent to some other word.

Syntactic Parsing
What is Syntactic Parsing?
Syntactic parsing (also called syntax analysis) is the process of analyzing the
structure of a sentence—how words are grouped and how they relate to each
other grammatically.
In other words:
It tells us which words play which roles in a sentence and how they are
connected.
Example:
Sentence: “The boy ate an apple.”
Syntactic parsing figures out:
• Who is the subject? → “The boy”
• What is the verb? → “ate”
• What is the object? → “an apple”
Two Main Types of Syntactic Parsing:
1. Constituency Parsing (also called Phrase Structure Parsing)
• This breaks the sentence into phrases or subgroups.
• It creates a tree where each node is a phrase like a noun phrase (NP) or
verb phrase (VP).
Example tree:
S
/\

20
 NP VP
/ /\
Det N V NP
The boy ate an apple
2. Dependency Parsing
• Focuses on the relationship between individual words, not phrases.
• Shows which word depends on which other word.
• Forms a graph/tree of head words and dependents.
Example (dependencies):
ate
├── subject → boy
│ └── determiner → The
└── object → apple
└── determiner → an

What's the difference?

Feature Constituency Parsing Dependency Parsing

Focus Phrase-based structure Word-to-word relationships

Tree Directed graph/tree of

Hierarchical phrase tree
Structure dependencies

Grammar-based Meaning and function

Use Case
applications understanding

Real-world NLP like translation,

Better for Formal grammar modeling
TTS

Syntactic vs. Semantic Parsing

• Syntactic Parsing = Structure: "How is the sentence built?"
• Semantic Parsing = Meaning: "What does the sentence mean?"
Example:
• Syntax: In “She gave him a gift,” parse who is the subject, verb, object.
• Semantics: Understand that “She” is giving something to “him”.

21
Applications of Syntactic Parsing
Here’s how syntactic parsing is used in real-world applications:
1. Text-to-Speech (TTS) Systems
• TTS uses syntactic parsing to generate more natural sounding speech.
• Understanding sentence structure helps the system know where to
pause, emphasize, or change tone.
2. Information Extraction
• Helps in identifying relationships in sentences, like:
“John works at Google.” → [Person: John] [Organization: Google]
3. Machine Translation
• Helps translate grammatically accurate sentences.
• E.g., it helps a system know how to translate subject-verb-object
correctly into another language.
Advancements in Syntactic Parsing Research
Recent studies explored:
Brain Studies:
• Found that different parsing methods (constituency vs dependency)
activate different brain regions.
SSUD Method (Unsupervised Parsing):
• A new method called SSUD learns syntactic structure without human-
annotated data, using patterns in large text corpora.
TTS Improvements:
• Parsing trees help generate better rhythm and tone in synthesized
voices.
Biomedical Parsing:
• Researchers tested popular parsers on medical texts (harder to
understand) to improve information extraction from health articles.
Company Example: Google Syntactic Ngrams
• Google created a huge dataset of parsed sentence patterns from books.
• This dataset helps in training better parsers and understanding
language usage over time.
In Summary – Why is Syntactic Parsing Important?

22
Benefit Description

Better Language Helps machines "read" language like

Understanding humans

More Natural Speech Improves computer voice intonation

Improved Translation Ensures accurate grammar across languages

Precise Information
Finds facts and entities in complex texts
Extraction

Used in studying how humans process

Supports Linguistic Research
language

Ambiguity
What is Ambiguity?
Ambiguity means confusion or [Link] language, a sentence or a word
is ambiguous when it can have more than one [Link] human
conversation, we usually figure out the correct meaning from [Link] for
a computer or NLP model, this is much harder.
Why is Ambiguity Important in NLP?
When we talk to computers (e.g., through voice assistants or chatbots), the
computer needs to understand what we mean.
But if the sentence is ambiguous, it doesn’t know which meaning is correct,
unless we program it carefully.
Types of Ambiguity in NLP
Here are the main types of ambiguity in NLP, with simple examples.
1. Lexical Ambiguity – Word has multiple meanings
One word = many meanings
Example:
“I went to the bank.”
• Do you mean a river bank?
• Or a financial bank?
Why it's tricky: The same word "bank" has different meanings. The
surrounding words (context) are needed to guess the correct one.
2. Syntactic Ambiguity – Sentence has multiple grammatical structures
Sentence = can be broken differently

23
Example:
“I saw the man with the telescope.”
• Does it mean:
o I used the telescope to see the man?
o Or the man had a telescope?
Why it's tricky: The sentence structure allows both meanings.
3. Semantic Ambiguity – Sentence has multiple meanings
Even after grammar is clear, meaning can change
Example:
“Visiting relatives can be annoying.”
• Are you annoyed because you are visiting them?
• Or because they are visiting you?
Why it's tricky: The meaning of the sentence is unclear, even though the
grammar is correct.
4. Pragmatic Ambiguity – Context-dependent meaning
Meaning changes depending on situation
Example:
A boss says to an employee: “You’re early today.”
• Is that a compliment?
• Or sarcasm?
Why it's tricky: The meaning depends on tone, context, or prior knowledge.
5. Anaphoric Ambiguity – Confusion about references
We don’t know what a word (like “he”, “it”) refers to
Example:
“John gave his friend the book. He thanked him.”
• Who is "he"?
• Who is thanking whom?
Why it's tricky: The pronouns are unclear.
6. Attachment Ambiguity – Where does a phrase belong?
Example:

24
“She saw the man in the park with binoculars.”
• Who had the binoculars?
o She?
o The man?
Real-Life Example of Ambiguity
Sentence:
“Flying planes can be dangerous.”
• Is the sentence about:
o Planes that are flying (noun)?
o The activity of flying planes (verb)?
It depends on how the word "flying" is used.
How Humans Resolve Ambiguity
Humans use:
• Tone of voice
• Facial expressions
• Knowledge of the world
• Previous conversation
This helps us guess the correct meaning easily.
How NLP Tries to Handle Ambiguity
1. Contextual Word Embeddings
o Tools like BERT or GPT understand the meaning of a word based
on its context.
2. Parsing
o NLP tools break down sentence structure (syntax trees,
dependencies) to guess correct meaning.
3. Knowledge Graphs / World Knowledge
o Some systems use stored knowledge (e.g., "banks store money")
to resolve word meaning.
4. Machine Learning
o Trains models on huge text corpora where correct meanings are
known (supervised learning).

25
 5. Word Sense Disambiguation (WSD)
o A special task in NLP focused on identifying the correct meaning
of a word from context.
Applications Affected by Ambiguity

Task Problem caused by ambiguity

Search engines Show wrong results if query is unclear

Machine translation Translate wrong meaning of a word

Speech recognition Misunderstand spoken words

Chatbots Reply incorrectly

Text summarization Summarize the wrong idea

Summary

Type of
Description Example
Ambiguity

One word, many

Lexical “Bank” – river or money place
meanings

Sentence allows different “I saw the man with the

Syntactic
structures telescope.”

Sentence meaning is “Visiting relatives can be

Semantic
unclear annoying.”

Meaning depends on
Pragmatic “You’re early today.”
context

Unclear reference words

Anaphoric “He thanked him.”
(he, she, it)

Confusion about phrase “She saw the man in the park

Attachment
belonging with binoculars.”

Dynamic Programming parsing

What is Parsing?
Parsing means analyzing a sentence to find its grammatical structure.
For example, for the sentence:
"The cat sat on the mat."
A parser figures out:

26
 • What is the subject?
• What is the verb?
• What is the object?
• How do these words group together into phrases?
What is Dynamic Programming (DP) Parsing?
Dynamic Programming Parsing is a method used to efficiently parse a
sentence by avoiding repeated work.
Imagine trying out every possible way to divide a sentence into parts — it
would take a lot of time!
So, DP parsing:
• Breaks the problem into smaller parts (sub-sentences).
• Saves the results of those smaller parts.
• Reuses them instead of recalculating.
This makes parsing faster and smarter.
Why is DP Parsing Needed?
In some parsers (especially for Context-Free Grammars (CFG)), many parts
of the sentence get re-analyzed multiple times.
For example:
"John saw the man with the telescope."
This sentence has multiple possible structures.
Without DP, a parser might try the same structure again and again while
exploring different interpretations.
DP avoids this waste by remembering previous results.
Basic Idea Behind Dynamic Programming Parsing
• Create a table (like a matrix) where:
o Rows represent the start of a phrase
o Columns represent the end of a phrase
• Fill in the table with possible parses of each sub-sentence
• Use the results to build up to the full parse of the whole sentence
CYK Algorithm – A Famous Example of DP Parsing
Let’s understand using the CYK algorithm (Cocke-Younger-Kasami).
It works only on CFGs in Chomsky Normal Form (CNF).

27
 Step-by-Step Explanation:
Step 1: Input sentence
Example:
“she eats fish”
Split into words (tokens):
[she, eats, fish]
Step 2: Create a triangular table
Create a 3x3 table since we have 3 words.
Each cell [i][j] stores the possible non-terminal symbols (e.g., NP, VP, S) that
can generate the substring from word i to j.
Step 3: Fill in the table bottom-up
• Start from individual words (length = 1)
• Then combine 2-word phrases (length = 2)
• Then the whole sentence (length = 3)
Use grammar rules (in CNF) like:
S → NP VP
VP → V NP
NP → she | fish
V → eats
Step 4: Use stored results
When combining "she" and "eats", you already know:
• "she" = NP
• "eats" = V
Now check if NP + V can lead to something useful using grammar rules.
This way, the parser builds up the structure and fills the table without re-
analyzing the same parts again.
Advantages of DP Parsing

Feature Benefit

Efficient Avoids recalculating same structures

Fast Good for long sentences

28
Feature Benefit

Reliable Works for context-free grammars

Practical Used in many real-world parsers

Real-World Use Cases

• Syntax checkers in compilers or NLP tools
• Speech recognition (parsing possible sentence interpretations)
• Machine translation (to understand sentence structure)
• Grammar correction tools like Grammarly
Simple Analogy
Think of solving a puzzle:
• Without DP: You keep trying the same pieces again and again
• With DP: You remember what fits where, and reuse that info
Summary

Term Meaning

Parsing Analyzing sentence structure

Dynamic Programming Solving big problems by solving and reusing

(DP) small parts

Parsing sentences by storing and reusing sub-

DP Parsing
parses

CYK Algorithm A popular DP parsing method for CFG in CNF

Table Used to store possible parses for sub-phrases

Shallow parsing
What is Shallow Parsing?
Shallow parsing means finding the main parts (chunks) of a sentence — like
noun phrases (NPs) or verb phrases (VPs) — but without going deep into their
structure.
It’s like identifying the big puzzle pieces, but not breaking them into smaller
parts.
Example:
Take this sentence:

29
"The quick brown fox jumps over the lazy dog."
A shallow parser might divide it into:
[NP The quick brown fox] [VP jumps] [PP over] [NP the lazy dog]
• NP = Noun Phrase
• VP = Verb Phrase
• PP = Prepositional Phrase
It doesn’t tell you the internal structure (e.g., which word is adjective, which
is noun), but gives you chunks of meaningful phrases.
Difference Between Shallow Parsing and Deep Parsing

Feature Shallow Parsing Deep Parsing

Depth Surface-level (top structure) Full tree structure

Speed Fast Slower

Output Chunks (NP, VP, etc.) Full parse tree

Complexity Simple Complex

Use case Quick phrase identification Detailed grammatical analysis

Why Is Shallow Parsing Useful?

• It’s faster than deep parsing.
• Good enough for many NLP tasks like:
o Information extraction
o Named Entity Recognition (NER)
o Text classification
o Question answering
• Helps identify key components without the full structure.
Components of Shallow Parsing
1. Part-of-Speech Tagging
First, each word is tagged with its grammatical category.
Example:

30
 2. Chunking
Then, the words are grouped into phrases (chunks) based on the POS
tags.
Example:
[NP The quick brown fox] [VP jumps] [PP over] [NP the lazy dog]

How Does Shallow Parsing Work?

It often uses rules or machine learning models to group words into
phrases.
1. Rule-based methods
Use patterns like:
NP → DT JJ* NN
This means: a noun phrase starts with a determiner (DT), followed by zero or
more adjectives (JJ), and ends with a noun (NN).
2. Statistical models / ML
Like:
• Hidden Markov Models (HMM)
• Maximum Entropy Models (MaxEnt)
• Conditional Random Fields (CRF)
These learn patterns from annotated training data and predict the chunks.
BIO Tagging Format
Shallow parsers often use BIO tagging to mark chunks:

Word Tag

The B-NP

quick I-NP

brown I-NP

fox I-NP

jumps B-VP

over B-PP

31
Word Tag

the B-NP

lazy I-NP

dog I-NP

• B-NP = Beginning of Noun Phrase

• I-NP = Inside Noun Phrase
• B-VP = Beginning of Verb Phrase
• B-PP = Beginning of Preposition Phrase
This format makes chunk identification easier for machine learning.
Real-Life Applications of Shallow Parsing

Application How Shallow Parsing Helps

Search Engines Identify phrases to improve search relevance

Chatbots Understand key noun/verb phrases in user input

Information Extraction Extract names, dates, places quickly

Text Summarization Capture main entities and actions

Grammar Checkers Detect basic phrase structure problems

Summary

Term Meaning

Shallow Parsing Identifying main phrases in a sentence

Focus Phrase chunks, not full grammar trees

Speed Fast and simple

Tools used POS tagging + chunking rules/models

Output format Chunks or BIO tags

Simple Analogy
Imagine reading a story and just underlining important phrases — like names
and actions — without analyzing each word's grammar.
That’s what shallow parsing does.

32
Would you like to:
• See a Python example using NLTK or spaCy?
• Try shallow parsing on a sentence of your choice?
Let me know, and I’ll guide you with code or more examples!

Probabilistic CFG
What is a Context-Free Grammar (CFG)?
Before jumping to Probabilistic CFG, let’s quickly recall CFG:
A Context-Free Grammar (CFG) is a set of rules used to describe the structure
(syntax) of a language.
Each rule tells how a non-terminal symbol (like a sentence or a noun phrase)
can be expanded into other symbols (words or phrases).
Example CFG:
S → NP VP
NP → Det N
VP → V NP
Det → "the" | "a"
N → "cat" | "dog"
V → "chased" | "saw"
This grammar says:
• A sentence (S) is made up of a noun phrase (NP) followed by a verb
phrase (VP)
• An NP is a determiner (Det) and a noun (N)
• A VP is a verb (V) and another NP
With this grammar, we can generate:
"the dog chased a cat"
But What's Missing?
If we have multiple rules, how do we decide which one to prefer?
Example:
VP → V NP (Rule 1)
VP → V (Rule 2)
For the verb "slept", do we expect an object or not?

33
CFG doesn’t tell us which rule is more likely or common.
What is a Probabilistic CFG (PCFG)?
Probabilistic CFG adds probabilities to each rule.
It tells us how likely each rule is used — based on real examples (usually
from a treebank).
So, it’s like CFG + probabilities.
Example of PCFG:
S → NP VP [1.0]
NP → Det N [0.6]
NP → N [0.4]
VP → V NP [0.7]
VP → V [0.3]
Det → "the" [0.8]
Det → "a" [0.2]
N → "cat" [0.5]
N → "dog" [0.5]
V → "chased" [0.6]
V → "slept" [0.4]
This says:
• A VP → V NP happens 70% of the time
• A VP → V happens 30% of the time
• The word "the" is used as a determiner 80% of the time
How Is PCFG Useful?
1. Handles ambiguity:
If there are multiple ways to parse a sentence, PCFG helps choose the
most probable one.
2. Learned from data:
We can build PCFGs from treebanks (annotated datasets), where
human experts have given correct parse trees.
3. Used in parsers:
Parsers like the Probabilistic CYK parser or Viterbi parser use PCFGs
to find the best parse tree.

34
How Probabilities Are Calculated?
From a treebank:
• Count how many times a rule is used.
• Divide it by the total number of times the left-hand side appears.
Example:
If:
• VP → V NP is used 70 times
• VP → V is used 30 times
Then:
P(VP → V NP) = 70 / (70 + 30) = 0.7
P(VP → V) = 30 / (70 + 30) = 0.3
Real-Life Example
Sentence:
"The dog saw the cat"
Two possible parse trees:
1. saw as main verb
2. saw as noun (e.g., "the dog’s saw was stolen")
Using PCFG, we can calculate the probability of each parse and pick the one
with higher probability, usually the first one.
Summary

Concept Explanation

CFG Describes sentence structure using rewrite rules

PCFG Adds probabilities to CFG rules

Helps with Ambiguity, choosing best parse

Learned from Treebanks (annotated corpora)

Used in Statistical parsers in NLP

Simple Analogy
Imagine you're building sentences using Lego blocks.
• CFG gives you the instruction manual.

35
 • PCFG tells you which instructions are used more often — so you can
guess the most common or likely shape!

Probabilistic CYK
What Is CYK Algorithm?
The CYK algorithm is a dynamic programming algorithm used to check if a
sentence belongs to a Context-Free Grammar (CFG) and to find its parse
tree.
But here's the twist:
The Probabilistic CYK version uses Probabilistic CFG (PCFG) instead of just
rules — it finds the most likely parse tree.
Before That – A Quick Recap

✅ Context-Free Grammar (CFG):

Rules like:
S → NP VP
VP → V NP
NP → Det N
Det → "the"
N → "dog"
V → "chased"

✅ PCFG adds probabilities:

S → NP VP [1.0]
VP → V NP [0.7]
VP → V [0.3]
NP → Det N [0.6]
NP → N [0.4]
Goal of Probabilistic CYK
Given:
• A sentence (like "the dog chased a cat")
• A PCFG
It finds the most probable parse tree (syntactic structure) of the sentence.
Requirements

36
 1. PCFG in Chomsky Normal Form (CNF)
CNF means:
o Every rule has the form: A → B C or A → a
(i.e., either two non-terminals or a single terminal)
2. Input sentence: The sentence must be tokenized into words.
Step-by-Step Explanation of Probabilistic CYK
Let’s say the sentence is:
"the dog chased"
And PCFG (in CNF) includes:
S → NP VP [1.0]
VP → V NP [0.7]
VP → V [0.3]
NP → Det N [0.6]
NP → "dog" [0.4]
Det → "the" [1.0]
V → "chased" [1.0]
Step 1: Create a table
Create a triangular table (like a pyramid) to store possible non-terminal
rules at different levels.
The table has n rows, where n = number of words in the sentence.
Step 2: Fill the base (words)
We look at each word:
• For "the" → Det [1.0]
• For "dog" → NP [0.4]
• For "chased" → V [1.0]
We record those probabilities in the first row of the table.
Step 3: Combine parts (bottom-up)
Now we combine:
• "the dog" → see if Det + N leads to NP (Yes: NP → Det N [0.6])
o So NP = 1.0 (Det) * 0.4 (N) * 0.6 = 0.24
• "dog chased" → check combinations (not possible here)

37
 • "the dog chased":
o Try NP VP → S [1.0] if we find both in previous cells
Step 4: Choose the best parse
If there are multiple ways to parse, CYK keeps track of the probabilities and
chooses the parse with the highest probability.
It remembers:
• Which rule was used
• Where the split happened
• What was the probability
Final Output
• The full parse tree (structure)
• The most probable way of building the sentence according to the
grammar
• The probability score
Why Is It Important?
• Handles ambiguity: Finds the best parse, not just any valid parse.
• Efficient: Uses dynamic programming to avoid re-computing things.
• Used in NLP tools for syntactic analysis (e.g., in speech recognition,
machine translation).

✅ Analogy
Imagine you're solving a jigsaw puzzle:
• CFG tells you the shapes (rules).
• PCFG tells you which shapes go together most often.
• CYK is the smart method that tries all possible ways to put it together
— and picks the most likely one using probabilities.

✅ Summary Table

Feature Explanation

Algorithm Name Probabilistic CYK

Based on PCFG + Dynamic Programming

Input Sentence + PCFG in CNF

38
Feature Explanation

Output Most probable parse tree and its probability

Key idea Tries all combinations and chooses the best using scores

Used for Syntax analysis in NLP

Probabilistic Lexicalized CFGs

What are Probabilistic Lexicalized CFGs?
A Probabilistic Lexicalized Context-Free Grammar is an advanced form of a
Probabilistic CFG (PCFG) that:
• Still uses grammar rules to describe how sentences are built.
• But also includes specific words (called lexical items) into the
grammar rules.
• Adds probabilities to handle uncertainty and ambiguity.
Let’s break it down clearly.
Step-by-step Breakdown
1. What is a CFG?
A Context-Free Grammar is a set of rules that describe how words in a
sentence are grouped into phrases and how phrases are grouped into
sentences.
Example:
S → NP VP
NP → Det N
VP → V NP
These rules say:
• A sentence (S) is made of a noun phrase (NP) and a verb phrase (VP).
• A noun phrase is a determiner + noun.
• A verb phrase is a verb + noun phrase.
But this is abstract – it doesn’t tell us which words are involved.
2. What is a Probabilistic CFG (PCFG)?
PCFG adds probabilities to each rule.
Example:
S → NP VP [1.0]

39
VP → V NP [0.7]
VP → V [0.3]
NP → Det N [0.6]
NP → N [0.4]
This helps when there are multiple possible parses of a sentence.
The PCFG chooses the most likely one using the rule probabilities.
3. But what’s missing?
Neither CFG nor PCFG knows anything about specific words like:
• "dog" vs. "idea"
• "eat" vs. "think"
They just say “N” for noun, or “V” for verb.
So they treat all nouns and all verbs the same, which is not always correct.
For example:
• "eat pizza" is normal.
• "eat idea" sounds strange.
We need to connect rules with actual words.
4. What is Lexicalization?
Lexicalization means we now:
• Attach specific words (lexical heads) to the grammar rules.
• A rule like NP → Det N becomes more detailed:
NP(dog) → Det(the) N(dog)
Here, "dog" is the head of the NP.
So every phrase remembers its main word (called its head), and that head is
used to guide parsing.
5. What is a Probabilistic Lexicalized CFG?
Now combine it all:
• It’s a CFG → with syntactic rules.
• It’s probabilistic → each rule has a probability.
• It’s lexicalized → each rule is linked to specific words (head words).
So it looks like this:
NP(dog) → Det(the) N(dog) [probability = 0.4]

40
VP(eat) → V(eat) NP(pizza) [probability = 0.6]
These rules are more precise than regular CFG rules because they:
• Reflect how words really combine in natural language.
• Help resolve ambiguity more accurately.
Why Use Lexicalization?
Let’s say you parse this sentence:
“The dog chased the cat.”
Without lexicalization:
• It just uses NP, VP, Det, etc., but doesn’t know who is doing what.
With lexicalization:
• It knows that "dog" is the head of the subject.
• "chased" is the head of the verb phrase.
• "cat" is the head of the object.
So, it understands the roles of words more accurately.
This is especially important for complex sentences or those with multiple
meanings (ambiguity).
Summary Table

Feature Description

CFG Grammar using syntactic rules like S → NP VP

PCFG CFG + probabilities on each rule

Lexicalized CFG CFG where rules include specific head words

Probabilistic Lexicalized
CFG + head words + probabilities
CFG

Better parsing, disambiguation, accurate syntactic

Used for
structure

More realistic and accurate for natural language

Benefit
understanding

Example
Regular PCFG Rule:
VP → V NP [0.7]

41
Lexicalized PCFG Rule:
VP(chased) → V(chased) NP(cat) [0.65]
This tells us that:
• The VP has "chased" as the head.
• The NP object of the VP has "cat" as its head.
• The structure chased the cat is more likely (0.65 probability).
Final Thought
Probabilistic Lexicalized CFGs help a parser not just know the structure of a
sentence, but also the meaningful roles of words within that structure.
They are especially useful in:
• Speech recognition
• Machine translation
• Information extraction
• Natural language understanding (NLU)

Feature structures
What Are Feature Structures?
In natural language, words carry many types of information — like tense,
number, gender, case, etc.
A feature structure is a way of representing these properties using key–value
pairs, kind of like a table or a dictionary.
Imagine This:
Think of feature structures like a form filled out for each word or phrase,
where:
• Each row (or field) is a feature (like gender or number).
• Each value is the specific detail (like “feminine” or “plural”).
Example: Noun "girls"
Let’s take the word "girls". It has:
• Category: Noun
• Number: Plural
• Gender: (Not important in English here)
• Person: 3rd
We can represent this as a feature structure:

42
[
CATEGORY: noun
NUMBER: plural
PERSON: 3
]
It’s like a small data record for the word "girls".
Why Do We Need Feature Structures?
Natural language is full of agreement rules, such as:
• Subject and verb should agree in number and person.

o "She eats"

o "She eat" (bad agreement)

To check and enforce such grammar rules, computers need a way to store
and compare these kinds of features.
Feature structures allow:
• Better grammatical checking
• More accurate parsing
• Richer understanding of syntax and semantics
Unification
One powerful operation used with feature structures is called unification.
What is unification?
It means: Merging two feature structures and checking if they are
compatible.
Example:
Suppose we have:
Subject: [NUMBER: singular]
Verb: [NUMBER: singular]
Since both have the same number, they unify → the sentence is
grammatically correct.
But if we have:
Subject: [NUMBER: plural]
Verb: [NUMBER: singular]

43
Unification fails → the sentence is grammatically wrong.
Feature Structures for Phrases
Not just words, phrases like noun phrases (NP) or verb phrases (VP) can also
have feature structures.
Example:
NP: [
CATEGORY: noun phrase
NUMBER: plural
]

VP: [
CATEGORY: verb phrase
TENSE: present
NUMBER: plural
]
These help parsers and grammar-checking systems understand how parts of
a sentence should match.
How Are They Represented?
Feature structures are usually written as attribute-value matrices (AVMs) or
nested dictionaries.
Example using AVM:
[
CAT: NP
AGR: [
NUM: plural
PER: 3rd
]
]
In programming (Python-like dictionary):
{
"CAT": "NP",

44
 "AGR": {
"NUM": "plural",
"PER": "3rd"
}
}
This nesting helps represent hierarchical and rich information.
Where Are Feature Structures Used?
Feature structures are used in:
• Parsing (analyzing sentence structure)
• Unification-based grammars (like HPSG and LFG)
• Speech processing
• Machine translation
• Grammar checkers
Summary

Concept Explanation

Feature A set of key-value pairs showing grammatical info (like

Structure number, gender, etc)

To describe and compare words/phrases in a structured

Purpose
way

Helps in Agreement checking, parsing, semantic analysis

Common NUMBER, GENDER, TENSE, PERSON, CASE,

Features CATEGORY

The process of combining/matching two feature

Unification
structures

Representation Tables, AVMs, or nested dictionaries

Final Example
Sentence: "The girls play."
We’ll assign feature structures:
"girls":
[ CAT: NP, NUMBER: plural ]

45
"play":
[ CAT: VP, NUMBER: plural ]
They match (both plural) → Sentence is grammatically correct.

Unification of feature structures

What are Feature Structures?
In Natural Language Processing (NLP) and Computational Linguistics, we
often need to represent information about words, phrases, or sentences.
This information can include:
• Part of speech (POS) (e.g., noun, verb)
• Number (e.g., singular, plural)
• Gender (e.g., masculine, feminine)
• Tense (e.g., past, present)
A Feature Structure is a formal way of organizing this information using
attribute–value pairs.
Example of a Feature Structure:
For the word “dogs”, the structure might look like this:
[
CATEGORY: noun,
NUMBER: plural
]
For “runs”:
[
CATEGORY: verb,
NUMBER: singular,
TENSE: present
]
Each structure shows the features (like CATEGORY, NUMBER, TENSE) and
their values.
What is Unification?
Now, imagine you're trying to combine two feature structures — maybe one
from a noun and one from a verb — to see if they agree or match in a
sentence.

46
Unification means merging two feature structures only if they do not
contradict each other.
It checks whether the values for common features in both structures are the
same. If they are, the structures can be unified into one. If not, unification
fails.
Unification Example (Successful)
Let’s unify these two:
Structure A:
[
CATEGORY: noun,
NUMBER: plural
]
Structure B:
[
NUMBER: plural,
CASE: nominative
]

👉 Common feature is NUMBER, and both have the value plural.

So, unification will succeed, and the result is:
[
CATEGORY: noun,
NUMBER: plural,
CASE: nominative
]

❌ Unification Example (Failure)

Now let’s try these:
Structure A:
[
CATEGORY: noun,
NUMBER: singular

47
]
Structure B:
[
NUMBER: plural,
CASE: accusative
]
Here, NUMBER has a conflict: one is singular, the other is plural.

So, unification fails ❌.

Why is Unification Useful in NLP?
In NLP, unification is used in:
1. Parsing sentences to ensure subjects and verbs agree (like "He eats" vs
"They eat").
2. Grammar checking.
3. Semantic analysis (to check roles like subject, object).
4. Handling ambiguity by filtering out incompatible interpretations.
Simple Analogy
Think of feature structures as forms filled with attributes.
• If two forms have matching information, you can combine them.
• If they have conflicting answers, you can’t merge them — just like you
can’t register a car with two different license numbers.
Summary

Concept Explanation

Feature
A list of attributes (like tense, number, etc.) with values
Structure

Combining two feature structures only if there's no

Unification
conflict in values

Used in Grammar rules, sentence parsing, agreement checks, etc.

Fails when There is a contradiction in shared features

48