Tutorial 10

What is Parsing?
Parsing is the process of analyzing a sentence to uncover its syntactic
structure—that is, how words are organized and related to each other within the
sentence.

Rather than treating a sentence as just a sequence of words, parsing allows us to

answer key structural questions such as:

• Who is performing the action (subject)?

• What is the action (verb)?
• What entities are affected (objects)?
• How are different parts of the sentence connected or modified?

Ex. The burglar robbed the apartment.

• “the burglar” → subject (the doer of the action)

• “robbed” → verb (the action itself)
• “the apartment” → object (the receiver of the action)

This structural relationship is typically represented using a parse tree where the
sentence is broken into hierarchical components like NP (noun phrase) and VP
(verb phrase).

Why Parsing is Important?

It provides multiple layers of linguistic information:

• Part-of-Speech Information
Identifies grammatical categories (noun, verb, adjective, etc.)
• Phrase Structure
Reveals how words group into meaningful units (e.g., noun phrases, verb
phrases)
• Syntactic Relationships
Determines how different elements of a sentence relate to one another
Real-World Applications
It is widely used in real NLP systems, including:

• Machine Translation
• Question Answering Systems
• Conversational Agents (Chatbots)
• Information Extraction Systems

Classical Parsing Problem

Before the 1990s, natural language parsing was primarily based on manually
constructed grammatical rules. Linguists designed rule-based systems, typically
using Context-Free Grammars (CFGs), to describe how sentences are formed.

The Problem of Ambiguity Explosion

A major limitation of classical parsing approaches was the issue of ambiguity.

Even relatively simple sentences could generate a very large number of possible
parse trees. Ex. Fed raises interest rates

• With a minimal grammar → dozens or hundreds of parses

• With a realistic, large-scale grammar → millions of possible parses

This phenomenon is known as ambiguity explosion, where the number of valid

syntactic interpretations grows rapidly with sentence complexity .

Classical parsing systems also faced a fundamental trade-off:

• Strict (highly constrained) grammars

o Reduce incorrect parses
o But Fail to parse many valid sentences
• Loose (less constrained) grammars
o Increase coverage (more sentences can be parsed)
o But Produce an overwhelming number of possible parses

As a result, these systems struggled to balance accuracy and coverage.

The Solution: Statistical Parsing

To overcome these limitations, modern approaches introduced statistical parsing.

Instead of trying to eliminate ambiguity, statistical parsing:

• Allows multiple possible parses

• Assigns a probability to each parse
• Selects the most likely (best) parse based on data

This shift enabled parsers to handle real-world language more effectively by

combining flexible grammars with probabilistic decision-making.

Two Views of Sentence Structure:

1. Constituency Structure (Phrase Structure)
Constituency parsing is a fundamental technique in syntactic analysis that
represents sentences as hierarchical structures of phrases (constituents). It is
based on the assumption that a sentence is not just a sequence of words, but a
structured combination of smaller units such as noun phrases (NP), verb phrases
(VP), and prepositional phrases (PP).

The primary goal of constituency parsing is to identify these constituent phrases

and determine how they are organized within a sentence. This allows us to
uncover the underlying grammatical structure, which is essential for understanding
the meaning of the sentence.

The output of constituency parsing is typically a parse tree, where:

• The root node represents the entire sentence

• Internal nodes represent phrases (e.g., NP, VP)
• Leaf nodes correspond to individual words

This hierarchical representation provides a clear view of how words combine to

form larger linguistic units.
Resolving Ambiguity

One of the most important advantages of constituency parsing is its ability to

resolve structural ambiguity.

Ex. I saw the man with the telescope.

This sentence has two possible interpretations:

1. The observer used a telescope

2. The man had a telescope

Constituency parsing distinguishes between these meanings by assigning different

tree structures, depending on where the phrase “with the telescope” is attached.

Sentence Constituents and Their Types

Constituents are the building blocks of sentence structure. The main types include:

• Noun Phrase (NP)

