NATURAL LANGUAGE

PROCESSING (18AI641)
Module 2- Word level and syntactic analysis
• Word Level Analysis:
 Regular Expressions
 Finite-State Automata
 Morphological Parsing
 Spelling Error Detection and correction
 Words and Word classes
 Part-of Speech Tagging.
• Syntactic Analysis:
 Context-free Grammar
 Constituency
 Parsing
 Probabilistic Parsing
Introduction
• Two important Concepts in natural language are
 constituency and word order.
 Constituency is about how words are grouped together.
 Word order is about how, within a constituent, words are
ordered with respect to one another, and also how
constituents are ordered with respect to one another.
• context-free grammar (CFG) is a widely used mathematical
system for modelling constituent structure in natural language
 Also known as phrase structure grammar
Context-free Grammar
• Context-free grammar (CFG) was first defined for natural language by
Chomsky (1957)
• Used for the Algol programming language by Backus (1959) and Naur
(1960).
• A CFG (also called phrase-structure grammar) consists of four components:
 A set of non-terminal symbols, N
 A set of terminal symbols, T
 A designated start symbol, S, that is one of the symbols from N.
 A set of productions, P, of the form:
• A→α
Where A ∈ N and α is a string consisting of terminal and non-terminal
symbols.
• A → α says that constituent A can be rewritten as α
 This is also called the phrase structure rule
 It specifies the occurrence of phrase elements and in its order
 E.g. S->NP VP states that SP consists of NP followed by VP
CFG contd..
• A CFG can be used to generate a sentence or to assign a structure to a
given sentence.
 consists of a set of rules or productions, each of which expresses the ways that
symbols of the language can be grouped and ordered together, and a lexicon of
words and symbols
 The symbols that correspond to words in the language are called terminal symbols
• the lexicon is the set of rules that introduce these terminal symbols.
 The symbols that express abstractions over these terminals are called non-terminals.
 In each context-free rule, the item to the right of the arrow (→) is an ordered list of
one or more terminals and non-terminals
• the left of the arrow is a single non-terminal
 The non-terminal associated with each word in the lexicon is its lexical category, or
part of speech Terminal symbols

A → aA | ε
Nonterminal symbols
CFG contd..
• A CFG can be used to generate a sentence or to assign a structure
to a given sentence.
 When used as a generator, the arrows in the production rule may be
read as rewrite the Symbol on the left with symbols on the right.
 E.g. sentence:
