Изменения

Перейти к: навигация, поиск
м
Псевдокод: tex
<code>
'''CYK_Modified'''(S, Г): <font color = darkgreen>// S {{---}} строка длины n, Г {{---}} КС-грамматика </font color = darkgreen>
'''for''' i = 1 \ldots ..n
'''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen>
'''if'''( A -> w[i] in Г) a[A, i, i+1] = true <font color = darkgreen>// если в грамматике Г присутствует правило A -> w[i] </font color = darkgreen>
'''else''' a[A, i, i] = false
h[A->alpha, i, i, 0] = true
'''for''' m = 1 \ldots ..n '''for''' i = 1 \ldots ..n
j = i+m
'''for''' k = 1 \ldots ..M
'''for''' Rj -> alpha <font color = darkgreen>// перебор состояний </font color = darkgreen>
h[A->alpha, i, j+1, k] = OR( for r = i \ldots ..j+1) (h[A->alpha, i, r, k-1] & a[alpha[k],r,j+1]) '''for''' i = 1 \ldots ..n '''for''' j = 1 \ldots ..n
'''for''' Rj -> alpha
a[A, i, j] = OR( for A->alpha) h[A->alpha, i, j, |alpha|] <font color = darkgreen>// где |alpha| {{---}} размер правой части правила</font color = darkgreen>
390
правок

Навигация