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

Приведем алгоритм синтаксического анализа, применимый для любой грамматики в нормальной форме Хомского

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

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

Выход. Таблица разбора Tab для w такая, что

тогда и только тогда, когда A

+ aiai+1 ... ai+j-1.

Метод.

(1) Положить

для каждого i. Так что, если

, то A

+ ai.

(2) Пусть tij вычислено для 1

n и 1

j' < j. Положим tij = {A| для некоторого 1

k < j правило

Так как 1

k < j, то k < j и j - k < j. Так что tik и ti+k,j-k вычисляются раньше, чем tij . Если

, то A

+ ai ai+k-1 C

+ aI ... ai+k-1ai+k ... ai+j-1.

(3) Повторять шаг 2 до тех пор, пока не станут известны tij

для всех 1

n и 1

n-i+1.

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

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

и таблица разбора Tab.

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

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

(1) Если j = 1 и A

ai = pm, выдать 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), если

, иначе ошибка.