Алгоритм Кока-Янгера-Касами

Вход. КС-грамматика G = (N, T, P, S) в нормальной форме Хомского и входная цепочка .

Выход. Таблица разбора Tab для w такая, что тогда и только тогда, когда A =>⁺ a_ia_i+1 ... a_i+j-1.

Метод.

(1) Положить для каждого i. Так что, если , то A =>⁺ a_i.

(2) Пусть t_ij вычислено для 1<=i<=n и 1<= j' < j. Положим t_ij = {A| для некоторого 1 <= k < j правило .

Так как 1 <= k < j, то k < j и j - k < j. Так что t_ik и t_i+k,j-k вычисляются раньше, чем t_ij. Если то A => BC =>⁺ a_i a_i+k-1 C =>⁺ a_I ... a_i+k-1a_i+k ... a_i+j-1.

(3) Повторять шаг 2 до тех пор, пока не станут известны t_ij для всех 1 <= i <= n и 1 <= j <= n-i+1.

Алгоритм нахождения левого разбора по таблице разбора Tab.

Вход. КС-грамматика G = (N, T, P, S) в нормальной форме Хомского с правилами, занумерованными от 1 до p, входная цепочка и таблица разбора Tab.

Выход. Левый разбор цепочки w или сигнал ошибка.

Метод. Процедура gen(i, j, A):

(1) Если j = 1 и A => a_i = p_m, выдать m.

(2) Пусть j > 1 и k - наименьшее из чисел от 1 до j-1, для которых существует и правилоpm = A -> BC. Выдать m и выполнить gen(i, k, B), затем gen(i + k, j - k, C).

Выполнить gen(1, n, S), если , иначе ошибка.

Разбор сверху-вниз (предсказывающий разбор)