UNIT – 2: GRAMMARS AND PARSING

1. Grammar

A grammar is a formal specification of the structures that are allowed in a language.

It defines:
How words combine to form phrases.
How phrases combine to form sentences.
The rules governing sentence formation.

2. Parsing

Parsing is the process of analyzing the grammatical structure of a sentence according

to a given grammar.
It involves:
Breaking sentence into words (tokenization)
Assigning POS tags
Grouping words into phrases
Building a parse tree
Parsing Structure is S-----> NP + VP
Example
Sentence:
“The student reads the book.”
Steps:
The → Det
student → N
reads → V
the → Det
book → N
Parse Tree Diagram
S
/ \
NP VP
/ \ / \
Det N V NP
| | | / \
The student reads Det N
| |
the book

3. What Makes a Good Grammar

A good grammar is:
Clear
Unambiguous
Expressive
Accurate
It follows:
Tense agreement
Subject-verb agreement
Proper word order
Bad grammar causes confusion.

4. Context-Free Grammar (CFG)

A Context-Free Grammar (CFG) is a set of production rules where each rule has a
single non-terminal on the left-hand side.
Components of CFG
Non-terminals (S, NP, VP)
Terminals (actual words)
Production rules
Start symbol (usually S)

Example Grammar
S → NP VP
VP → V NP
NP → Adj N

Categories of Phrases
Phrase Type Head Word
Noun Phrase (NP) Noun
Verb Phrase (VP) Verb
Adjective Phrase (ADJP) Adjective
Adverb Phrase (ADVP) Adverb
Prepositional Phrase (PP) Preposition

5. Need for Parsing

Parsing is required:
To resolve ambiguity
Example:
“I like Frozen” vs “I like frozen yogurt”
To check grammatical correctness
 To identify subject, object, verb
For NLP applications

Applications of Parsing
 Sentiment Analysis
 Question Answering
 Machine Translation
 Speech Recognition
 Grammar Checking

6. Parsing Strategies

Top-Down Parsing
Bottom-Up Parsing
Chart Parsing
Top-Down Chart Parsing

Top-Down Parsing
Definition
Parsing from root (S) to leaves.
Characteristics
Predictive
Grammar-driven
May generate invalid structures

Search Strategies
1. Depth-First Search (DFS)
Uses Stack (LIFO)
2. Breadth-First Search (BFS)
Uses Queue (FIFO)

Bottom-Up Parsing
Definition
Parsing from words to root.
Characteristics
Sentence-driven
No unrelated structures generated
May generate incomplete parses
 The CKY (Cocke–Kasami–Younger) algorithm is a bottom-up dynamic
programming parsing algorithm used to check whether a sentence can be
generated by a context-free grammar (in CNF) and to construct its parse tree.
Top-Down vs Bottom-Up
Aspect Top-Down Bottom-Up
Start S Words
Predictive Yes No
Sentence-driven No Yes
Wasted Search Grammar-based Structure-based

Chart Parsing
Chart parsing stores intermediate results in a table to avoid recomputation.

Example Sentence
“The student reads the book”
Chart Representation
Word Index 0 1 2 3 4
Words the student reads the book
Edges:
0–1 Det
1–2 N
0–2 NP
2–3 V
3–4 Det
4–5 N
3–5 NP
2–5 VP
0–5 S

Parse Tree
S [0-5]
/ \
NP [0-2] VP [2-5]
/ \ / \
Det[0-1] N[1-2] V[2-3] NP[3-5]
/ \
Det[3-4] N[4-5]

Top-Down Chart Parsing

Combination of:
 Top-down parsing
Chart storage
Benefits:
Reduces redundancy
Efficient for ambiguous grammar

7. Morphological Processing in NLP

Morphological Processing is the stage in Natural Language Processing (NLP) that

analyzes the internal structure of words by breaking them into smaller meaningful
units called morphemes and identifying their grammatical features such as tense,
number, gender, case, and derivation.
It helps answer:
What is the root word?
Is the word singular or plural?
What is the tense of the verb?
Is the word derived or inflected?
What grammatical features does the word carry?

What is a Morpheme?
A morpheme is the smallest meaningful unit in a language.
Types of Morphemes
Free Morphemes
Free morphemes can stand alone (e.g., book).

Bound Morphemes
Bound morphemes cannot stand alone (e.g., -s, -ing).

Types of Morphology
Morphology is divided into two major types:
Inflectional Morphology
Changes the grammatical form of a word without changing its meaning or word class.
Examples:
Base Word Inflected Form Function
student students plural
play playing continuous tense
walk walked past tense
book books plural
Meaning remains same
Only grammar changes
Derivational Morphology
Creates a new word and may change the word class.
Examples:
Root Derived Word Change
happy happiness adjective → noun
happy unhappy meaning change
teach teacher verb → noun
kind kindness adjective → noun
Meaning changes
Word class may change

