Главная Промышленная автоматика.

И 1/-i+l. Значениями переменных t,j будут подмножества множества N. Нетерминал Л будет принадлежать t-j тогдаитолько тогда, когда Л z>+. .a,.+y i, т, е. когда из Л выводятся / входных символов, начиная с позиции /. В частности, входная цепочка w принадлежит L(G) тогда и только тогда, когда St„.

Таким образом, чтобы выяснить, принадлежит ли w языку L(G), вычислим для W таблицу разбора Т и посмотрим, принадлежит ли S ее элементу Г. Затем, если нужен один (или все) разбор цепочки W, его можно построить с помощью таблицы разбора. Для этой цели можно использовать алгоритм 4.4.

Сначала мы приведем алгоритм, вычисляющий таблицу разбора, а затем алгоритм, строящий разборы по этой таблице.

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

Вход. КС-грамматика G = (N, 2, Р, S) в нормальной форме Хомского без е-правил и входная цепочка waa. . .ai,+.

Выход. Таблица разбора Т для цепочки w, такая, что At,-, тогда и только тогда, когда Л а-ач!-. .a,.+y i.

Метод.

(1) Положить = {А\А->а принадлежит Р} для каждого i. После этого шага из Л следует, очевидно, Л>+й;.

(2) Допустим, что уже вычислены tcj- для всех 1</<п н всех < /. Положить

tij= {А I для некоторого lk < j правило А~ВС принадлежит Р, Btik н Cti,

Так как 1 </г </, то ft и /-ft меньше /. Таким образом, tf, и ti+,j f вычисляются раньше, чем tj. После этого шага из Atij следует

(3) Повторять шаг (2) до тех пор, пока пе станут известны tij для всех l<i<rt и 1/rt -i+l. □

Пример 4.8, Рассмотрим грамматику G в нормальной форме Хомского с правилами

S-А-

AA\AS\b ~SA]AS\a

) Заметим, что мы ие обсуждаем в деталях, как это сделать. Очевидно, что соответствующее вычисление можно выполмить на вычислительной машине, Когда речь пойдет о временной сложности алгоритма 4.3, будут дани детали этого шага, обеспечивающие его эффективное выполнение,

2 А. Ахо, Дж. Ульман, т. 1 353

Одна реализация алгоритма Домёлкн описана Хекстом н Робертсом [1970] В обзорной статье Коэпа и Готлиба [1970] описывается использование

б алгоритмах разбора (с возвратами и без них) представлений КС-грамматик

с помощью списочных структур.

4.2. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

Мы изучим два метода синтаксического анализа, работающие для всех контекстно-свободных грамматик: алгоритм Кока -Яп-гера -Касами и алгоритм Эрли. Каждый нз них требует времени и емкости п, но последнему алгоритму для однозначных грамматик достаточно времени п. Кроме того, можно добиться, чтобы алгоритм Эрли тратил линейные время и емкость для большинства грамматик, которые можно анализировать за линейное время методами, излагаемыми в последующих главах.

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

В последнем разделе мы обнаружили, что нисходящие н восходящие алгоритмы с возвратами могут затрачивать на разбор экспоненциальное время. Здесь мы изложим метод, для которого гарантируется, что оп выполнит ту же работу для произвольной грамматики за время, пропорциональное кубу длины входной цепочки. Это по существу метод „динамического программирования", и мы включили его сюда из-за его простоты. Сомнительно, однако, что он найдет практическое применение, поскольку

(1) время п» слишком велико, чтобы его можно было позволить потратить на разбор,

(2) используемая емкость памяти пропорциональна квадрату длины входа,

(3) метод разд. 4.2.2 (алгоритм Эрли) во всех отношениях так же хорош, как этот, а для многих грамматик даже лучше.

Метод работает следующим образом. Пусть G -(N, S, Р, 5)- КС-грамматика без е-нравил в нормальной форме Хомского. Простое обобщение алгоритма работает и для грамматик, не находящихся в этой нормальной форме; мы оставим это обобщение читателю. Так как КС-грамматика без циклов лево- и правопокрывается КС-грамматикой в нормальной форме Хомского, то это обобщение не так уж важно.

