49
правок
Изменения
Нет описания правки
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех продукций(правил этой грамматики) являются одиночными нетерминалами.
Для того, чтобы определить контекстно-свободную грамматику, необходимо:
* 1) Задать конечное множество 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 < 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><a_i> и <a_{i+1}...a_j>; <a_ia_{i+1}> и <a_{i+2} ...a_j></math>''', и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <math>t_{ij}</math> помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t". Входная строка принадлежит языку, порождаемому грамматикой, если в элементе <math>t_{1n}</math> встретится начальный нетерминал.
