Общие принципы работы табличных распознавателей
Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов α=a1a2...an, αVT*, |α| = n, а построение вывода основывают на правилах заданной КС-грамматики G(VT,VN,P,S). Принцип их работы заключается в том, что искомая цепочка вывода строится не сразу – сначала на основе входной цепочки порождается некоторое промежуточное хранилище информации объема n*n (промежуточная таблица), а потом уже на его основе строится вывод.
Табличные алгоритмы обладают полиномиальными характеристиками требуемых вычислительных ресурсов в зависимости от длины входной цепочки. Для произвольной КС-грамматики G(VT,VN,P,S) время выполнения алгоритма Тэимеет кубическую зависимость от длины входной цепочки, а необходимый объем памяти Мэ– квадратичную зависимость от длины входной цепочки: α, αVT*, n=|α|: Тэ = О(n3) и Мэ = О(n2). Квадратичная зависимость объема необходимой памяти от длины входной цепочки напрямую связана с использованием промежуточного хранилища данных.
Табличные распознаватели универсальны – они могут быть использованы для распознавания цепочек, порожденных с помощью произвольной КС-грамматики (возможно, саму грамматику первоначально потребуется привести к заданному виду, но это не ограничивает универсальности алгоритмов). Кроме того, табличные распознаватели – это самые эффективные с точки зрения требуемых вычислительных ресурсов универсальные алгоритмы для распознавания цепочек КС-языков.
3.6.2. Алгоритм Кока–Янгера–Касами
Алгоритм Кока–Янгера–Касами для заданной грамматики G(VT,VN,P,S) и цепочки входных символов α = а1а2…an, αVT*, |α| = n строит таблицу Тn*n, такую, что AVN: AT[i,j], тогда и только тогда, если A+ai...ai+j-1. Таким образом, элементами таблицы Тn*nявляются множества нетерминальных символов из алфавита VN.
Тогда существованию вывода S*α соответствует условие ST[1,n].
При условии существования вывода по таблице Тn*nможно найти всю полную цепочку вывода S*α.
Для построения вывода по алгоритму Кока–Янгера–Касами грамматика G(VT,VN,P,S) должна быть в нормальной форме Хомского. Поскольку, как было показано выше, любую произвольную КС-грамматику можно преобразовать в нормальную форму Хомского, это не накладывает дополнительных ограничений на применимость данного алгоритма.
Алгоритм Кока–Янгера–Касами фактически состоит из трех вложенных циклов. Поэтому ясно, что время выполнения алгоритма имеет кубическую зависимость от длины входной цепочки символов. Таблица Тn*n, используемая для хранения промежуточных данных в процессе работы алгоритма, является таблицей множеств. Очевидно, что требуемый для ее хранения объем памяти имеет квадратичную зависимость от длины входной цепочки символов.
Сам алгоритм Кока–Янгера–Касами можно описать следующим образом:
Шаг 1.
Цикл для j от 1 до n
T[1,j] := {А | Ааj Р} – в Т[1, j] включаются все нетерминальные символы,
для которых в грамматике G существует правило Ааj.
Конец цикла для j.
Шаг 2.
Цикл для i от 2 до n
Цикл для j от 1 до n–i+1
T[i,j] :=;
Цикл для k от 1 до i–1
T[i,j] := T[i,j] {A | АВС Р, BT[k,j], CT[i–k,j+k]}
Конец цикла для k
Конец цикла для j
Конец цикла для i
Результатом работы алгоритма будет искомая таблица Тn*n. Для проверки существования вывода исходной цепочки в заданной грамматике остается только проверить условие ST[1,n].
Если вывод существует, то необходимо получить цепочку вывода. Для этого существует специальная рекурсивная процедура R. Она выдает последовательность номеров правил, которые нужно применить, чтобы получить цепочку вывода. Ее можно описать следующим образом: R(i,j,A), где AVN.
1. Если j=1 и существует правило Ааi, то выдать номер этого правила.
2. Иначе (если j > 1) возьмем k как наименьшее из чисел, для которых АВХ Р, BT[k,j], CT[i–k,j+k] (таких правил может быть несколько, для определенности берем наименьшее k). Пусть правило АВС имеет номер m. Тогда нужно выдать этот номер m, потом вызвать сначала R(i,k,B), а затем – R(i–k,j+k,C).
Для получения всей последовательности номеров правил нужно вызвать R(1,n,S).
Рекурсивная процедура R не требует дополнительной памяти для своего выполнения, кроме стека, необходимого для организации рекурсии. Время ее выполнения имеет квадратичную зависимость от длины входной цепочки.
На основании последовательности номеров правил, полученной с помощью алгоритма Кока–Янгера–Касами и рекурсивной процедуры R, можно построить левосторонний вывод для заданной грамматики G(VT,VN,P,S) и цепочки входных символов α. Таким образом, с помощью данного алгоритма решается задача разбора.