Табличные распознаватели КС-языков

Табличные распознаватели КС-языков основаны на иных принципах, нежели МП-автоматы. Они также получают на вход цепочку входных символов a=a₁a₂…a_n½aÎV_T^*, ½a½=n, а построение вывода основывается на правилах заданной КС-грамматики. Но цепочка вывода строится не сразу – сначала на основе входной цепочки порождается промежуточная таблица (или некое другое хранилище информации) размера n´n, а уже потом на её основе строится вывод.

Алгоритмы этого класса обладают полиномиальными характеристиками. Для произвольной КС-грамматики время выполнения алгоритма имеет кубическую, а требуемый объём памяти – квадратичную зависимость от длины входной цепочки: T=O(n³), M=O(n²).

Так же, как и алгоритмы с возвратами, табличные распознаватели универсальны – они могут использоваться для распознавания цепочек языка, задаваемого произвольной КС-грамматикой, хотя, быть может, её и требуется предварительно привести к некоторому заранее определённому виду. Табличные распознаватели являются самыми эффективнымиуниверсальнымиалгоритмами с точки зрения используемых вычислительных ресурсов.

Примерами алгоритмов этого класса являются алгоритм Кока-Янгера-Касами и алгоритм Эрли.

Алгоритм Кока-Янгера-Касами

Для построения вывода по рассматриваемому алгоритму грамматика должна находиться в нормальной форме Хомского, следовательно, произвольную грамматику следует сначала преобразовать к БНФ.

Работа алгоритма состоит из двух этапов. На первом этапе по заданной цепочке символов строится таблица, на втором с помощью этой таблицы осуществляется разбор цепочки. Процесс построения таблицы состоит из трёх вложенных циклов, чем и определяется кубическая зависимость времени работы алгоритма от длины входной цепочки. Итак:

Этап 1. Для заданной грамматики G(V_T,V_N,P,S)и цепочки символов a=a₁a₂…a_n, aÎV_T^*, ½a½= n алгоритм строит треугольную таблицу T_n*n состоящую из нетерминальных символов и такую, что "AÎV_N AÎT_i,j тогда и только тогда, когда AÞ⁺ a_ia_i+1…a_i+j–1. Например, существованию вывода SÞ⁺a соответствует условие SÎT_1,n.

Рассмотрим алгоритм построения таблицы:

Шаг 1 Первый столбец таблицы:

В T_i,1 включаются все нетерминальные символы, для которых в грамматике G существует правило A ® a_i, т.е. T_i,1 = {A½$(A ® a_i)ÎP} "i = 1,…,n. Очевидно: AÎT_i,1 Û AÞ⁺a_i.

Шаг 2 Пусть вычислены T_i,k "i =1,…,n, 1 £ k < j. Тогда остальные столбцы T_i,j ={A½$k: 1 £ k < j ½(A ® BC)ÎP, BÎ T_i,k, CÎ T_i+k,j–k}.

После этого шага AÎ T_i,j Û A Þ BC Þ⁺ a_i…a_i+k–1C Þ⁺
a_i…a_i+k–1a_i+k…a_{i+k+j–k–1} = a_i…a_i+j–1.

Шаг 3 Повторять шаг 2 до тех пор, пока не найдем все T_i,j "i,j: 1 £ i £ n, 1 £ j £ n–i+1.

Результатом работы данного алгоритма является таблица T. Для проверки существования вывода исходной цепочки в заданной грамматике остается проверить условие SÎT_1,n.

Пример: Рассмотрим грамматику G в БНФ: G({a,b},{S,A},P,S),
P ={S ® AA½AS½b; A ® SA½AS½a}.

Входная цепочка a='abaab', т.е. n=5. Построим таблицу T_i,j.

В первой колонке в i-й строке будут находиться те нетерминальные символы, из которых выводится i-й символ входной цепочки.

Для второго столбца (j=2): "i 1£ i< 4 T_i,2 ={X½$k: 1£ k< 2½(X ® BC)ÎP, BÎT_i,k, CÎT_i+k,2–k}. Очевидно, что в таком случае единственно возможное k=1, следовательно, BÎT_i,1, а CÎT_i+1,1, т.е. B и C – нетерминалы из первого столбца, из i-й и i+1-й строк.

Далее: "i 1£ i< 3 T_i,3 ={X½$k: 1£ k< 3½(X ® BC)ÎP, BÎT_i,k, CÎT_i+k,3–k}, т.е. k=1 или k=2 и либо BÎ T_i,1, CÎ T_i+1,2, либо BÎT_i,2, CÎT_i+2,1. Аналогично: "i=1,2 T_i,4 ={X½$k: 1£ k<4½(X ® BC)ÎP, BÎT_i,k, CÎT_i+k,4–k}, т.е. k=1, или k=2, или k=3. Либо BÎT_i,1, CÎT_i+1,3, либо BÎT_i,2, CÎT_i+2,2, либо BÎ T_i,3, CÎ T_i+3,1… В итоге получим таблицу T: 

Ti,j:	A	A,S	A,S	A,S	A,S	Проверка показывает, что целевой символ грамматики SÎ T1,5, следовательно, цепочка a выводима в грамматике G.
	S	A	S	A,S
	A	S	A,S
	A	A,S
	S

Этап 2. Построение цепочки вывода.

Если вывод существует, то для получения цепочки вывода имеется специальная рекурсивная процедура R. Она выдаёт последовательность номеров правил, которые надо применить, чтобы получить цепочку вывода. Процедура R порождает левый разбор, соответствующий выводу AÞ⁺ a_ia_i+1…a_i+j–1.