Hena reads a book
parse tree

 The parse tree can be represented as follows (bracketed

representation):
[S[NP[N Hena]][VP[V[reads][NP[DET[a] [N book]]]]]
 The mapping of a string to its parse tree is known as parsing.
• The parse tree for “I prefer a morning flight”
CONSTITUENCY
• Phrase Level Constructions
 A fundamental notion in natural language is that certain groups of words behave as
constituents.
 These constituents are identified by their ability to occur in similar contexts.
 A group of words can be decided as a phrase it they substitute with some other group of
words without changing the meaning.
• This is called the substitution test.
 E.g Hena reads a book - This sentence can be substituted by a number of other phrases:
• Hena reads a book.
• Hena reads a storybook.
• Those girls read a book.
• She reads a comic book.
 In above sentences constituents are Hena, she, and Those girls and a book, a storybook, and
a comic book.
 These are the words that form a phrase
CONSTITUENCY
• Phrase types are named after
their head, which is the lexical
category that determines the
properties of the phrase.
 Thus, if the head is a noun, the
phrase is called a noun phrase, if
the head is a verb, the phrase is
called a verb phrase
• Note: phrase structure rules are
of the form A→BC, which states A sentence with NP, VP, and PP
that constituent A can be
rewritten as two constituents B
and C
Noun Phrase
• A noun phrase is a phrase whose head is a noun or a pronoun,
optionally accompanied by a set of modifiers.
• It can function as subject, object, or complement.
• The modifiers of a noun phrase can be determiners or
adjective phrases.
• The mandatory constituent of a noun phrase is the noun head
 all other constituents are optional.
• the phrase structure rules for a noun phrase are as follows.
NP→ Pronoun
NP → Det Noun
NP → Noun
NP → Adj Noun
NP→ Det Adj Noun
Noun Phrase contd..
• All these rules can be combined in a single phrase structure rule as
NP → (Det) (Adj) Noun|Pronoun
• The constituents in parentheses are optional
 Above rule states that noun phrase consists of a noun, possibly preceded by a
determiner and an adjective.
• A noun phrase may include post-modifiers and more than one adjective.
 it may include a prepositional phrase (PP).
 More than one adjective is handled by allowing an adjective phrase (AP) for the
adjective in the rule.
• After incorporating PP and AP in the phrase structure rule:
NP → (Det) (AP) Noun (PP)
• Example of Noun Phrases:
They consists only of a pronoun
The foggy morning consists of a determiner and an adjective
Chilled water comprises an adjective phrase and a noun
A beautiful lake in Kashmir consists of a determiner (the), an adjective phrase (beautiful), a noun
(lake), and a prepositional phrase (in Kashmir)
Cold banana shake consists of an adjective followed by a sequence of nouns
Noun Phrase contd..
• A noun sequence is termed as nominal.
 The nominal construction follows the determiner and contains any pre- and post head noun
modifiers.
 Before the Head Noun (premodifiers.) – include
• cardinal numbers - e.g: two friends, one stop
• ordinal numbers - e.g.: (the first one, the last flight)
• Quantifiers - e.g.: many fares, few flights
• Adjectives - e.g.: a first-class fare, the longest layover, a non-stop flight
 After the Head Noun (postmodifiers)
• all flights from Cleveland, any flights arriving after eleven
• Grammar Rules:
NP→(Det) (AP) Nom (PP)
Nom →Noun I Noun Nom
• A noun phrase can act as a subject, an object, or a predicate.
• E.g.
 The foggy damped weather disturbed the match.
• noun phrase acts as a subject
 I would like a nice cold banana shake.
• noun phrase acts as an object.
 Kula botanical garden is a beautiful location.
• noun phrase acts as a predicate.
Verb Phrase
• Verb phrase is headed by a verb.
• There is a fairly wide range of phrases that can modify a verb
• The verb phrase organizes various elements of the sentence that depend syntactically on
the verb.
• E.g.
Khushbu slept consists only verb
The boy kicked the ball a verb followed by an NP [VP → Verb NP ]
Khushbu slept in the garden a verb followed by a PP [VP → Verb PP ]
The boy gave the girl a book a verb followed by two NPs [VP → Verb NP NP]
The boy gave the girl book A verb followed by two NPs and a PP [VP → Verb NP NP PP]
with blue cover
• Objects may also be entire clauses as in the sentence.
 E.g. l know that Taj is one of the seven wonders
• an alterative phrase statement rule:
 VP → Verb S
• Objects may also be entire clauses as in the sentence.
 E.g. l know that Taj is one of the seven wonders
• an alterative phrase statement rule:
 VP → Verb S
Prepositional Phrase
• Prepositional phrases are headed by a preposition
• They consist of a preposition, possibly followed by some
other constituent, usually a noun phrase.
 E.g. We played volleyball on the beach.
• preposition phrase that consists of only a preposition.
 John went outside.
• The phrase structure rule that captures the above
eventualities is as follows.
PP→Prep (NP)
Adjective Phrase
• The head of an adjective phrase (AP) is an adiective\
• Aps consists of an adjective which may be preceded by
an adverb and followed by a PP.
• E.g.
 Ashish is clever.
 The train is very late.
 My sister is fond of animals.
• The phrase structure rule for adjective phrase is
AP→(Adv) Adj (PP)
Adverb Phrase
• An adverb phrase consists of an adverb., possibly
preceded by a degree adverb
• E.g.
 Time passes very quickly
• The phrase structure rule for adverb phrase is
AdvP → (Intens) Adv
Sentence Level Constructions
• A sentence can have varying structure.
• The four commonly known structures are
 declarative structure,
 imperative structure,
 yes-no question structure, and
 wh-question structure
• Sentences with a declarative structure have a subject followed
by a predicate.
 The subject of a declarative sentence is a noun phrase
 the predicate is a verb phrase,
• e.g., I like horse riding.
 The phrase structure rule for declarative sentences is
S → NP VP
Sentence Level Constructions contd..
• Sentences with an imperative structure begin with a verb phrase
and lack subject.
 The subject of these types of sentence is implicit and is understood to
be 'you’.
 These types of sentences are used for commands and suggestions, and
hence are called imperative.
 The grammar rule for this kind of sentence structure is
S→VP
 E.g.
• Look at the door.
• Give me the book.
• Stop talking.
• Show me the latest design.
Sentence Level Constructions contd..
• Sentences with the yes-no question structure ask questions
which can be answered using yes or no.
 These sentences begin with an auxiliary verb, followed by a
subject NP, followed by a VP.
 E.g.
• Do you have a red pen?
• Is there a vacant quarter?
• Is the game over?
 Can you show me your album?
 The grammar rule is
S→Aux NP VP
Sentence Level Constructions contd..
• Sentences with wh-question structure are more complex.
 sentences begin with a wh-words-who, which, where, what, why, how.
 A wh-question may have a wh-phrase as a subject or may include another subject.
 E.g.
• Which team won the match?
 This sentence is similar to a declarative sentence except that it contans a wh-
word.
 A rule to handle this type of sentence structure is
• S → Wh-NP VP
 Another type of wh-question structure involves more than one NP
• In this type of questions. the auxiliary verb comes before the subject NP, just as
in yes-no question structures.
• Which cameras can you show me in your shop?
 The rule for this type of wh-questions is
• S → Wh-NP Aux NP VP
Summary of grammar rules
Coordination
• Coordination refers to conjoining phrases with conjunctions like
'and', 'or', and 'but’.
 E.g. a coordinate noun phrase can consist of two other noun phrases
separated by a conjunction 'and', as in
I ate [NP [NP an apple] and [NP a banana]]
 verb phrases and prepositional phrases can be conjoined as:
• It is [VP [VP dazzling] and [VP raining]]
 a sentence also can be conjoined
• [S [S I am reading the book] and [S I am also watching the movie]]
• Conjunction rules for NP, VP, and S can be built as follows:
 NP → NP and NP
 VP → VP and VP
 S → S and S
Agreement
• Most verbs use two different forms in present tense
 one for third person, singular subjects, and
 the other for all other kinds of subjects.
 The third person singular (3sg) form ends with a -s whereas the non-3sg
does not.
• This agreement has to be confirmed whenever a verb that has some noun
acting as a subject.
• E.g.
 Does [NP, Priya] sing?
 Here, the -es form of 'do', i.e. 'does' is used as the subject NP is singular.
 Do [NP they] eat
 the form 'do' is used as sentence has a plural NP subject
• Sentences in which subject and verb do not agree are ungrammatical.
 E.g.
• [Does] they eat?
• [Do] she sings?
Agreement contd..
• Rules that handle the yes-no questions are as follows:
S → Aux NP VP
• To take care of the subject-verb agreement, above rule is
replaced with a pair of rules as follows:
S → 3sg Aux 3sg NP VP
S → Non 3sg Aux Non 3sg NP VP
• These rules ensure appropriate subject-verb agreement.
 Rules can be added for the lexicon :
• 3sg Aux → does| has| can
• Non3sg Aux → do | have | can
Agreement contd..
• Similarly the phrase structure rules for noun phrase are
replaced by a pair of rules as follows:
 3sgNP → (Det) (AP) SgNom (PP)
 NonJsgNP → (Det) (AP) PlNom (PP)
 SgNom → SgNoun | SgNoun SgNom
 PlNom → PlNoun | PlNoun PlNom
 SgNoun → Priya | lake | banana | sister | …
 PlNoun → Children | …
Agreement contd..
• Rules need to be added for the first and second person pronouns
 doubles the size of the grammar
• The new versions of NP and noun rules need to be introduced for various
cases,
 e.g., nominative (I,she, they,he) and
 accusative (me, her, him, them) cases of pronoun
• The problem of over-generation can be solved by introducing new
grammatical categories corresponding to each such constraint
 This results in an explosion in the number of grammar rules and loss of
generality
• An alternative solution is to associate each non-terminal of the grammar
with feature structures.
 Feature structures are able to capture grammatical properties without
increasing the size of the grammar.
Feature Structures
• Feature structures are sets of feature-value pairs.
• They can be used to efficiently capture the properties of
grammatical categories.
• Features are symbols representing properties that we wish to
capture
 E.g. the number property of a noun phrase can be
represented by NUMBER feature.
• The value of NUMBER is SG for singular and PL for plural
 Values can be either atomic symbols or feature structures
• Feature structures are represented by attribute value matrix
(AVM). FEATURE_1 VALUE_1
FEATURE_2 VALUE_2
...
FEATURE_N VALUE_N
Feature Structures contd..
• An AVM consisting of a single NUMBER feature with the value SG is
represented as follows:
 [NUMBER SG]
• The value of a feature can be left unspecified and represented by an empty
pair of square brackets
 [ NUMBER []]
• The feature structure can be used to encode the grammatical category of a
constituent and the features associated with it. CAT
NUMBER
NP
SG
PERSON 3

• Third person plural noun phrase can be represented as follows:

CAT NP
NUMBER PL

• A feature can have another feature structure as its value PERSON 3

 E.g. combining the NUMBER: and PERSON features into a single AGREEMENT feature
CAT NP

AGREEMENT NUMBER SG
PERSON 3
Operation on features:
• Two important operations:
 merging the information content of the two structures that are similar and
 rejecting structures that are incompatible
• Unification:
 implemented as a binary operator( ) that takes two feature structures as
arguments and returns a merged feature structure if they are compatible,
otherwise reports a failure
• [NUMBER PL] |_|[NUMBER PL]= [NUMBER PL]
• [NUMBER PL] |_|[NUMBER SG]= failure
 A feature with an unspecified value in one structure, can be successfully
matched with any value in a corresponding feature in another structure.
• the unification operation produces a structure with the value provided by
the structure having non-null value
• [NUMBER PL] |_|[NUMBER []]= [NUMBER PL]
PARSING
• Parsing is the task that uses the rewrite rules of grammar to
either generate sequence of words or reconstrut its derivation
• A phrase structure tree constructed from a sentence called a parse.
• The syntactic parser is responsible for recognizing a sentence and
assigning a syntactic structure to it.
 A sentence can have multiple parses which is known as syntactic
ambiguity.
• Garden pathing is another phenomenon related to syntactic
parsing.
 It refers to the process of constructing a parse by exploring the parse
tree along different paths, one after the other till, eventually, the
right one is found.
• Finding the right parse can be viewed as a search process.
PARSING contd..
• The search finds all trees whose root is the start symbol S and whose
leaves cover exactly the word in the input.
• The following constraints guide the search process.
 Input: The first constraint comes from the words in the input sentence.
• A valid parse is one that covers all the words in a sentence.
• Hence, these words must constitute the leaves of the final parse tree.
 Grammar: The second kind of constraint comes from the grammar.
• The root of the final parse tree must be the start symbol of the grammar. .
• These two constraints give rise to the two most widely used search
strategies by parsers,
 top-down or goal-directed search
 bottom up or data-directed search.
Top-down Parsing
• Starts its search from the root node S and works downward towards the leaves
• The input can be derived from the designated start symbol S, of the grammar
• The next step is to find all sub trees which can start with S
 To generate the sub trees of all second level search, expand the root node using all the
grammar rules with S on their left hand side
 Each non-terminal symbol in the resulting sub trees is expanded next using the grammar
rules having a matching non – terminal symbol on their left hand side
 The right hand side of the grammar rules provide the nodes to be generated, which are then
expanded recursively
• As the expansion continues, the tree grows downward and eventually reaches a
state where the bottom of the tree consists of part of speech categories.
 All trees whose leaves do not match words in the input sentence are rejected, learning only
trees that represents successful parses, matches exactly with the words in the input
sequence.
• A successful parse corresponds to a tree which matches exactly with the words in the
input sentence
Sample grammar
• S →NP VP
• S →VP
• NP→Det Nominal
• NP→noun
• NP →Det noun PP
• Nominal → Noun
• Nominal→Noun nominal
• VP →Verb NP
• VP →Verb
• PP →preposition NP
• Det → this/that/a/the
• Verb→sleep/sing/saw/open/paint
• Preposition → from/with/on/to
• Pronoun → she/he/they
• A top down search begins with the start symbol of the grammar.
 Thus the first level(ply) search tree consists of a single node labeled S.

• The grammar in table has two rules with S on their left hand side.
 These rules are used to expand the tree, which gives us two partial trees at the
second level search.

• The third level is generated by expanding the non – terminal at the bottom of the
search tree is the previous ply.
• Due to space constraints, only the expansion corresponding to
the left most non- terminals has been shown .
• The subsequent steps in the parse are left.
• The correct parse tree is obtained by expanding the fifth parse
tree by the third level.
Bottom – up parsing
• Starts with the words is the Input sentence and attempts to
construct a parse tree is an upward direction towards the root
• At each step, the parser looks for rules in grammar where the right
hand side matches some of the portions in the parse tree
constructed and reduces it using the left hand side of the
production
• The parse is considered successful of the parser reduces the tree to
the start symbol of the grammar
• E.g.
 Level 1: Paint the door
 Level 2: Noun Det Noun Verb Det Noun

Paint the door paint the door

Correct Phrase Tree
Advantages and disadvantages
• Top down search
 Advantages: it starts generating trees with the start symbol of the
grammar, it never wastes time exploiting a tree leading to a different
root
 Disadvantages: It wastes considerable time exploiting S trees that
eventually result in words that are inconsistent with the input,
because a top down parser generates trees before seeing the input
• Bottom up parser
 Advantages : Never explores a tree that does not match the input .
 Disadvantages: It wastes time generating trees that have no chance
of leading to an S-rooted tree.
A Basic Top-down Parser -top-down, depth-first, left-to-right
search algorithm
• Uses a depth first, left to right search. Top-down, depth-first parsing algorithm
• The depth first approach expands the 1. Initialize agenda
search space incrementally by one state 2. Pick a state, let it be curr_state, from
at a time. agenda
• At each step, the left-most unexpanded 3. If (curr_state) represents a successful
parse then return parse tree
leaf nodes of the tree are expanded first  else if curr_stat is a POS then
using the relevant rule of the grammar. • if category of curr_state is a subset of POS
associated with curr word then apply
 The left-most node is selected as it lexical rules to current state
determines the order in which input • else reject
words needs to be considered.  else generate new states by applying
• When a state inconsistent with the grammar rules and push them into
agenda
input, the search continues by returning 4. If(agenda is empty) then return failure
to the mostly generated and unexplored  else select a node from agenda for
tree. expansion and go to step 3
top-down, depth-first, left-to-right contd..
• The algorithm maintains an agenda of search states
• Each search state consists of partial trees and a pointer to
the next input word of the sentence.
• The algorithm starts with the agenda and generates a set of
new states by applying grammar rule to the left most
unexpanded node of the tree associated with it.
• The newly generated states are put on the front of the agenda
in the order defined by the textual order of the grammar rules.
• The process continues until either a successful parse tree is
discovered or the agenda is empty, indicating a failure.
Example sentence: Open the door
• The algorithm starts with the node S and
input word Open.
• It first expands S using the grammar rule
S→NP VP.
• It then expands the left most unexpanded
non-terminal NP using NP → Det Nominal.
 Parser eliminates the rule as the word
Open cannot be derived from Det.
 The next rule i.e., NP → noun, also leads
to a failure.
• The next search space on the agenda
corresponds to the S → VP rule.
 The expansion of VP using the rule VP
Verb NP, successfully matches the first
input words.
• The algorithm proceeds in a depth-first, left-
to-right manner, to match the rest of the
input words.
• In any successful parse the current input word must match the
first word in the derivation of the expanded node
• A grammar rule that cannot lead to the input word as the first
word along left side of a derivation (known as left corner of
the tree), should not be considered for expansion.
 The first word along left side of the derivation is called the
left corner of the tree
• While selecting a rule for expansion, the left comer table
which contains valid left corner categories is consulted to see
if the non-terminal associated with the rule has a part-of-
speech associated with the current input.
• If not, then the rule is not considered.
• Disadvantages of top-down, depth-first, left-to-right search algorithm
 left recursion, which causes the search to get stuck in an infinite loop.
• This problem arises if the grammar is left recursive that, is, it contains a non-
terminal which derives a string beginning with the same non-terminal in
many more steps
 structural ambiguity, which occurs when a grammar assigns more than
one parse to a sentence.
 Coordination ambiguity occurs when it is not clear which phrases are
being combined with a conjunction like and
 local ambiguity resulting in inefficient parsing.
• Local ambiguity occurs when certain parts of a sentence are ambiguous
 Repeated parsing requires extra effort to build valid trees for portions of
the input that it discards during backtracking.
• These problems are solved using dynamic programming algorithms
 E.g. the Cocke-Younger-Kasami (CYK) algorithm, the Graham-Harrison-
Ruzzo (GHR) algorithm, and the Earley algorithm
CYK Parser
• it follows a bottom-up approach in parsing.
• It builds a parse tree incrementally.
• Each entry in the table is based on previous entries.
• The process is iterated until the entire sentence has been parsed.
• The CYK parsing algorithm assumes the grammar to be in Chomsky
normal form (CNF).
• A CFG is in CNF if all the rules are of only two forms:
 A →BC
A→ w, where w is a word
• The algorithm first builds parse trees of length one by considering
all rules which produce words in the sentence being parsed.
• Then, it constructs the most probable parse for all the constituents
of length two ·
CYK Parser contd..
• Basic CYK algorithm is also a chart based algorithm
• A non-terminal is stored in the [ i,j]th entry of the chart if, and only if, A=>
wi ·wi+1 · ·· · wi+j+1
• A sentence is recognized if the start symbol is in the entry [1, n] of the
chart.
• First, the terminal derivation rules of the grammar are used to generate
the [i,1]th entries.
 These entries represent non-terminals that derive the individual words
appearing in the sentence wi1=wi, for 1≤i ≤n, n is the length (number of
words) of the sentence
 A=> wi1 if A-> wi is a rule in the grammar.
• Then the algorithm continues with sub-string of length two, three, and so
on.
• For every non-terminal A in the grammar, the algorithm determines if A*→
wij*
• A*→ wij* if
• A → BC is a rule in grammar
• B*=> wik
• C*=> w kj
• For a substring wij of length j starting at i, the algorithm
considers al possible ways of breaking it into two parts
wik and wkj
Example sentence : The girl wrote an essay
• Consider the following simplified grammar in CNF:
• S →NP VP The (1) girl (2) wrote (3) an (4) essay (4)

• Verb → wrote 1 2 3 4 5

• VP → Verb NP 5 Det→The NP→Det Noun S→NP VP

2 Noun→Girl
• Noun → girl 3 Verb→wrote VP→Verb NP

• NP → Det Noun 4 Det→an NP→Det Noun

5 Noun→essay
• Det → an | the
• Noun → essay