Информатика и выч. техника \ Теория языков программирования и методы трансляции

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 12

Алгоритм успешно завершён, в стеке возврата содержатся номера правил: L₂=[4,13,0,2,12,0,0,6,0,0,0,11,0]=[4,13,2,12,6,11]. Тогда цепочка вывода имеет вид: SÞT/EÞT/(S)ÞT/(S–T)ÞT/(S–b)ÞT/(a–b)Þa/(a–b). Дерево вывода строится аналогично построенному ранее.

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

Как и алгоритм нисходящего распознавателя с возвратами, сам по себе алгоритм «сдвиг-свёртка» не используется в компиляторах, но его основные принципы лежат в основе многих восходящих распознавателей, строящих правосторонние выводы и работающих без возвратов.

Оба рассмотренных распознавателя имеют приблизительно одинаковые показатели. Выбор того или иного алгоритма для реализации простейшего распознавателя зависит от грамматики языка.

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

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

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

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

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

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

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

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

Этап 1. Для заданной грамматики G(VT,VN,P,S) и цепочки символов a=a₁a₂…a_n, aÎVT^*, ½a½= n алгоритм строит треугольную таблицу T_n_*_n состоящую из нетерминальных символов и такую, что "AÎVN AÎT_i_,_j тогда и только тогда, когда AÞ⁺a_ia_i₊₁…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:

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

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

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Скачать файл