Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 60

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

Текст из файла (страница 60)

Д о к а за т ель с т в о. Структура, создаваемая алгорнт. мом 10.5, представляет собой набор деревьев. Поэтому никакая вершина не может быть потомком двух различных вершин ранга ). Поскольну в структуре л вершйн, результат вытекае~ непосредственно из леммы 10.4. Следствие. Никакая вершина яг имеет рант, балы,гга )ой„п. С) Определение. При фиксированном числе п объектов определим группы рангов. Будем говорить, что целое ) принадлежит группе 1, тогда и только тогда, когда !ой)Р(л) жг) (ойе)""(л) где 1ойи'(п) =!абел и 1ой,"+и (и) = (ой А' ((ой, (л)). Таким обРазом, !ай!е' — это функция, представляющая собой последовательное применение й раз функции 1ой,. Например, (ойи'(65 536) = 1ой!" (16) = (ой,(4) = 2 Говорят, что ранг г принадлежит гшруяяг раягаг 1, если г принадлежит группе й Поскольку (ой, (Р(!г)) — — 1 и никакая вершина ве имеет ранга, большего!ой, л, заключаем, что никакая вершина не принадлежит группе рангов, балсс высокой, чем 6 (я).

Группы рангов при я =65536 приведены в табл. 10.4. Г ггия«)а.г Регг гере«еи Гругве ре гее о ) 3, 4 б, б..., )б )ш)л )") и а )„) (10 25) Слагаемые в формуле (!0.2,1) образуют геометрическую прогрессию со гнаыенателем О„так что их сумма не превосходит -)еги'ь удвоенного первого члена. Таким образом, у, 2л 2 (л) =- 2пу(ой())(п).

Так как цена с, ограничена сверку величиной у,)ойе))'(л), то с (2л. Поскольку ( могкет меняться только от 1 до 6(я), видим, что вершинам назначена иена в 0(лб(я)) единиц времени. Следовательно, общая стоимость работы алгоритма 10.5 равна 0(л6(л)). С) !) А. А**, д . р е, . г 32) Теперь мы готовы доказать, что временная сложность алгоригма 10.5 рвана 0 (л6 (л)). Теорема 10.3.

Любая лжлгдогитгяьиость а, Гост ояи(ия из 0 (я) команд, гыполяягтгя за гремя 0(лб (л)). До к аз в телес) во. Ясна, что общее нремя выполнения команд слить в а равно 0(я). Длины путей, проходимых каман. дами найти в а, подсчитаем в два этапа. Предположим, чта ири выполнении команды найти мы поднимаемся вверх от вершвны М к першине )У. Если М и Д) принадлежат разным группам рангоя, то увеличим цену команды найти на одну единицу времени. Гели Л) †коре, увеличим цену еще на одну единицу. Поскольку вдоль любого пу)и не более 6(я) различных групп рангов, никакой из команд найти не будет назначена цена, большая, чем 6(л) единиц. Если, с другон стороны, М н й) принадлежат одной группе рангов и 5) ие корень, то вершине М набавим цену на 1 единнпу времени. Отметим, что в агом случае вершина М должна бь)ть перемещена.

По лемме 10.5 ее новый прямой предок имеет болсс высокий ранг, чем предыду)ций прямой прсдок Таким образом, если вершина М принадлежит группе рангов ), то ей можно набавлять цену ие более чем 1ой!Р(я) раз, прежде чем ее прямой предок попадет в более низкую группу рангов. На)иная с этого моыента, пена для М уже больше нс будет меня гься; цена перемещения М будет порождаться выполпеш)ой командой найти, как это описано выше. Ясно,что иена для всех команд найти составляет 0(я6(л)).

