Теория и реализация языков программирования

       

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


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

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

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

.

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

тогда и только тогда, когда A
+ aiai+1 ... ai+j-1.

Метод.

(1) Положить

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

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

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

Так как 1

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

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

для всех 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

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), если

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



Содержание раздела