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




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


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

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

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

w = a_1a_2 \ldots a_n \in T^+
.

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

A \in t_{ij}
тогда и только тогда, когда A
+ aiai+1 ... ai+j-1.

Метод.

(1) Положить

t_{i1} = \{A \mid A \rightarrow a_i \in P\}
для каждого i. Так что, если
A \in t_{i1}
, то A
+ ai.

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

i
n и 1
j' < j. Положим tij = {A| для некоторого 1
k < j правило
A \rightarrow BC \in P, B \in t_{ik}, C \in t_{i+k,j-k} \}
.

Так как 1

k < j, то k < j и j - k < j. Так что tik и ti+k,j-k вычисляются раньше, чем tij . Если
A \in t_{ij}
, то 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, входная цепочка

w = a_1a_2 \ldots a_n \in T^+
и таблица разбора Tab.

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

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

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

ai = pm, выдать m.

(2) Пусть j > 1 и k - наименьшее из чисел от 1 до j-1, для которых существует

B \in t_{ik}, C \in t_{i+k,j-k}
и правило pm = A
BC. Выдать m и выполнить gen(i, k, B), затем gen(i + k, j - k, C).

Выполнить gen(1, n, S), если

S \in t_{1,n}
, иначе ошибка.




Содержание  Назад  Вперед