Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 61
Текст из файла (страница 61)
е, таблица с ячейкой для л, на которую указывает элемент таблицы расстановки для !), будет иметь в качестве свойства для ! текущее объявление идентификатора л. Таким образом, решить, вещественный ли или целый идентификатор, можно сразу же, как только ои обнаружен во входном потоке. 10.2.9. Найдите выход алгоритма 10.3 и окон !ательвое дерево придя~пол! множестве объектов [он ..,, ан) н следующей последовательности команд, Предположите, что в случае равенства размеров корень лля Аг становится потомком корня для А, при л<Ь слить(АИ АР А,) слить(АН А,, 4,) слить(А,, А„А,) слить(АН А„А,,) слить (А„А„АР) слить (А„АА Аг) найти (а,) слить(АИ А„А,) слить(А;, Аи. 4л) найти (а,) слить (А „А„А л) найти (пл) найти (л,) 323 1О ОРГЛИИЗДЦНЯ ННФОРМДЦИИ ""10.2.10.
Предположим, что алгоритм !О.б модифицирован так, что при выполнении слияний каждый корень может стать потомком другого. Покажите, что временная сложность такого алгоритма не лучше 0 (л !ой л). Ошкрыттште проблемы 10.2.11. Действительно ли алгоритм !0.5, как зто утверждается в нашей книге, имеет сложность 0(лб(л)), илн его сложность равна 0 (я), илн, вовможно, лежит где-то межд) этими величинами? 10.2.12. Составляет ли вреыеппая сложность модифицированного алгорвтма из упр. !0.2.!О аеличиву 0(л !ой л)? )Уробтлелта с?ля исслед1твпния 10.2.13.
Исследуйте или охарактеризуйте разновидности свойств идентификаторов, которые можно правильно обработать грамматиками снойств. Замечания по литературе Грвмметекв свойств висрвмс быш оврелелмнн Цтлривом и джонсом )1909!. В их работе выжив изйтн отеетм в увр. 1026 н 10.2.7 Лтетол реелизвции трвммвтии свойств ве в 1о21од л обсужделсн Стиоизон и Розенкранцем !1969! Насколько нзм известно, ниервтзе алгоритм 10 6 цредлоткилн Моррис и Мзк Нлрой, но они не овубвиковлли его Лнзлиз влторитмз нровсдец Хоикрофшм е Ульмзиом (И72! Увр Ю2.Ю взвто у Фишера !!972!.
П оптимиздция койА Одной из самых трудных и непонятных проблем, возникающих при построении компнтшторов, является генерация „хорошего" объекююго кода. Два наиболее широко распространенных крятсрия, по которым определяют качество программы, заключаются в оценке времени сс выполнения и размера. К сожалению, для данной конкретной программы, вообще говора, невозможно установить время выполнения самой быстрой зквивалентпой программы или длвну самой короткой эквивалентной програм.
мы. Как уже указывалось в гл. 1, если программа имеет циклы, мы выиуждсны довольствоваться только улу ппеннем кода, а не его истинной оптимизацией. Большинство алгоритмов улучшения кода лтожпо рассматривать как приложение различных преобразований к некоторому промежуточному представлению исходной программы с целью привести промежуточную программу к форме, яз которой можно получить более аффективный объектный код.
Эти преобразования по улучшению кода могут применяться в любой точке процесса компиляции. Один из широко распространенных методов заключается в применении этих преобразований к программе на промежуточном языке, появляющейся после синтаксического анализа, но перед генерацией кода. Преобразования по улучцтению кода можно разделить на машинно-независимые н машинно-зависимые. Првмером машин. но-независимой оптимизации может служить удаление из программы бесполезных операторов, т.
е. таких, поторые никаким образом не влняктт нз выход программы '). Такие машиннонезависимые преобразования были бы полезны во всех компиляторах. С помоцдью машинво-зависимых преобразований можно попытаться привести програыму к форме, в которой вюгут ска') Пыкольку обычно текие оисрзтарм иедолжн~лцо ятьс вире римме, весьлв нероясно, что в ератрзмме ошибка, и потому комиилзтору с.тсдоввло бм ьнформироввть иользоиетели о бесволезиасти онершорв.
327 гл н аптнмшззння 1гадз заться преимущества, связанные с машиннымн командами спениалыюга вида. Как следствие этого машинно-завпснмые преобразования грудка охарактеризовать в обн1ем аале, н потому мы их рассматривать не будем. В настоящей главе мы изучим различные машинно-независимые преобразования, применимые к промежуточной программе, появляющейся виугрн компилягора после сннтаисичсского анализа, но перед генерапией када.
Начнем с того, чта покажем, как гснсрировать оптимальный кад для простата, иа важного класса линейных программ. Затеи расширим этот класс, включав в программы Никлы, и исследуем некоторые методы улучшения када, которые можно применить к этим програымач. 11.1. ОПТИМИЗАЦИЯ ЛИНЕЙНОГО УЧАСТКА Рассмотрим сначала схему программы, представляю~пей со. бой последовательность операторов присваивания, каждый из которых имеет внд А ('(В,, ..., В,), где А и Вн, В,— скалярные переменные, а 1 — функния ат г переменных для некоторгн о г.
Д.тя этого ограниченного класса г~рограмьг ыы разработаем множество преобразований н покажем, как испольаовать их для нахождения программы, оптимальной относительно некоторой опенки. Поскольку действительная опенка программы зависит о~ природы ыашинного кода, который в конечном итоге будет выработан, мы рассмотрим, какие части пропедуры оптимизации машинно-пезавнсамы в как заввсят оставшиеся от реально выбранной машины. 11.1.1, Модель линейного участив Начнем с определенна блока. Блок моделирует часть про- граммы на промежуточноч языке, которая содержит только операторы присваивания.
Определение. Пусть Х вЂ счетн множества имен переменных, а 0 в конечное множество операций. Предположим, что кал дая операиия О Е ГЗ имеет известное фикгирояанное количество апе. рандов Предположим также, что В и Х не псресекаются. Оператором называется непа ~ха аида А ОВ,...В, где А, Вн ..., В,— переменные из 2, а Π— зто г-местная опе- рания из Еь Будем говорить, что оператор осуществляет лри- соииваиие перемеаной А и сгмлагтсл на В„ ..., В,. Блок хг †э тройка (Р, Г, (7), где (!) Р— список оператороа 5В 5;,...; 5„(п~)0), шь аптнмнззння линейноГО Участка (2) à — множество ахадннх переменных, (3) (7 — множество выходных переменных.
1зудем предполагать, что если оператор 5 ссылается на Л, то либо А †входн переменная, либо осуществлено присваи- ванве ей значения некоторым оператором до 5 (т. е. не- которым оператором 5„ 1 < 1), Таким образом, внутри блока все переменные, на которые ссылаются, к этому моменту опре- делены яибо внутренним образом как переменные, которым присвоены значения, либо внешним как входные переменные. Аналогично будем предполагать, что каждая выходная перемен- ная либо является входной переменной, либо ей присвоено значение некоторым оператором.
Типнчныы можно считать оператор Л вЂ” + ВС, когорый есть нг что иное, как префикспая запись более привычного опера- тора присваивания Л . В 1 С. Если операгор осуществляет прнсванвание переменной А, то с этим присваиванием можно связать некоторое „значение". Последнее представляет собой формулу для А в терминах (неизвестных) первоначальных зна. чеиий входных перемепнЫх. Эту формулу можно записать как прафнксипе выражение, включающее входные переменные н опе- рашш. Начиная отсюда, будем предполагать, что входные перемен- ные имеют неизвестные зна ~ения и их надо рассматривать как алгебраические неизвестные. К роме того, значения операппй и множества, на которых они определены, не конкретизированы, так что в качестве значения мы можем рассматривать лишь форм) лу, а не некоторую вели ~ину.
Определение. Пусть (Р, Г, (7) — блок, Р =5,;...;5„. Опре. делим значение о,(А) переменной А непосредственна после мо- мента времени (, 0 ( ( -:и, как следующее префиксное выра- жение: (1) Если Л Е Г, то о,(А] =А. (2) Если оператором 5, является Л ОВ,...В„, то (а) з,(А).
Оаг,(В.) ог-ь(В.) (б) о,(С)=а,,(С) для всех СННА, при условии что о,, (С) определено. (3) Для всех А Е 2, если о,(А) не определено по (1) илн (2), то оио не определена. Отметим, что поскольк) у каждой операции известное число операндов, каждое вырвжеиие, нмегощее значение, либо является одиночным символом из 2, либо допускает единственное пред.
ставление в виде ОЕ,... Е„ где 0 †э г-местная операция, а Е„ ..., Е, -выражения, имеющие значения.(См. упр.3.1.17 ) зхэ ГЛ. Ц ОПТИМИЗЧЦНЯ КОДЛ ил. Оптимизлция лицзяного ьчщсткл Зкичгкием р(чй) блока 33=(Р, 1, У) называется множество (р„(А)(А Е)г, и — число операторов в Р) Два блока считаются (шолалогичлскк) зкзизаленшнмжи (=), если они имеют одно и то же значение.
Отметин, что цепочки, образуюцгие префиксные выражения, равны тогда и только тогда, когда оии тождественны, Таким образом, пока мы пе будечч предполагать никаких алгебраических тождеств. В равд. 11,1.б мы изучим эквивалентность блоков относительно некоторых алгебраическик заковав. Пример 11.1. Пусть 1=(А, В), (У=(Р, 6) и Р состоит из ояераторов') Т вЂ” А -1-В В А — В Т ТьТ 5 — Вэ5 Р ТА В 6 Т вЂ” В Сначала р,(А)=А и о,(В)=В.
После первого оператора вг(Т)=А-(-В (в префиксной записи а,(Т)= 4-АВ), а,(А)=А и р, (В) =В. После второго оператора оч(5) = А — В, з значения остальных переменных прежние. После третьего оператора р„(7) — — (А+В)ч(А-,'-В). Последние три оператора приводят к следующии значениям (остальные значения переносятся с предыдущего шага): ч'а (В) = ('1 — В) «(А — В) Оь(Р). (1-1-В)ч(4 ЕВ)-1-(А — В)«(А — В) оч (6) = (А 4- В) л (А -1- В1 — (А — В) э (А — В) Поскольку р,(Р) = О,(Р), значением блока будет ((А+В)э(А-1-В)+(А — В) (А — В), (А -1-В) (А -;- В) — (А — В) (А — В)) ') Напомним, что иы не учитываем никаких алгебраических законов.
Если применить обычные законы алгебры, то можно было бы записать Р=-2(А'-1-В") и 6= 4АВ. ') При изабражеэлл списка алерлтарал ин часто лальлуемсл аереладам эл лазу~а страду амчста тачки с злалтаэ з ллчлсглл рллдчл талл между алчратарлил. В примерах длл биалримх алерлцлл им будем улшрлблять ллфиксную запись. ч) Б лрчфилслаа злалси члачеала блаха галала (-1-ч -(-АН-( АВ ч — АВ, — АВ, — ч -гА —,АВ * — АН вЂ” АН) 330 Во избежание излишней сложности мы не будем ва этот раз рассматривать операторы, включающие структурированные переменные (массивы и т, д.). Один из путей обработки массивов заключается в следующем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
