UNIT-3

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

Normal Forms for grammar – Dependency Grammar – Syntactic Parsing, Ambiguity, Dynamic
Programming parsing – Shallow parsing Probabilistic CFG, Probabilistic CYK, Probabilistic
Lexicalized CFGs – Feature structures, Unification of feature structures

Syntactic Parsing:
Syntactic parsing is the process of analyzing the grammatical structure of a sentence according
to the rules of a formal grammar. It determines how words in a sentence combine to form phrases
and how those phrases relate to each other to form the complete sentence. The output of syntactic
parsing is usually a parse tree (constituency tree) or a dependency structure, which clearly
represents the hierarchical organization of the sentence.

Syntactic parsing plays an important role in understanding the grammatical structure of a

sentence which helps machines interpret the meaning of the text correctly.
Why it is need of Syntactic Parsing?
Natural language sentences can often be complex and ambiguous. Simply knowing the
meanings of individual words is not sufficient to understand the sentence. It is also necessary to
understand how the words are arranged and related to each other.

For example:
“The boy saw the man with a telescope.”
This sentence can have two possible interpretations:
1. The boy used a telescope to see the man.
2. The man had the telescope.
Syntactic parsing helps identify the different possible structures of the sentence and represent
them formally.

Basic Concepts in Syntactic Parsing

1. Grammar Rules

Syntactic parsing uses grammar rules, usually defined using Context-Free Grammars (CFGs).
These rules describe how smaller units combine to form larger grammatical structures.

Example grammar rules:

S → NP VP
NP → Det N
VP → V NP
Det → the, a
N → boy, apple, man
V → eats, saw
1
Example of Syntactic Parsing :

Consider the sentence: “The boy eats an apple.”

Step 1: Lexical Analysis

Each word is assigned a part of speech.

Word Part of Speech

The Determiner
Boy Noun
Eats Verb
An Determiner
Apple Noun

Step 2: Apply Grammar Rules

Using the grammar rules:

NP → Det N
VP → V NP
S → NP VP

The parser groups the words into phrases.

NP → The boy
NP → an apple
VP → eats an apple

Finally: S → NP VP

Step 3: Construct the Parse Tree

This tree shows the hierarchical structure of the sentence.

2
Types of Syntactic Parsing

1. Constituency Parsing (Phrase Structure Parsing) :In this approach, a sentence is divided
into constituents or phrases.
Example: The boy eats an apple
Constituents:
NP → The boy
VP → eats an apple
This method produces a parse tree showing phrase structure.

2. Dependency Parsing

Dependency parsing focuses on relationships between words rather than phrases. Each word
depends on another word called its head.

Example:

eats
/ \
boy apple
| |
The an

Here:

 eats is the main verb (root)

 boy is the subject of eats
 apple is the object of eats

Dependency parsing is widely used in modern NLP systems.

Parsing Strategies :

Different strategies are used to perform syntactic parsing.

1. Top-Down Parsing

Top-down parsing starts from the start symbol (S) and tries to derive the sentence step by step
using grammar rules.

3
Example:

S → NP VP
NP → Det N
VP → V NP

The parser attempts to generate the sentence starting from S.

2. Bottom-Up Parsing

Bottom-up parsing starts with the input words and gradually combines them into phrases until
the start symbol (S) is produced.

Example:

The + boy → NP
an + apple → NP
eats + NP → VP
NP + VP → S

3. Dynamic Programming Parsing

Dynamic programming methods store intermediate results to avoid repeated calculations.

Examples include:

 CYK Algorithm
 Earley Parser
 Chart Parsing

These methods improve parsing efficiency.

Challenges in Syntactic Parsing :

1. Ambiguity
Many sentences can have multiple valid parse trees.
Example:
“I saw the man with a telescope.”
Two interpretations are possible depending on the attachment of with a telescope.

2. Long Sentences
As sentence length increases, the number of possible parse trees grows rapidly.

3. Complex Grammar
Natural language grammar is often very complex and irregular.

4
Applications of Syntactic Parsing :
Syntactic parsing is used in many NLP applications:
1. Machine Translation – understanding sentence structure helps translate correctly.
2. Question Answering Systems – identifying subject, object, and relations.
3. Information Extraction – extracting important facts from text.
4. Speech Recognition – analyzing spoken language.
5. Grammar Checking Systems – detecting grammatical errors.

