21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

UNIT III SYNTACTIC ANALYSIS 9

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.

3.1: Context-Free Grammars

Linguistic Organization of NLP

 Grammar and lexicon - the rules for forming well-structured sentences,

and the words that make up those sentences
 Morphology - the formation of words from stems, prefixes, and suffixes
E.g., eat + s = eats
 Syntax - the set of all well-formed sentences in a language and the rules for
forming them
 Semantics - the meanings of all well-formed sentences in a language
 Pragmatics (world knowledge and context) - the influence of what we
know about the real world upon the meaning of a sentence.
E.g., "The balloon rose." allows an inference to be made that it must be filled
with a lighter-than-air substance.
 The influence of discourse context (E.g., speaker-hearer roles in a
conversation) on the meaning of a sentence
 Ambiguity
 lexical - word meaning choices (E.g., flies)
 Syntactic - sentence structure choices (E.g., She saw the man on the hill
with the telescope.)
 Semantic - sentence meaning choices (E.g., They are flying planes.)

Grammars and parsing

What is Grammar?
Grammar is defined as the rules for forming well-structured sentences. While
describing the syntactic structure of well-formed programs, Grammar plays a very
essential and important role. In simple words, Grammar denotes syntactical rules
that are used for conversation in natural languages.

1
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Syntactic categories (common denotations) in NLP

NP - noun phrase
VP - verb phrase
S - sentence
Det - determiner (article)
N - noun
TV - transitive verb (takes an object)
IV - intransitive verb
Prep - preposition
PP - prepositional phrase
Adj – adjective

Context Free Grammar (CFG)

A context-free grammar consists of a set of rules or productions that

define the set of all well-formed sentences in a language. Each rule has
a left-hand side, which identifies a syntactic category, and a right-
hand side, which defines its alternative component parts, reading from
left to right.

Context Free Grammar (CFG) - Formal Definition

Context-free grammar G is a 4-tuple.

G = (V, T, S, P)
These parameters are as follows;
 V – Set of variables (also called as Non-terminal symbols)
 T – Set of terminal symbols (lexicon)
 The symbols that refer to words in a language are called terminal
symbols.
 Lexicon is a set of rules that introduce these symbols.
 S – Designated start symbol (one of the non-terminals, S Є V)
 P – Set of productions (also called as rules).
 Each rule in P is of the form A → s, where
 A is a non-terminal (variable) symbol.

2
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

 Each rule can have only one non-terminal symbol on the left
hand side of the rule.
 s is a sequence of terminals and non-terminals. It is from (T U
V)*, infinite set of strings.
 A grammar G generates a language L.

Example 1:

G = (V, T, S, P)
V = {S, NP, VP, PP, Det, Noun, Verb, Aux, Pre}
T = {„a‟, „ate‟, „cake‟, „child‟, „fork‟, „the‟, „with‟}
S=S
P = { S → NP VP
NP → Det Noun | NP PP
PP → Pre NP
VP → Verb NP
Det → „a‟ | „the‟
Noun → „cake‟ | „child‟ | „fork‟
Pre → „with‟
Verb → „ate‟}

Some notes:
 Note 1: In P, pipe symbol (|) is used to combine productions
into single representation for productions that have same
LHS. For example, Det → ‘a’ | ‘the’ derived from two rules Det →
‘a’ and Det → ‘the’. Yet it denotes two rules not one.
 Note 2: NP – Noun Phrase, VP – Verb Phrase, PP – Prepositional
Phrase, Det – Determiner, Aux – Auxiliary verb

Sample derivation:
S → NP VP
→ Det Noun VP
→ the Noun VP
→ the child VP
3
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

→ the child Verb NP

→ the child ate NP
→ the child ate Det Noun
→ the child ate a Noun
→ the child ate a cake

From this derivation, we can understand that the sentence „the child
ate a cake‟ is a valid and accepted sentence by the grammar G. in
other words, the sentence is part of the language produced by G.

Generation of Derivation Tree

A derivation tree or parse tree is an ordered rooted tree that graphically
represents the semantic information a string derived from a context-free
grammar.
Representation Technique
 Root vertex − Must be labeled by the start symbol.
 Vertex − Labeled by a non-terminal symbol.
 Leaves − Labeled by a terminal symbol or ε.
If S → x1x2 …… xn is a production rule in a CFG, then the parse tree /
derivation tree will be as follows −

There are two different approaches to draw a derivation tree −

Top-down Approach −
 Starts with the starting symbol S
 Goes down to tree leaves using productions

4
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Bottom-up Approach −
 Starts from tree leaves
 Proceeds upward to the root which is the starting symbol S

Derivation or Yield of a Tree

The derivation or the yield of a parse tree is the final string obtained by
concatenating the labels of the leaves of the tree from left to right,
ignoring the Nulls. However, if all the leaves are Null, derivation is Null.

Example
Let a CFG {N,T,P,S} be
N = {S}, T = {a, b}, Starting symbol = S, P = S → SS | aSb | ε
One derivation from the above CFG is “abaabb”
S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

5
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Sentential Form and Partial Derivation Tree

A partial derivation tree is a sub-tree of a derivation tree/parse tree such

that either all of its children are in the sub-tree or none of them are in
the sub-tree.

Example

If in any CFG the productions are −

S → AB, A → aaA | ε, B → Bb| ε
the partial derivation tree can be the following −

If a partial derivation tree contains the root S, it is called a sentential

form. The above sub-tree is also in sentential form.

Leftmost and Rightmost Derivation of a String

 Leftmost derivation − A leftmost derivation is obtained by applying
production to the leftmost variable in each step.
 Rightmost derivation − A rightmost derivation is obtained by
applying production to the rightmost variable in each step.

Example
Let any set of production rules in a CFG be
X → X+X | X*X |X| a
over an alphabet {a}.
The leftmost derivation for the string "a+a*a" may be −
X → X+X → a+X → a + X*X → a+a*X → a+a*a

6
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

The stepwise derivation of the above string is shown as below −

The rightmost derivation for the above string "a+a*a" may be –

X → X*X → X*a → X+X*a → X+a*a → a+a*a

The stepwise derivation of the above string is shown as below −

7
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Example 2:

8
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Derivations:

s => np vp
=> det n vp
=> the n vp
=> the giraffe vp
=> the giraffe iv
=> the giraffe dreams

Goals of Linguistic Grammars

 Permit ambiguity - ensure that a sentence has all its possible

parses (E.g., "fruit flies like an apple" in Figure 2)

 Limit ungrammaticality - E.g., require agreement in number,

tense, gender, person. Disallow "the giraffe eat the apple" (Figure 1)

 Ensure meaningfulness - E.g., disallow "the apple eats the giraffe"

(Figure 1)

9
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3.2: Grammar Rules for English

Context-Free Grammar (CFG) is a formalism used to describe the
syntax of a language. In the context of English grammar, CFG provides
a set of rules for generating valid sentences. Here are some grammar
rules for English with respect to CFG:

 Sentence Structure:
S → NP VP: A sentence (S) consists of a noun phrase (NP) followed
by a verb phrase (VP).
S → NP VP
Example: "The cat (NP) sleeps (VP)."

 Noun Phrase (NP):

NP → (Det) (Adj*) N (PP*): A noun phrase (NP) can consist of an
optional determiner (Det), followed by zero or more adjectives (Adj*),
a noun (N), and zero or more prepositional phrases (PP*).
NP → (Det) (Adj*) N (PP*)
Example: "A (Det) small (Adj) black (Adj) cat (N) with green eyes (PP)."

 Verb Phrase (VP):

