Изменения

= Контекстно#перенаправление [[Алгоритм Кока-свободная грамматика =Янгера-Касами разбора грамматики в НФХ]]'''Задача о выводе в контекстно-свободной грамматике''' - задача о том, выводимо ли данное слово в данной контекстно-свободной грамматике. '''Алгоритм Кока-Янгера-Касами''' - алгоритм, решающий эту задачу.

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

Пусть алфавит состоит из символов a{{Определение|definition='''[[Контекстно-свободные грамматики, вывод, b лево- и Sправосторонний вывод, при этом S дерево разбора|Контекстно- стартовый символ, а и b свободная грамматика]]''' ('''КС- терминальные. Пусть в этой грамматике определены следующие правила:* S → SS;* S → ab;* S → aSb;Тогда в ней можно вывести слово ababab следующим образом: S → SS → Sab → SSab → abSab → abababПри этомграмматика''', например'''бесконтекстная грамматика''') — способ описания формального языка, слово bab невозможно вывести в этой грамматике.задающийся:

* Множеством <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 &rarr; SS* S &rarr; ()* S &rarr; (S) Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность (()(())) может быть выведена следующим образом: * <tex> S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) </tex>Задача вывода в контекстно== Нормальная форма Хомского == '''[[Нормальная форма Хомского]]''' - нормальная форма КС-свободной грамматике состоит грамматик, в томкоторой все продукции имеют вид:* A &rarr; a, чтобы выяснитьгде ''A'' - нетерминал, можно ли вывести данное слово в этой КСа ''a'' -грамматикетерминал* A &rarr; BC, где ''A'', ''B'', т.е. выяснить принадлежность этого слова определяемому грамматикой языку. Для решения этой задачи существуют несколько способов''C'' - нетерминалы, напримерпричем ''B'' и ''C'' не являются начальными нетерминалами* S &rarr; ε, нисходящий анализ методом линейного спуска. Также применяется восходящий алгоритм синтаксического анализа Кока где S - начальный нетерминал и ε - Янгера пустая строка (данная продукция необходима, если в языке присуствует пустая строка) [[Нормальная форма Хомского|Можно показать]], что любую КС- Касамиграмматику можно привести к нормальной форме Хомского.

'''Алгоритм является универсальным для всех Кока-Янгера-Касами''' (''Cocke — Younger — Kasami algorithm'', '''CYK - алгоритм''') - универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматикграмматике в нормальной форме Хомского. Пусть дана строка <tex>a_1 a_2 ... a_n</tex>. Заведем трехмерный массив d, состоящий из логических значений, которые должны быть приведены и <tex>d[A,i,j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>a_i a_{i+1} ... a_j</tex>. Тогда:* <tex>d[A,i,i] = true</tex>, если в нормальную форму Хомского без &epsilon;грамматике присутствует правило <tex>A \rightarrow a_i</tex>, иначе <tex>false</tex>* Остальные элементы массива заполняются динамически: <tex>d[A,i,j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{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>d[S,1,n]</tex> содержит ответ на вопрос, выводима ли данная строка в данной грамматике. Правила такой грамматики имеют вид либо А&rarr; Заметим, что если массив будет хранить целые числа, аформулу заменить на <tex>d[A, либо А&rarr;i,j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B,i,k] \cdot d[C,k+1,j]</tex>, то <tex>d[A, где a i,j]</tex> - количество способов получить подстроку <tex>a_i...a_j</tex> из нетерминала <tex>A</tex>. Пусть <tex>P_{A \rightarrow BC}</tex> - терминал''стоимость'' вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A,i,j] = \min\limits_{A \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>. Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке. === Сложность алгоритма === Пусть, <tex>n</tex> - длина входной строки, а <tex>m</tex> - количество правил вывода в грамматике. Обработка правил вида <tex>A \rightarrow a_i</tex> выполняется за <tex>O(nm)</tex>. Проход по всем подстрокам выполняется за <tex>O(n^2)</tex>. В обработке подстроки присутствует цикл по всем правилам вывода и C нетерминалы по всем разбиениям на две подстроки,не являющиеся начальнымиследовательно обработка работает за <tex>O(nm)</tex>. В итоге - <tex>O(n^3 m)</tex>. Алгоритм имеет сложность  Следовательно, общее время работы алгоритма - <tex>O(n^3m)</tex> и использует . Кроме того, алгоритму требуется память (на массив <tex>d</tex>) объемом <tex>O(n^2m)</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 = Ссылки =

Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<tex>a_1, a_2, \ldots, a_n<* [http:/tex>'''/en. В каждый элемент этой матрицы <tex>t_{ik}</tex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: '''<tex>a_i, \ldots, a_{i+k-1}</tex>'''wikipedia.Элементы матрицы вычисляются следующим образом::: <tex>\forall<org/tex>i <tex>t_{i1}<wiki/tex> = { A | A &rarr; <tex>a_i</tex>};CYK_algorithm Википедия - CYK algorithm]* [http:: <tex>\forall</tex>i < j <tex>t_{ij}</tex> = {A | A&rarr;BC и <tex>1 \leqslant k < j : B \in t_{ik}, C \in t_{i+k, j-k}</tex>}www.Действительно, в каждый элемент <tex>t_{i1}</tex> (в данном случае удобнее рассматривать первой нижнюю строку) помещаются все нетерминалы, для которых существует правило A &rarr; <tex>a_i</tex>ctc. Пусть теперь заполнены все строки до j-1-й включительноmsiu. Рассмотрим элемент <tex>t_{ij}<ru/tex>, соответствующий фрагменту &lt;<tex>a_1,\ldots, a_j <program/tex>&gt; входной строки. Разобьём его всеми способами на пары соседних строк '''<tex> <a_i> и <a_{i+1}...a_j>; <a_ia_{i+1}> и <a_{i+2} ...a_j><t-system/tex>''', и т.д. Каждому варианту разбиения соответствует пара элементов матрицы, в которых стоят нетерминалы, из которых могут быть выведены соответствующие строки. Пусть эта пара элементов – (t',t"). В рассматриваемый элемент <tex>t_{ij}<diploma/tex> помещаем нетерминал А, если среди правил грамматики есть правило А&rarr;ВС, и нетерминал В входит в элемент t', а С – входит в элемент t"node39.html Алгоритм Кока-Янгера-Касами]