Ч )обы найти верхнюю границу общей цены для всех объектов, просумчируем по всем группам рангов максимальную цену для иаждаГ) вершины в группе, умноженную на максимальное )вело вершин в группе, Пусть у) — максимальное пшло вершин в группе рангов 1, а с — пена для всех вершки в гр)ппе 1. Тогда по / лемме 10.6 ГЛ !О ОРГАНИЗАЦИЯ ИИФОРМЛЦИИ упРлжпсния Применим теперь абстрактные результаты к грамматикам свойств. Теорема ! 0.4. Предположим, нто механизм разбора и обработки таблиц, роэработаяный е алгоритмах 10.3 и 10.4, применяется ко оходной цепочке длины п. Предположим гиакже, что число эалросое относительно сеоисте индехси е таблице составляет ее- личину О (и) и элеи запроси относятся только к верхней таблице магазина, для которой индекс обладает не нсйтраяьньсм сеойст. зол '). Тогдп общее время, затраченное ни обробо!пку таблицы на машине с проиээолсным доступом, риека 0(п6[а)).

Доказательство. Заметим прежде всего, что предположения о нашей модели выполняются, а именно, что врсмя, требуемое в алгоритме 10.3 для достижения любой вершины, которую нужно обработать, фиксировано н яе завнснт от п. Заголовков свойств (корней деревьев) можно достичь за фнкснрованное время, поскольку пх конечное чнсло на одну таблицу и они связаны. Индексные ячсйкн (вершины для объектов) непосредственно достижимы либо яз таблицы расстановки, когда нам надо узнать нх свойства (вот почему мы предполагали, что запросы осуществляются только для нндексов верхней таблнцы), лнсю в процессе спуска по списку пересечений.

Теперь достаточно показать, что каждый индекс н ячейку заголовка, которые порождаются, можно смоделировать как объектные вершины, что нх всего 0(л) я что все манипуляпни можяо пыразнть в точности как некоторую последовательность команд слить и найти. Приведем полный список всех возможных порождаемых ячеек. (1) 2л ,Объектов" соответствуют л ячейнам заголовков я и индексным ячейкам, создаваемым в процессе операции переноса (часть 1 алгоритма 10.3). С помощью операции слить можно сделать так, чтобы пвяексная ячейка указывала на ячейку заголовка. (2) Новым индексным ячейнам, порожденным нз шаге (б) исти 2 алгоритма 10.3, соответствует самое большее и объектов.

С помощью подходящей операции слить можно сделать так, чтобы эти ячейка указывали на правнльный корень. Такнм образом, существует не более Зп объектов (л в алгоритме 10.5 означает Зп здесь). Кроьге того, число команд, необходимых для обработка множеств и объектов при „моделировании" алгоритмов 10.3 н !0.4 алгоритмом 10.3, равно 0(п). Уже ') Если речь лет о гипнчном ьспользоеьонн этих сэойстэ (нэярямер, ногль ори сэертке о э л ь гйлмнлтнкс а,ж !э!ельнь эьзть сьойстзь «онирет. нога нлентифнкаторл о), то это оэедяоломенне кежеюя вполне праедоподобным. 322 было отмечено, что для инициализации таблиц после переноса ((1) выше] н для сопоставлеяш! новых индексных я геек с заголовками ](2) выше] достаточно не более Зл команд слить. Кроме того, на шаге (4) части 2 алгоритма 1О.З, когда два ьшожества индексов, обладающих одним и тем же свойством, сливаются, достаточно 0(п) команд слить.

Зто следует из того, что числа различных свойств фиксировано н что можно сделать только и†1 сверток. Из леммы 10.3 вьпекает, что для проверки свойств индексов в спнс! е перссечепнй (шаг (1) части 2 ал горитыа 1 О.З] достаточно 0(и) команд найти. Наконец, по условню теоремы для определения свойств индексов (подразумевается использование в процессе перевода) гребуетсн 0(п) дополнительных команд найти Если разместить все зти команды в порядке, определяе.