VP → V (NP): A verb phrase (VP) consists of a verb (V) optionally
followed by a noun phrase (NP).
VP → V (NP)
Example: "She (NP) eats (V) apples (NP)."

 Prepositional Phrase (PP):

PP → P NP: A prepositional phrase (PP) consists of a preposition (P)
followed by a noun phrase (NP).
PP → P NP
Example: "The book (NP) is on (P) the table (NP)."

 Determiners (Det):
Det → a | an | the: Determiners are words that introduce nouns
and help to specify them.
10
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Det → a | an | the
Example: "An (Det) apple (N) fell from the tree (PP)."

 Adjectives (Adj):
Adj → tall | blue | beautiful: Adjectives modify nouns and provide
additional information about them.
Adj → tall | blue | beautiful
Example: "The (Det) tall (Adj) building (N) is located in the city (PP)."

 Verbs (V):
V → run | eat | sleep: Verbs indicate actions or states of being.
V → run | eat | sleep
Example: "They (NP) run (V) every morning (PP)."

 Prepositions (P):
P → in | on | at: Prepositions show relationships between nouns
and other elements in a sentence.
P → in | on | at
Example: "She lives (V) in (P) New York (NP)."

 Conjunctions (Conj):
Conj → and | but | or: Conjunctions join words, phrases, or
clauses.
Conj → and | but | or
Example: "He likes apples (NP) and (Conj) she likes oranges (NP)."

 Interjections (Interj):
Interj → wow | oh | hey: Interjections express emotion or
sentiment.
Interj → wow | oh | hey
Example: "Wow (Interj), what a beautiful sunset (NP)!"

These examples illustrate how the CFG rules can be applied to

generate syntactically valid sentences in English.

11
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3.3: Treebanks

Corpus
A corpus is a large and structured set of machine-readable
texts that have been produced in a natural communicative
setting. Its plural is corpora. They can be derived in different ways like
text that was originally electronic, transcripts of spoken language and
optical character recognition, etc.

Treebank
Treebank is a corpus in which each sentence is annotated with a parse
tree. It represents syntactic and semantic relations of words in a
sentence. Treebanks are created by
 Parsing texts using parsers
 Human annotations

TreeBank Corpus
 It may be defined as linguistically parsed text corpus that
annotates syntactic or semantic sentence structure.
 Geoffrey Leech coined the term „treebank‟, which represents that
the most common way of representing the grammatical analysis
is by means of a tree structure.
 Generally, Treebanks are created on the top of a corpus, which
has already been annotated with part-of-speech tags.

Types of TreeBank Corpus

Semantic and Syntactic Treebanks are the two most common types of
Treebanks in linguistics.

1. Semantic Treebanks:-
 These Treebanks use a formal representation of sentence‟s
semantic structure.
 They vary in the depth of their semantic representation. Robot
Commands Treebank, Geoquery, Groningen Meaning Bank,
12
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

RoboCup Corpus are some of the examples of Semantic

Treebanks.

2. Syntactic Treebanks:-
 Opposite to the semantic Treebanks, inputs to the Syntactic
Treebank systems are expressions of the formal language
obtained from the conversion of parsed Treebank data.
 The outputs of such systems are predicate logic based meaning
representation.
 Various syntactic Treebanks in different languages have been
created so far.
 For example, Penn Arabic Treebank, Columbia Arabic
Treebank are syntactic Treebanks created in Arabia
language. Sininca syntactic Treebank created in Chinese
language. Lucy, Susane and BLLIP WSJ syntactic corpus
created in English language.

Example: The Penn Treebank Project:

 It is the most cited Treebank for the English language.

 It consists of over 4.5 million words of American English.
 Each sentence has PoS and syntactic structure.
 It has 36 PoS tags and 12 other tags for punctuation and symbols.
 Data in the Penn Treebank are stored in separate files for different
layers of annotation.

Examples of Penn Treebank Format:

Here's the parse tree for the sentence "The cat chased the mouse" in the
Penn Treebank format:
(S
(NP (DT The) (NN cat))
(VP (VBD chased)
(NP (DT the) (NN mouse))))

13
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

In this parse tree:

 "(S" represents the start of the sentence.

 "(NP" represents the noun phrase.
 "(DT The)" represents the determiner "the".
 "(NN cat)" represents the noun "cat".
 "(VP" represents the verb phrase.
 "(VBD chased)" represents the past tense verb "chased".
 "(NP" represents the noun phrase.
 "(DT the)" represents the determiner "the".
 "(NN mouse)" represents the noun "mouse".

This parse tree captures the syntactic structure of the sentence according to
the Penn Treebank annotation format.

Here's a visual representation of the parse tree for the sentence "The cat
chased the mouse":

In this parse tree:

 (S) represents the start of the sentence.
 (NP) represents the noun phrase "The cat".
 (DT) represents the determiner "The".
 (NN) represents the noun "cat".
 (VP) represents the verb phrase "chased the mouse".
 (VBD) represents the past tense verb "chased".
 (NP) represents the noun phrase "the mouse".

14
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

 (DT) represents the determiner "the".

 (NN) represents the noun "mouse".
This parse tree visually captures the hierarchical structure of the sentence
according to its syntactic constituents.

3.3.1: Extracting Grammars from Treebank

Extracting grammars from a treebank involves identifying recurring patterns

in the parse trees and using them to derive grammar rules. Here's a general
approach to extracting grammars from a treebank:

1. Parse Tree Analysis:

 Analyze the parse trees in the treebank to identify common syntactic
patterns and structures.
 Look for recurring sub-trees or subtrees that represent similar
linguistic constructions.
2. Identify Constituent Phrases:
 Identify the constituent phrases (e.g., noun phrases, verb phrases) in
the parse trees.
 Determine the combinations of words and their syntactic categories
that form these phrases.
3. Extract Production Rules:
 For each constituent phrase, extract the production rules that
describe its formation.
 Production rules specify how phrases are constructed from their
component parts.
 Example production rule: NP -> (Det) (Adj*) N (PP*) (where NP is a
noun phrase, Det is a determiner, Adj* represents zero or more
adjectives, N is a noun, and PP* represents zero or more prepositional
phrases).
4. Generalize Rules:
 Generalize the extracted rules to capture broader syntactic patterns
and variations.
 Identify commonalities among rules and consolidate them to reduce
redundancy.
 Ensure that the rules cover a wide range of syntactic constructions
observed in the treebank.
15
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

5. Refinement and Validation:

 Refine the extracted grammar rules based on linguistic principles and
domain knowledge.
 Validate the grammar by applying it to unseen data from the treebank
and checking its coverage and accuracy.
 Iterate on the extraction and refinement process to improve the quality
of the grammar.
6. Grammar Representation:
 Represent the extracted grammar rules in a formalism suitable for
parsing algorithms.
 Common formalisms include Context-Free Grammar (CFG),
Dependency Grammar, and Lexical Functional Grammar (LFG).
7. Application:
 Apply the extracted grammar to tasks such as syntactic parsing,
language generation, and grammar checking.
 Evaluate the performance of the grammar on test data and refine it
further based on feedback and analysis.

This process helps to create a formal representation of the grammatical

structures observed in the Treebank facilitating the development of
computational models for understanding and generating human language.

Example:

Step 1: Preprocessing
Let's say we have the following sentence in our treebank:
Sentence: "The cat chased the mouse."

We start by tokenizing the sentence:

Tokens: ["The", "cat", "chased", "the", "mouse", "."]

Step 2: Parsing
Using a parser (e.g., Stanford Parser, spaCy), we generate a parse tree for
this sentence. Let's say the constituency parse tree looks like this:

16
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

(S
(NP (Det The) (N cat))
(VP (V chased) (NP (Det the) (N mouse)))
(. .)
)

Step 3: Treebank Representation

