Difference between revisions of "CYK Parsing"
From Cohen Courses
Jump to navigationJump to searchm |
m |
||
| Line 11: | Line 11: | ||
<pre> | <pre> | ||
| − | + | for each i = 1 to n | |
| − | + | for each production A -> a | |
| − | + | if a == X[i] | |
| − | + | add A -> a to C[i,i] | |
| − | |||
| + | for each L = 2 to n | ||
| + | for each i = 1 to n-L+1 | ||
| + | for each j = 1 to L - 1 | ||
| + | for each production A -> A1 A2 | ||
| + | if A1 in C[i,i+j] and A2 in C[i+j+1,i+L] | ||
| + | add A -> A1 A2 to C[i,i+L] | ||
</pre> | </pre> | ||
Revision as of 17:50, 30 October 2011
This is a Method page for CYK Parsing.
The Cocke–Younger–Kasami (CYK) algorithm is an algorithm for parsing PCFG. It is bottom up and makes use of dynamic programming.
Description
The input to the algorithm is a grammar in Chomsky Normal Form, and a sentence . The idea behind the parsing algorithm is to recursively build parses from bottom up, and mantaining a chart C[i, j] which contains productions that generates X[i] ... X[j].
Pseudocode
for each i = 1 to n
for each production A -> a
if a == X[i]
add A -> a to C[i,i]
for each L = 2 to n
for each i = 1 to n-L+1
for each j = 1 to L - 1
for each production A -> A1 A2
if A1 in C[i,i+j] and A2 in C[i+j+1,i+L]
add A -> A1 A2 to C[i,i+L]
