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

Обсуждаемый алгоритм предназначен для разбора методом «снизу-вверх» слов любой контекстно-свободной грамматики, т.е. это – универсальный метод. Для его применения грамматика должна быть преобразована к нормальной форме Хомского (т.е. правила имеют вид: Aa или ABC). Этот алгоритм имеет сложность O(n³) по времени и O(n²) по памяти. На первом этапе алгоритм строит треугольную таблицу с элементами t_ik, в каждую клетку которой помещается множество нетерминалов, из которых можно вывести отрезок слова начинающийся с символа a_i и длиной k.

Формально: t_ik = {A | Aa_i…a_i+k-1}. Очевидно, что множества t_ik формально (рекурсивно) можно определить так:

t_i1 = {A | Aa_i - правило грамматики},

t_ij = {A | ABC - правило грамматики и k, 1k<j такое, что Bt_ik  Ct_i+k,j-k}.

Если в t_1n есть S, то слово  языку.

t16
t15	t25
t14	t24	t34
t13	t23	t33	t43
t12	t22	t32	t42	t52
t11	t21	t31	t41	t51	t61
a1	a2	a3	a4	a5	a6

Пусть заполнены все строки таблицы до j-1 включительно. Рассмотрим t_ij.

Эта ячейка соответствует фрагменту слова <a_i…a_i+j-1>. Разбиваем этот фрагмент на пары слов всеми способами. Каждому варианту разбиения соответствует пара клеток таблицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть это пара (t,t). В t_ij поместим нетерминал A, если есть правило ABC и Bt, Ct.

Пример. Рассмотрим неоднозначную грамматику: G = ({S,L,R}, {(,)}, {SSS | LR, L(, R)}, S). Пусть задано слово ()()(). Построим таблицу.

S16
S14		S34
S12		S32		S52
L11	R21	L31	R41	L51	R61
(	)	(	)	(	)

На втором этапе восстанавливаем дерево вывода.

Это можно выполнить с помощью следующей рекурсивной процедуры:

GEN(i,j,A)

| 1. Если j=1  Aa_i – правило с номером m, то выдать m.

| 2. Если j>1. Пусть k – наименьшее из чисел, для которых  Bt_ik Ct_i+k,j-k и ABCR

| имеет номер m. Выбрать это правило, выдать m и выполнить последовательно:

| GEN(i,k,B) ???

 GEN(i+k,j-k,C) ???

Старт: GEN(1,n,S)

Замечание. Описанный алгоритм существенно опирается на то, что грамматика имеет форму Хомского.