We represent the parse tree in a suitable format. For example, we can use a
bracketed representation:
(S
(NP (Det The) (N cat))
(VP (V chased) (NP (Det the) (N mouse)))
(. .)
)

Step 4: Grammar Extraction

We extract production rules from the parse tree. Each rule typically consists
of a parent node and its children.

For the given parse tree, the extracted rules are:

S -> NP VP
NP -> Det N
VP -> V NP
N -> cat
V -> chased
Det -> The
N -> mouse
Det -> the
. denotes the end of the sentence.

Step 5: Generalization
We can generalize the extracted rules to capture common patterns and
eliminate redundancy. For example:

NP -> Det N can be generalized to NP -> NounPhrase, where NounPhrase

represents any sequence of words that forms a noun phrase.
17
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Step 6: Evaluation and Refinement

We evaluate the extracted grammar by testing it on unseen data or
comparing it against existing grammars. We refine the grammar based on
evaluation results, adjusting rules as needed to improve accuracy and
coverage.

Step 7: Application
Once we have the grammar extracted from the treebank, we can use it for
various natural language processing tasks such as parsing, generation, and
machine translation.

3.3.2: Treebank Searching

Treebank searching involves querying a treebank to find specific linguistic

patterns or structures within parsed sentences.

Overview:

1. Define search query:

Specify the linguistic patterns or structures you are interested in finding
within treebank,
2. Use Query Language or Tools:
Some treebanks provide query languages or tools to search for specific
patterns. For example,
Tregex is the tool for the Stanford parser which allows you to formulate
complex tree patterns and search the Penn Treebank.
Tgrep & Tgrep2 are publicly available tools for searching treebanks that
use a similar language for expressing tree constraints.
3. Regex or Treebank Pattern Matching:
Formulate search queries using regular expressions or specialized tree
pattern languages that match the syntactic structures you are looking
for.
4. Example Query:
Suppose we want to find sentences with a specific verb phrase structure.
Our query might look like: „(S(VP…))‟, where … represents the internal
structures of verb phrase.

18
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

5. Execute Search:
Apply the search criteria to the treebank data using the chosen query
language or tool.
6. Retrieve Results:
Obtain sentences or tree structures that match the specified criteria.

A pattern in tgrep or Tgrep2 consists of a specification of a node

followed by links to other nodes. A node specification can then be
used to return the subtree rooted at that node.

For example, the pattern ‘NP’ returns all subtree in a corpus whose
root is NP.

Nodes can be specified by a name, a regular expression inside slashes or a

disjunction of these.

Example:

We can specify a singular or plural noun(NN or NNS) in Penn Treebank

notation as follows: /NNS?/  NN|NNS

The power of tgrep/Tgrep2 pattern lies in the ability to specify information

about links using the operator „<‟. It means immediately dominates.

Thus the following pattern matches an NP immediately dominating a PP:

NP < PP

NP << PP ->this pattern matches a NP dominating a PP.

The relation . marks linear precedence. The following pattern matches an

NP that immediately dominates a JJ and is immediately followed by a PP.

NP < [Link]

Example 1: Write the command using Tregex to search for the sentences
where the top-level structure in a sentence („S‟) with a verb phrase („VP‟).

Ans: [Link] -s “treebank_file” “S>VP”

Example 2: Find the sentences where the verb phrase (VP) includes a past
tense verb (VBD) for the given treebank.

19
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

1. ( S ( NP ( DT The ) ( NN cat ) )
( VP ( VBD chased )
( NP ( DT the )
( NN mouse ) ) ) )
2. ( S ( NP ( DT A ) ( NN dog ) )
( VP ( VBD barked )
( ADVP ( RB loudly ) ) ) )

Ans: VP < VBD which results in

( S ( NP ( DT The ) ( NN cat ) )
( VP ( VBD chased )
( NP ( DT the )
( NN mouse ) ) ) )
( S ( NP ( DT A ) ( NN dog ) )
( VP ( VBD barked )
( ADVP ( RB loudly ) ) ) )

3.4: Normal Forms for Grammars

A formal language is defined as a (possibly infinite) set of strings of words.

This suggests that we could ask if two grammars are equivalent by asking if
they generate the same set of strings. Infact, it is possible to have two
distinct context-free grammars generate the same language.

Two kinds of Grammar Equivalence:

1. Weak Equivalence
2. Strong Equivalence

1. Strong Equivalence: - Two grammars are strongly equivalent if they

generate the same set of strings and if hey assign the same phrase
structure to each sentence.

20
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

2. Weak Equivalence: Two grammars are weakly equivalent if they generate

the same set of strings but do not assign the same phrase structure to
each sentence.

Chomsky Normal Form (CNF):

There are special forms for CFGs such as Chomsky Normal Form, where
every production has the form A→BC or A→c.

A Context-Free Grammar G = (V, Σ, R, S) is in Chomsky Normal Form (CNF)

if and only if every rule in R is of one of the following forms:
1. A→a, for A∈V and a∈Σ or
2. A→BC, for A, B, C∈V.

Converting CFG to CNF:

The conversion to Chomsky Normal Form has four main steps:
1. Get rid of all ε productions.
2. Get rid of all productions where RHS is one variable.
3. Replace every production that is too long by shorter productions.
4. Move all terminals to productions where RHS is one terminal.

Example:

Convert the following CFG into Chomsky Normal Form:

S→AbA
A→Aa|ε
Solution:
After the first step, one has:
S→AbA|bA|Ab|b
A→Aa|a

The second step does not apply.

After the third step,one has:

S→TA|bA|Ab|b
A→Aa|a
T→Ab

21
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

And finally, one has:

S→TA|BA|AB|b
A→AC|a
T→AB
B→b
C→a

3.5: Dependency Grammars

What is Dependency Parsing?

Dependency parsing is a technique used in natural language processing for
analyzing the grammatical structure of sentences. A Dependency Parser
simply transforms a sentence into a Dependency Tree.
It involves identifying the relationships between words in a sentence and
representing them in the form of a dependency tree.

Dependency grammar is a segment of syntactic text analysis. It determines the

relationship among the words in a sentence. Each of these relationships is
represented in the form of a triplet: relation, governor, and dependent. As a result of
recursively parsing the observed relationship between the words is represented in a
top-down manner and depicted as a tree, which is known as the dependency tree.

Dependency Tree
A Dependency Tree is a structure that can be defined as a directed graph,
with |V| nodes (vertices), corresponding to the words, and |A| Arcs,
corresponding to the syntactic dependencies between them.

Dependency trees follow three rules:

1. They have a single designated root node that does not have any
incoming arcs.
2. Each vertex, other than the root note, has exactly one incoming arc.
3. A unique path exists between the root node and every single vertex in
the set of vertices.
 These rules work together to make sure that every word has just one
head, that the dependency structure is well connected, and that there is

22
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

only one root node from which a unique directed path connects each of
the words in the sentence.

Example
Let's use the dependency grammar framework to represent the following
sentence “Kevin can hit the baseball with a bat”:

3.5.1: Breakdown of dependency grammar

Here's a simplified breakdown of dependency grammar:

Word tokens: In natural language processing, the text is divided into basic
units called tokens. A sentence is made up of a group of word tokens. Each
of these tokens has a unique function and is a building block of the
language. For the sentence: “Kevin can hit the baseball with a bat,” the
tokens are: “Kevin,” “can,” “hit,” “the,” “baseball,” “with,” “a,” “bat.”

23
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Dependency relations: Dependency grammar focuses on how words relate

to each other by using arrows or lines. For example, in the dependency
grammar example above, the word “with” depends on the word “hit” as a
preposition.

