Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
![](/wiki/images/thumb/c/ca/Table.jpg/300px-Table.jpg)
Контекстно-свободная грамматика
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами. Для того, чтобы определить контекстно-свободную грамматику, необходимо:
- 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 нетерминалы ,не являющиеся начальными. Алгоритм использует только квадратную матрицу, т.е.
памяти. В алгоритме осуществляется для каждой ячейки перебор по всем разделениям фрагмента строки, выводимого из нетерминалов в этой ячейке, и по всем элементам алфавита, поэтому сложность можно оценить как , где G - алфавит.Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке
. В каждый элемент этой матрицы помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: . Элементы матрицы вычисляются следующим образом:- i = { A | A → };
- i < j = {A | A→BC и }.
Действительно, в каждый элемент
(в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A → Пусть теперь заполнены все строки до j-1-й включительно. Рассмотрим элемент , соответствующий фрагменту < > входной строки. Разобьём его всеми способами на пары соседних строк < > и < >; < > и < >, и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".Входная строка принадлежит языку, порождаемому грамматикой, если в элементе
встретится начальный нетерминал.