Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 67
Текст из файла (страница 67)
!1.1.23. Докажите лемму 1!.1. 1!.1.24. Докажите лемму 1! 2 П .1.28. Закончите доказательство леммы П .3. 11.1.28. Закончите доказательство леммы !!.4. э!1.!.27. Дайте пример такой оценки С, что Зг~ьз З, влечет С(ЗЕ) щС (З,), но не для каждого блока существует блок, оптимальный относительно С. 11.!.28. Докажите лемму 11,6. 11.1.29. Покажите, что если З,— открытый блом и З,=Р,З,~РЗ„то существует такой блок З, что З,=Р,Зш~,З,. !1.1.30. Докажите лемму 11.7. Указание: Воспользуйтесь упр. 1 1.1.29. *1!.1.31. Предположим, что у нас есть машина с гу регистрами, причем в этих регистрах можно разместить некоторые или все аргументы операции, а также ее результат.
Покажи~с, гжо выходные значения блока можно вычислять на такой машине, ке прибегая к командам запоминания (результаты помещаются в регистры), тогда и только тогда, когда для этого блока существует эквивалентный блом, в нагаром н командах встречается не более У разных имен переменных. *1!.1.32. Покажите, что если к данному блоку З в любом порядке пряменять преобразования Т, и Т„пока не получитси приведенный блок, то результатом будет всегда одиН и тот же блок (с точносгью до перейменовапия). Проблемы д гл иссзедозанил 1!.1.33.
Используя опенку из примера 1!.9 или какую-нибудь другую интересную оценку, постройте быстрый алгоритм нахождения оптимального блока, эквивалентного данному. 1!.1.34. Укажи!е набор алгебраических преобразовавий, полезных при оптимизация широкого класса программ. Разработайте эффективные методы применения зтнх преобразованнй.
зы гл гг оптимиэлция кодл п.х. «эиеизтичзские Вырхгкиния Упралгигния на празралгмирооание 1!.1.36. Используя подходящее представление графов, реализуйте преобразования Т, н Тю описанные в настоя!пем разделе. 1!.1.36. Реализуйте эвристнку, предложенную в примере 1!.9, Аля „оптимизации«кода машины с опиям сумматором. Замечания по литературе Мэтаргээ этага разлапо изкэгэотся з саалютстэяк с рвбатай Аха к Ухь. макк 11972е!. Игхрэая 11968! лээт преобрэзазэккя экэлогкчкмх бкакое, э катерка лапускэются аперэтари А В э счктхются суа!а«тзаккммк кметы змхолкмх переменных. Дэ Бэккэр (Ю7Ц рэссматркээег б.юхк, э каюрых эсо опаркгори имеют зкя А В. Брака 1!972! кэт»эег лэкэйкма азаке с перехалэкк эпэрея.
Ркчэрлсок (19681 доказал, чта аа сушастэует атгарэгиа „уарашсккя** амрэжакнй. коглх поаяэхэкэ сасгаяг ю залах«за !грос!их оаэрх»орое Б ага рэбате можно найти ответ ка уар. 11 1 !9. Кэзнкааа 11970! тэ жэ рхссмктркэаг кхэссм эхгабрякчасккк эаказоэ, ятя которых арабкэиэ экэкээзезтзастк блоков керээрешииэ. Фаайя 11961а) и Брюер 11969! праясгазклк элгорктям икхажнквк абелях палзмражекий з кккейнмх у гасткэх при змаолиеккк апрэлзленкм» акгебракчаакхх ээкакаэ.
Ахо и У.»ьмэк 1!972ж( ксслелозали экзнзклакткаст«блоков са структуркраваккммя переменными, как к з уар. 1!.! 22. !!ската(ые методы, покаэкыа тюк уэр. !1.1.82, содержатся з рабате Ахо к лр. (!972! 11.2. АРИФМЕТИИЕСКИЕ ВЫРАЖЕНИЯ Займемся теперь построением генератора кода, вырабатывающего Аля блоков коц нз языке ассемблера. Входом Аля генератора кода служит блок, состоящий нз послеловательности операгоров присваивания.
Выхояом сл)жнт эквивалентная црограмл!а на языке ассемблера. Нам бы хотелось, чтобы результирующая програмл!а на языке ассемблера была хорошей относительно нскоторои оценки, такой, например, как число кочанл языка ассемблера нли число обращений и памяти. К со!калению, как отмечено в предыдущем разделе, эффективный алгори!м, который лазал бы оптимальный кал иа языке ассемблера, ие и»вестен даже цли простой машины с одним сумматором, такай, как в упр. !1.9.
'1 Аэюрм ке упаяэкэют рэбаг ааэатсккх эзтараэ аа могахэм аглхмээкчкк программ, катя соэетакэмк 7»еаммк внесен экк гитал«кмй эклэх э эту облэсть кэтамэткэкчкк прагрэкмкраэаикк. Б рабагак 7!эараэх (!961! к Бршозк (1962! аркмаэяюгая ошржаркме схемы лхя рашеэкя шлэчэ глобальной экааамяк аккяга Б рэбога Ершов* к яр. (!9661 эта теория используется зкк экааакг аэиягк э АЛЬФА-гркэахя аре Крана тога, а э й гка рабле звался а кя»ка лккейюю у»жгли уаогребзэекаго лля пастраакик аперэторэой схакм цм.
»з«жэ пркисчаккя аерээаачк«к к эакечэзкяи аа ккшрэтуре з разя. 1! 2 — !1,4.— ПРим. лерга. Здесь мы приведем эффективный алгоритм генерации кода на языке ассемблера лля ограниченного иласса блоков, а именно блоиов, представляющих собой одно выражение без одинаковых операндов, ))ля этого класса блоков алгоритм будет генерировать коп на языке ассемблера, оптимальный относительно различных оценок, включая такие, как Алина программы и число используемых сумматоров. Предположение об отсутствии одинаковых операндов, разумеется, не реально, по часто оно бывает хорошим первым приближением, Кроме того, эта прелположеняе весьма удобно, если мы собираемся гекернравать коц, применяя синтаксически управляемый'перевал только с синтезированными атрибутами.
Наконец, проблема генерации оптимального кола Аля выражений с одной только парой олинаковых операндов уже оказывается значительно более сложной. Блок, представляюпгий одно выражение, имеет только олиу выходную переменную. Например, оператор присваивании Р = Х э (Х -1-1 ) можно прелста вить блоком ю = (Р, (Х, У, Х), (Р)), гле Р состоит из )с Х+У р-З«Х Огра!и!ченне, состоящее в том, что выражение не имеет опн. иаковых операндов, эквивалентно требованию, чтобы граф Аля этого выражения был деревом.
Для удобства будем предполагать, что все операпяи бинарные. Зто ограничение несущественно, поскольку реяультаты этого раздела легка обобщаютси на выражения с произвольцылш операциями. Кол на языке ассемблера будем генерировать Аля машины с И с мматорами, гце Аг.Р1. Оцепиой буле1 длина программы иа языке ассемблера (т. е. число команд), Алгоритм впоследствии будет расширен, н во внимание будут приняты коммутативность и ассоциативность операций !1.2А. лйодвпь машины Рассмотрим вычнсяительную машину с Аг ) 1 универсальными сумматорами и команяами четырех типов. Опреяеленне.
Командой языка ассемблера называетси цепочка символов олиого из четырех типов: 1.ОАР М, А БТОЕЕ А, М ОРЕ А,М,В ОРБ А,В,С 262 ГЛ Ц. ОПТНМИЗЛЦИя КОДА В этих командах М вЂ” ячейка памяти, а А, В н С вЂ” имена сумматоров (возможцо, одинаковые). ОР8 — это код бинарной опе. рации 8. Предполагается, что каждой операции 8 соответствует машинная команда типа (3) или (4).
Эти команды выполннют следующие действия: (1) ).ОАО М, А помещает содержимое ячейки памяти М на сумматор А. (2) 3ТОКЕ А, М помещает содержим>>е сумматора А в ячейку памяти М. (3) ОР 0 А, М, В применяет бинарную операцию 0 к содер. жимому сумматора А и ячейки памити М, а результат помещает на сумматор В. (4) ОР 0 А, В, С применяет бинарную операцию 0 к содержимому сумматоров А и В, а результат помещает ца сумматор С.
Если сумматор только один, то множество команд сводится к множеству, приведенному в примере 11.9, ио только теперь команды типа (4) превращаются в ОР 0 А, А, А. Возможности применения этой команды не используются, так что с этой точки зрении множество команд можно считать обобщением команд для одноадресной машины с одним сумматором. Программой ни линце ассемблера (илн для краткости просто программой) будем называть последовательность команд языка ассемблера, Если Р = 1,; 1,; ...; 1н †програм, то можно определить мяат)лиг о>(К) регистра К после команды 1 (здесь под рггистрол> понимается сулгматор илн ячейка памнти]; (1] он(К) равно К, если К вЂ” ячейка памяти, и не определено, если К вЂ” сумматор, (2) если 1 — вто (.ОАО М, А, то о,(А) =о,,(М), (3) если 1,— это БТОКЕ А, М, то о,(М)=о,,(А), (4) если 1,— это ОР 0 А, К, С, то о,(С)=йо,,(А)о,,(К) (напомним, что К может быть сумматором йли ячейкон памяти), (5) если о,(К) не определено по (2) — (4), а ог,(К) опреде.
лоно, то о,(К) = о>,(К]1 а противном случае оиК) йе определено. Таким образом, эинчени» нычислюотся именно так, как н следовало ожидать. Команды ЕОАО и ЗТОКЕ передают значения с одного регистра на другой, оставляя их в исходном регистре. Операции помещают вычисленное значение на сумматор, определяемый третьим аргументом, пе меняя значений остальных регистров. Будем говорить, что программа Р вычисляет выражение а, помещая результат на сумматор А, если после последнего оператора из Р сумматор А имеет значение а. Пример 1!.14. Рассмотрим программу на языке ассемблера с двумя сумматорами А н В, значения которых после каждой хья Таблица П Я »л. лниеметичнския вынлжгиия нн онрнтлнно не ннрехетно х х Х Хм)' Х;У д н (ХЯ-У) ЬОАО Х, А А()П А, У, Л ЬОАЦ Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