Ambiguity:
In Natural Language Processing (NLP), ambiguity arises when a word, phrase, or sentence can
have multiple interpretations. Unlike humans, who use intuition and context to resolve meaning,
machines rely on algorithms and statistical models, making ambiguity a significant challenge for
tasks like machine translation, chatbots, and sentiment analysis.

Types of Ambiguity

Lexical ambiguity:

Definition: Lexical ambiguity refers to a situation where a word or phrase has multiple m
eanings, leading to potential confusion in understanding the intended message. This type of ambi
guity often arises from polysemy, where a single word can have different meanings depending o
n the context in which it is used
Example : "The chicken is ready to eat"
 Meaning 1: The chicken is cooked and ready to be eaten.
 Meaning 2: The chicken is hungry and ready to eat food.

Structural ambiguity

Definition: Structural ambiguity, also known as syntactic ambiguity, occurs when the arr
angement of words in a sentence allows for multiple interpretations. This type of ambiguity c an
arise from the placement of modifiers, ambiguous pronoun references, or unclear sentence
structures.

Example : " I saw the man with a telescope."

 Meaning 1: I used a telescope.

 Meaning 2: The man had a telescope.

5
Dynamic Programming Parsing:

Dynamic Programming (DP) parsing in Natural Language Processing (NLP) is a technique

used to efficiently parse sentences,especially when dealing with complex
grammars or ambiguous [Link] works by breaking the problem into smaller
subproblems and reusing intermediate results instead of recomputing them.

Why Dynamic Programming for Parsing?

 Avoids recomputation: Many subtrees in parsing are repeated; DP stores and reuses
them.
 Handles ambiguity: Can store multiple possible parses for the same span.
 Improves efficiency: Reduces exponential parsing time to polynomial time for certain
grammars.

Common DP Parsing Algorithms:

CYK Algorithm (Cocke–Younger–Kasami)

CYK algorithm is a parsing algorithm for context free grammar. In order to apply CYK
algorithm to a grammar, it must be in Chomsky Normal Form. It uses a dynamic
programming algorithm to tell whether a string is in the language of a grammar.

Algorithm : Let w be the n length string to be parsed. And G represent the set of rules in our
grammar with start state S.
1. Construct a table DP for size n × n.

6
 2. If w = e (empty string) and S -> e is a rule in G then we accept the string else we reject.
3.
For i = 1 to n:
For each variable A:
We check if A -> b is a rule and b = wi for some i:
If so, we place A in cell (i, i) of our table.
4.
For l = 2 to n:
For i = 1 to n-l+1:
j = i+l-1
For k = i to j-1:
For each rule A -> BC:
We check if (i, k) cell contains B and (k + 1, j) cell contains C:
If so, we put A in cell (i, j) of our table.
5
We check if S is in (1, n):

If so, we accept the string

Else, we reject.

Example :

This example uses a simple grammar and sentence to illustrate the process.

a). Define the Grammar (in CNF)

A grammar must be in Chomsky Normal Form, where all rules are in the form of A → BC (two

non-terminals) or A → a (a single terminal).

S → NP VP

NP → Det N | N

VP → V NP

7
 Det → 'the' | 'a'

N → 'cat' | 'dog'

V → 'chased'

b). The Input Sentence

w = "The cat chased a dog"

Length of sentence n = 5 words.

c). Construct the Triangular Table

A table of size n x n is created. The algorithm fills this table bottom-up, one row (substring

length) at a time. Each cell (i, j) represents the set of non-terminals that can derive the substring

starting at position j with length i.

1 (The) 2 (cat) 3 (chased) 4 (a) 5 (dog)

Len 1 {Det} {N} {V} {Det} {N}
Len 2 {NP} {} {NP} {NP}
Len 3 {} {VP} {VP}
Len 4 {} {}
Len 5 {S}

8
d). Filling the Table

Length 1 (Bottom Row): For each single word, find the non-terminal(s) that produce it.

 T[1, 1] ("The") = {Det} (from Det → 'the')

 T[1, 2] ("cat") = {N} (from N → 'cat')
 T[1, 3] ("chased") = {V} (from V → 'chased')
 T[1, 4] ("a") = {Det} (from Det → 'a')
 T[1, 5] ("dog") = {N} (from N → 'dog')

Length 2: For each two-word substring, consider all possible splits (only one split for length 2)
and applicable rules A → BC.

 T[2, 1] ("The cat"): Split at 1. Check Det (T[1, 1]) and N (T[1, 2]). NP → Det N is a
