begin
for p:= 1 to n do V[p,1]:= {A | A__p_P} /* first len 1 */
for q:= 2 to n do /* then length 2, 3, ..., n substrings */
for p:= 1 to n-q+1 do /* len q can't begin after p = n-q+1 */
begin V[p,q]:= _;
/* length q>1 substrings are only generated by A_BC where
B derives an initial segment of length k, 1Šk
derives the remainder of length q-k */
for k:= 1 to q-1 do
V[p,q]:= V[p,q] _ {A | A_BC_P, B_V[p,k], and C_V[p+k,q-k]}
end
end
The CKY algorithm
Previous slide | Next slide | Back to first slide | View graphic version |