Общие принципы работы табличных распознавателей

 

Табличные распознаватели используют для построения цепочки вывода КС-грамматики другие принципы, нежели МП-автоматы. Как и МП-автоматы, они получают на вход цепочку входных символов α=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, та­кую, что AVN: AT[i,j], тогда и только тогда, если A+ai...ai+j-1. Таким обра­зом, элементами таблицы Тn*nявляются множества нетерминальных символов из алфавита VN.

Тогда существованию вывода S*α соответствует условие ST[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 |  АВС  Р, BT[k,j], CT[i–k,j+k]}

Конец цикла для k

Конец цикла для j

Конец цикла для i

 

Результатом работы алгоритма будет искомая таблица Тn*n. Для проверки существования вывода исходной цепочки в заданной грамматике остается только про­верить условие ST[1,n].

Если вывод существует, то необходимо получить цепочку вывода. Для этого существует специальная рекурсивная процедура R. Она выдает последователь­ность номеров правил, которые нужно применить, чтобы получить цепочку вы­вода. Ее можно описать следующим образом: R(i,j,A), где AVN.

1. Если j=1 и существует правило Ааi, то выдать номер этого правила.

2. Иначе (если j > 1) возьмем k как наименьшее из чисел, для которых  АВХ  Р, BT[k,j], CT[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) и цепочки входных сим­волов α. Таким образом, с помощью данного алгоритма решается задача разбора.