418
правок
Изменения
м
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики, у которой левые части всех правил являются одиночными нетерминалами.Для того, чтобы определить контекстно-свободную грамматику, необходимо:* 1) Задать конечное множество A - алфавит; егоэлементы называют символами, а конечные последовательности симво-лов называют словами (в данном алфавите);* 2) Разделить все символы алфавита A на две группы: терми-нальные ("окончательные") и нетерминальные ("промежуточные");* 3) Выбрать один из нетерминальных символов, который будет считаться начальным;* 4) Указать конечное число правил грамматики(продукций) вида: K → Xгде K - некоторый нетерминальный символ, а X - слово, которое может состоять как из терминальных, так и не из терминальных символов.Выводом в контекстно-свободной грамматике называется последовательность слов X[0], X[1], ... ,X[n], где X[0] состоит только из начального символа, а каждое слово X[i+1] получается из X[i] заменой какого-либо нетерминального символа на слово по одному из правил грамматики.= Определения =
Пусть алфавит состоит из символов a{{Определение|definition='''[[Контекстно-свободные грамматики, вывод, b лево- и Sправосторонний вывод, при этом S дерево разбора|Контекстно- стартовый символ, а и b свободная грамматика]]''' ('''КС- терминальные. Пусть в этой грамматике определены следующие правила:* S → SS;* S → ab;* S → aSb;Тогда в ней можно вывести слово ababab следующим образом: S → SS → Sab → SSab → abSab → abababПри этомграмматика''', например'''бесконтекстная грамматика''') — способ описания формального языка, слово bab невозможно вывести в этой грамматике.задающийся:
Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<tex>a_1Заметим, a_2что если массив будет хранить целые числа, \ldots, a_nа формулу заменить на </tex>'''. В каждый элемент этой матрицы <tex>t_{ik}</tex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины kd[A, начинающийся i-ым символом: '''<tex>a_i, j] = \ldots, a_{i+k-1}</tex>'''.Элементы матрицы вычисляются следующим образом::: <tex>sum\forall</tex>i <tex>t_limits_{i1}</tex> = { A | A → <tex>a_i</tex>};:: <tex>\forall</tex>i < j <tex>t_{ijrightarrow BC}</tex> = {A | A→BC и <tex>1 \leqslant k < j : B sum\in t_{ik}, C \in t_limits_{k = i+k, j-k}</tex>}.Действительно, в каждый элемент <tex>t_^{i1}</tex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A → <tex>a_i</tex>. Пусть теперь заполнены все строки до j-1-й включительно. Рассмотрим элемент <tex>t_{ij}</tex>d[B, соответствующий фрагменту <<tex>a_1i,k] \ldotscdot d[C, a_j </tex>> входной строки. Разобьём его всеми способами на пары соседних строк <<tex>a_i</tex>> и <<tex>a_{ik+1}...a_j,j]</tex>>; <, то <tex>a_ia_{d[A,i+1},j]</tex>> и <- количество способов получить подстроку <tex>a_{i+2} a_i...a_j</tex>>, и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент нетерминала <tex>t_{ij}A</tex> помещаем нетерминал А, если среди правил грамматики есть правило А→ВС, и нетерминал В входит в элемент t', а С – входит в элемент t".
Входная строка принадлежит языку, порождаемому грамматикойПусть <tex>P_{A \rightarrow BC}</tex> - ''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если в элементе использовать формулу <tex>t_d[A,i,j] = \min\limits_{1nA \rightarrow BC}\min\limits_{k = i}^{j-1} ( d[B,i,k] + d[C,k+1,j] + P_{A \rightarrow BC} )</tex>, то <tex>d[A,i,j]</tex> - минимальная стоимость вывода подстроки <tex>a_i...a_j</tex> из нетерминала <tex>A</tex> встретится начальный нетерминал.
* [http://www.intuit.ru/department/algorithms/mathformlang/7/]
Перенаправление на Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
#перенаправление [[Файл:table.jpg|300px|thumb|right|Таблица Алгоритм Кока-Янгера-Касами разбора алгоритма для цепочки из шести символов. В клетку <tex>t_{34}</tex> должны быть помещены нетерминалы, из которых выводится фрагмент входной строки длиной четыре символа, начинающийся с <tex>a_{3}</tex>, т.е. это цепочка <tex>a_{3}a_{4}a_{5}a_{6}</tex>. Этот фрагмент тремя способами можно разбить на пары непустых соседних фрагментов: (1) <tex>a_{3}</tex> и <tex>a_{4}a_{5}a_{6}</tex>, (2): <tex>a_{3}a_{4}</tex> и <tex>a_{5}a_{6}</tex>, (3): <tex>a_{3}a_{4}a_{5}</tex> и <tex>a_{6}</tex>. Этим трем парам фрагментов соответствуют пары клеток, грамматики в которых могут стоять нетерминалы, из которых эти фрагменты выводятся: (1) <tex>t_{31}</tex> и <tex>t_{43}</tex>, (2): <tex>t_{32}</tex> и <tex>t_{52}</tex>, (3): <tex>t_{33}</tex> и <tex>t_{61}</tex>. Если НФХ]]'''Задача о выводе в этих клетках находятся соответственно нетерминалы B и C и существует правило A→BCконтекстно-свободной грамматике''' - задача о том, то A заносится выводимо ли данное слово в <tex>t_{34}</tex>]]= Контекстноданной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' -свободная грамматика =алгоритм, решающий эту задачу.
==ПримерКонтекстно-свободная грамматика ==
* Множеством <tex>\Sigma</tex> терминальных символов* Множеством <tex>N</tex> нетерминальных символов* Стартовым нетерминалом <tex>S \in N</tex>* Множеством продукций вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части - одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.}} = Задача о выводе == Пример === Терминалы: {(, )}. Нетерминалы: {S}. Продукции:* S → SS* S → ()* S → (S) Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом: * <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex>Задача вывода в контекстно== Нормальная форма Хомского == '''[[Нормальная форма Хомского]]''' - нормальная форма КС-свободной грамматике состоит грамматик, в томкоторой все продукции имеют вид:* A → a, чтобы выяснитьгде ''A'' - нетерминал, можно ли вывести данное слово в этой КСа ''a'' -грамматикетерминал* A → BC, где ''A'', ''B'', т.е. выяснить принадлежность этого слова определяемому грамматикой языку. Для решения этой задачи существуют несколько способов''C'' - нетерминалы, напримерпричем ''B'' и ''C'' не являются начальными нетерминалами* S → ε, нисходящий анализ методом линейного спуска. Также применяется восходящий алгоритм синтаксического анализа Кока где S - начальный нетерминал и ε - Янгера пустая строка (данная продукция необходима, если в языке присуствует пустая строка) [[Нормальная форма Хомского|Можно показать]], что любую КС- Касамиграмматику можно привести к нормальной форме Хомского.
= Алгоритм Кока-Янгера-Касами =
'''Алгоритм является универсальным для всех Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматик, которые должны быть приведены грамматике в нормальную форму нормальной форме Хомского без ε-правил. Правила такой грамматики имеют вид либо А→а Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, либо А→BCи <tex>d[A, где a - терминалi, B j] = true</tex> тогда и C нетерминалы только тогда,не являющиеся начальнымикогда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} .. Алгоритм использует только квадратную матрицу, т.еa_j</tex>. Тогда:* <tex>O(nd[A,i,i] = true</tex>, если в грамматике присутствует правило <tex>A \rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A,i,j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^2){j-1} d[B,i,k] \wedge d[C,k+1,j]</tex> памяти. В алгоритме осуществляется для каждой ячейки перебор по всем разделениям фрагмента строкиТо есть, выводимого подстроку <tex>a_i...a_j</tex> можно вывести из нетерминалов в этой ячейкенетерминала <tex>A</tex>, если существует продукция <tex>A \rightarrow BC</tex> и по всем элементам алфавитатакое <tex>k</tex>, что подстрока <tex>a_i...a_k</tex> выводима из <tex>B</tex>, поэтому сложность можно оценить как а подстрока <tex>a_{k+1}...a_j</tex> - из <tex>C</tex>. Значение <tex>O(d[S,1,n^3 \cdot |G|)]</tex>содержит ответ на вопрос, где G - алфавитвыводима ли данная строка в данной грамматике.
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке. =Литература== Сложность алгоритма === Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике. Обработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>. Следовательно, общее время работы алгоритма - <tex>O(n^3 m)</tex>. Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2 m)</tex>. === Псевдокод === function CYK (a - строка длины n, G - набор правил вывода грамматики с m нетерминалами, S - стартовый нетерминал) -> bool begin d : array [1..m,1..n,1..n] of bool for i = 1 to n if (A -> a[i] - продукция) d[A,i,i] = true for len = 1 to n-1 for i = 1 to n-l for (A -> BC - продукция) for k = i to i+len-1 d[A,i,i+len] = d[A,i,i+len] or (d[B,i,k] and d[C,k+1,i+len]) return d[S,1,n] end = Ссылки =
* [http://en.wikipedia.org/wiki/CYK_algorithm Википедия - CYK algorithm]
* [http://www.ctc.msiu.ru/program/t-system/diploma/node39.html Алгоритм Кока-Янгера-Касами]
[[Категория:В разработке]]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Теория формальных языков]]
