Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 64
Текст из файла (страница 64)
Табэчяа !!.! ш с в ° в О А А В О1С С О вЂ” С Л вЂ” Г(В С А ел О В В В С вЂ” О й С--О л — с)г в табл. !1.1. Блоки Я, и Я, имеют олин н тат же граф, изображенный на рис. !1.2. С помощью Т, можно отобразить Я, и Я, в открытые блоки „'В; — (Р;, (Л, В), (Х,)) и Я; = (Р;, (А, В), (Х,)), при этан будет удовлетворяться условие (3)из доказатс;шства теоремы 11.2.
Р; и Р;при- рис. 1!.з. 1гзф а я ш, и вь всдены в таба. 11.2. Затем, начиная с блока йа у которого Р; †спис операторов, легко построить блоки е'„ ва 'ва Я, и Юм упомянутые в доказательстве теоремы 11.2. Блок ьт получается применением преобразования Т„ перемещающего второй оператор на первое место (см. табл.
11.3). Далее, 6„= во Блок в, строится из йт с помощью преобразования Т„ставяще! о четвертый оператор перед третьим (табл. 11.3); блоки Т, н З(, совпадают с йм (З ЗА! Пример 11.3. Рассмотрим два блока Я, =(Р„ (Л, В), (Р)) и Я., =(Р„ (Л, В), (Р)), множества Р, и Р, для них приведены гл ц, оптимизация кода Тгбгтгэ т! Г л',,— л л Х, — Вел х, х, — х, х, х,зх,' х,+ — л,гл, х,--в в х, х,— (х, Х, ЛтюХ, Х, Х,!Х, Тзбгмза гтм х — в в л.,— л л х, х,— х, х, — л',!х, Хз Хз Л', х — в в л', А л Х Л', 4.
Х х х,— х х, х,гх, 342 1!.1.4. Крнтермй зивмввпонтностн блоков Покажем теперь, что З, = Зз тогда и только тогда, когда З, Ф=Р Я,. На самом деле справедливо более сильное утверж- ' Г. 4. 4, денне, а именно: ВЗ,= — ЗЗ, тогда и только тогда, когда З, озЗ4 !.. Иными словами, преобразований Т, н Т, достаточно, чтобы отобразить любой блок в любой эквивалентный ему. Доказательство этого более сильного утвержденна предлагаем в качестве упражнения (упр. 11 З н !1.!О).
Определение. Блок .З называется приведенным, если ае существует такого блока З', что УЗ~! 4Я'. Приведенный блок не содержит ни бесполезных операторов, но взбьжочных вычислений. Если дан блок Я, то можно нанти эквивалентный еьгу приведенный блан, повторно применяя Т, и Т,. Поскольку каждое применение Т, нлн Т, сокращает длину блока, в конце концов мы должны прийти к приведенному блоку. Ната цель заключаезся в том, чтобы показать, что для приведенных блоков .З, = =З, тогда и только тогда, когда 0(З!) = (З(З4) Таким образом, если дан блок З, то можно найти елицсгвешолй граф, соответствующий всем приведенным блокам, получаемым из З, независимо ог той конкретиой последоватезь- и.!.
оптнмнзхцня линеяного эчлсткз ности преобразований Т, и Т„ в результаге которой был получен приведенный блок. Какова бы ни была ыашинная модель, нахождение этого графа — важный шаг „оптнмпзаини" блока. Определение. Пусть Р =- 5,; ...; 5„ — список операторов блока. Обозначим через Е(Р) множество выражений, вычисляемых в Р, Формально Е(Р) —.(о(Л)(5, осуществляет присваивание переменной А, ! ~ ! щ,г!) Выражение ц выгистяется в Р й раз, если существуют ровна й таких различных значений 1, что о,(Л) =ц и 5, присваивает значение А.
Лемма П,З. Егт! Я =(Р, I, (() — лриэгденнмй блок, то Р нг нюшглкгт к!!какого гырижгиия долге одного риза. До к аз а тельство. Если два оператора выпюлюот одно и то жа выражение, находим „первое" вхождение выражения, вычисляемого дважды. Иными словамв, если 5! и 5г, ! < 1, вычисляют одно н то же выраженно 41, будем называть (г, !) яграьгм вхождением, если для всех пар 5„н 5о Л С 1, вычвслягощнх то же самос выражение, либо ! < й, либо одновременно ! — й и ! (1. В качестве упражнения предлагаем показать, что к 5 и 5 можно применить в прямом направлении преобразование Т„ а это противоречит предположециго о приведенности Р.
Е) Лемма 11.4. Если Я,=-(Р„(„()з) и З„.— (Р„)„((,) — гкбивюынтнмг приэгдгкммг блоки, то Е(Р,) =-Е(Р,). Доказатсльот во. Если Е(Р,)чаЕ(Рз), то без пагери общности можно считать, что ц — последнее нычислясмое ныраженнс е Е(Р,) — Е(Р,), Поскольку о(З,) =о(З,) и каждое выражение единственным образом можно разбить на подвыражения'), то ц не является подвыражением никакого выражения из о(ВЗ,).
Таким образом, оператор, вычисляющий з! в Р„бесполезен, н его можно удалить с поыащью преобразования То чта прогизоре. чит предположению о прнведенности Зо Подробное доказательство ос!валяем в качестве упражнения. ГЗ Теорема 11.3. Если Я, и Я,— дза призгдгнных блока, то З,=== 34 тогда и то,юко тогда, когда )З(З!) —.-Р(З4). До к а з а г ел ь с та о. Достаточность услония — частный случай следствия теоремы 1!ЗЕ Докажем необходимость. Пусть Я, =-З,.
Из предыдущих двух лемм вытекает, что существует '! 41огвирюкенэе — э"о префньсное еирамгэне, аэля!ощееся операндом другого префиксного заражения.— Прим. лерга. гл. и оплимизлции кола ~ьь оптнмизгщия линьпиога . частка взаимно одпозпачггос соответствие между операторами иэ Я и З 1 х вычисляющими одни и те же выражения. Прелположим, что 0(Я,) хи 0(Я,). Попьпаемся „сопосгашпь" вершины в 0(З,) и в 0(Яа) настолько „высоко" по графу, насколько это иозможио. Ясно, что листья дзух графов можно сопоставить — а противном случае входные множества блоков Я, и 33, были бы различны.
Затем можно найти зхолпуго поре. менную одного из блоков, на которую ие было ссылки, и, при. меняя То удалить ее. Поскольку Я, и Я„приведены, приходим к противоре ~ию. Продолжаем сопостаалять вершины; если некоторая зерцшна з 0(В,) имеет ту жс лштку (операцию), что и какаи-то вершина в 0(33,), если из них выходит одинаковое количество дуг п соответствующие дуги (начиная слева) указывают на сопоставленные першины, то рассматриваемые две вершяны можно сопостзвять. Если, продолжая а том же духе, мы сопоставим все вершинм из 0(Я,) и 0(Я,), то эти графы совпадут.
В противном случае мы придем к некоторой иершяпс з 0(З,) или 0(д,), кпторой нс соответствует никакая вершина я другом графе. Без потери общности можно считать, что эта вершина принадлежит 0(З,) н что обнаружена самая „пижаяя" такая вершина, т. е яершина, каждая выходящая дуга которой указывает па сопостзалениую вершину. Пусть этой вершиной будет л,. Можно видеть, что сопоставленные вершины о 0(З,) и 0(З,) порождаготся операторами э Я, и З,, вычисляющими одни и те жс выражения.
Это легко показать простой индукпней по порядку сопоставления. Однако по лемме 1!.3 никакую вершину нельзя сопоставить с двуми вергпинами другого графа. По лемме ! 1.1 а 0(уда) найдется вершина л„порождаемая опсратороч из Я„вычисляющим то же самое выражение, что и оператор из Зо порождаюгций л,. Поскольн) „разбор" аыражепий определен однозначно, прямые потомки вершин л, и л, сопоставлены. Это следует из прсгположепия, что вершина л, находится з 0(З,) настолько „нгыко", насколько возможно. Таким образом, вершины л, и л, можно сопоставить вопреки предположению.
Следовательно, 0(Яе).= .=- 0(33,). Следствие. Всг приэгденимг бгщки, ахаиеаггнтнмг данюхму, имеют один и тот же граф. Е) Соберем теперь вместе доказанные выше результаты н !гокажем, что четырех описанных преобразований достаточно для того, чтобы превратить блок в любой ему эквивалентный. Теорема 1! А. Зхяя Я, тогда и только!когда, ксгда З, г:=':; Я„.
х, а, а, 344 До каз атсльст во. Достаточность условия — это следствие теоремы 11.1. Обратно, предположим, что Я, = — !Ва. Тогда суще. ствуюг такие приаеденные блоки Я,' и Я„', что Я, ез Я; и За йзЯ',. Согласно следствию теоРемы 11.1, .6, =.13; и З,==Я;. Таким образом, 53; =З;.
По теореме 11.3 0(З;) — 0(Я;). По теореме 11.2 Я;еэ .13;. Следовательно, Я, ф=р Я,. Е) а. х. а, а, а 11.1.5. Оптимизация бпоиов Займемся теперь преобразованием блока 33 з блок З', оптимальный относительно некоторой оценки блока. На практике часто встречается снт)ации, изображенная на рис.
11 3. По данному блоку З мы хотим и конце копцов получить програмлгу Рас. !1.3. Схема аахаяазаиаа на объектном языке, оптимальную относительно некоторой опенки объектных програьглц такой, например, кэк размер прогрзлеь~ы или скорость ее выполнении. Оптимизатор применяет к блоку Я последонагельность преобразовании, чтобы построить блок Я', экзиаалентный Я, из которого можно получит~ оптимальную программу на объектном языке. Таким образом, одна из аадач заключается в нахогкдеггии опенки блокоэ, отражающей оценку вырабатываемой а конце концов обьектпой программы.
Существует несколько оцеаок блоков, для которых идея опти. мязапии даже не имеет смысла. Например, если мы будем говоРнтггь жо блок тем лУчше, чем он даиннее, та эообпге нет оптимального блока, эквааалентного данному. Здесь чы ограничимся опенками блоков, отражающими наиболее широко применяемые критерии качества программ па объектном языке, такие, например, как скорость аыполнсния или объем используемой памяти. Определение. Оценка блоков †э функция, отображаю!цая блоки в вещественные числа. Блок гд называется оптимишнмм отиоситслыго опенки С, если С(Я](С(33') лля всех 53, экеиаалеитпых З Оценка называется лриглглгмой, если Яхта, аЗ, илечет С(Я,) (С(334) н любой блок имеет эквивалентный блок, опигмальный относительно С.
Инымн словами, опенка приемлема, если преобразования Т, и Т„примспяемыс э прямом направлении, нс увеличивают оценки блока. 345 тл. н. оптимизлпня кодл Лемма 11.5, Если С вЂ” приемлемал оценка, то любой блок имеет вквилалентимй аритденнмй блок, оптимальный относите.пно С. Доказательство. Счедует непосредстэешю из определений. Лемма 11.6 устанааливаст, что если даи блок Я, то поиски эквивалентного оптимального блока можно ограничить множеством приведенных блоков, эквивалентных Я.
В лемме 11.б ниже утверждается, что в результате ариэле!те~тип и данному приведенному блоку Я последовательности преобразований Т, и Т, получаются только приведенные блоки, эквивалентные Я. Лемма 11.6. Если Я,— приведенный блок и Я, алЗм тоЯ,— также приведенный блок. Доказательство.
Упражнение. ц Наш следующий результат показывает, что если дан открытый блок, то последовательность переименований, за которой идет перестановка, можно заменить на перестановку, за которой следуют переименоэанип. Лемма 11.7. Пусть Я,— открытый блок и Я, еэЯ,=-л,Я,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
