Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 66
Текст из файла (страница 66)
д. (б) Константа ! нейтральна о~носнтельао умножения. (в) Логнческап константа нстнна нейтральна относительно конъюнкции (т. е. а ут истина =ц для всех ц), (г) Логическая константа ложь нейтральна Относительно дкзъюнкцнн (т. е. а ту ложь =п для всех ж). Если а/ †множество алгебраических закопав, будем говорить, что змрлженпс а зкелеахснюно еырпжснню [! оглнаситслана .1 (н ппсать ц= [ О), если О можно преобразовать в )[, применяя только жтгебран ~еские законы нз /.
Пример !1.10. Рассмотрим выражение А»(ВвС)+(Внд) О+А кЕ С помощью ассоциативного законе умножения можно записать А е(В»С) в виде (Л в В) нС. С помощью комчутатнвпого закона '! Олнска иссбхаднма саблюдеть осторожность, сел апсрамдн каннуте. тинная апсреснк — фуекаии с сабам ик к[фе ган пеарннср, /(х)-;-х(у) нажю аынчаться ат Х(у) /(Ю, сслн функння / невест значение у.
Эта срссбрюаеение также нала прянсвять с астаражнастью. Напри. нср, пус х з б . З т — х, л осуществляются с плавающее таская '!Огдх [у-(-х)-!-г малют в рсзухыате дащ О, в ~о авена хак у-(-[х-!-х) дает у, нл Оптнмнздцнк линейнОГО учдсткд умножения можно записать Вн А в виде Л в В. Применяя днстрнбутнвный закон, все выражение можно записать как (А и В] н (С + Р) чп А н Е Наконец, применяя ассоциативный закон к первому слагаемому, затеи днстрнбутввный закон, можно записать выражение как А «! В н (С -[- Р) й- Е] Таким образом, это выражение эквивалентно исходному относительно ассоциативного, коммутативного п дистрибутивного законов умножения и сложения.
В то же время последнее выраже. ние яычнсляется только двумя сложениями н двумя умножениями, в то время как для исходного требовалось пять умноженйй н дпа сложения. С) Определение зквнвалентностт~ отвоснтелыю множества алгебраических занонов А можно распространять н нз блоки. Будем гояорить, что блоки Я, и Я, зкеиепчслщны оглносигпельно а[ (Н ПИСатЬ Я, =.— П/Ят), ЕСЛН дпя ЛЮбОГО аЫражЕНИя ОБО(Я,) существует танце выражение ОБО[Як), что О= — а/О, и обратно.
Каждый алгебраический закон приводит к соответствующим преобразованиям блоков (н графоя). Пример 11.11. Если сложение коммутатнвно, то преобразованне блоков, соответству~опдее этому алгебраическому закону, позволяет заменить в блоке оператор вида Х Л -[- В на оператор Х В+А. Соответствующее преобразование графа позволяет заменить всюду в графе структуру Пример 11, !2, Рассмотрим преобразование блокам, сосозетствующее ассоциативному закону сложения. Последовательность кз двух операторов нида Х-В !.С )х А+Х можно заменить на трн оператора Х В+С Х' А+В Е Х'+С ГЛ !! ООТИЧИЭАЦИЯ КОДА где Х' — новая переменная.
Зто преобразование имеет следую. щий аналог на графах: !!.! Оптимизация линейнОГО учАсткА Блок Я вычисляет выражение У = (А э ( — С) ) «(О е [Е «Р]) Граф для Оь приведен на рис. 11.6. Предположим, жо для В генерируется программа на языке ассемблера, в которой участвуют команды языка ассемблера и Отметим, что мы сохранили оператор Х В -! С, поскольку на переменную Х может быть ссылка из последующего оператора. Однако, если оператор Х В -1- С после этого преобразования становится бесполезным, его можно удалить, применяя уи Если, кроме того, можно удалить Х' А -(- В с помощью Г„ то использованнс ассоциативного занона принесло выгоду. ьт Если даи конечный набор алгебраических законов и соогветству!ощне преобразования блоков, го для нахождении оптнмаль. ного блока, эквивалентного данному, желательно было бы применить их вместе с четырьмя топологическимн преобразованиями, описанными в равд.
!1.1 дй К сожалению, для конкретного набора алгебраических знтонов может ие быть эффективного способа применения этих преобразований для нахождения оптимального блока. Обычный подход к решению этого вопроса заключается в том, что алгебраические преобразования применяют в ограниченном виде, надеясь сделать возможно больше „упрощений" выражений и выработать возможно большее число общих подвыражений. В типичной схеме ййа замевяется ва айб, ести й †коммутативная бинарная операция, а и предшествует )) при некотором лексикографическом упорядочении имен переменных.
Если й— ассоциативная н коммутатнзная бинарная операция, то а,йа,й ... Ои„ можно преобразовать, располагая имена и,, ..., сс„ в лексикографнческом порядке и группируя их слева направо. Закончим этот раздел примерам, иллюстрирующим возможный эффект алгебраических прсобразований блоков. Пример 11.13. Рассмотрим блок Я = [Р, (,(У)), где ! = [А, В, С, О, Р) и Р— последова~ельнос~ь операторов Х, —  — С Хг А Х, Х, ЕэР Х, --0 Х„ у Х, Рзс. !! В. Граф лая ЛГ функция опенки, описанные в примере 11АЕ Если генерировать программу на языке ассемблера прямо нз Ю, то результирую птая программа будет иметь оценку 16.
Предположим теперь, что умножение коммутативно и ассопиативно и мы хотим найти оптимальный блок для уз, эквивалентный В относнтелшю ассоциативного и коммутативного законов умножения. Применим к Я алгебраические преобразования, соответствующие этим двум законам. Мы хотим получить после.
довательность Операторов, в которой промежуточные результаты можно без запоминания немедленно использовать последующими командами. Пре,!полагая, 'по умножение ассоциативно, можно заменить в ГВ два оператора Х, — Е«Р Х,. — 0 . Х! на три оператора Хз — Е«Р Х; 0«Е Х, Х,; Р Теперь оператор Х, Еер бесполезен, и его можно удалить Та* 355 УПРАЖНЕНИЯ Гл. и ОптимизАния КОДА Х,— Ха»Р Х, Х, Х,-Х;.Р х; х,»х,' 1 -Х;.Р Рвс. Ы.г. Граф для ж'. гапэАжиаиия 357 преобразованием Т,. Затем с помощью ассоциативного преобразо.
ваиия можно замени~ь операторы Оператор Х, Х„'» Р теперь бесполезен, и его можно удалить. К этому моменту у нас пять операторов Х,  — С Х, А Х, Гг»Е Х;-Х,»Х; 1 Х;»Р Если применить ассоциативное преобразование еще раз к третьему и четвертому операторам, получим (после исключения бесполезных операторов) блои Х,  — С Х, А»Х, Х;-Ха»П Х; Х;»Е У Х; Р Наконец, если предположитть что умножение хоммутативио, можно переставить операнды второго оператора и получить блок З'.
Х,  — С Х, Х,»А Х," Х, и Х; Х,"»Е У - — Х;»Р Граф для З' приведен на рис. 11.7. Блок З' имеет оценку 7, самую нижнюю возможную оценку для блока, эквивалентного З', В следующем разделе мы изложим систематический способ оптимизации арифметических выражений с использованием ассоииативного и коммутативного алгебраических законов. [3 11.1.1. Пусть З=(Р, (А, В, С), (Р, 6)) — блок, в котором Р состоит из Т А(-В )7 А»Т Е-ВЕС Р 77»Е Т А»А )7 А РВ Е А»)7 аа-ВЧ т (а) Что представляет собой о(З)Р (б) укажиге область действия каждого оператора из Р. (в) Имеет лн Р бесполезные операторыт (г) Преобразование Та применимо к первому н шестому операторам.
Какие значения может принимать 0 (см. определение 0 в равд. 11.1,2) при этом применении Т,р гя. н оптимиздция кодл УПРАЖНЕНИЙ (д) Изобразите граф для .З. (е) Найдите для Я эквиваяентный приведенный блок. ля (ж) Скольио существует зквива.те~гтных приведенных блок в о д я З, пе считая тех, которые получаются переиыеновавиему ( очнее, пусть З' — открытый приведеннын блок, эквивалент- Т ный З. Какова мощность множества )Зп(З" ьь З'~?) (з) Найдите для З эквивалентный блок, оптимальный относительно оценки из примерз 11.9.
11.1.2. Докажите, что преобразования То Т, и Т, сохраняют эквиваленту~ость блокоя (т. е. ЗюгЗ' влечет о(Я) =о(З') для с=1, 3 и 4). 11.1.3. Докажите, что если в преобразовании Т„(равд. ! !.1.2) Р— любой символ, не употребляемый в Р, то о(З) =о(Я'). "1!.!.4. Дайте алгоритм определения множества допустимых имен для (У в преобразовании Т,. 11.!.3. Докажите, что алгоритм, изложенный после примера !!.3, удаляет из блока все бесполезные операторы и вход.
ные переменные. Покажите, что число щагов, требуемых для выполнении алгоритма, линейно зависит от числа операторов блока, *11.1.6. Приведите алгоритм удаления из блока всех лишннд вычислений (преобразование ТВ за время 0(а (ой и), где п — число операторов блока' ). (Это аналогично минимизации автоматов с конечным числом состояний с помощью алгоритма 2.6.) 1!.1.7. Приведите алгоритм определения области действия оператора в блоке. 11.1.8. Определите преобразования графов, аналогичные преобразованиям блоков Т, — Т,.
Упр. 1!.1.9 н 1!.1.10 показывают, что:В С=Ю З влечет ' ИЛ, з, с * 11..9. Покажите, что если З,~ьЗ„то существует такой блок Зь, что З,=Ь,Яс и,Зь=Р,З,, Такйм обРазом, пРеобРазование 7', можно выполннпь одним применением Т, в обратном порядке с последующим применением Тг ь)Ньз п б Ппмн т ьд ззбнзьть, и чксдс зсзнсмвыз диск псрспсппнк бсскппеч а. о у могу прпгпдпгься нь~сды пргзназацян ндфсрнацпз, аналогичные упсмппу1ым з рььд. !0.1. *11.1.10.
Покажите, что если Зь~,З„то существует такой блок З„, что Я,=ьь З, и,Зь=ь,З,. Определение, Множество 5 преобразований блоков называется по!Нь~м, если о(З,) =.О(З,) влече~ З, <ОЗь Множество 5 называется минимально полным, если никакое его собственное подмнсжрстзо нс' пОлнО. Упр, 11.!.9 н П.!.1О показывают, что множество (То Т,) полно Следующие два упражнения показывают, что (Т„Т,) миннмалыю полно. "11.1.11.
!1окажите, что с помощью только преобразований Т„ Т, ьг'Ть нельзя преобразовать блок Я = (Р, (А, В), (С, Р)) в Я' =(Р', (А, В), (С, О)), где Р и Р' таковы; Е А 4 В О Е Е С Ас-В С АУВ О .С С Следовательно, множество (Т„Т„Т,) не полно, и потому (Т,) не полао. "11.1.12. Покажите, что с помощью только преобразований Т„Т, и Т, нельзя преобразонать блок З=(Р, (А, В), (С)) в Я'=(Р', (А, В), (С)), где Р и Р' таковы: С' — А ьВ С А-(-В С А -(-В ззэ 11.1.13.
Приведите алгоритм, выясняющий, эквивалентны ли два данных блока. 1 1. 1.!4. Пусть Р .†. 5,; 5,; ...; 5„ — последовательность операторов присваивании, а 1 — чножество входных переменных. Дайте алгоритм нахождения всех неопределенных [т, е. таких, иа которые есть ссылка до присваивания) переменных из Р. *!1.1.!3. Пусть в качестве операторов бдока, помимо данных выше в определении блока, допускаются также операторы вида гл и. оптимнззпия кода А В, имеющие очевидный смысл.
Найдите для таких блоков полное множество преобразований. **11.1,18, Г!редположим, что сложение коммутативно. Пусть Т, --преобрззованяе, заменяющее оператор А — В+С на А С -, 'В. Покажите, что Т, вместе с Т, и Т, преобразуют два блока друг в друга тогда и только тогда, когда они эквивалентны относвтельно закона коммутативности сложения. **1!.1.17. Предположим, что сложение ассоциативно. Пусть Т; преобразованве, заменяющее операторы Х А+В; У Х+С на Х А 4 В; Х' — В+С; У - А+Х' или операторы Х В-)-С;1' А, Х нз Х В+С')Х' А-1-В;У Х'; С, где Х' новая переменная.
Покажите, что Т„Т, в Т, преобразуют Лва блока друг в друга тогда и только тогда, когда они эквивалентны относительно закпна ассоциативности сложения. !!.!.!8. Что представляет собой преобразование блоков, соответствующее закону дистрибутивноств умножения относительно сложения? Что представляет собой соответствующее преобразование графов? **11.1.19. Покажи~с, что существуют алгебраические законы, для которых рекурсивно неразрешима проблема эквивалентности двух выражеянй. Определение. Говорят, что алгебраический закон сохрантт операнды, если при одном его применении операнды не порождаются и не исчезают. Например, коммутвтивный и ассоциативный законы сохравяют операндЫ, а дистрибутивный нет.
Говорит, что алгебраический занан сохраняет операции, если одно его примвненне не влияет на число операций. Алгебраический закон 08а=а (идемпотентность) не сохраняет операции, а закон (а — ()) — у=а — 16+7) сохраняет. Числа внутренних вершин и листьев н графе, связанном с блоком, сохраняются прн применении к блоку преобразований, соответствующих алгебраическим законам, сохраняющим операции и операнды. *!1.1.20. Покажите, что проблема эквивалентности двух блоков относительно алгебраических законов, сохраняющих ояерации и операнды, разрешима. *11.1.2!. Обобщите теореиу !1.5 так, чтобы можно было оо.
тимизировать блоки, применяя как топологическне преобразования из равд. 11.1.2, так и произвольный набор алгебраических преобразований, сохраняющих операции и операнды. *!1.1.22. Рассмотрим блоки, в которых переменные могут представлять одномерные массивы. Рассмотрим операторы при!Ее упРАЖНЕНИЯ сванвания вида (П А (Х) - В, (2) В А(Х), где А — одномерный массив, в В и Х вЂ” скаляры. Используя тот факт, что А — массив, найдите преобразования, применимые к блокам, в которых каждый оператор имеет внд (1), (2] нлн В ВС, ... С„где В, Со ..,, С,— скалнры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
