Dynamic Programming
Parsing
Dynamic Programming Parsing
• To avoid extensive repeated work, must
cache intermediate results, i.e.,completed
phrases.
• Dynamic programming algorithms based
on both top-down and bottom-up search
can achieve O(n3) recognition time
where n is the length of the input string.
Dynamic Programming Parsing
Methods
1. CKY (Cocke-Kasami-Younger)
algorithm: bottom-up, requires
normalizing the grammar
2. Chart Parsers - retain completed phrases
in a chart and can combine top-down
and bottom-up searches.
3. Earley Parser - top-down, does not
require normalizing grammar, more
complex
The CYK Algorithm
CYK Algorithm
• The Cocke–Younger–Kasami algorithm
(alternatively called CYK, or CKY) is a
parsing algorithm for context-free
grammars, named after its inventors, John
Cocke, Daniel Younger and Tadao Kasami.
• It employs bottom-up parsing and dynamic
programming
• It determines if a sentence is in the
language generated by grammar.
The CYK Algorithm
– Problem:
• Given a context-free grammar G and a
string w
– G = (V, ∑,P , S) where
V finite set of variables
∑(the alphabet) finite set of terminal symbols
P finite set of rules
S start symbol (distinguished element of V)
V and ∑are assumed to be disjoint
– G is used to generate the string of a language
– Question:
• Is w in L(G)?
CYK Algorithm Basics
–The Structure of the rules in a
Chomsky Normal Form grammar
–Uses a “dynamic programming” or
“table-filling algorithm”
Chomsky Normal Form
• Normal Form is described by a set of
conditions that each rule in the grammar
must satisfy
• Context-free grammar is in CNF if each
rule has one of the following forms:
A BC at most 2 symbols on right
A a, or side terminal symbol
Sϵ null string
where B, C Є V – {S}
Converting to CNF
Aux → is, am
PP → on, in, over
Converting to CNF
Aux → is, am
PP → on, in, over
CYK Algorithm
Construct a Triangular Table
• Each row corresponds to some length of
substrings
Construct a Triangular Table
0 1 2 3 4 5
Table for string ‘w’ that has length 5
Example CYK Algorithm
• Show that the sentence s ϵ L(G) [where
s= “a pilot likes flying planes”, using
CYK Algorithm with the following G:
Grammar G
S NP VP VBZ likes
VP VBG NNS VBG flying
VP VBZ VP DT a
VP VBZ NP NN pilot
NP DT NN JJ flying
NP JJ NNS NNS planes
Construct a Triangular Table
0 1 2 3 4 5
Table for sentence that has length 5
Construct a Triangular Table
0 1 2 3 4 5
= DT -> a
= NN -> pilot
= VBZ -> likes
= VBG -> flying, JJ ->flying
= NNS -> planes
Construct a Triangular Table
0 1 2 3 4 5
x0, 2= x0, 1 x1, 2
= DT NN = NP
x1, 3= x1, 2 x2, 3
= NN VBZ,
NN JJ = φ
0 1 2 3 4 5
x0, 3= x0, 1 x1, 3, x0,2 x2,3 VP1=VBZ VP
= DT--, NP VBZ VP2=VBZ NP
=φ
x1, 4= x1, 2 x2, 4 , x1, 3 x3,4
= NN --,--VBG, --JJ
=φ
x2, 5= x2, 3 x3, 5 , x2, 4 x4, 5
= VBZ VP, VBZ NP, -- NNS
= VP1, VP2
0 1 2 3 4 5
x0, 4= x0,1x1,4 , x0, 2x2,4 , VP1=VBZ VP
VP2=VBZ NP
x0, 3 x3, 4 = DT--, NP--, -- VBG ,
-- JJ = = φ
x1, 5 = x1, 2x2, 5 , x1, 3 x3, 5 , x1,4
x4, 5 = NN VP1,NN VP2,-- VP,
--NP, --NNS= φ
0 1 2 3 4 5
x0, 5= x0, 1 x 1, 5 , x0, 2 x2, 5, VP1=VBZ VP
x0, 3 x3,5 , x0,4 x4, 5 VP2=VBZ NP
=DT --,NP VP1,NP
VP2, -- VP/NP, -- NNS
= S1, S2
Theorem
• The CYK Algorithm correctly computes Xi j for
all i and j; thus sentence S is in L(G) if and
only if S is in X0n.
• The running time of the algorithm is O(n3).
Question
Analyze the following sentence using CYK algorithm.
Does the sentence belongs to the L(G) ?
Astronomers saw stars with telescope
Grammar(G):
S→ NPVP NP →saw
VP →VP PP V → saw
VP →V NP P →with
NP →NP PP NP -> astronomers
PP →P NP
NP →stars
NP →telescope
Question
• Show the CYK Algorithm with the following example:
– CNF grammar G
• S AB | BC
• A BA | a
• B CC | b
• C AB | a
– w is ababa
– Question Is ababa in L(G)?
• Basics of CYK Algorithm
– The Structure of the rules in a Chomsky Normal Form
grammar
– Uses a “dynamic programming” or “table-filling algorithm”
• Complexity O(n3)