Root node: Every sentence has a central idea represented by a main verb,
which connects all other words in the sentence to it. This central idea is
known as the root in dependency grammar.

The governor and the dependent: In every word relationship, there are two
key roles: the governor and the dependent. For instance, in the sentence
“Kevin can hit the baseball with a bat,” the word “hit” acts as the governor
because it's the main action, while “Kevin” serves as the dependent since
the action relies on the subject.

Dependency labels: Each dependency relation line is labeled to illustrate

the relationship between the words on each end. Labels like subject (subj)
and object (obj) provide the grammatical role for every word in the sentence
structure.

3.5.2: Applications
Dependency grammar is a fundamental concept in natural language
processing (NLP) and is essential for various applications. Here are some
examples:

Figure: Applications of dependency grammar

24
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

 Dependency parsing: Using dependency grammar principles, this

process automatically analyzes sentences and produces a tree that
illustrates the grammatical relationships between words. This is
essential for understanding the structure of sentences.
 Information extraction: Structured information can be extracted
from text using dependency relations, which allows for identifying
relationships between entities and facts in a document.
 Machine translation: When translating between languages,
dependency structures help align words and phrases. They help to
ensure accurate and clear translations.
 Text-to-speech synthesis: Dependency information influences the
rhythm and tone of synthesized speech, which enhances its natural
sound.

3.5.2: Dependency Parsing Techniques

There are two main techniques used for dependency parsing: Transition-
Based Parsing and Graph-Based Parsing.

1) Transition-Based Parsing
Transition-based parsing is a machine learning-based approach to
dependency parsing. It involves predicting a sequence of actions to build a
dependency tree. These actions include shifting a word onto the stack,
reducing the stack by creating a dependency between the top two words, or
creating a new dependency by combining two existing dependencies.

Example of constructing a dependency tree for a simple sentence:

Sentence: "The cat chased the mouse."

1. Tokenization:
 Tokens: ["The", "cat", "chased", "the", "mouse", "."]
2. Part-of-Speech (POS) Tagging:
 POS Tags: ["DT", "NN", "VBD", "DT", "NN", "."]
 DT: Determiner
 NN: Noun
 VBD: Verb, past tense
 .: Punctuation mark (period)

25
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3. Dependency Parsing Algorithm:

 We'll use a simple transition-based dependency parsing algorithm for
this example.

4. Parsing:
 Starting with an initial configuration (empty stack, all words in the
buffer), we apply transitions to build the dependency tree.
 Here's a simplified sequence of transitions:
1. SHIFT: Move "The" from the buffer to the stack.
2. SHIFT: Move "cat" from the buffer to the stack.
3. LEFT-ARC: Create a dependency arc from "cat" to "The" with the
label "det" (determiner).
4. SHIFT: Move "chased" from the buffer to the stack.
5. SHIFT: Move "the" from the buffer to the stack.
6. SHIFT: Move "mouse" from the buffer to the stack.
7. RIGHT-ARC: Create a dependency arc from "chased" to "cat" with
the label "nsubj" (nominal subject).
8. RIGHT-ARC: Create a dependency arc from "chased" to "mouse"
with the label "dobj" (direct object).
9. SHIFT: Move "." from the buffer to the stack.
10. LEFT-ARC: Create a dependency arc from "." to "chased"
with the label "punct" (punctuation).
5. Dependency Tree Representation:

In this visualization:
 "(nsubj)" indicates that "cat" is the nominal subject of "chased".
 "(dobj)" indicates that "mouse" is the direct object of "chased".
 "(det)" indicates determiner dependency.
 "(punct)" indicates punctuation dependency.

26
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

This visualization provides a clearer understanding of the dependency

relationships between words in the sentence.

2) Graph-Based Parsing

Constructing a graph-based dependency tree involves representing the

syntactic dependencies between words in a sentence as a directed graph.
Here are the general steps to construct a graph-based dependency tree:
1. Tokenization: Break down the input sentence into individual words or
tokens.
2. Part-of-Speech (POS) Tagging: Assign a part-of-speech tag to each word in
the sentence to capture its grammatical role.
3. Dependency Parsing: Identify the syntactic dependencies between words in
the sentence. This step involves determining the relationships between
words, such as subject-verb, verb-object, modifier-head, etc.
4. Graph Representation: Represent the dependencies as a directed graph,
where each word is a node and the dependencies between them are
represented as directed edges (arcs). The edges are labeled with the type of
dependency they represent.
5. Visualization (Optional): Optionally, visualize the dependency tree
graphically for better understanding and interpretation.

Let's illustrate these steps with an example sentence "The cat chased the
mouse.":
1. Tokenization:
 Tokens: ["The", "cat", "chased", "the", "mouse", "."]
2. Part-of-Speech (POS) Tagging:
 POS Tags: ["DT", "NN", "VBD", "DT", "NN", "."]
 DT: Determiner
 NN: Noun
 VBD: Verb, past tense
 .: Punctuation mark (period)
3. Dependency Parsing:
 Determine the syntactic dependencies between words. For example:
 "The" (DT) is a determiner for "cat" (NN).

27
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

"cat" (NN) is the nominal subject (nsubj) of "chased" (VBD).

 "chased" (VBD) is the root of the sentence.
 "the" (DT) is a determiner for "mouse" (NN).
 "mouse" (NN) is the direct object (dobj) of "chased" (VBD).
 "." (.) is a punctuation mark.
4. Graph Representation:
 Construct a directed graph based on the identified dependencies:

In this dependency tree:

 The word "chased" is the root of the tree, as it is the main verb of the
sentence.
 "cat" and "mouse" are direct dependents of "chased", representing the
subject and object of the verb, respectively.
 The word "The" is a dependent of "cat" and "mouse", indicating that "The"
is a determiner for both "cat" and "mouse".

3.7: Syntactic Parsing, Ambiguity, Dynamic Programming parsing

3.7.1: Syntactic Parsing

Parsing: Parsing is the process of examining the grammatical structure and

relationships inside a given sentence or text in natural language processing
(NLP). It involves analyzing the text to determine the roles of specific words,
such as nouns, verbs, and adjectives, as well as their interrelationships.

This analysis produces a structured representation of the text, allowing NLP

computers to understand how words in a phrase connect to one another.
Parsers expose the structure of a sentence by constructing parse trees or
dependency trees that illustrate the hierarchical and syntactic relationships
between words.

28
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Syntactic Parsing:
Syntactic parsing deals with a sentence‟s grammatical structure. It involves
looking at the sentence to determine parts of speech, sentence boundaries,
and word relationships.
The two most common approaches included are as follows:
1) Constituency Parsing: Constituency Parsing builds parse trees that
break down a sentence into its constituents, such as noun phrases and
verb phrases. It displays a sentence‟s hierarchical structure,
demonstrating how words are arranged into bigger grammatical units.
2) Dependency Parsing: Dependency parsing depicts grammatical links
between words by constructing a tree structure in which each word in
the sentence is dependent on another. It is frequently used in tasks such
as information extraction and machine translation because it focuses on
word relationships such as subject-verb-object relations.

Parsing Techniques in NLP

The fundamental link between a sentence and its grammar is derived from a
parse tree. A parse tree is a tree that defines how the grammar was utilized
to construct the sentence. There are mainly two parsing techniques,
commonly known as top-down and bottom-up.

29
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

1. Top-Down Parsing
 A parse tree is a tree that defines how the grammar was utilized to
construct the sentence. Using the top-down approach, the parser
attempts to create a parse tree from the root node S down to the
leaves.
 The procedure begins with the assumption that the input can be
derived from the selected start symbol S.
 The next step is to find the tops of all the trees that can begin with S
by looking at the grammatical rules with S on the left-hand side,
which generates all the possible trees.
 Top-down, left-to-right, and backtracking are prominent search