Опишем эту процедуру R(i,j,A), AÎV_N:

1. Если j=1 и существует правило (A®a_i,)ÎP, то выдать номер правила.

2. Если j>1, то возьмем k (1£ k <j) как наименьшее из чисел, для которых существует правило $ (A ® BC)ÎP, BÎT_i,k, CÎT_i+k,j–k (таких правил может быть несколько). Пусть правило A®BC имеет номер m. Тогда нужно выдать этот номер m, а затем вызвать сначала R(i,k,B), потом R(i+k,j–k,C).

Для получения цепочки вывода нужно вызвать R(1,n,S).

На основании полученной последовательности номеров правил строится левосторонний вывод для заданной грамматики G и входной цепочки a. Þ Данный алгоритм позволяет решить задачу разбора.

Вернёмся к нашему примеру. Поскольку для построения вывода нужно будет выдавать номера правил, удобнее переписать все правила грамматики G по отдельности, перенумеровав их:

Пример: Запишем грамматику G в виде:

(1) S ® AA (2) S ® AS (3) S ® b

(4) A ® SA (5) A ® AS (6) A ® a

Для получения всей последовательности номеров правил вывода нужно вызвать R(1,n,S), т.е. в нашем случае R(1,5,S).

1) R(1,5,S): i=1, j=5. Поскольку j>1, нужно взять такое минимальное k, что существует правило $ (S ® BC)ÎP, BÎT_1,k, CÎT_1+k,5–k. Раз k должно быть минимальным, начинаем проверку с наименьшего из возможных: k=1, т.е. должно $ (S ® BC)ÎP, BÎT_1,1=’A’, CÎT_2,4=’A,S’. Такое правило есть: S ® AA (либо S ® AS), его номер 1 (либо 2). Условимся брать первое по порядку подходящее правило. Тогда нужно выдать его номер 1, а затем вызвать сначала R(1,1,A), потом R(2,4,A).

2) R(1,1,A): i=1, j=1. $ (A®a₁=’a’)ÎP, это правило с № 6.

3) R(2,4,A): i=2, j=4. Найдем минимальное k, такое что $ (A ® BC)ÎP, BÎT_2,k, CÎT_2+k,4–k. Проверим k=1, т.е. должно $ (A ® BC)ÎP, BÎT_2,1=’S’, CÎT_3,3=’A,S’. Такое правило есть: A ® SA, его номер 4. Тогда нужно выдать этот номер 4, а затем вызвать сначала R(2,1,S), потом R(3,3,A).

4) R(2,1,S): i=2, j=1. $ (S®a₂=’b’)ÎP, это правило с № 3.

5) R(3,3,A): i=3, j=3. Найдем минимальное k, такое что $ (A ® BC)ÎP, BÎT_3,k, CÎT_3+k,3–k. Возможно только k=1 или 2. Проверим k=1, т.е. должно $ (A ® BC)ÎP, BÎT_3,1=’A’, CÎT_4,2=’A,S’. Такое правило есть: A ® AS, его номер 5. Тогда нужно выдать этот номер 5, а затем вызвать сначала R(3,1,A), потом R(4,2,S).

6) R(3,1,A): i=3, j=1. $ (A®a₃=’a’)ÎP, это правило с № 6.

7) R(4,2,S): i=4, j=2. Найдем минимальное k, такое что $ (S ® BC)ÎP, BÎT_4,k, CÎT_4+k,2–k. Единственно возможно k=1, т.е. должно $ (S ® BC)ÎP, BÎT_4,1=’A’, CÎT_5,1=’S’. Такое правило есть: S ® AS, его номер 2. Тогда нужно выдать этот номер 2, а затем вызвать сначала R(4,1,A), потом R(5,1,S).

8) R(4,1,A): i=4, j=1. $ (A®a₄=’a’)ÎP, это правило с № 6.

9) R(5,1,S): i=5, j=1. $ (S®a₅=’b’)ÎP, это правило с № 3.

Процесс закончился. Получили последовательность использованных правил: 1,6,4,3,5,6,2,6,3. Построим вывод: S Þ⁽¹⁾AA Þ⁽⁶⁾aA Þ⁽⁴⁾aSA Þ⁽³⁾ ÞabA Þ⁽⁵⁾abAS Þ⁽⁶⁾abaS Þ⁽²⁾abaAS Þ⁽⁶⁾abaaS Þ⁽³⁾abaab.

Поскольку рассмотренная грамматика не является однозначной, можно было выбирать другие номера правил и, соответственно, цепочка вывода могла получиться иной.

Алгоритм Эрли

Для заданной грамматики G(V_T,V_N,P,S)и цепочки символов a=a₁a₂…a_n, aÎV_T^*, ½a½=n алгоритм строит последовательность «списков ситуаций» I₀, I₁, …, I_n, которая организована несколько сложнее, чем простая таблица. Каждая ситуация, входящая в список I_j для входной цепочки a, представляет собой структуру специального вида. На основании полученного списка ситуаций можно построить всю цепочку вывода и получить номера применяемых правил.

В нашем курсе данный алгоритм подробно рассматриваться не будет.

Алгоритм Эрли также является универсальным и имеет полиномиальную сложность, как и предыдущий рассмотренный алгоритм. Для произвольной КС-грамматики он имеет такие же оценки. Для однозначной КС-грамматики время его работы имеет квадратичную зависимость, а для некоторых более узких классов его характеристики ещё улучшаются. В целом он обладает лучшими характеристиками среди всех универсальных алгоритмов, хотя и более сложен в реализации.