rule. Add NP to T[2, 1].
 T[2, 2] ("cat chased"): Split at 2. Check N (T[1, 2]) and V (T[1, 3]). No rule
matches N V.
 T[2, 3] ("chased a"): Split at 3. Check V (T[1, 3]) and Det (T[1, 4]). No rule
matches V Det.
 T[2, 4] ("a dog"): Split at 4. Check Det (T[1, 4]) and N (T[1, 5]). NP → Det N is a
rule. Add NP to T[2, 4].

Length 3:
 T[3, 1] ("The cat chased"): Splits: "The" + "cat chased" (Det + empty); "The cat" +
"chased" (NP + V). No rules match these combinations.
 T[3, 2] ("cat chased a"): Splits: "cat" + "chased a" (N + empty); "cat chased" + "a"
(empty + Det). No rules match.
 T[3, 3] ("chased a dog"): Splits: "chased" + "a dog" (V + NP); "chased a" + "dog"
(empty + N). VP → V NP is a rule. Add VP to T[3, 3].

9
Length 4:
 T[4, 1] ("The cat chased a"): Splits: "The" + "cat chased a" (Det + empty); "The
cat" + "chased a" (NP + empty); "The cat chased" + "a" (empty + Det). No rules
match.
 T[4, 2] ("cat chased a dog"): Splits: "cat" + "chased a dog" (N + VP); "cat chased"
+ "a dog" (empty + NP); "cat chased a" + "dog" (empty + N). No rules match N VP.

Length 5 (Top Row):

 T[5, 1] ("The cat chased a dog"): Splits: "The" + "cat chased a dog" (Det + empty);

"The cat" + "chased a dog" (NP + empty); "The cat chased" + "a dog" (empty + NP);
"The cat chased a" + "dog" (empty + N).
 Check the split: "The cat" (NP in T[2, 1]) and "chased a dog" (VP in T[3, 3]).
 S → NP VP is a rule. Add S to T[5, 1].
5. Result
Since the start symbol S is present in the top-left cell covering the entire sentence, the string
"The cat chased a dog" is valid according to the grammar.

Earley Parser

The Earley parser is a chart parsing algorithm in NLP that uses dynamic programming to
efficiently parse sentences with a given context-free grammar (CFG). It employs three operations
(prediction, scanning, and completion) to build a table, or "chart," of states representing partial
parses.
Example: Parsing "book that flight"
Consider the following simple grammar and input sentence:
Grammar (G):
S → NP VP
S → VP
NP → Det Nominal
Nominal → Noun
VP → Verb
VP → Verb NP

10
Det → that | this | a | the
Noun → book | flight | meal | money
Verb → book | include | prefer
Input Sentence: "book that flight"
Input Tokens (indexed 0 to 3): book (0) that (1) flight (2)

