49
правок
Изменения
Нет описания правки
[[Файл: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>.]]
= Контекстно-свободная грамматика =
= Алгоритм Кока-Янгера-Касами =
Алгоритм является универсальным для всех КС-грамматик, которые должны быть приведены в нормальную форму Хомского без ε-правил. Правила такой грамматики имеют вид либо А→а, либо А→BC, где a - терминал, B и C нетерминалы ,не являющиеся начальными. Алгоритм использует только квадратную матрицу, т.е. <tex>O(n^2)</tex> памяти. В алгоритме осуществляется для каждой ячейки перебор по всем разделениям фрагмента строки <tex>O(n^3)</tex> и использует <tex>O(n^2)</tex> памяти.
Сам алгоритм состоит в построении треугольной матрицы разбора T по заданной входной строке '''<tex>a_1, a_2, \ldots, a_n</tex>'''. В каждый элемент этой матрицы <tex>t_{ik}</tex> помещаются все нетерминалы, из которых можно вывести отрезок входной строки длины k, начинающийся i-ым символом: '''<tex>a_i, \ldots, a_{i+k-1}</tex>'''.