strategies that are used in this method.
 The search begins with the root node labeled S, i.e., the starting
symbol, expands the internal nodes using the next productions with
the left-hand side equal to the internal node, and continues until
leaves are part of speech (terminals).
 If the leaf nodes, or parts of speech, do not match the input string, we
must go back to the most recent node processed and apply it to
another production.

Let‟s consider the grammar rules:

Sentence = S = Noun Phrase (NP) + Verb Phrase (VP) + Preposition Phrase
(PP)
Take the sentence: “John is playing a game”, and apply Top-down parsing

If part of the speech does not

match the input string, backtrack
to the node NP.

30
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Part of the speech verb does not match the input string, backtrack to the
node S, since PNoun is matched.

The top-down technique has the advantage of never wasting time

investigating trees that cannot result in S, which indicates it never examines
subtrees that cannot find a place in some rooted tree.

2. Bottom-Up Parsing
 Bottom-up parsing begins with the words of input and attempts to
create trees from the words up, again by applying grammar rules one
at a time.
 The parse is successful if it builds a tree rooted in the start symbol S
that includes all of the input. Bottom-up parsing is a type of data-
driven search. It attempts to reverse the manufacturing process and
return the phrase to the start symbol S.
 It reverses the production to reduce the string of tokens to the
beginning Symbol, and the string is recognized by generating the
rightmost derivation in reverse.
 The goal of reaching the starting symbol S is accomplished through a
series of reductions; when the right-hand side of some rule matches
the substring of the input string, the substring is replaced with the

31
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

left-hand side of the matched production, and the process is repeated

until the starting symbol is reached.
 Bottom-up parsing can be thought of as a reduction process. Bottom-
up parsing is the construction of a parse tree in postorder.

Considering the grammatical rules stated above and the input sentence
“John is playing a game”,

The bottom-up parsing operates as follows:

Comparison of Top-Down and Bottom-Up Parsing

Top-Down Parsing Bottom-Up Parsing

It is a parsing strategy that first looks at It is a parsing strategy that first looks
the highest level of the parse tree and at the lowest level of the parse tree
works down the parse tree by using the and works up the parse tree by using
rules of grammar. the rules of grammar.

32
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Top-Down Parsing Bottom-Up Parsing

Bottom-up parsing can be defined as

Top-down parsing attempts to find the
an attempt to reduce the input string
left most derivations for an input string.
to the start symbol of a grammar.

In this parsing technique we start

In this parsing technique we start
parsing from the bottom (leaf node of
parsing from the top (start symbol of
the parse tree) to up (the start symbol
parse tree) to down (the leaf node of
of the parse tree) in a bottom-up
parse tree) in a top-down manner.
manner.

This parsing technique uses Left Most This parsing technique uses Right
Derivation. Most Derivation.

The main leftmost decision is to select The main decision is to select when to
what production rule to use in order to use a production rule to reduce the
construct the string. string to get the starting symbol.

Example: Recursive Descent parser. Example: ItsShift Reduce parser.

Applications of Parsing in NLP

Parsing is a key natural language processing approach for analyzing and
comprehending the grammatical structure of natural language text. Parsing
is important in NLP for various reasons.
Some of them are mentioned below:
1. Syntactic Analysis: Parsing helps in determining the syntactic
structure of sentences by detecting parts of speech, phrases, and
grammatical relationships between words. This information is critical
for understanding sentence grammar.
2. Named Entity Recognition (NER): NER parsers can detect and
classify entities in text, such as people‟s, organizations, and locations‟
names, among other things. This is essential for information
extraction and text comprehension.
3. Semantic Role Labeling (SRL): SRL parsers determine the semantic
roles of words in a sentence, such as who is the “agent,” “patient,” or

33
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

“instrument” in a given activity. It is essential for understanding the

meaning of sentences.
4. Machine Translation: Parsing can be used to assess source language
syntax and generate syntactically correct translations in the target
language. This is necessary for machine translation systems such as
Google Translate.
5. Question Answering: Parsing is used in question-answering systems
to help break down a question into its grammatical components,
allowing the system to search a corpus for relevant replies.
6. Text Summarization: Parsing is the process of extracting the
essential syntactic and semantic structures of a text, which is
necessary for producing short and coherent summaries.
7. Information Extraction: Parsing is used to extract structured
information from unstructured text, such as data from resumes, news
articles, or product reviews.

3.7.2: Ambiguity

Syntactic Ambiguity refers to ambiguity in sentence structure and be able

to interpret in different forms. This structural ambiguity occurs when the
grammar assigns more than one possible parse to a structure.
Example: Consider the following sentence:
“I shot an elephant wearing pyjama”
The above sentence has the structural ambiguity as discussed below:
 First, Does shoot mean taking a photo or pointing a gun to?
 Second, who is wearing pyjama? Is it the person or the elephant?

34
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Types of Ambiguity:
There are three types of structural Ambiguity:

Attachment Ambiguity: A sentence has an attachment ambiguity if a

particular constituent can be attached to the parse tree at more than one
place.
Example:
“Guna ate an ice crème with fruits from Chennai”
In the above sentence, we have two prepositional phrases “with fruits” and
“from chennai”.
They can be understood with following possible meanings:
 Guna who is from Chennai ate an ice crème filled with fruits.
 Guna ate an ice crème filled with fruits and the ice crème is brought
from Chennai.
 Guna who is from Chennai ate the ice crème with the help of fruits.
 Guna with the help of fruits ate the ice crème which is bought from
Chennai.

Coordination Ambiguity: In this, different set of phrases can be conjoined

by a conjunction like “and”.
Example: The phrase “old men and women can be bracketed as [old[men
and women]], referring to old men and old women, or as [old men] and
[women] in which case it is only the men who are old.

Local Ambiguity: Even if a sentence is not ambiguous [ie. It does not have
more than one parse in the end], it can be inefficient to parse because of
local ambiguity. Local ambiguity occurs when some part of sentence is
ambiguous, ie. It has more than one parse, even if the whole sentence is not
ambiguous.
Example:
“Book that flight” - this sentence is not ambiguous, but when the parser
sees the first word “BOOK”, it cannot know if the word is a verb or noun
until later. That is, it must consider both possible parses.

Existing Solution to Syntactic Ambiguity:

 Previously parsers were based on deterministic grammar rules.
 However, now parsers are mostly based on neural networks.
35
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Disambiguation:-
It is the process of determining the choosing the correct parse from the
multitude of possible parses. It is the group of techniques to handle
ambiguity.
 Unfortunately, effective disambiguation algorithms generally require
statistical, semantic and pragmatic knowledge which are not readily
available during syntactic processing.
 Lacking such knowledge, we are left with the choice of simply
returning the entire possible parse tree for a given input.
Unfortunately, generating all the possible parses from robust, highly
ambiguous, wide-coverage grammars such as the Penn Treebank
grammar is problematic.

3.7.3: Dynamic Programming Parsing

Dynamic Programming provides a framework for solving the problems such

as, ambiguity, repeated substructures, recursion and space and time
complexity, arises during the syntactic parsing.

[Link]: CKY Parsing

 CKY = Cocke-Kasami-Younger (called as CKY algorithm)
 It is a bottom-up parsing method which starts with the words.
 It follows dynamic programming model
o Saves the results in a table/chart
o Re-use these results in finding larger constituents.
 Complexity: O(n3|G|) – where, n: length of string, |G|:size of grammar
 Presumes a CFG in Chomsky Normal Form.

Chomsky Normal Form (CNF):

A CFG G is in Chomsky normal form if each of its productions has one of
the following forms:
XYZ
Xa
Conversion CFG to CNF:

1. Copy all conforming rules to the new grammar unchanged.

2. Converting terminals within rules to dummy non-terminals.

36
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3. Convert unit-productions.
4. Make all rules binary and add them to new grammar.

CKY Algorithm:

37
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

CYK Algorithm:

Example:

Given: Grammar in CNF:

S  NP VP
S  X1 VP
X1  Aux NP
S  book | include | prefer
S  Verb NP
S  X2 PP
S  Verb PP
S  VP PP
NP  I | she | me
NP  TWA| Houston
NP  Det Nominal
NP  NP Nominal
Prop-Noun  Houston
Det  the
Nominal  book | flight | meal | money
Nominal  Nominal Noun
Nominal  Nominal PP
VP  book | include |prefer
VP  Verb NP
VP  X2 PP
X2  Verb NP
VP  Verb PP
VP  VP PP
PP  Prep NP
Noun  flight

38
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Prep  through
Verb  book

Sentence: “book the flight through Houston”

39
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Advantages of CKY Parsing:

1. Efficiency:
 CKY parsing is a dynamic programming algorithm that works
efficiently for parsing context-free grammars (CFGs) in Chomsky
Normal Form (CNF).
 It has a time complexity of O(n^3) for general CFGs, which is relatively
efficient compared to some other parsing algorithms.
 For CFGs in CNF, it has a time complexity of O(n^3) where n is the
length of the input sentence.
2. Completeness:
 CKY parsing is guaranteed to find a parse if one exists for the given
sentence and CFG.
 It explores all possible parse trees for a sentence within the given
grammar.
3. Space Efficiency:
 It requires space proportional to the square of the input sentence
length, which is generally reasonable for most sentences.
4. Supports Ambiguity:
 CKY can handle ambiguous grammars and sentences, providing
multiple possible parse trees if they exist.

Disadvantages of CKY Parsing:

1. Limited to CFGs:
 CKY parsing is specifically designed for context-free grammars (CFGs)
and requires the grammar to be in Chomsky Normal Form (CNF) or a
close equivalent.
 Some natural language phenomena, such as long-distance
dependencies or cross-serial dependencies, may not be captured well
in CFGs, limiting the expressiveness of CKY parsing for certain
linguistic structures.
2. Preprocessing:
 The grammar must be transformed into CNF before applying the CKY
algorithm, which can be an additional preprocessing step.
 This transformation can lead to an increase in the number of rules in
the grammar, potentially making it more complex and harder to
maintain.

40
 21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3. Ambiguity:
 While CKY can handle ambiguity and return multiple parse trees,
dealing with ambiguity can also be a disadvantage in some cases.
 When a sentence has multiple valid parse trees, CKY will return all of
them, potentially complicating downstream processing tasks that rely
on a single interpretation.
4. Lack of Semantic Information:
 CKY parsing focuses on syntactic structure and does not directly
capture semantic relationships between words.
 For tasks requiring deep semantic understanding, additional
processing or post-parsing steps are needed.
5. Not Ideal for Large Grammars:
 For very large grammars, CKY parsing can become computationally
expensive and memory-intensive.
 The efficiency of CKY parsing depends on the size and complexity of
the grammar, and very large grammars may not be practical to use
with CKY.

[Link]: Earley Algorithm

 Proposed by Jay Early

 It uses dynamic programming.
 A clever hybrid Bottom-Up and Top-Down approach.
 Bottom-Up parsing completely guided by Top-Down prediction.
 Handles general CFGs.
 Time Complexity O(n3).
 Core idea is a single left-to-right pass that fills an array called chart
that has N+1 entries.
 For each word position in the sentence, the chart contains a list of
states representing the partial parse tree that have been generated so
far.
 The indexes represent the location between the words in an input
(like 0 Book 1 that 2 flight 3).
 At the end of the sentence, the chart compactly encodes all the
possible parses of the input.

41
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

 Maintains sets of “dotted” grammar rules that:

– Reflect what the parser has “seen” so far
– Explicitly predict the rules and constituents that will combine into a
complete parse
 We use (.) dot within the right-hand side of a states grammar rule to
indicate the progress made in recognizing it. The resulting structure is
called a dotted rule.
Definition: A dotted rule is a data structure used in top-down parsing to record parital solutions
towards discovering a constituent.
 The fundamental operation of a Early parser is to march through
the N+1 set of states in the chart in a left-to-right fashion,
processing the states within each set in order.
 At each step, three operations are applied to each state:
1. Predict sub-structure (based on grammar)
The predictor runs when the next term after dot is not a terminal. It
will "expand" the term suggest some new candidates from the
grammar rule set.
2. Scan partial solutions for a match
The scanner runs when the term after dot is a terminal. It checks
whether a state could match the next term. If it matches:
1. add this state to next state set as a candidate;
2. move the dot to the next position.
3. Complete a sub-structure (i.e., build constituents)
It is completion of the parsing process, which traces back the
rules matched before expansion

Algorithm: Earley Parsing:

42
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Example:

Consider the following grammar rules:

X  S eos
S  NP VP
NP  DET N
NP  N
VP  V NP
N  Mary
N  otter
DET  the
V  feeds
eos  eos

Parse the below sentence using Earley Algorithm:

Marry feeds the otter eos

43
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

44
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

45
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

46
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

47
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

48
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

49
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

50
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

51
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

52
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Advantages of Earley Parsing:

 Generality: Earley parsing can handle a wide range of grammar types,

including ambiguous and context-free grammars, making it suitable
for various natural language processing tasks.
 Efficiency: It has linear-time complexity for unambiguous grammars
and cubic-time complexity for ambiguous grammars, which can be
more efficient than other parsing algorithms for certain types of
grammars.
 Incremental Parsing: Earley parsing is inherently incremental,
meaning it can update parse states as new input tokens are processed
without reanalyzing previous parts of the input.
 Predictive Parsing: It can predict possible future parse states based
on the current input, allowing for lookahead and anticipation of
potential parse paths.

Disadvantages of Earley Parsing:

 Space Complexity: Earley parsing can consume significant memory

resources, especially for ambiguous grammars or long input
sentences, due to the need to maintain a chart of parse states.
 Performance for Ambiguous Grammars: While Earley parsing is
capable of handling ambiguity, its performance can degrade
significantly for highly ambiguous grammars, leading to slower parsing
times.
 Overhead for Predictive Parsing: The predictive capabilities of Earley
parsing can introduce additional overhead, particularly when dealing
with lookahead and maintaining multiple potential parse paths.
 Complexity in Implementation: Implementing Earley parsing can be
more complex compared to simpler parsing techniques, requiring
careful management of parse states and chart data structures.

53
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

[Link]: Chart Parsing:

Chart Parser is a type of parser suitable for ambiguous grammars including

grammars of natural languages.
Chart: It is a data structure that sores partial results of the parsing process
in such a way that they can be reused. The chart for an n-word sentence
consists of:
 N + 1 vertices
 A number of edges that connect vertices

General Idea:

The process of parsing an n-word sentence consists of forming a chart with

n + 1 vertices and adding edges to the chart one at a time.
 Goal: - To produce a complete edge that spans from vertex 0 to n and
is category S.
 There is no backtracking.
 Everything that is put in the chart stays there.
 Chart contains all information needed to create parse tree.

General Operation:

The basic operation involves combining an active arc with a complete

constituents (keys).
Three kinds of data structures used:

1. Agenda (to store new complete constituents)

2. Active arcs (partial parse tree)
3. Chart
54
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Algorithm:

1) i = 0
2) if Agenda is empty and I < n, then set I = i+1, find all PoS of Xi and add
them as constituents <pi> C <pi+1> to the Agenda.
3) Pick a key constituent <pj> C <pk> from the Agenda.
4) For each grammar rule of the form A  CX1….Xm, add <pj>[A 
.CX1….Xm]<pk> to the list of active arcs.
5) Use Key to extend all relevant active arcs.
6) Add LHS of any completed active arcs into the Agenda.
7) Insert the Key into the Chart.
8) If Key is <1>S<n>, then Accept the input, else goto (2).

Example:

Given the following grammar rules, parse the sentence:

“The cute girls sing a song”

Rule No Rules Dictionary Words

1 S  NP VP Det  a | the | an
2 NP  Det Noun Noun  girls | apple | song
3 NP  Det Adj Noun Adj  cute | smart
4 NP  Adj Noun Verb  sing | ate
5 VP  Verb
6 VP  Verb NP

Solution

1 The 2 cute 3 girl 4 sing 5 a 6 song 7

Active Rule Status of Rule Completed

Token Agenda Operation
arc No. processing Constituent
1 Insertion S  .NP VP
The Det2 1, 2 2 Insertion NP  [Link] Det
1, 2 3 Insertion NP  [Link] Noun Det
cute Adj1 1, 3 3 Extension NP  Det [Link] Det Adj
2, 3 4 Insertion NP  [Link] Adj

55
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

girl Noun1 1, 4 3 Extension NP  Det Adj Noun. NP

2, 4 4 Extension NP  Adj Noun. NP
1, 4 1 Extension S  [Link] NP
sing Verb1 4, 5 5 Insertion VP  Verb. VP
4, 5 6 Insertion VP  [Link] Verb
a Det1 5, 6 2 Insertion NP  [Link] Det
5, 6 3 Insertion NP  [Link] Noun Det
song Noun3 5, 7 2 Extension NP  Det Noun. NP
4, 7 6 Extension VP  Verb NP. VP
1, 7 1 Extension S  NP VP. S

56
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Advantages of Chart Parsing:

 Efficient handling of global ambiguity
 incremental parsing
 flexibility in representation
 suitability for complex grammars.

Disadvantages of Chart Parsing:

 High space and time complexity
 challenges in parsing ambiguity
 initial setup overhead
 complexity in implementation.

COMPARISON OF DYNAMIC PROGRAMMING PARSING METHODS

Feature CKY Parsing Earley Parsing Chart Parsing

Efficiency Efficient for CNF General-purpose Efficient handling of
grammars parsing ambiguous and
complex grammars
Space Complexity Space-efficient Space-intensive due High space
to chart maintenance complexity, especially
for long sentences
Time Complexity Efficient for Moderate time High time
unambiguous complexity, complexity,
grammars, Particularly for particularly for
Exponential for highly ambiguous lengthy sentences
ambiguous grammars
grammars
Applicability Limited to CNF General-purpose, Suitable for a wide
grammars handles a wide range range of grammars
of grammars including ambiguous
and unambiguous
grammars
Incremental Not inherently Incremental parsing, Incremental parsing
Parsing incremental updates parse states compatibility
as new input tokens
are processed
Ambiguity Limited capability Handles ambiguity Efficient handling of
Handling for ambiguity efficiently but may global ambiguity,
suffer performance considers all possible
issues with highly parse trees
ambiguous simultaneously
grammars
Implementation Moderate Complex complex
Complexity

57
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3.8: Shallow Parsing

Shallow parsing, also known as chunking, is a type of natural language

processing (NLP) technique that aims to identify and extract meaningful
phrases or chunks from a sentence.
 Unlike full parsing, which involves analyzing the grammatical
structure of a sentence, shallow parsing focuses on identifying
individual phrases or constituents, such as noun phrases, verb
phrases, and prepositional phrases.
 Shallow parsing is an essential component of many NLP tasks,
including information extraction, text classification, and sentiment
analysis.

 One of the primary benefits of shallow parsing is its efficiency.

 Full parsing involves analyzing the entire grammatical structure of a
sentence, which can be computationally intensive and time-
consuming.
 Shallow parsing, on the other hand, involves identifying and extracting
only the most important phrases or constituents, making it faster and
more efficient than full parsing.
Shallow parsing involves several key steps.
1) The first step is sentence segmentation, where a sentence is divided
into individual words or tokens.
2) The next step is part-of-speech tagging, where each token is assigned
a grammatical category, such as noun, verb, or adjective.
3) Once the tokens have been tagged, the next step is to identify and
extract the relevant phrases or constituents from the sentence. This is
typically done using pattern matching or machine learning algorithms

58
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

that have been trained to recognize specific types of phrases or

constituents.
Example:

 In yhe sentence, “The black cat sat on the mat” the noun phrase “The
black cat” can be identified and extracted using noun phrase
chunking.

Chunking
Chunking is the process of identifying and classifying the flat, non-
overlapping segments of a sentence that constitute the major parts-of-
speech found in wide-coverage grammars.
Chunk: typically includes headword and pre-head material.

Example:

[NP The HD box] that [NP you] [VP ordered] [PP from] [NP shaw] [VP
never arrived]

Approaches to Chunking:

1. Finite-State Rule-Based
2. Machine Learning

1. Finite-State Rule-Based
 In this, rules are hand-crafted to capture the phrases of interest for
any particular application.
 The rules must be of no recursion
o Eg:- NP  (Det) Noun* Noun
 Implemented as FSTs. (unionized/determinized/minimized)
 Chunking proceeds from left-to-right, finding the longest matching
chunk from the beginning of the sentence and continuing with the
first word after the end of the previously recognized chunk.
 F-measure 85-92.

59
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

In this approach, an initial set of transducers is used, in the way just

described, to find a subset of syntactic base-phrases. These base-phrases
are then passed as input to further transducers that detect larger and larger
constituents such as prepositional phrases, verb phrases, clauses, and
sentences. Consider the following rules, again adapted from Abney (1996).
FST2 PP → Preposition NP
FST3 S → PP* NP PP* VP PP*

2. Finite-State Rule-Based

A sequential classifier is a type of machine learning model that makes

predictions based on sequences of input data. These classifiers are
particularly useful for tasks where the order of the input matters, such as
time series data, natural language processing (NLP), speech recognition, and
genomics.

60
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Fig. 13.19 illustrates this scheme with the example given earlier. During
training, the classifier would be provided with a training vector consisting of
the values of 12 features (using Penn Treebank tags) as shown. To be
concrete, during training the classifier is given the 2 words to the right of
the decision point along with their part-ofspeech tags and their chunk tags,
the word to be tagged along with its part-of-speech, the two words that
follow along with their parts-of speech, and finally the correct chunk tag, in
this case I NP. During classification, the classifier is given the same vector
without the answer and is asked to assign the most appropriate tag from its
tagset.

3.9: Probabilistic CFG

Probabilistic Context-Free Grammar, also known as Stochastic Context-Free

Grammar, G is defined by four parameters (N, Σ, R, S) with a slight
augmentation to each of the rules in R:
N a set of non-terminals or variables.

61
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Σ a set of terminal symbols

R a set of rules or productions, each of the form A  β [p],
Where, A is a non-terminal,
Β is string of symbols from the set (Σ U N)* and p is a number
between o and 1 expressing P(β|A).
S a designated start symbol.

PCFG differs from CFG by augmenting each rule in R with a conditional

probability:
A  β [p] Here, p represents the probability that the given Non-
terminal A will be expanded to the sequence β.

We can represent this probability as,

P(Aβ) or P(A  β|A) or P(RHS|LHS)
If we consider all the possible expansions of a non-terminal, the su of their
probabilities must be 1;

∑ ( )

3.9.1: PCFG for Disambiguation:

A PCFG assigns a probability to each parse tree T of a sentence. This