A phrase centered around a noun.
Ex: “The cute cat”
• Verb Phrase (VP)
A phrase centered around a verb, including its objects and modifiers.
Ex: “sleeps soundly”
• Prepositional Phrase (PP)
A phrase beginning with a preposition followed by a noun phrase.
Ex: “on the table”
• Adjective Phrase (ADJP)
A phrase centered around an adjective.
Ex: “very tall”
• Adverb Phrase (ADVP)
A phrase centered around an adverb.
Ex: “very quickly”
Hierarchical Structure
A key property of constituency parsing is its hierarchical organization.

Constituents are recursively nested inside one another to form larger structures. For
example, a noun phrase may contain a prepositional phrase, which itself contains
another noun phrase.

This hierarchy is typically represented as a tree structure, where:

• Each node corresponds to a constituent

• Parent-child relationships indicate how smaller units combine into larger
ones

Understanding this hierarchy is essential for capturing the syntactic relationships

and meaning of a sentence.

Each bracketed segment is called a constituent, meaning it behaves as a single unit

within the sentence.

How Do We Identify Constituents?

Linguists use several tests to determine whether a group of words forms a

constituent:
1. Movement Test (Distribution Test)

A constituent can often be moved to a different position without breaking the

sentence:

• John talked to the children about drugs.

• John talked about drugs to the children.

The ability to move the phrase while preserving grammatical correctness indicates
that it is a constituent.

2. Substitution Test

A constituent can be replaced by a single word (e.g., a pronoun or adverb):

• on the box → there

• I sat there.

If substitution works, the phrase behaves as a single unit → therefore, it is a

constituent.

2. Dependency Structure
Dependency parsing is a fundamental technique in Natural Language Processing
(NLP) that analyzes the grammatical structure of a sentence by identifying
relationships between individual words. Unlike constituency parsing, which
focuses on grouping words into phrases, dependency parsing emphasizes direct
word-to-word connections.

In this approach, a sentence is represented as a tree or graph, where:

• Each node corresponds to a word

• Edges represent dependency relationships between words
• These edges are labeled to indicate the type of grammatical relationship
(e.g., subject, object, modifier)

The central idea is that every word (except the root) depends on another word,
forming a structured network that captures the sentence’s meaning.
Fundamental Principles of Dependency Parsing
Dependency parsing is based on several key principles:

• Word Relationships
It determines how words in a sentence are connected through grammatical
dependencies.
• Graph Representation
The syntactic structure is represented as a directed graph or tree, where
labeled edges define the relationships between words.
• Grammatical Roles
It captures the syntactic roles of words, such as:
o Subject
o Object
o Modifier
o Complement
• Head-Dependent Structure
Each word (dependent) is linked to a head (parent), and the parser assigns
appropriate labels to describe their relationship.

Context-Free Grammars (CFG)

A Context-Free Grammar (CFG) is a formal system used to model the syntactic
structure of natural language. It defines how sentences can be constructed by
recursively combining smaller units according to a set of production rules.

A CFG is formally represented as:

G = (N, Σ, R, S)

Where:

• N is the set of non-terminal symbols (e.g., S, NP, VP), which represent

abstract syntactic categories
 • Σ is the set of terminal symbols, corresponding to the actual words in the
language
• R is the set of production rules that define how symbols can be expanded
• S is the start symbol, representing a complete sentence

Production Rules

Production rules specify how larger syntactic structures are formed from smaller
components. Each rule takes the form:

X → Y₁ Y₂ ... Yₙ

Where:

• X is a non-terminal symbol
• Y₁, Y₂, ..., Yₙ are either terminals or non-terminals

These rules allow the grammar to generate sentences by repeatedly replacing non-
terminals with their corresponding expansions.

Ex. Derivation using CFG

Probabilistic Context-Free Grammar (PCFG)

A Probabilistic Context-Free Grammar (PCFG) is an extension of a Context-
Free Grammar (CFG) in which each production rule is associated with a
probability. This allows the grammar not only to generate possible sentence
structures but also to evaluate how likely each structure is.
A PCFG is formally defined as:

G = (N, Σ, R, S, P)

Where:

• N is the set of non-terminal symbols