Word Breakdown Examples

Word Morphological Breakdown Meaning
unhappiness un + happy + ness state of not being happy
students student + s plural noun
playing play + ing present participle
went go (past tense form) irregular verb

Morphological Processing Steps in NLP

When a sentence is given, NLP system performs:
Tokenization (splitting words)
Root extraction
Feature identification
Morphological tagging

Example Sentence Analysis

Sentence:
“The students are reading books.”
Step 1: Tokenization
The | students | are | reading | books
Step 2: Morphological Analysis
Word Root Type Features
The the Determiner singular/plural neutral
students student Noun plural
are be Auxiliary verb present, plural
reading read Verb present participle
books book Noun plural

Morphological Output
students → noun, plural
are → auxiliary verb, present tense
reading → verb, present participle
books → noun, plural

Why Morphological Processing is Important

Improves Parsing Accuracy
Supports POS Tagging
Essential for Machine Translation
Improves Speech Recognition
Helps in Information Retrieval

8. Morphological Analysis Methods

Stemming
Reduces word to base form by removing suffixes.
Example:
playing → play
studies → studi (sometimes imperfect)
Tools:
Porter Stemmer
Snowball Stemmer
May produce non-dictionary words.
Lemmatization
Converts word into its dictionary base form considering context.
Example:
ran → run
better → good
More accurate than stemming.
Uses dictionary + POS tagging.

Finite State Transducers (FST)

Uses state machines to model word formation rules.
Example:
play → playing
State transition:
play → add -ing → playing
Morphological Features in Grammar Rules
Morphological features help enforce agreement.
Example Rule:
NP → Det + N (NUMBER = same)

“The student” ✓
Correct:

“The students” ✓
Incorrect:
“The students is” ✗
Because:
students = plural
is = singular

Regular vs Irregular Morphology

Regular
Add suffix:
walk → walked
play → played
Irregular
No fixed rule:
go → went
eat → ate
run → ran
Irregular words stored in lexicon.

Morphological Processing Diagram (Text Representation)

Input Sentence
↓
Tokenization
↓
Word Analysis
↓
Root Extraction
↓
Feature Identification
↓
Morphological Tags
↓
Grammar / Parser

Real-Life Example
User types:
“I am studying”
System identifies:
am → auxiliary (present)
studying → verb (continuous)
Chatbot understands:
Action in progress

Difference Between Stemming and Lemmatization

Feature Stemming Lemmatization
Uses dictionary No Yes
Accuracy Moderate High
Example studies → studi studies → study
Context aware No Yes

9. Transition Networks (TN)

When grammar becomes complex, we use Transition Networks (FSM-based

representation).

Types of Transition Networks:

RTN(Recursive Transition Network)
ATN(Augmented Transition Network)
Recursive Transition Network (RTN)
An RTN (Recursive Transition Network) is a graph-based representation of
grammar used for parsing natural language.
Formally:

Where:
Qi → Finite set of states
Σ (Sigma) → Set of terminal symbols (words)
Δi → Set of transitions (terminal, non-terminal, epsilon)
qi0 → Initial state
Fi → Set of final states
Each non-terminal (like S, NP, VP) is represented as a separate network.
Visual Structure Example
S Network
q0 --NP--> q1 --VP--> q2
Start at q0
Move to q1 after recognizing NP
Move to q2 after recognizing VP
q2 is final state

NP Network
q0 --Det--> q1 --N--> q2
Recognizes structures like:
the student
a boy

VP Network
q0 --V--> q1 --NP--> q2
Recognizes:
reads the book
eats food

How RTN Works (Example)

Sentence:
“The boy eats food”
Step-by-step:
Enter S network
Call NP network → matches “The boy”
Return to S
Call VP network → matches “eats food”
Reach final state → sentence accepted
Because RTN allows one network to call another, it can handle recursive structures
like:
“The boy who likes ice cream eats food.”

Limitations of RTN
Excessive Backtracking
Re-parsing Same Structures
Limited Semantic Handling
RTN mainly handles syntax.
It cannot enforce meaning-based constraints easily.
Example:
“The stone eats food.”
Syntactically correct → RTN accepts
Semantically incorrect → RTN cannot detect

Augmented Transition Network (ATN)

An ATN (Augmented Transition Network) is an extension of RTN that adds:

ATN = RTN + memory + conditions + actions

It includes:
Registers (memory storage)
Feature checking
Semantic interpretation

What ATN Handles

Syntax
Semantics
Agreement
Feature constraints

Example of Agreement Checking

Sentence 1:
“The cats are running.” ✓
Sentence 2:
“The cat are running.” ✗
ATN checks:
NP number
VP number
Verb agreement
If mismatch → sentence rejected.
RTN would accept both (since grammar structure matches).
ATN Structure (Basic Flow)
Start S
|
NP
|
VP
 |
End S
But internally ATN includes:
Feature registers
Condition checks
Semantic actions

