Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 72
Текст из файла (страница 72)
3, > — и) ' ' ' ((ь Т-з, 14- 1 — з, 1) Тогда, если ВЕГ4А И СЕГГ,„Т „ДЛя некотОрОгО 1(й <1 и А- ВСТР, добавляем А к 1,, Это значит, что мы одновременно движемся вверх по 1-му столбцу и вниз по диагонали, спускающейся вправо от ячейки Гзм обозревая нетерминалы, расположенныс в проходимых таким образом парах ячеек.
Так каь Я Е з,„то абааб ~ Е (6). () Теорема 4.6. Если алгоритм 4.3 примгняетая к гральиатикг 6 в норлгальной форлгг Хомского и входной цепочке а,...а„, то по окончании его работы А принадлеж44т Г,Т тогда и только тогда, когда А ~" аг...а„;,. До к а з а тел ь ство. Доказательство проводится нндукцисй по 4; мы оставляем его в качестве упражнения. Наиболее трудный шаг содержится в доказательстве достаточности условия; здесь нужно заметить, что если 1 1 и А =>+ а;...а, „- „то найдутся такис нстерминалы В и С н число й, что А — ВСЕ( Р, В~+аг...а,»А, и С=->+аз»л...а4„т, () Покажем, что алгоритм 4.3 можно выполнить на машине с произвольным доступом к памяти за и' подходящим образом определенных элементарных операций. Предположим, что в ва.
шем распоряжении несколько целых переменных, одна из кото- 354 ых — длина и входной цепочки. Элементарной ОГ4грацигй будем считать каждую из следующих: (1) Прнсваивание переменной значения другой переменной или константы, а также суммы нли разности значений двух переменных или констант, (2) проверка Равенства значений двух переменных, (3) обследование и!или изменение значения переменной (В, ЕСЛИ 4 И 1 — текуЩие значения двух целых переменных нли констант, (4) обследование 4-го входного символа ан если 4 †значен некоторой переменной. Заметим, что операция (3) имеет ограниченный объем, если грамматика заранее известна.
Если грамматика становится более сложной, то объем памяти, необходимой для храпения переменной 1Ы, и время, необходимое для ее обследования, возрастают, если рассматривать разумные шаги более элементарной природы. Однако здесь мы интересуемся только зависимостью времени от длины входной цепочки.
Читателю предоставляется самому определить более элементарные шаги, которыми можно заменить (3), и найти функциональную зависимость времени их вычисления от числа нетсрминалов и правил грамматики. Соглашение. Запись 1(п) -.. О (д(Г4)) означает, что существует такая константа й, что 1(п) ч .йд(п) для всех п) 1. Таким образом, когда мы говорим, что алгоритм 4.3 выполняет свао работу за время 0(п'), мы подразумеваем, что существует такая константа й, что для входной цепочки длины и тратится не более нпз элементарных операпий, Теорема 4.7. Алгоритму 4.3 для вычисления всех Г, требуется 0(Г4з) элементарных операций указанного вьииг снипа. Показательство.
Чтобы вычислить 44, для всех 4', надо положить Г .=1 (операция (1)), затем несколько раз полагать Гп =- (А ! А — а; Е Р) (операции (3) и (4)), проверять, справедливо ли равенство 1=-и (операция (2)), и, если нет, увеличивать 4 на 1 (операция (1)). Общее число выполняемых при этом операций равно 0(п). Лалее, чтобы вычислить ГГт, нужно выполнить следующие шаги: (1) Положить 1=1, (2) Проверить, справедливо ли равенство (=и. Если нет, у~сличить 1 на 1 и выполнить 11пе(1) — процедуру, которая бу- дет определена ниже. (3) Повторять шаг (2), пока не будет 1 =- и.
12» 355 ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.2. ТАБЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Не считая операций, требующихся для Впе(!), эта подпрограмма тратит 2и — 2 элементарных операций. Общее число элементарных операций, требующихся алгоритму 4.3, равно, таким образом, 0(и)+ ~4 !(!), где !(!) — число элементарных опег=г раций, используемых процедурой 14пе ()).
Мы покажем, что 1(1) =О(и'), и потому общее число операций равно 0(и'). процедура !1пе(1) вычисляет все элементы (,, для которых 14-.1 < и — !. Она включает процедуру вычисления Г,, описанную в примере 4.8, и определяется так (предполагаем, что вначале все (;т имеют значение Я); (!) Положить 4=-1 и ! =и — !+1.
(2) Положить й=.1. (3» Положить й' = 4+ й и !" = ! — й. (4) Обследовать Гг» и Г».;-. Положить Гы — — (70(А )А — ВСТР, ВЕ(т, СЕ !»Е) (5) Увеличить й на !. (6) Если й=-), перейти к шагу (7). Иначе перейти к шагу (3). (7) Если !.= !', Остановиться. Иначе сделать шаг (8). (8) Увеличить 4 на 1 и перейти к шагу (2). Заметим, что написанная программа содержит внутренний цикл (3) — (6) и внешний цикл (2) — (8).
Внутренний цикл выполняется ! — ! раз (для значений переменной й от 1 до ! — !) всегда, когда программа попадает в него. В конце цикла Г;7 принимает значение, предписываемое алгоритмом 4.3. Сам цикл состоит из семи элементарных операций, так что каждый раз, когда программа попадает в него, она затрачивает 0(1» элементарных операций. Во вненгний цикл программа входит и — !+1 раз и каждый раз при этом тратится 0(!) элементарных операций. Так как !'~и, каждое вычисление процедуры 1!пе(!) требует 0(и') операций.
Так как Впе(!) вычисляется и раз, то общее число элементарных операций, выполняемых алгоритмом, равно, таким образом, 0(и'). (! Теперь опишем, как по таблице разбора найти левый разбор. Метод излагается в ниде алгоритма 4.4. Алгоритм 4 4. Нахождение левого разбора по таблице разбора. Вход. КС-грамматика 6=((ч), Х, Р, В) в нормальной форме Хомского с правилами, занумерованными от 1 до р, входная 356 цепочка ш=-а,а,...а„и таблица разбора Т, построенная для цепочки ш алгоритмом 4.3.
Выход. Левый разбор цепочки ш или сигнал „ошибка". Метод. Опишем рекурсивную процедуру йеп(4, /, А», порождающую левый разбор, соответствующий выводу А:>~-'ага, „,... а»4.7-4. (1) Если ) —... 1 н А — а,.— правило нз Р с номеромт, выдать номер т. (2) Пусть ! ) 1 и й — наименьшее из целых чисел от 1 до ! — 1, для которых существугот ВЕ!4», СЕ(,„»» и правило А ВС из Р с номером, скажем, т. (Может оказаться несколько таких правил. Произвольно выберем одно из них, например с наименыпим т.) Тогда выдать номер т и выполнить йеп(4', й, В), а затем йеп(!+й, ! — й, С). Алгоритм 4.4 заключается в выполнении реп (1, и, Я) при условии, что Я Е („,. Если Я( (и„выдать сигнал „ошибка".
! ! Расширим понятие элементарной операции, включив в него запись номера правила. Тогда можно доказать следующий результат. Теорема 4.8. Для входной цепочки а,... а„алгоршим 4.4 окончит работу, выдав некоторый левый разбор этой цепочки, если он существует. Число элементарных шагов, затрачиваемых алгоритмом 4.4, равно 0(иг). Доказательство. Ипдукция по порядку вызовов процедуры реп показывает, что если вызывается реп(4, 1, А), то АЕ(,, Отсюда легко вывести, что алгоритм 4.4 дает левый разбор. Чтобы показать, что алгоритм 4.4 заканчивает работу за время 0(и'), докажем индукцией по 1, что для всех ! вызов йеп(4', 1, А) расходует не более с,!' шагов, где с, †некотор константа, Базис, ! = 1, тривиален, так как шаг (!) алгоритма 4.4 использует одну элементарную операцию.
Для доказательства шага индукции заметим, что вызов йеп(4, 1, А) для ! > 1 приводит к выполнению шага (2). Читатель может проверить, что найдется такая константа с„что, не считая вызовов, шаг (2) расходует не более сг) элементарных операций. Если вызываются йеп(4, й, В) н реп((-»-й, ! — й, С), то по предположению индукции на вызов йеп(1, 1, А) тратится не более с,йг+с,(! — й)2+с,! шагов. Приведем это выражение к виду с,(!гл-2йг — 2й!)-;с!.
Так как 1 =)г<) и 1~2, то 2И' — 2й/~2 — 2!( — !. Таким образом, если в предположении индукции взять с,=с„получим с,йг-~-с»(! — й)'ц сг!(с,!". По. ~кольку мы вправе это сделать, теорема доказана. 357 ГЛ. Е ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА Пример 4.9. Пусть 6 — грамматика с правилами (1) 5- АЛ (2) 5 — А5 (3) 5 Ь (4) А — 5А (5) А — А5 (6) А — а Пусть щ=аЬааЬ вЂ” входная цепочка. Таблица разбора цепочки приведена в примере 4.8. Так как 561„, то ьпь-5(6). Чтобы найти левый разбор це.
почки аЬааЬ, вызовем процедуру йеп(1, 5, 5). При этом обнаружится, что А принадлежит гн и 1„и существует правило 5 — ЛА, Тогда будет выдано число 1 (помер правила 5- ЛА) и затем вызваны йеп(1, 1, А) и реп(2, 4, А). Вызов реп(1, 1, А) даст правило номер 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