мом ааалнзатором и алгоритмом 10.3, получим последователь. ность из 0(п) команд. Настоящая теорема следует, таким абра. зом, нз леммы 1О.З к теоремы 10.3. УПРАЖНЕНИЯ 10.2.1. Пусть 6--КС-грамматика с правилами Е- Е )-Т(ЕЯТ(Т Т (Е)(а где а — ндентифнквтор, ое прсдставлнет сложение с фнксиро. ванной точкой, Я вЂ” сложепне с плавающей точкой. Образуйте нз 6 грачматкку свойств, в которой (!) каждый символ а имеет таблицу с одним не нейтральным элементом, (21 если в вершине и дерева разбора применяется правило Е Е-!-Т, то все а, вершины которых находятся ниже и, обладаю! свойством „используются в сложении с фикснроаанной точкой", (3) если, как и в (2), применяется правило Š— Е~~Т, то все а, находяшаеся ниже и, обладают свойством „используются в сложения с плана!Ощей тачкой'*, (4) осуществляется разбор в соответствви с грамматикой 6, прн этом ведется контроль за тем, чтобы идентификатор, использованный в сложении с плавающей точкой, не использовался затем (выше в дереве разбора) в слаженна с фиксированной точкой.

10.2.2. С помощью грамматики свойств нз примера 10.9 постройте дерево разбора, если опо существует, для каждой из следующих входных цепочек: г!* ГЛ. !Л ОРГАННЗАЦИЯ ИНФОРМАЦИИ УПРЛЖНРНИЯ (а) Ьеб)п дес!аге [1:1) бес1аге [1:1) Ьеб!п а [1;3[ епб (аЬе! Ье91п бес(аге [3:1[ а[3:3] епд до!о [2:4[ епб (б) Ьед(п бес!аге [1.1[ а [1:3[ Ье91п бес1аге [2:![ 9о1о [1;4) епд епб Определение.

Нгдстерипигл резанная гролмотака свойств определяется так же, как граллл~атика свойств, за всключепием того, что (!) значениями функции р являются подмножества множества у, н (2) ве требуется наличия нейтрального свонства. В соответствии с соглашениями этого раздела иы пшпем аг!Тб =>ИХ,ТА... Х„ТР(1, если А Х,... Х„ — некоторос правило вывода, скажеы р, и для каждого г таблица Т(л) принадлежит множеству р (р, Т,(г)...Т„(!)). Отношение =Ь" и порождаемый язык определяются в точности так же, как и в детерминированном случае. *10.2.3, 2(окажите, что для каждой недетсрминироаанной грамматики свойств 6 найдется грамматика свойств 6 (возможно, без нейтрального свойства), порождающая тот же язык, в которой !л является функпиеи.

10.2.4. Покажите, что ести грамиатика 6 из упр. 10.2.3 обладает нсйтральным свойством (т. е. все, кроме конечного числа, целые числа обладают этим свойством в каждой таблице каждого вывода), то 6' — грамматика свойств с нейтральным свойством. 10.2.3. Обобщите алгоритм 10.3 для грамматик нс в нормаль. ной форме Хомского Обобщенный алгоритм должен иметь ту же времеинчю сложностлн что н исходный. 324 *10.2.0.

Изменим определение грамматики свойств, потребо. вав, чтобы ни у какого терминального символа не было полностью нейтральной тзблицы. Если 6 †так грамматика свойств, то пусть !.'(6) = (ал...о„[алТл...а„Т„ к (.(6) для некоторых (не полностью нейтральных) таблиц Ти .., Т„[. Покажите, что ь'(6) мажет не быть КС-языком. Указание: Покажите, что таким способом порождается язык (агьгл'(4 <1<8). "*10.23К Покажите, что для „грань!вгики свойств" 6, модифицированной в упр. 10.2.8, неразрешима проблема пустоты мио. жества !.'(6), даже если входная КС.грамматика для 6 праволнисбная. 10.2.8.

Пусть 6 †входн КС-грамматика из примера 10.9, Предположим, что терминал бес(аге связывает с индексом одно нз двух свойств: либо „обьявлсн как вещественное", либо „объявлен как целое". Определите на 6 такую грамматику свойств, что если реализуется алгоритм 10.3, то самая верхняя таблица в магазине, имеющая конкретный индекг л' с не нейтральным свойством (т.

Характеристики

Список файлов книги