Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 72
Текст из файла (страница 72)
Пусть 5 — кисть, содсржагаая корень. Можно считать, что нн в одном из поддеревьев, корнямн ноторых служат прямые поломки вершин из 5, не нарушается ни одно иа указанных выше условий. Любое ассоциативное нли коммутатнвное преобразование должно совершаться целиком внутри одного нз этих поддеревьев или целикол| внутри 5. Если внимателыю присмотреться к шагу (2) процедуры асооппи!е, с|апет ясно, что число младп|нх вершин, возникающих из 5, минималы|о.
По лел|ме 11,12 число стзрших вершин, возникающих из Я, минимально (для гого чтобы это увидеть, надо вновь исследовать результат процедуры асо|ппш!е), и значит, метка корня минимальна. Наконец, видно, что изменения, вносимые алгорнтиом !!.4, всегда можно совершить с помощью ассоциативных и кочмутативных преобразований. !) 11.2.1. Предполагая, что не выполняются никакие алгебраи- ческие ааконы, найдите оптимальную программу иа языке ассемб.
лера при числе сумматоров Н .. 1, 2 и 3 для каждого из сле- дующих выражении|' (а) Л вЂ” В»С вЂ” 0»(Е-|-Е), (б) А + (В+ (С» (О-'- Е)Е- С)» Н)) ' () + 3), (в) (А»(В--С))»(0»(Е»Р)) *-(С+(Н (-)))+(У--(КА-Е))), Вычислите оценку каждой нз найденных программ. !1.2.2. Повторите упр. !1.2.! в предположении, что сложе- ние и умножение коммутативны. 11.2.3. Повторите упр. 11 2.1 в предположении, что сложе- ние и умножение коммутативны н ассоциативны.
1!.2.4. Пусть Š†бинарн выражение с Й операциями. Ка- кое максимальное число скобок .требуется для того, чтобы вы- разить Е без лишних скобок? *11.2,3. Г!усть Т -двоичное синтаксическое дерево, корень которого после прпменеаия алгоритма !1.! имеет метку Н '. 2. Покажите, ч | о Т содержит не менее 3 х 2» -» - -1 внутреаннх вершин. 11.2.6. Пусть Т вЂ” дерево бинарного выражения с Й внутрен- аимн вершинами. Покажите, что Т может содержать не более Й младших вершин.
*11.2.7. Покажите, что при данном Н) 2 дерево с М стар- шими вершинами содержит нс менее 3(М+ !) 2»'-г — ! внутренних вершин. *11,2,8. Какова максимальная оценка двоичного синтансического дерева с Й вершинами? *11Ш.О. Каков максимальный выигрыш в опенке двоичного синтаксического дерева с Й вершинами прн переходе ат машины с Н сумматорами к л|ашине с Ф4- ! сумматорами? "*1!.2,10. Пусть»Г — произвольное множество алгебраических законов. Разрешима лн проблема эквивалентности относитель. но Н двух двоичных синтаксических деревьев? 11.2.11.
Для алгоритма 11.2 определите процедуру соде(л,!ÄÄ..., (л)), которая вычисляет значение вершины л, пользуясь сумматорами Л,„Ль, ..., Л,„, и помещает результат на сумиаторе Л,. Покажите, что если взять в иачестве шага (Б) соде(л,(!т, 1„,, !л)) саде(л,,((!м !г! |м ..., 1„!) соде(а,!Го !». !»....,ГД ОР 9*4,'„'Л,,', Л,,' то алгоритм 11.2 можно модифицировать так, что все команды языка ассемблера типов (3) н (4) примут вид ОРО А,В,А 11.2.12, Пусть (а( при Ь) 0 з!йп(а, Ь) = 0 при 0=0 »( — (а( при Ь < О Покажите, чта операция з(йп ассоциативна, на не коммутативна. Лайте примеры других операций, ассоциативных, но не коммутативных.
*11,2.13. Каждан из команд ЕОА0 М, А ВТОКЕ А, М ОРО Л,М,В использует одно обращение к памнти. Если  †суммат, то ОР О Л, В, С вообще не содержит обращений к памяти. Найдите минимальное число обращений к памяти, генерируемое программой, вычислнющей двоичное синтаксическое дерево с Й вершинами. *1!.2.14. Покажите, что, алгоритм 11.2 вырабатывает программу, требующую при вычислении да|того выражения минимального числа обращений к памлти. *11.2.13.
Взяв в качестве входной грамматики С„постройте схему синтаксически управяяемого перевода, переводящего нн. гл. ц. оптимизация кодл фиксные выражения в оптимальную программу на языке ассЕмблера. Считайте, что имеется М сумматоров и (а) нс выполняются никакие алгебраические законы, (б) сложение и умножение комч)тативны, (в) сложение и умножение аесациативиы и комчутативны. 11.2.1б, Приведите алгоритмы реализации процедур соде, сапппп1е и асопппц1е за линейное вречя.
*11.2.17. Некоторые операции могут потребовать дополнитель. ных сумматоров (например, вызов подпрОграмм или арифметика с кратной точностью). Молифицируйте алгоритмы !1.! н 11.2 так, чтобы учитывать эту возможную потребность н дополнительных сумматорах со стороны операций.
11.2.10. Алгоритмы 11.1 — 11.4 также чожна применить к произвольному двоичному графу, если сначала с помощью расщепления вершин преобразовать его в дерево, Покажите, что алгоритм 11.2 в этом случае ие всегда будет генерировать оптимальную программу. Оцените, насколько плохим он может оказаться при этих условиях.
11.2.10. Обобщите алгоритмы 11.1 — 11.4 так, чтобы они могли обрабатывать выражения, включающие операции с произвоть. ным числом аргументов. *1!.2.20. Арифметические выражения мокнут содержать также н унарные операции + и —. Постройте алгоритм генерации оптималю!ого кода для этого случая. (Предполагается, гго все операнды различны и что четыре бинарные арифметические опе. рации и унарные + и — связаны обычными алгебраическими закопал!и.) *11.2.21. Постройте алгоритм генерапии оптимального кода для одного арифметического выражения, в котором каждый операнд является либо отличной от другкх переменной, либо целой константой.
Считайте, что для сложения и умножения выполняются ассоциативный и коммутативиый законы и справедливы следующие тождества: (1) а-!-О=.О.)-а=а, (2) а+1=.1еа=а, (3) с,бек =с„где с,— целое число, результат применения операции 0 к целым числаы с, и с,.
11.2.22. Найдите алгоритм гсаерации оптимального кода для одного логического выражения, в котором каждый операнд нвлнется либо отличной от других переменкой, либо логической константой (О илн 1). Считайте, что логическое выражение включает операции н, или, ие и онн удовлетворяют законам булевой алгебры (см. том 1). зэа упркжиенин **11.2.23. В некоторых ситуациях две или более операции могут выполняться параллелью.
Алгоритмы из равд. 11.1 и 11.2 предполагают воследовательное выполнение, Однако„ если машина способна выполнить параллельные операции, можно попы. таться так упорядочить выполнение, чтобы порождалось кзк можно болыпе одновременных параллельных вычислений. Пред. положим, например, что у нас есть машина с четырьмя регистрами, в которой одновременно могут выполняться четыре опе. рации.
Тогда выражение Аг+Лв+Ав+Ав+Лк+Ав+Аг+Ав ива 3 иег 1 иаг 1 Рвс, !! 2!. Дерева ллв вврвллвльвык вычвслеввз. можно представить так, как показано иа рис. !1.21. На первом шаге нужно поместить А, в первый регистр, А„ — во второй, А, — в третий, А, — в четвертый. На втором шаге нужно при. бавить Лв к содержимому регистра 1, Л, — к содержимому регисгра 2, А, — к содержииому регистра 3, а А, — к содержимому регистра 4. После этого шага регистр 1 будет содержать А, Р Л„ регистр 2 будет содержать А,ч- Л, и т.
д. На третьем шаге прибавляем содержимое регистра 2 к содержимому регистра 1, а содержимое регистра 4 к содержимому регистра 3. На четвергом шаге прибавлнем содержимое регистра 3 к содержимому регистра !. Постройте машину с М регнстрньюи, в которой ю одном ше~е может выполнн~ься до дГ параллельных ! операяий.
Модифицируйте алгоритм !1.1 так, чтобы он генерировал оптимальнЫй код (в счысле минимального чис.та п!агав) для одного арифметического выражении с рааличными операндами для такой машины. Ироблгжи длл исследования 11.2.24. Найдите эффективный алгоритч, ксаорый будет ге. нерировагь оптимальный код того же типа, что и рассматриваемый в этом разделе, на для произвольного блана. 13'" 1>.Э. ПРОГРАММЫ С ЦИКЛАМИ ГЛ. 11 ОПТИМИЗАЦИЯ КОЛА Замечания по литературе 293 392 Упрцжнеппе нп лрагрцымиразпяые 11.2.26.
Напишите программы, реализующие алгоритмы 11.1 — 11.4. Репер»пни хорошего када дли эрифметическик вырэжени» для каикретнык мешин или нллссов машин посвящена многа статей. Флойд 1196)э) описывает рвд методов оптимнзвцин врнфметичсснит ыр ж нвй, включв» определение опция подвыражений. Ов предлэгвет также, чтобы второй операнд не»амму. т инной биаврной опервдни вычислялся первым.
Андерсон !1964! дает Алгоритм генерации када для машины с одним регистром, па существу совпвдэющий с кодом, вырабатываемым влгоритмом 11.1 при ж=!. Нвквтэ [1967) н Мейере !19661 приводят аналогичные реэультэты. Число регистров, требуеыыа для вычисления дерева выражения, исследовали Нвнвте 11967), Редзневский 1 Ш691, Сети и Ульмвн 1 И70), Алгоритмы 1!.1 — 11.4 в том виде, в каком оии представлены здесь, реэрэбпвиы Сети и У. ьмэном 11976). Упр. 11.2.11 предложил Стокээуэен. Бити [1972! и Фрейли 1!970) исслелаввли ресшире»ня, включающие операцию унэриого минуса.
Чеэ 119721 обобщил алгоритм 11.2 нв некоторые ориентированные эциклические графы. Эффективный алгоритм геиервнии аптимвльиога кода для праизеальнык выражений не известен. Один эвристический метод испольэ »вни» регистров в процахе вычисления выражения ссновви ив следующем алгоритме. Предположим, что должно выч слвться выражение а, э его значение должно зэпоминвтьсн в быстром регмстре !сумм»тор*).
!1) Если энэченне а уже ээпомеепо в иеноторам регистре 1, та ие перевычислаем а. Регис~Р 1 нэшДитса тепеРь ав УпотРеблении". [2) Если значение а ие э*пампе»о ни в каком регистре, эвпоминэем ега в очередном сна!юлиан регистре, скажем !. Регистр 1 ивзодится теперь в употреблении. Если нет свободных доступнмк регистров, та содержимое некаторога регистре д ввпомвивем н основной и мяти, в значение а ввпомииэем в регистре А.
Регистр й выбираем так, чтобы к его внвчеиню кэк можно дольше не была сер»щения. Бнледи !19661 показал, что в иекатарык снт> вцннк этот алгоритм опгимэлен. Однэко этот элгоритм !Рвзрэботэнный ллв листов»ни») нредполвгэет модель, ие совпэдзющую в точности с моделью линейного кода. В частности, порядок вычислений считается фиксировэаиым, в та еремы «эк в равд. 11.1 и 11.2 было пакэзапо, чта, переупорядочиввя вычислеииа, можно добиться внэчшельного.выигрыша. Аиыогнчнэя ээдвчв распределении регистров исследуется в рабате Хореи»в и др. 11966).
твм предполагается, чта дена паследаэвтельность ппервннй, абрэщэк>щэяся к виэченням и изменяющая к. Задача ээключэется в том, чтобы в»нести эти значения в быстрме регистры тэк, чтобы число записей и счи1ываинй иэ быстрык регистров в основную пвмвть была минимальным. Нх решение с»а»вши к выбору пути с минимальной оценкой нэ ориентиро«ваном вциклнчесном грифе ооэмажнмк решемвй. Деются методы умеиьшени» размера грифа. Дальнейшее исследование распределения ре нстрав, «огдэ по. рядок вычислений не финсироввн, проведена Кеииед» !1972) н Сети !1972!. Перевод врифметнческик выражений в кад длв пэрвллельиых машин иэ. лвгветсэ Аллэрдам и др. [1964), Хеллермвнам 119661, Стоуном [19671, Бэром и Базе 11968! Общая ээдвчв оптимального рвспределеии» задач между пв- рэллельвымн процессарэми очень трудна.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
