Input:  O CFG ˆın FNC, G = (N, Σ, S, P ) ¸si un cuvˆant w = a₁a₂ . . . a_n  a.i.

|w| = n.

Output:  o matrice triunghiular˘a T pentru w ale c˘arei celule cont¸in numai neterminale a.i.  A € t_ij   iff  A =>⁺   a_i a_i+1 · · · a_i+j−1.

Metoda:

 

Pas1  Construim t_i1  = {A | A → a_{i  €} P }, pentru i = 1, 2, · · · n.

 

Pas2  Presupunem c˘a t_ij,   a fost construit pentru tot¸i 1 ≤ i ≤ n ¸si tot¸i 1 ≤ j’  <

j.  Construim

 

 

t_ij  = {A | pentru un k, 1 ≤ k < j, A → BC € t_ik ,  B € t_ik  si C € ti+k,j−k ^}

 

 

Deoarece 1 ≤ k < j, avem k < j ¸si j − k < j, deci atˆat t_ik  cˆat ¸si t_i+k,j−k sunt calculat¸i ˆınainte ca t_ij  s˘a fie calculat.  Dup˘a acest pas, dac˘a t_ij  э A, atunci

 

 

A => BC=>⁺  a_i . . . a_i+k−1C =>⁺  a_i . . . a_i+k−1 a_i+k . . . a_i+j−1

 

 

Pas3  repet˘a  Pasul  2  pˆan˘a  cˆand  t_ij   este   cunoscut  pentru  orice  1  ≤  <i  <≤  n  ¸si

1 ≤ j ≤ n − i + 1.