Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 74
Текст из файла (страница 74)
Достаточность. Зта часть состоит в доказательстве утверждения (4.2.1) если 5=>'уАЬ, у=>'а, ... ао Л вЂ” О4) принадлежит Р и м =>*а;„... а,, то [А- а 11» ] включается в список 11 Утверждение (4.2.1) надо доказать для всевозможных значений входящих в него параметров. Каждый набор параметров состоит из цепочек а, Ь, у и 6, нетермипала Л и чисел >' и 1, так как 5 и а, ... а„фиксированы. Обозначим такой набор [и, р', у, 6, А, >', 1], Заключение, которое нужно получить для этого набора, состоит в том, что [А — а (1, 1] включается в 1;.
Заметим, что в этом утверждении у и Ь пе фигурируют явно. Введем понятие ранга набора параметров и проведем доказательство индукцией по рангу. Ранг набора 7 [>х, р, у, Ь, А> >, 1] вычисляется следующим образом: Пусть т (7) — длина кратчайшего вывода 5=>*уАЬ, т, (7)— длина кратчайшего вывода у~'а> ...
а>, т,(7) — длина кратчайшего вывода а=о'а> > ... а,. Тогда ранг набора,7 равен т, (7) + 2 [/+ т> (7) + т> (7)]. Теперь докажем (4.2.1). Если ранг набора Я =- [а, (1, у, 6, А, >, 1] равен О, то т, (2)--т,(7) — т,(7) =1'=О. Отсюда и=-у= 6 — с и А=5. Тогда нУжно показать, что [5 1т, О] входит в 1,. Однако это сразу следует из правила (1), так как правило 5 †.[) должно принадлежать Р. Для доказательства шага индукции предположим, что набор параметров 7 для утверждения (4.2.1) имеет ранг Г > О и (4.2.1) верно для наборов с меньшими рангами. Рассмотрим отдельно три случая, связанные с тем, что а может оканчиваться терминалом, нетерминалом и быть пустой цепочкой.
Случай 1: >х -- >Б'а для некоторого а Е Х. Так как а =>'а;„...а,, то а — а,. Рассмотрим набор,7' — [а', аф, у, 6, А, >, 1 — 1]. Так как А — и'йт[1 принадлежит Р, то 7' служйт набором параметров для (4.2.!) и его ранг, как легко видеть, равен à — 2. Отсюда следует, что [А — а' а>6, >] входит в 1,. По правилу (4) ситуация [А и р, >] будет помещена в 1Р Случай 2: а=-и'В для некоторого ВЕ)з.
Существует такое число >(Й(1, что с>'=>*а», ... аА и В=>" а„„... а,.Исследуя набор,7'.— [и', В1>, у, 6, А, >, й] меньшего ранга, заключаем, по [А а' В(7, >'] входит в 1А. Пусть В=О>1 — первый шаг в кратчайшем выводе В=>" а„,, ... а,. Возьмем набор 7"=-[>), г, уа', 1ЗЬ, В, й,)(. Так как 5=>'уАд=>уа'Врб, то т,(7")(т>(7)+1. Пусть и,— минимальное число шагов вывода а'=>" а;„... аА и п,--минимальное число шагов вывода В~*аА >...
а,. Тогда т,(7)==н>+н,. Так как В=э>т)=>*аА,... иэч то тя(7")=н„— 1. Легко видеть, что т,(7")=-т>(7)+п,. Следовательно, т>(7")+ т,(з")=ТБ(7)+н>-) п,— 1=Т,(7)+т,(7) —.1. Таким образом, т>(7")+2[/+т,(0")+т„(7")] меньше Г. По предположению индукции для 7" заключаем, что [ — т) °, й] входит в 1тч и так как [А- >х' В[), >] входит в 1„, то по правилу (2) или (5) [А — а 6, 1] включается в 1Р Случай ск >Б=с.
В этом случае можно считать, что >'=1 и т> (Э) = О. Так как Г > О, то длина вывода 5=>'уА6 больше нузя. Если бы оиа равнялась нулю, то было бы т,(7) = О, а тогда у=с, так что т,(7)=">'=-О. Поскольку в этом случае, как Уже отмечалось, > =1 и т,(7) =-О, то было бы Г=О. Итак, можно найти ВЕН и такие цепочки у', у", Ь' и 6" из ЛИХ)', что 5=>'1'ВЬ'=>у'у"Аб"6', где В- у"АЬ" принадлежит Р, у=у'у", 6=6"Ь' и у'Вб' — результат предпоследнего шага кратчайшего вывода 5 =>'уАЬ.
Возьлтем набор б' — [у", ЛЬ", У, 6', В, )г, 1], где й — такое число, что у'=>" а, ... аА и у'>* ОА+,, а, Пусть наименьшие длины указанных выводов равны 363 ГЛ, 4. ОВЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА СООтВЕтСтВЕННО П, И и,. ТОГда Т,(З') =ли„тг(О') -=Пг И Тл(О) = п, + и,. Мы уже убеднлнсь, что т, (У) =-О, а В, у' и 6' выбраны так, что тг(д') =-т, (д) — 1. Поэтому ранг набора д' равен г — 1.
Таким образом, [В- у" Аб", й| входит в 1,. По правилу (5) или (3) ситуация [А — (1, /1 будет включена в 1/. (л Заметим, что в качестве частного случая теоремы 4.9 мы получаем, что [5 — а, 01 входит в /л тогда и только тогда, когда 5 — а принадлежит Р и а =>*а,... а„, т. е. а,... а„принадлежит 1. (6) тогда-и только тогда, когда [5 — а, 01 для некоторой цепочки а входит в 1„.
Теперь исследуем вопрос о времени работы алгоритма 4.5. Читателю предоставляем доказать„ что вообще для разбора любой цепочки длины п в произвольной заданнон грамматике достаточно 0(гг') подходящим образом определенных элементарных шагов. Мы докажем сейчас, что если грамматика однозначная, то достаточно 0(п') шагов. Лемма 4.6. Пусть 6 = ()х), Х, Р, 5) — однозначная КС-грамматика и а,, ал — иепочка из Хл.
Тогда при вьтолнении алгоритма 4.5 мы пытаемся включить [А — сг !3, 11 в 1, не более одного раза, если гг~е. Доказательство, Ситуацию [А — а !1, г'1 можно включить в 1/ только на шагах (2), (4), или (5). Если она включается на шаге (4), то последний символ цепочки а — терминал, а если на пгагах (2) или (5), то — нетерминал. В первом случае результат очевиден. Во втором случае допустим, что [А а'В 6, 11 включается в 1и когда рассматриваются две различные ситуации [В- у °, й1 и [ — 6, 11. Тогда ситуация [А а' ВР, 1[должна оказаться одновременно в 1 и в 1, (возможно й — — 1). Допустим, что /г~/. По теореме 4.9 существуют такие О„ О,„О и О, что 5=>'О АО =ггО а'В[10 => а„...
а„и 5=Ф О АО =м О„а'Вэр04=~'аг... а„. Но в первом выводе Ога'=гулаг... а, а во втором Ола' =>'а,... а,. Тогда для цепочки а,... а„существуют два разных дерева вывода, в которых аи„,... а, вьшодится из а'В двумя разными способами. Пусть й =1. Тогда должно быть уча 6. Снова для цепочки а,... ал легко найти два различных дерева вывода. Детали доказательства оставляем в качестве упражнения. Д Изучим теперь сложность алгоритма 4.5. Определение „элементарной операции" этого алгоритма предоставляем читателю. Решающий момент в доказательстве того, что алгоритм 4.5 имеет квадратичную временную сложность, состоит не в том, как определить „элементарные операции", — подойдет любое разумное множество основных операций, применяемых при обработке списков, Главное здесь связано с организацией „бухгалтерии" для 4Л.
ТАЕЛИЧНЫЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА учета всех затрат времени. Грамматика 6 предполагается фиксированной, так что обычные операции с ее прав11лами и символами можно считать элементарными. Как и в предыдущем разделе, вопрос о зависимости нрсмени от „объема" грамматики оставляем в качестве упражнения. Шаг (1) для /„ можно, очевидно, проделать за фиксированное число элементарных операций. Шаг (3) для /, и шаг (5) в общем случае можно проделать за ограниченное число элементарпых операций каждый раз, когда рассматривается очередная ситуация, при условии, что мы следим за ситуапиями [А — а Р, 11, уже включенными в 1. Так как грамматика 6 фиксирована, эту информацию можно хранить для каждого / в конечной таблице.
Тогда ист необходимости просматривать весь список 1, чтобы узнать, находятся ли уже в нем эти ситуации. Иа шагах (2), (4) и (5) включение ситуаций в 1 произойдет в том случае, если удастся отыскать в некотором списке /г (г' /) все ситуации, в которых нужный символ расположен справа от точки, причем этот символ — терминальный на шаге (4) и нетерминальный на шагах (2) и (5). Таким образом„для каждой ситуации из списка мы должны устроить две связи. Перван из них указывает следующую ситуацию списка.
Эта связь позволяет по очереди рассматривать каждую ситуацию, Вторая указывает следующую ситуацию с тем же символом, расположенным справа от точкп. Эта связь позволяет эффекгивно просматривать список на шагах (2), (4) и (5). Общая стратегия заключается в том, чтобы при включении новых ситуаций каждую ситуацию из списка рассматривать только один раз.
Однако сразу после включения в /. ситуации вада [А- а В(), 11 мы справляемся в конечной таблице, заготовленной для 1,, есть ли в 1, ситуации вида [В- у., /1. Если да, включаем в 1, также и [А — аВ р, 1). Заметим, что в качестве первых компонент может появиться фиксированное число цепочек, скажем й. Поэтому в 1 может / появиться пе более й(1+!) ситуаций. Если мы покажем, что алгоритм 4.5 расходует иа каждую ситуацию из списка фиксиРовангше количество времени, скажем с, то этим будет доказано, что общие затраты времени составлшот 0(п'), так как л чл . 1 с '„ /г(/+1) = — сй(п —, ,:1) (и-1-2)с:си' /=о для некоторой константы с'. „Бухгалтерский трюкл состоит в следующем.
Время расходуется на ситуацию при разных обстоятельствах — и тогда, когда она на Рассматривается, и тогда, когда опа включается в список. Максимальное количество затрачиваемого времени в обоих слу- 366 ГЛ. 4, ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА чаях фиксировано.
Фиксированное время расходуется также на список в целом. Предоставляем читателю показать, что 1, можно построить за фиксированное время. Мы рассмотрим ситуации в списке 1, для 1 > О. На шаге (4) исследуется а, и предыдущий список Для каждой ситуации из 1,, с символом а, расположенным справа от точки, в 1 включается некоторая ситуация.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