The parser fills a chart of state sets, S(k), for each position k
in the input. A state is represented as (Rule, Origin), where the dot • indicates the current parsing
position in the rule, and Origin is the input position where the rule started.
Chart S(0) (before processing book)
The process begins by adding the top-level rules for the start symbol S (often augmented with a
special starting rule like

.
Chart S(1) (after processing book)
The scanner processes the word book. It finds a match with the predicted Verb rule in S(0).

The completer then uses this completed state to update any states in S(0)
that were expecting a Verb.

11
(S → VP •, 0): Completed in S(1). This S rule is fully complete, indicating "book" could be a
valid (albeit minimal) sentence.

Chart S(2) (after processing that)

The scanner processes the word that

 (Det → that •, 1): Scanned from S(1). that is a Determiner (Det).

The completer uses this completed state to update states in S(1)
that were expecting a Det.
 (NP → Det • Nominal, 1): Completed in S(2)
. The NP rule is now expecting a Nominal.

Chart S(3) (after processing flight)

The scanner processes the word flight.
 (Noun → flight •, 2): Scanned from S(2). flight is a Noun.

The start rule is complete, confirming the input string is valid according to the grammar.

12
(which covers the entire input from index 0 to 3) confirms the sentence is grammatically correct.
The stored states allow the reconstruction of the full parse tree.

Chart Parsing Algorithm:

Chart parsing is a dynamic programming technique used in syntactic parsing to analyze the
grammatical structure of sentences in Natural Language Processing. The main idea of chart
parsing is to store intermediate parsing results in a special data structure called a chart, so that the
same computations are not repeated many times during parsing. In traditional parsing methods,
the same phrase may be analyzed repeatedly in different parts of the sentence, which increases
computation time.
Chart parsing solves this problem by recording partial results and reusing them whenever needed.

A chart is a data structure that stores partial results of [Link] contains edges that
represent partial or completed grammar [Link] edges help the parser build larger syntactic
structures step by step.

Example chart positions for a sentence with 4 words:

Position Word
0 the
1 cat
2 eats
3 fish

Chart positions represent word boundaries.

An edge represents a syntactic constituent or partial grammar rule.

There are two types of edges.

1. Active Edge : An active edge represents a partially completed rule.

VP → V • NP

Meaning:

 Verb has been recognized

 Noun phrase is still expected

13
The dot (•) shows the current progress.

2. Passive Edge: A passive edge represents a completed rule.

NP → Det N •

Meaning:

A noun phrase has been fully recognized.

Chart Parsing Process:

Chart parsing generally follows these steps:

1. Initialize chart
2. Add lexical entries
3. Build larger constituents
4. Store edges in chart
5. Continue until the full sentence is parsed

Example: "The cat chased the mouse"

A classic example uses a simple context-free grammar (CFG) to parse a sentence like "The cat

chased the mouse".

Grammar Rules:

S → NP VP
NP → Det N
VP → V NP
Det → "The" | "the"
N → "cat" | "mouse"
V → "chased"

14
Chart Parsing Process (Bottom-Up approach):

Start End Constituent Explanation

0 1 Det "The" is a determiner.
1 2 N "cat" is a noun.
0 2 NP Det (0,1) + N (1,2) combine to form a Noun Phrase.
2 3 V "chased" is a verb.
3 4 Det "the" is a determiner.
4 5 N "mouse" is a noun.
3 5 NP Det (3,4) + N (4,5) combine to form a Noun Phrase.
2 5 VP V (2,3) + NP (3,5) combine to form a Verb Phrase.
NP (0,2) + VP (2,5) combine to form a complete Sentence, indicating a
0 5 S
successful parse.

The chart records each of these findings as "edges," preventing redundant computations and
managing ambiguity by storing multiple possible constituents for the same span.

Time Complexities :

Algorithm Time Complexity

CYK Algorithm O(n³)
Earley Parser O(n³) worst case, O(n²) average, O(n) for some grammars
Chart Parsing O(n³) worst case

15
Shallow Parsing :

Definition:
Shallow parsing, also known as chunking, is a Natural Language Processing (NLP) technique
used to identify and label segments of a sentence. Unlike full parsing, which attempts to generate
a complete syntactic structure (a parse tree), shallow parsing only identifies constituents like noun
phrases (NP), verb phrases (VP), etc., without delving into the internal structure of these phrases
.
Key Components:
1. Tokenization: Breaking the sentence into tokens (words).
2. Part-of-Speech Tagging (POS): Assigning each token a part of speech (e.g., noun, verb).
3. Chunking: Grouping tokens into chunks (e.g., “The big dog” as a noun phrase).

Example:
For the sentence “The quick brown fox jumps over the lazy dog,” shallow parsing might produce:
NP: “The quick brown fox”
VP: “jumps over”
NP: “the lazy dog”

Applications

• Information extraction
• Named entity recognition
• Question answering

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. These probabilities
represent how frequently a particular rule is used when generating sentences. PCFGs are widely
used in Natural Language Processing to resolve syntactic ambiguity by selecting the most
probable parse tree among multiple possible parses.

16
For example, consider the following grammar rules with probabilities:

Production Rule Probability

S → NP VP 1.0
NP → Det N 0.6
NP → ProperNoun 0.4
VP → V NP 0.7
VP → V 0.3
Det → the 1.0
N → boy 0.5
N → apple 0.5
V → eats 1.0

Now consider the sentence:

“the boy eats apple.”

One possible parse tree is:

S → NP VP
NP → Det N
VP → V NP
NP → N

The probability of the entire parse tree is calculated by multiplying the probabilities of the
rules used:

P(Tree) = P(S → NP VP) × P(NP → Det N) × P(VP → V NP) × P(N → boy) × P(N → apple)

Substituting values:

P(Tree) =
1.0 × 0.6 × 0.7 × 0.5 × 0.5
= 0.105

If there are multiple possible parse trees for the same sentence, the PCFG parser computes the
probability for each tree and selects the parse tree with the highest probability. This approach
helps NLP systems choose the most likely grammatical structure when a sentence is ambiguous.

17
Probabilistic Cyk :

The Probabilistic CYK algorithm is an extension of the CYK parsing algorithm used with
Probabilistic Context-Free Grammars (PCFGs). In this method, every grammar rule has a
probability, and the parser calculates the probability of different parse structures for a sentence.
The parse with the highest probability is selected as the correct syntactic structure.

Consider the previous examples :“the boy eats apple”

Step 1: Identify Word Categories

First, determine which grammar rule produces each word.

The probability of a grammar rule is estimated from training data using the following formula:

P(A→β)=Count(A→β)
Count(A)

where

 Count(A → β) = number of times the rule occurs in the corpus

 Count(A) = total number of times the non-terminal A appears on the left side of any rule.

Word Category Probability

the Det 1.0

boy N 0.5

eats V 1.0

apple N 0.5

Step 2: Form Noun Phrase “the boy”

Now combine the + boy. i.e., NP → Det N

Probability formula:

P(NP) = P(rule) × P(Det) × P(N)

Calculation:

18
P(NP) = 0.6 × 1.0 × 0.5= 0.3

So the phrase “the boy” forms NP with probability 0.3.

Step 3: Convert “apple” into NP

Word apple is first identified as N.

Now apply rule:

NP → N

Calculation:

P(NP) = 0.4 × 0.5= 0.2

So apple forms NP with probability 0.2.

Step 4: Form Verb Phrase “eats apple”

Now combine:

eats + apple

Rule used:VP → V NP

Probability formula:

P(VP) = P(rule) × P(V) × P(NP)= 0.7 × 1.0 × 0.2= 0.14

So “eats apple” forms VP with probability 0.14.

Step 5: Form the Sentence

Now combine:

NP(the boy) + VP(eats apple)

which means, S → NP VP

Calculation:

P(S) = P(rule) × P(NP) × P(VP)= 1.0 × 0.3 × 0.14= 0.042

19
Final Result

The probability of the parse tree for the sentence

“the boy eats apple” is: 0.042

If there were multiple possible parse trees, the probabilistic CYK algorithm would calculate
probabilities for all possible structures and choose the one with the highest probability.

Probabilistic Lexicalized CFGs:

A Probabilistic Lexicalized Context-Free Grammar (PLCFG) is an extension of a
Probabilistic Context-Free Grammar (PCFG) in which each syntactic constituent is
associated with a specific lexical head word. In other words, every phrase in the parse tree
contains a head word that determines the syntactic behavior of that phrase. Lexicalization
helps capture important dependencies between words in a sentence, which normal PCFGs cannot
represent effectively.

Example :
Rule Probability

S(eats) → NP(boy) VP(eats) 1.0

VP(eats) → V(eats) NP(apple) 0.7

NP(boy) → Det(the) N(boy) 0.6

NP(apple) → N(apple) 0.4

Sentence to parse:“the boy eats apple”

Step 1:First identify the lexical category and head word for each word.
Word Category Head Probability

the Det the 1.0

boy N Boy 0.5

eats V Eats 1.0

apple N apple 0.5

20
Step 2: Form Noun Phrase “the boy”

Now combine the + boy.

Rule used: NP(boy) → Det(the) N(boy)

Probability calculation:

P(NP(boy)) = P(rule) × P(Det) × P(N) = 0.6 × 1.0 × 0.5 = 0.3

The head of the NP is “boy”.

Step 3: Form Noun Phrase “apple”

Rule used: NP(apple) → N(apple)

Probability: P(NP(apple)) = 0.4 × 0.5 = 0.2

Here the head word is “apple”.

Step 4: Form Verb Phrase

Now combine: eats + apple

Rule used: VP(eats) → V(eats) NP(apple)

Probability calculation: P(VP(eats)) = 0.7 × 1.0 × 0.2 = 0.14

The head of the VP remains “eats”.

Step 5: Form the Sentence

Now combine: NP(boy) + VP(eats)

Rule used: S(eats) → NP(boy) VP(eats)

Probability: P(S) = 1.0 × 0.3 × 0.14 = 0.042

Final Result
The lexicalized parse tree for the sentence: “the boy eats apple” has probability: 0.042

The head word of the whole sentence is “eats” because the verb usually acts as the syntactic
head of the sentence.

21
Normal PCFGs only consider syntactic categories, but lexicalized grammars also consider
specific words (heads). This helps capture important relationships such as:

 Verb–object relationships
 Verb–subject dependencies
 Collocations between words

For example:

Sentence 1:
The boy eats apple

Sentence 2:
The boy eats idea

A simple PCFG may treat both sentences similarly, but a lexicalized grammar recognizes that
“eats apple” is more probable than “eats idea.” Both sentences follow the same syntactic
structure:

S→NP VP

NP→Det N

VP→V NP

In a PCFG, only the grammatical categories are considered.

Example rules:

Rule Probability

S → NP VP 1.0

NP → Det N 0.6

VP → V NP 0.7

Both sentences have the same structure: NP + VP

Therefore the PCFG assigns almost the same probability to both sentences because it does not
consider the meaning of the words.

22
How Lexicalized Grammar Treats These Sentences?

A Probabilistic Lexicalized CFG considers both:

 syntactic category
 specific words (heads)

Here the verb “eats” prefers certain nouns as its object, especially food-related nouns.

Example probabilities learned from a corpus:

Rule Probability

VP(eats) → V(eats) NP(apple) 0.6

VP(eats) → V(eats) NP(idea) 0.01

This happens because in real language data:

 “eat apple” occurs frequently

 “eat idea” almost never occurs.

Feature structures:
Definition : Feature structures are a way of representing linguistic information using a set of
attributes (features) and their corresponding values. They are widely used in syntactic and
semantic analysis to represent grammatical properties of words and phrases. Feature structures
help in handling linguistic information such as number, gender, tense, person, and agreement
in a systematic way.

Types of Features in NLP: Some common features used in NLP are:

Feature Description

Category Part of speech (Noun, Verb, Adjective)

Number Singular or Plural

Gender Masculine, Feminine, Neuter

Person First, Second, Third

Tense Past, Present, Future

Case Nominative, Accusative

23
A feature structure is written as:

[Feature1 = Value1
Feature2 = Value2
Feature3 = Value3]

Example:

[Category = Noun
Number = Singular
Gender = Masculine
Person = Third]

*This structure describes a singular masculine noun for the word “boy”

[Category = Noun
Number = Plural
Gender = Masculine
Person = Third]

*This structure describes a singular masculine noun for the word “boys”

[Category = Verb
Tense = Present
Person = Third
Number = Singular]

*This structure describes feature structure for the verb “eats”

[Category = Verb
Tense = Present
Person = First/Second
Number = Singular or Plural]

*This structure describes feature structure for the verb “eat”.

Unification of Feature Structures in NLP :

Unification is the process of combining two feature structures into a single consistent
structure. If the features in both structures are compatible, they merge successfully; if there is a
conflict in feature values, the unification fails. This mechanism is widely used in syntactic
parsing and grammar frameworks such as unification-based grammars.

24
Unification works by comparing the feature–value pairs of two structures.

 If the values are compatible, they are merged.

 If the values are different and incompatible, unification fails.

Example 1: Successful Unification

Consider the sentence:

“The boy eats apple.”

Feature Structure of Noun Phrase (Subject)

[Category = NP
Number = Singular
Person = Third]

Feature Structure of Verb

[Category = Verb
Number = Singular
Person = Third
Tense = Present]

Unification Process

Both structures have:

 Number = Singular
 Person = Third

Since the values match, the structures can be combined.

Result After Unification

[Category = Sentence
Number = Singular
Person = Third
Tense = Present]

Thus the sentence is grammatically valid.

25
 Example 2: Failed Unification

Consider the sentence:

“The boys eats apple.”

Feature Structure of Subject

[Category = NP
Number = Plural
Person = Third]

Feature Structure of Verb

[Category = Verb
Number =
Singular Person =
Third]

Comparison

Feature Subject Verb

Number Plural Singular
Person Third Third

The Number feature conflicts.

Therefore unification fails, meaning the sentence is grammatically incorrect.

QUESTIONS

1. What is a Context-Free Grammar (CFG), and how does it help in syntactic analysis of natural
language? Explain with examples.
2. Explain the concept of a Treebank. How are Treebanks useful for training syntactic parsers and
understanding linguistic structures?
3. What are Normal Forms for grammars, and why are they important in parsing algorithms like CYK?
4. Describe the basic principles of Dependency Grammar. How does it differ from Phrase Structure
Grammar?
5. Discuss the role of Dynamic Programming in syntactic parsing. How does it improve the efficiency
of parsing algorithms?
6. What is Shallow Parsing, and how is it different from Deep Parsing?
7. Explain the concept of Probabilistic Context-Free Grammars (PCFGs). How do they aid in resolving
ambiguity in parsing?
8. What are Feature Structures, and how is Unification used to analyze syntactic and semantic
information?

26