Пусть шаад.. .«„-входная цепочка, которую нужно разобрать согласно грамматике G. Предполагается, что аб lin. Суть алгоритма состоит в построении треугольной таблицы разбора Т, элементы которой обозначим ip где К /

) Уместно упомянуть работы самого Домёлкн [1964, 1965].Яр«ж. nepeS



Пусть а&ййЬ -входная цепочка. Таблица разбора Г, получающаяся в результате работы алгоритма 4.3, показана на рис 4.8. После шага (1) = {Л}, так как Лй принадлежит Р и аа. На шаге (2) в i. добавляем S, так как S-AA принадлежит Р и Л принадлежит /д и /41. Заметим вообще, что, как видно

Рис. 4.8. Таблица разбора Т.

из рисунка, tfj для i > 1 можно вычислить, обследовав нетерминалы в следующих парах элементов таблицы разбора:

{(1» 1-11. y-i)i (Л2> i-\-2, /-а)» • • > ((, U+J-i, 1)

Тогда, если Btik и Ct+fj.} для некоторого 1<</ и А-ВСР, добавляем Л к tj. Это значит, что мы одновременно движемся вверх но i-му столбцу и вниз по диагонали, спускающейся вправо от ячейки t, обозревая нетерминалы, расположенные в проходимых таким образом парах ячеек. Так как St, то abaab £L{G). □

Теорема 4.6. Если алгоритм 4.3 применяется к грамматике G в нормальной форме Хомского и входной цепочке а.. ,а„, то по окончании его работы А принадлежит тогда и только тогда, когда Л +й,-. .

Доказательство. Доказательство проводится индукцией по /; мы оставляем его в качестве упражнения. Наиболее трудный шаг содержится в доказательстве достаточности условия; здесь нужно заметить, что если />1 и Л й,-. . .й+у., то найдутся такие нетерминалы Л и Си число k, что Л-ВСР,

Ч + к-

i+J-L-

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

рых-длина п входной цепочки. Элементарной операцией будем считать каждую из следующих:

(1) Присваивание неременной значения другой переменной или константы, а также суммы или разности значений двух переменных или констант,

(2) проверка равенства значений двух неременных,

(3) обследование и/или изменение значения переменной tij, если i и / - текущие значения двух целых переменных нли констант,

(4) обследование /-го входного символа а, если / - значение некоторой переменной.

Заметим, что операция (3) имеет ограниченный объем, если грамматика заранее известна. Если грамматика становится более сложной, то объем памяти, необходимой для хранения неременной tij, и время, необходимое для ее обследования, возрастают, если рассматривать разумные шаги более элементарной природы. Одиако здесь мы интересуемся только зависимостью времени от длины входной цепочки. Читателю предоставляется самому определить более элементарные шаги, которыми можно заменить (3), и найти функциональную зависимость времени их вычисления от числа нетерминалов и правил грамматики.

Соглашение. Запись / (п) = 0{g (п)) означает, что существует такая константа /г, что f{n)kg{n) для всех Таким об-

разом, когда мы говорим, что алгоритм 4.3 выполняет свою работу за время O(rt), мы подразумеваем, что существует такая константа /г, что для входной цепочки длины п тратится не более kn элементарных операций.

Теорема 4.7. Алгоритму 4.3 для вычисления всех t/j требуется 0{п) элементарных операций указанного выше типа.

Доказательство. Чтобы вычислить t-y для всех i, надо положить 1 (операция (1)), затем несколько раз полагать t(y = \A\A-a-EP} (операции (3) и (4)), проверять, справедливо ли равенство i = n (операция (2)), и, если нет, увеличивать / на 1 (операция (1)). Общее число выполняемых при этом операций равно 0(0-

Далее, чтобы вычислить tf., нужно выполнить следующие Шаги:

(1) Положить

(2) Проверить, справедливо ли равенство / = Если нет, увеличить / на 1 и выполнить line (/) -процедуру, которая будет определена ниже.

(3) Повторять шаг (2), пока не будет у = д.



Не считая операций, требующихся для Ипе(/), эта подпрограмма тратит 2п - 2 элементарных операций. Общее число элементарных операций, требующихся алгоритму 4.3, равно, та-

ким образом, 0(aO+SM/), где /(/) -число элементарных опе-

раций, используемых процедурой line (/). Мы покажем, что l(i) = 0{ti), и потому общее число операций равно O(rt).

Процедура line (/) вычисляет все элементы tij, для которых 1/<п - /. Она включает процедуру вычисления описанную в примере 4.8, и определяется так (предполагаем, что вначале все tj имеют значение 0):

(1) Положить ( = 1 и ] =n - i+\.

(2) Положить k=\.

(3) Положить k = i + k и r - j-k.

(4) Обследовать и twr- Положить

(5) Увеличить /г на 1.

(6) Если /, перейти к шагу (7). Иначе перейти к шагу (3).

(7) Если остановиться. Иначе сделать шаг (8).

(8) Увеличить ( на 1 и перейти к шагу (2).

Заметим, что написанная программа содержит внутренний цикл (3) -(6) и внешний цикл (2) -(8). Внутренний цикл выполняется /-1 раз (для значений переменной /г от 1 до /-1) всегда, когда программа попадает в него. В конце цикла tj принимает значение, предписываемое алгоритмом 4.3. Сам цикл состоит из семи элементарных операций, так что каждый раз, когда программа попадает в него, она затрачивает О (/) элементарных операций.

Во внепший цикл программа входит п - /+1 раз и каждый раз при этом тратится О (/) элементарных операций. Так как /rt, каждое вычисление процедуры line (/) требует О(я) операций.

Так как line(/) вычисляется п раз, то общее число элементарных операций, выполняемых алгоритмом, равно, таким образом, О [п)- □

Теперь опишем, как по таблице разбора найти левый разбор. Метод излагается в виде алгоритма 4.4.

Алгоритм 4.4, Нахождение левого разбора по таблице разбора.

Вход. КС-грамматика G(N,2,P, S) в нормальной форме Хомского с правилами, занумерованными от 1 до р, входная

цепочка w=aa...a и таблица разбора Г, построенная для цепочки W алгоритмом 4.3.

Выход. Левый разбор цепочки w или сигнал „ошибка".

Метод. Опишем рекурсивную процедуру gen(i, /, А), порождающую левый разбор, соответствующий выводу Л г+аа....

(1) Если /1 и А-а - правило из Рсномеромт, выдать номер т.

(2) Пусть /> 1 и k - наименьшее из целых чисел от 1 до j - для которых существуют Bi, С i.., j-k и правило /ВС из Р с номером, скажем, т. (Может оказаться несколько таких правил. Произвольно выберем одно из них, например с наименьшим т.) Тогда выдать номер т и выполнить gen(i, k, В), а затем gen (г + А:, j-k. С).

Алгоритм 4.4 заключается в выполнении gen (1, п, S) при условии, что 5€1„. Если St,j, выдать сигнал „ошибка". □

Расширим понятие элементарной операции, включив в него запись номера правила. Тогда можно доказать следующий результат.

Теорема 4.8. Для входной цепочки ... алгоритм 4.4 окончит работу, выдав некоторый левый разбор этой цепочки, если он существует. Число элементарных шагов, затрачиваемых алго-ршпмом 4.4, равно О (п).

Доказательство. Индукция по порядку вызовов процедуры gen показывает, что если вызывается gen (/, /, Л), то Л tij. Отсюда легко вывести, что алгоритм 4.4 дает левый разбор.

Чтобы показать, что алгоритм 4.4 заканчивает работу за время О (я-), докажем индукцией по /, что для всех / вызов gen(/, /, Л) расходует не более с/ шагов, где с - некоторая аонстанта. Базис, / = 1, тривиален, так как шаг (1) алгоритма 4.4 Использует одну элементарную операцию.

Для доказательства шага индукции заметим, что вызов gen(i, /, Л) для /> 1 приводит к выполнению шага (2). Читатель может проверить, что найдется такая константа с, что, не Считая вызовов, шаг (2) расходует не более cj элементарных операций. Если вызываются gen (г, k. В) и gen(/ + ft, /-k, С), то по предположению индукции на вызов gen (/, /, Л) тратится Не более ck -{-сЦ-ку -\-cJ шагов. Приведем это выражение к виду c/{j + 2k - 2kj)+cj. Так как 1 <ft < / и />2, то 2ft2 -2/г/2 - 2/-/. Таким образом, если в предположении индукции взять Ci = C2, получим c-k+ c{j~ky-\ cJ-cj. Поскольку мы вправе это сделать, теорема доказана. □





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 [58] 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0018