Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами

Контекстно-свободная грамматика

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами. Для того, чтобы определить контекстно-свободную грамматику, необходимо:

• 1) Задать конечное множество A - алфавит; его

элементы называют символами, а конечные последовательности симво- лов называют словами (в данном алфавите);

• 2) Разделить все символы алфавита A на две группы: терми-

нальные ("окончательные") и нетерминальные ("промежуточные");

• 3) Выбрать один из нетерминальных символов, который будет считаться начальным;
• 4) Указать конечное число правил грамматики(продукций) вида:

    K → X

где K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов. Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.

Пример

Пусть алфавит состоит из символов a, b и S, при этом S - стартовый символ, а и b - терминальные. Пусть в этой грамматике определены следующие правила:

• S → SS;
• S → ab;
• S → aSb;

Тогда в ней можно вывести слово ababab следующим образом:

  S → SS → Sab → SSab → abSab → ababab

При этом, например, слово bab невозможно вывести в этой грамматике.

Задача о выводе

Задача вывода в контекстно-свободной грамматике состоит в том, чтобы выяснить, можно ли вывести данное слово в этой КС-грамматике, т.е. выяснить принадлежность этого слова определяемому грамматикой языку. Для решения этой задачи существуют несколько способов, например, нисходящий анализ методом линейного спуска. Также применяется восходящий алгоритм синтаксического анализа Кока - Янгера - Касами.

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

Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без ε-правил. Правила такой грамматики имеют вид либо А→а, либо А→BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм имеет сложность [math]O(n^3)[/math] и использует [math]O(n^2)[/math] памяти.

Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке [math]a_1, a_2, \ldots, a_n[/math]. В каждый элемент этой матрицы [math]t_{ik}[/math] помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: [math]a_i, \ldots, a_{i+k-1}[/math]. Элементы матрицы вычисляются следующим образом:

[math]\forall[/math]i [math]t_{i1}[/math] = { A | A → [math]a_i[/math]};

[math]\forall[/math]i < j [math]t_{ij}[/math] = {A | A→BC и [math]1 \leqslant k \lt j : B \in t_{ik}, C \in t_{i+k, j-k}[/math]}.

Действительно, в каждый элемент [math]t_{i1}[/math] (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A → [math]a_i[/math]. Пусть теперь заполнены все строки до j-1-й включительно. Рассмотрим элемент [math]t_{ij}[/math], соответствующий фрагменту <[math]a_1,\ldots, a_j [/math]> входной строки. Разобьём его всеми способами на пары соседних строк [math] \lt a_i\gt и \lt a_{i+1}...a_j\gt ; \lt a_ia_{i+1}\gt и \lt a_{i+2} ...a_j\gt [/math], и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент [math]t_{ij}[/math] помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".

Входная строка принадлежит языку, порождаемому грамматикой, если в элементе [math]t_{1n}[/math] встретится начальный нетерминал.

Литература

• [1]
• Википедия - CYK algorithm
• Алгоритм Кока-Янгера-Касами