Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 70
Текст из файла (страница 70)
Если л не является ее потомком, тол' — старшая вершина в Т'. Таким образом,достаточно рассмотреть только стершие вершинм л,, л„... на пути от п к корню дерева Т. В соответствии с рассуждениями, проведенными в случас 3 теоремы 11.6, сама вершина л не может быть старшей. Первая верпшаа ло если она сугцествует, не может тогда быть старшей в ТС Однако метка вершины л, в Т' не меньше чем 1Ч, погому что ее прямой пото. мок, не являющийся предком вершины л, должен иметь метку не менее Ч н в Т, и в Т'. Следовательно, л,, л„ ... остаются старшими вершинами в ТС Отсюда можно заключить, что Т' имеет не менее М вЂ” 1 старших вершин. Индукции проведена полностью. Е) Теорема 11.7.
Аггориглм 11.2 всегда вырабатывает кратчабгмую программу для вычислено.ч донного варажвяия. 1(он аз атель с тво. В соответствии с леммами 11.16 и 11.11 алгоритм 11.2 генерирует программу с мини»альна возможным число» команд ЕОАО и ЗТОКЕ. Поскольиу ясно, что ьгинимальное число команд операций равно числу внутренних вершин дерева, а ал1.орнтм 1!.2 дает по одной такой комавде для каждой внутренней вершины, то угверждение теоремы очевидно Е) Пример П.20. Как указывалось в приьгере ! 1.19, арифьгетнческое выражение на рис. 1!.9 имеет одну старшуго и четыре младших вершины (в предположении, ч1о У=2). Оно имеет также пять внутренних вершин.
Таким образом, для его вычисления требуется не менее десяти операторов. Программа из 315 гл. и оптимизация коЛл примера 11.18 содержит как раз десять операторов. Отметим, что среди них одна команда ВТОРОЕ, четыре ЕОАО, а остальные "-команды операций. лз 11.1.й. Влияние некоторык алгебраических законов Определим оценку синтоксичегхого дерева как сулгму (1) числа вяутренних вершин, (2) числа старших вершин, (3) числа младших вершин. Результаты предыдущего раздела показывают, что эта оПенка служит разумной мерой всложносгив синтаксического дерева, поскольку число команд, йеобходимых для вычисления синтаксического дерева, равно его оценке. Рве !! !1. Дсооцввтввнов вреоврвзовввве сн толов ~ослов деревьев Часто к некоторым операциям можно применить алгебраические законы и с их помощью уменьшить оценку данного синтаксического дерева.
Из равд. 11.1.6 известно, что каждый алгеб. раический закон индуцирует соотнетствуюпгее преобразование сиигаксичсского дерева. Например, если и — внутренняя вершина сннтаксвческого дерева, связапнан с коммутативной операиией, то коммутативное преобразование меннст порядок прямых потомков вершины а. Аналогично, если 8 †эс!ша швная операция (т, с.иб(887)— †.(айй)87), го, применяя соответствующее преобразование деревьев, можно перевести лруг в друга два дерева, изображенные на рис, 11.11. Ассопвативяое преобразование, приведенное 77Ь м.в вривматнчяскив вырлжзния на рис. 11.11, соответствует преобразованию блоков Х ВВС Х' АВВ еэ ?' АОХ У ХВС В равд.
11.1 б после применения преобразования слева направо оператор Х ВВС сохранялся. Однако теперь после преобра. зования этот оператор становится бесполезным, так что его можко удалить, не меняя значения блока Определение. Если дано множество И алгебраических законов, то дкэ синтаксических дерева Т, и Т„ будем называть эяэиедвентнызли относительно о( и писать Т,= — 7 Т„если существует последовательность преобразований, выводимая из э~их законов, переводящая Т, в Т,.
Через [Т[И булем обозначать класс эквивалентности деревьев (Т [ Т =.- в Т'). Таким образом, если дано синтаксическое дерево Т и известно, что выполняются алгебраические законы из некоторого множества заноиов оС то для нахождения оптимальной программы для Т надо искать в [Т),( дерево выражения с минимальной оценкой. Если дерево с минимальной оценкой найдено, то для нахождения оптимальной программы можно применить алгоритм 1!.2. Теорема 11.7 гарантирует, что получаемая программа будет оптимальной. Если каждый закон сохраняет число операций, как в случае коммутагивного и ассоциативного законов, достаточно минимизировать сумму чисел старших и младших вершин. В качестне примера приведем алгоритм щой минимизации сначала для случая, когда некоторые операции иоммутвтивны, в ветен длн случаи, когда некоторые коммутативвыс операции также и ассоциативны.
По данному синтаксическому дереву Т и множеству .в алгебраических законов приведенный ниже алгоритм будет строить синтаксичесиое дерево Т' Е[Т[А с минимальной оценкой при условии, что:7 содержит только коммутативные законы, применимые к определенным операциям. Затем к Т' можно будет применить алгоритм 1!.2 и найти оптимальную программу для исходвого дерева Т. Алгоритм 1(Л. Построение дерева с минимальной оценкой, некоторые операции которого коммутативны.
Вход, Синтаксическое дерево Т (с тремя или более вершинами) и множество И комыутативных законов. Выход, Синтаксическое дерево из [Т~ ! с миннлгальной оценкой. 377 Гл 11. Оптимиэиция кОдА 11.2 АРиоматическиа выРАжвиия зтв Метод. Ядро алгоритма составляе~ рекурсивная процедура сотен(е(а), аргументом которой служит вершина л синтаксического Лерева, а результатом †моднфнцпрованн поддерево с вершиной и в качестве корня. Вначале вызывается сопппа(е(а,), где п, †коре данного дерева Т.
Процедура сопипи1е(л). (1) Если п -лист, полагаем сонмище(л)=л. (2) Еслн л — внутренняя вершина, рассмотрим два случая; а) Пусть вершина л имеет два прямых потомна л, и а„ (в указанном порядке) и операция, связанная с л, кочмутативна. Если л, †ли, а а, нет, то выход со1ппш1е(а] †-дерево на рис. П .12, а.
б) Во всех дру1нх случаях выход со1пши1е(а) -дерево на рнс. 11.!2, б. Рис. 11.12. Редультет процедуры еоюоы!е. Пример П.21. Рассмотрим ряс. 11.9 н предположим, что колшутативпо только умножение. Результат прнмснеиня алго- рнтма П.З к этому дереву показан на рис. П.13. Отметим, что корень на рнс. !1.13 помечен 2 н что здесь две младшие вершнны. Таким образом, если у нас два сумматора, то для Рис П 13 Преобреэоиееаое ерпфиетическоо заражение. вычисления этого дерева требуется только семь команд, а для дерева на рнс. 11.9 †деся.
Теорема 11.8. Если допустима применение одного только коммутативнага дяя некоторых операций закона, то алгоритм П.3 вырабатывает таков синтаксическое дерево из класса эквивалеитнасаш для данного дерева, которое имеет минимальную оценку. Показательство. Легко внпетть что коммУтатиаиый закон не может изменять числа внутренних вершин.
Простая нядукцня по высоте вершины показывает, что алгоритм 11.3 миннмизнрует число младших вершин н метки, ноторые должны быть у вершин после применения алгоритма 11.1. Следовательно, мнпимнзируется также чнсло старших аер1пнп. ( ! Сптуацкя усложняется, когда некоторые операции одновременно коммутатнвны н ассоциативны. В этом случае уменьшись чис,ю старшнх вершин часто можно за счет существенного пре. образования дерева. Определение, Пусть Т вЂ синтаксическ дерево.
Множество 5 из двух илн более его вершин называется кистью, если (!) все вершины в 5 внутренние н представляют одну и ту же ассоцнатявную н коммутатнвную операцию, гд и. Оптимизвцня КОЛА и в лвиаматичвскив выражения ьз Рнс г1.!4. Скнтвкснчвсквв дерево. (2) вершины из 5 вместе с соединяющими нх дугами образуют дерево, (3) нн одно из собственных иадмножеств множества 5 не обладаег свойствачн (!) и (2).
Корнем кисеи называется корень дерева, о котором идет речь в пункте (2). Прямыми по!ломками кисти 5 называются те вершины из Т, которые не принадлежат 5, но являются прнмыми потомками вершин из 5. Пример 1!.22. Рассмотрим синтакси !еское дерево на рис. ! !. !4, в котором сложение н умножение коммутативны, а никакие другие алгебраические законы неприменимы. Три кисти обведены штриховычн лнниячи.
Кисть, включающая корень дерева, имеет в качестве прямых потомков в порядке слева направо корень кисти 2, вершину, с которой сопоставлена операция выгнтапин, и корень кисти 3. '3 Заметим, что кисти синтаксического дерева Т определяются однозначяо и не пересекаются. Дли нахождения в (Т~)( дерева с минимальной оценкой, когда к( содержит законы, отражаюшие тот факт, что одни операции коммутативны и ассоциа. тивны, а другие только коммутативны, вводится поантие ассоииат нвного дерева, а котором кисти представляются одной вершиной.
Определение. Пусть Т вЂ” синтаксическое дерево. Ассоаиапивным деревом Т' для Т назовем дерево, получающееся заменой каждой кисти 5 н Т на единственную вершину л с той же ассоциативной и коымутативной операцией, что и у верьпины кисти 5. Прямые потомки кисти в Т становятся прямыми потомками вершины л в Т'. Пример 11.23. Рассиотрим синтаксическое дерево на рис. 11,!3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