attribute is useful in disambiguation.
The probability of a particular parse tree T is defined as the product of the
probabilities of all the n rules used to expand each of the n non-terminal
nodes in the parse tree T, where each rule I can be expressed as LHS i 
RHSi:

( ) ∏ ( )

The resulting probability P(T,S) is both the joint probability of the parse and
the sentence and also the probability of the parse P(T).

Example:

62
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

63
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Equation for choosing the most likely parse neatly simplifies the to choosing
the parse with highest probability:
̂( ) ̇ ( )
( )

3.10: Probabilistic CKY Parsing of CFGs

The problem PCFG is to produce the most-likely parse ̂ for a given sentence
S.

The algorithms for computing the most likely parse are simple extensions of
the standard algorithms for parsing; is the probabilistic version of CKY.

As with the CKY algorithm, we assume fpr the probabilistic CKY algorithm
that the PCFG is in CNF form.

Algorithm:

64
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

65
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3.11: Probabilistic Lexicalized CFGs

Problems with PCFG
PCFGs suffer from tow serious problems,
 lack of sensitivity to lexical information
 lack of sensitivity to structural preferences.
 Due to these two problems, PCFGs cannot always capture the full range of
syntactic variation and ambiguity that exists in natural languages leading
to errors and incorrect parses, particularly when working with sentences
that are structurally complex or contain multiple possible interpretations.
 Lexicalized PCFGs are developed from a motivation to solve these issues
and work better when compared with PCFG.

Probabilistic Lexicalized CFG

Probabilistic Lexicalized Context-Free Grammar (PLCFG) is also a type of
grammar used in natural language processing to generate and analyze
sentences in a given language.
It is a combination of a lexicalized context-free grammar which uses lexical
items that word as the basic units for generating sentences, and
probabilistic models which assign probabilities to the different rules and
structures in the grammar.
What is Lexicalization?
Lexicalization is the process of making a word expresses a concept by
turning a phrase or sentence into a single word or a sequence of words.
Lexicalization is done by combining the most important words in the phrase
or sentence to maintain the meaning of the original phrase or sentence.
Example: to be honest could be lexicalized as candidly or frankly.

66
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Example:

3.11.1: Collins Parser

The first intuition of the Collins parser is to think of the right-hand side of
every (internal) CFG rule as consisting of a head non-terminal, together with
67
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

the non-terminals to the left of the head, and the non-terminals to the right
of the head. In the abstract, we think about these rules as follows:

LHS → Ln Ln−1 ...L1 H R1 ...Rn−1 Rn

Since this is a lexicalized grammar, each of the symbols like L1 or R3 or H
or LHS is actually a complex symbol representing the category and its head
and head tag, like VP(dumped,VP) or NP(sacks,NNS).

Since this is a lexicalized grammar, each of the symbols like L1 or R3 or H

or LHS is actually a complex symbol representing the category and its head
and head tag, like VP(dumped,VP) or NP(sacks,NNS).
Now instead of computing a single MLE probability for this rule, we are
going to break down this rule via a neat generative story, a slight
simplification of what is called Collins Model 1. This new generative story is
that given the left-hand side, we first generate the head of the rule, and then
generate the dependents of the head, one by one, from the inside out. Each
of these generation steps will have its own probability.
We are also going to add a special STOP non-terminal at the left and right
edges of the rule; this non-terminal will allow the model to know when to
stop generating dependents on a given side. We‟ll generate dependents on
the left side of the head until we‟ve generated STOP on the left side of the
head, at which point we move to the right side of the head and start
generating dependents there until we generate STOP.
So it‟s as if we are generating a rule augmented as follows:

P( V P(dumped,V BD) → STOP V BD(dumped,V BD) NP(sacks,NNS) PP(into,P) STOP

Let‟s see the generative story for this augmented rule. We‟re going to make
use of three kinds of probabilities: PH for generating heads, PL for
generating dependents on the left, and PR for generating dependents on the
right.

68
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

3.12: Feature Structures

Feature structures are used for the representation of linguistic information

in several grammar formalisms for natural language processing. These
structures are a type of directed graph, in which arcs are labelled by names
of features, and nodes correspond to values of features.
69
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Feature structures are often written as attribute value matrices. The

attribute value matrix expressing that something is singular and 3rd
person, i.e. that the feature number has the value singular and the
feature person has the value 3, looks as follows:

In this example all feature values are atomic, but they can also be feature
structures again. As in this feature structure for instance:

This makes it possible to group features of a common type together.

Another common way of representing feature structures is to use directed
graphs. In this case, values (no matter whether atomic or not) are
represented as nodes in the graph, and features as edge labels. Here is an
example. The attribute value matrix

can also be represented by the following directed graph.

Paths in this graph correspond to sequences of features that lead

through the feature structure to some value. The path carrying the
labels and corresponds to the sequence of
features and leads to the value .

The graph that we have just looked at had a tree structure, i.e., there was
no node that had more than one incoming edge. This need not always be the
case. Look at the following example:

70
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Here, the paths and both lead to the same node,

i.e., they lead to the same value and share that value. This property of
feature structures that several features can share one value is
called reentrancy. It is one of the reasons why feature structures are so
useful for computational linguistics.

In attribute value matrices, reentrancy is commonly expressed by

coindexing the values which are shared. Written in the matrix notation the
graph from above looks as follows. The boxed 1 indicates that the two
features sequences leading to it share one value.

3.12.1: Feature Structure Unification

Unification is a (partial) operation on feature structures. Intuitively, it is the

operation of combining two feature structures such that the new feature
structure contains all the information of the original two, and nothing more.
For example, let be the feature structure

and let be the feature structure

Then, , the unification of these two feature structures is:

Clearly contains all the information that is in and --- and it

doesn't contain any other information.

71
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

Why did we call unification a partial operation? Why didn't we just say that
it was an operation on feature structures? The point is that unification
is not guaranteed to return a result. For example, let be the feature
structure

and let be the feature structure

Then does not exist. There is no feature structure that contains all
the information in and , because the information in these two feature
structures is contradictory. So, the value of this unification is undefined.
Those are the basic intuitions about unification, so let's now give a precise
definition. This is easy to do if we make use of the idea of subsumption,
which we discussed above.
The unification of two feature structures and (if it exists) is
the smallest feature structure that is subsumed by both and . That
is, (if it exists) is the feature structure with the following three
properties:
1. ( is subsumed by )
2. ( is subsumed by )
3. If is a feature structure such that and , then (
is the smallest feature structure fulfilling the first two properties.
That is, there is other feature structure that also has properties 1 and
2 and subsumes .)
If there is no smallest feature structure that is subsumed by both and ,
then we say that the unification of and is undefined.
We said above that the subsumption relation on feature structures can be
thought of as analogous to the subset relation on sets. Similarly,
unification is rather like an analog of set-theoretic union (recall that the
union of two sets is the smallest set that contains all the elements in both
sets). But there is a difference: union of sets is an operation (that is, the
union of two sets is always defined) whereas (as we have discussed)
unification is only a partial operation on feature structures.
Now that the formal definition is in place, let's look at a few more examples
of feature structure unification. First, let be

72
21ML1601 – NLP Unit – 3 III Year / VI Semester AI&DS

and let be the feature structure

Then is

Next, an example involving reentrancies. Let be

Then is

A final example. What happens if one of the feature structures we are trying
to unify is the empty feature structure --- that is, the feature structure
containing no information at all? Pretty clearly, for any feature structure ,
we have that:

That is, the empty feature structure is the identity element for the (partial)
operation on feature structure unification. That is, the empty feature
structure behaves like the empty set in set theory (recall that the union of
the empty set with any set is just ).

73