• Σ is the set of terminal symbols
• R is the set of production rules
• S is the start symbol
• P is a probability function that assigns a probability to each production rule

For any given non-terminal, the probabilities of all rules expanding that non-
terminal must sum to 1.

Ex. Consider the following PCFG:

S → NP VP 1.0
VP → V NP 0.4
VP → VP PP 0.2
NP → DT NN 0.3
NP → NP PP 0.7

Each rule is associated with a probability that reflects how frequently or likely that
structure occurs.

Probability of a Parse Tree

In a PCFG, the probability of a complete parse tree is calculated as the product of
the probabilities of all production rules used in generating that tree:

P(tree) = ∏ P(rule used)

This means that more probable trees are those constructed using more likely rules.
Importance of PCFG
PCFGs address one of the main limitations of CFGs—ambiguity—by introducing a mechanism
to rank competing parse trees.

They enable:

• Comparison of multiple parses for the same sentence

• Selection of the most probable parse
• Data-driven parsing decisions, rather than purely rule-based ones

Chomsky Normal Form (CNF)

Chomsky Normal Form (CNF) is a standardized and restricted form of a
Context-Free Grammar (CFG) in which every production rule follows a specific
simplified structure.

In CNF, all rules must conform to one of the following forms:

X → Y Z
X → w

Where:

• X, Y, Z are non-terminal symbols

• w is a terminal symbol (a word in the language)

This restriction ensures that each rule either expands into exactly two non-
terminals or directly produces a terminal.

Why it is important ?
Converting a CFG into CNF is not meant to change the language it generates, but
rather to make the grammar more suitable for efficient computational processing.

CNF is particularly important because it:

• Simplifies the structure of grammar rules

• Enables the use of dynamic programming algorithms
• Is required for parsing algorithms such as the CKY algorithm
• Reduces computational complexity during parsing
Transformation Process
To convert a general CFG into CNF, the following steps are applied
systematically:

1. Eliminate empty productions (ε-rules)

Remove rules that produce an empty string.
2. Eliminate unit productions
Remove rules of the form:

X → Y

where both X and Y are non-terminals.

3. Convert long productions into binary form

Any rule with more than two symbols on the right-hand side is broken into
smaller binary rules by introducing new non-terminal symbols.

CKY Parsing Algorithm

The Cocke–Kasami–Younger (CKY) algorithm is a dynamic programming
algorithm used for parsing sentences based on a grammar in Chomsky Normal
Form (CNF). It systematically builds possible syntactic structures for a sentence
while avoiding redundant computations.

Where The primary goal of the CKY algorithm is to determine the most probable
parse tree for a given input sentence, based on a probabilistic grammar (typically
a PCFG).

Idea:
CKY constructs a triangular chart (parsing table) that represents all possible
constituents for different spans of the sentence.
Each cell in the table is defined as:

This structure allows the algorithm to reuse previously computed results, ensuring
efficiency.

Algorithm Steps
1. Initialization (Lexical Filling)

The algorithm begins by filling the diagonal of the chart:

• Each word in the sentence is assigned its possible grammatical categories

using lexical rules
• These entries correspond to spans of length 1

2. Building Larger Spans

The algorithm then processes spans of increasing length:

• For each span (i, j), all possible split points k are considered
• The span is divided into two sub-spans: (i, k) and (k, j)
• For each split, the algorithm checks grammar rules of the form:

X→YZ

• If Y exists in cell[i][k] and Z exists in cell[k][j], then X is added to cell[i][j]

3. Incorporating Probabilities (Viterbi CKY)

When using a PCFG, CKY computes probabilities to select the best parse:

score(X, i, j) = max P(X → Y Z) × score(Y, i, k) × score(Z, k, j)

• The algorithm keeps the maximum probability for each constituent

• This ensures that only the most likely parse is retained
Backtracking
To reconstruct the final parse tree:

• The algorithm stores backpointers indicating:

o Which rule was used
o Where the split occurred
• After filling the chart, these backpointers are used to recover the best parse
tree

Computational Complexity
• Time Complexity: O(n³)
• This is significantly more efficient than naive parsing approaches, which
may be exponential