Advantages of ATN
Handles Ambiguity Better
Captures Semantic Information
Enforces Feature Agreement
Reduces Invalid Parses
More intelligent than RTN.

Challenges of ATN
Complex to Maintain
Hard to Debug
Scalability Issues
Large-scale language systems become difficult to manage.

Differences between RTN and ATN

Aspect RTN ATN

Complexity Simple Complex
Agreement Checking No Yes
Semantic Handling No Yes
Backtracking High Reduced
Efficiency Moderate Better but computationally heavy
Suitable For Basic syntax Advanced NLP parsing

10. Feature Systems & Agreement

Agreement is a grammatical constraint where certain features (such as number,

gender, or person) of one word must match the corresponding features of another
word in a sentence.
Example:
✅ She runs (singular subject + singular verb)
❌ She run (agreement error)
Here, the verb must agree with the subject in number and person.

Problem

“a fish” ✓
“A men” ❌

The Problem of Agreement

Natural languages contain agreement restrictions between words.
Example:
❌ “A men”
✔ “A man”
✔ “Men are happy”
In “A men”:
“A” = singular determiner
“men” = plural noun
→ Number mismatch
In “a fish”:
“a” = singular
“fish” = singular (also can be plural depending on context)
→ Agreement is correct
Agreement ensures grammatical correctness between:
Determiner and Noun
Subject and Verb
Pronoun and Antecedent
Agreement ensures matching grammatical features like number and person between
words.
Example: “She runs” (correct) vs “She run” (incorrect).

Feature Structure
A Feature Structure represents grammatical information using feature-value pairs.

Here:
?n = variable
All NUMBER features must match
If:
ART = singular
N = plural
→ Rule fails
Feature structures help enforce:
Number agreement
Gender agreement
Person agreement

AGR Feature (Agreement Feature)

AGR combines:
Person
Number
AGR Values
Person Singular Plural
1st 1s (I run) 1p (We run)
2nd 2s (You run) 2p (You all run)
3rd 3s (He runs) 3p (They run)

Examples
He runs → 3s
They run → 3p
Verb must match subject’s AGR value.
Incorrect:
❌ He run
Correct:
✔ He runs
Thus, feature systems enforce subject-verb agreement.
11. Bayes’ Theorem

Bayes’ Theorem helps in calculating the probability of an event occurring given new
evidence by combining prior knowledge with observed data.
Formula
[
P(A|B) = \frac{P(B|A) \times P(A)}{P(B)}
]
Where:
P(A|B) = Posterior probability
P(B|A) = Likelihood
P(A) = Prior
P(B) = Evidence
Example: Rain Prediction
Given:
P(Rain) = 0.03
P(Cloudy) = 0.12
P(Cloudy | Rain) = 0.6
Using Bayes’ Rule:
Probability of rain when cloudy = 15%
Even though rain is rare, cloudy condition increases its probability.

12. Naive Bayes Classifier

Based on Bayes’ Theorem.

Assumption:
Features are conditionally independent.
This simplifies calculation.

Used In:
Sentiment Analysis
Spam Detection
Topic Classification
Language Identification

Example
Sentence:
“This movie is awesome”
Words like:
awesome, thrilling → high probability in positive class
Therefore:
Classified as Positive
Naive Bayes is:
Fast
Simple
Effective for text classification

13. Shannon’s Information Theory

Introduced by Claude Shannon (1948). Shannon’s Information Theory helps in

measuring and quantifying information, uncertainty, and efficient communication in
data transmission systems.
Provides mathematical theory of communication.
Key Concepts
Entropy
Information
Channel Capacity
Redundancy

Entropy Formula
[
H(X) = -\sum p(x) \log p(x)
]
Measures uncertainty in data.
English entropy ≈ 2.3 bits per character
Redundancy ≈ 50%
This means:
English language has predictable structure.

Shannon Game
Example sentence:
“THE CAT IS ON THE MAT”
Remove letters:
T_E_C_T_I_O_T_E_A
Still readable because:
Language has redundancy.
Redundancy helps:
Error correction
Text compression
Noise handling

14. Entropy in NLP

Entropy measures:
Uncertainty
Predictability
Used in:
Language modeling
Feature selection
Decision trees
Information gain
Higher entropy → more uncertainty
Lower entropy → more predictable

Cross-Entropy
Cross-Entropy measures difference between:
True distribution
Predicted distribution
Used as loss function in:
Neural Networks
Classification models
Machine Translation
Language Models
During training:
Model minimizes cross-entropy.
Lower cross-entropy → better prediction

Cross-Entropy
Entropy
Measures uncertainty of single Measures difference between two
distribution distributions
Used to understand randomness Used to measure prediction error
H(X) H(p, q)
Theoretical concept Practical training loss
Relationship:
Cross-Entropy = Entropy + Extra penalty for wrong prediction