А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 89
Текст из файла (страница 89)
Таким образом, ориентированный ациклический граф не только представляет выражение более кратко, но и дает генератору кода возможность генерации более эффективного кода для вычисления выражения. Пример 6.1. На рис. 6.3 показан ориентированный ациклический граф для выра- жения а+а* ( Ь-с ) + ( Ь-с ) *с( Ь с Рнс. 6.3. Ориентированный ацнклнческнй граф лля выражения а+а*(Ь-с)+(Ь-с)*г( Лист, представляющий а, имеет два родителя, поскольку а встречается в выражении дважды.
Еще более интересно то, что два общих подвыражения Ь-с представлены одним узлом, помеченным —. Этот узел имеет два родительских узла, представляющих два использования упомянутого подвыражения в подвыра- 446 Глава 6. Генерация промежуточного кода жениях а*(Ь-с) и (Ь-с) *с). Несмотря на то что Ь и с встречаются в полном выражении дважды, их узлы имеют один родительский узел, поскольку оба раза они встречаются в общем подвыражении Ъ-с. п СУО на рис. 6.4 может строить как синтаксические деревья, так и ориентированные ациклические графы. Оно использовалось для построения синтаксических деревьев в примере 5.11, в котором функции Аеа( и Моде создают новые узлы при каждом вызове. Те же функции позволяют построить ориентированный ациклический граф, если перед созданием нового узла эти функции будут сначала проверять, не существует ли уже идентичный узел, и если существует, то не создавать новый узел, а возвращать существующий. Например, перед созданием нового узла Моде (ор, 1еЯ, г186г) мы проверяем, имеется ли узел с меткой ор и дочерними узлами 1е11 и щй| (в указанном порядке).
Если имеется, то функция Моде возвратит существующий узел; в противном случае она создаст новый узел. Рис. 6.4. Синтаксически управляемое определение для получения синтаксических деревьев илн ориентированных ациклических графов Пример 6.2.
Последовательность шагов, показанная на рис. 6.5, строит ориентированный ациклический граф, показанный на рис. 6.3, обеспечивая по возможности возврат функциями МоЫе и 2,еа1 существующих узлов, как рассматривалось ранее. Предполагается, что елггу-а указывает на запись таблицы символов для а; то же выполняется и для других идентификаторов. Когда вызов 1,еа1(И, еппу-а) повторяется на шаге 2, возвращается узел, созданный предыдущим вызовом, так что рз = рь Аналогично узлы, возвращаемые на шагах 8 и 9, те же, что и возвращаемые на шагах 3 и 4 (т.е.
ра = рз и рз = = р4). Следовательно, узел, возвращаемый на шаге 10, должен быть тем же, что и возвращаемый на шаге 5, т.е. рю = ры Б 447 6.1. Варианты синтаксических деревьев 1) рз = АеаД!и, еп1гу-а) 2) рз = АеаДЫ, епггу-а) = рз 3) рз = 1,еаДЫ, ептгу-Ь) 4) р4 = Ееа/(!и, еппу-с) 5) рз = Моде(' — ',рз,р4) 6) ро = Моде('~',р1,ро) 7) рт = Моде (' + ', ры Ро ) 8) ра = 7еа~(Ы, епггу-Ь) = рз 9) ро = Сей"(!Й,еп!гу-с) = р4 !0) рю =Моде(' — ',рз,р4) =рз 11) Ры = 2,еаза'(Ы, епггу-д) 12) рщ = Моде('* Рь,ры) 13) Рзз = Моде('+' Рт Р1з) Рис.
6.5. Шаги построения ориентированного ациклического графа, показанного на рис. 6.3 6.1.2 Метод номера значения для построения ориентированных ациклических графов Зачастую узлы синтаксического дерева или ориентированного ациклического графа хранятся в массиве записей, как предложено на рис. 6.6.
Каждая строка массива представляет одну запись, а следовательно, один узел. Первое поле каждой записи представляет собой код операции, указывая метку узла. На рис. 6.6, б у листьев имеется по одному дополнительному полю, в котором хранится лексическое значение (указатель на запись в таблице символов или константа), а внутренние узлы имеют по два дополнительных поля, указывающих левый и правый дочерние узлы.
Мы обращаемся к узлам с использованием целочисленного индекса соответствующей записи в массиве. Это целочисленное значение исторически носит название номер значения (уа!це пшпЬег) узла или выражения, представленного этим узлом. Например, на рис. 6.6 узел с меткой + имеет номер значения 3, а номера значений его левого и правого дочерних узлов равны соответственно 1 и 2. На практике вместо целочисленных индексов можно использовать указатели на записи или ссылки на объекты, но мы в любом случае будем говорить о ссылке на узел как о "номере значения". Будучи сохраненными с применением подходящей структуры данных, номера значений помогают эффективно строить ориентированные 448 Глава 6. Генерация промежуточного кода К записи для з б) Массив в) Ориентированный вциклический граф Рис. 6.6. Узлы ориентированного ациклического графа ддя г. '= з + 10, расположенные в массиве ациклические графы выражений; как это делается, показано в приведенном ниже алгоритме.
Предположим, что узлы хранятся в массиве, как показано на рис. 6.6, и что обратиться к каждому узлу можно по его номеру. Назовем сигнатурой внутреннего узла тройку (ор,1, т), где ор — метка, 1 — номер значения левого, а т — правого дочернего узла. Унарный оператор можно рассматривать как имеющий значение т = О. Алгоритм 6.3. Метод номера значения построения узла ориентированного ациклического графа Вход: метка ор, узлы 1 и т. Выход: номер значения узла с сигнатурой (ор,1, т) в массиве.
Метод: выполнить поиск в массиве узла М с меткой ор, левым дочерним узлом 1 и правым дочерним узлом т. Если такой узел найден, вернуть номер значения М. Если нет, создать в массиве новый узел )Н с меткой ор, левым дочерним узлом 1 и правым дочерним узлом т и вернуть его номер значения. а Хотя алгоритм 6.3 и выдает на выходе требуемую информацию, сканирование всего массива всякий раз, когда нам требуется получить информацию об одном узле, — метод слишком расточительный, в особенности если в массиве хранятся выражения из всей программы. Более эффективный подход заключается в использовании хеш-таблицы, в которой узлы помещаются в блоки (Ьцс)се)з), в каждом из которых обычно хранится всего лишь несколько узлов.
Хеш-таблица представляет собой одну из нескольких структур данных, эффективно поддерживающих словари.! Словарь представляет собой абстрактный тип данных, который позволяет добавлять и удалять элементы множества, а также определять, имеется ли Вопрос о структурах данных, поддерживвюшнх словари, рвссывтриееется в Аьо, А.Н., ).Е. Норсгой, вяд 13Х О)!ювп, 0ага 5ггнсгнгкз апаг А!лагг!)зньз, Ада)зев-'зуев)еу, )983 (русский перевод — А.
Ахо, Д. Хопкрофт, Д. Ульмвн. Структуры данных и алгаритлгы. — Мк Издательский дом "Вильямс", 2000). 449 6.1. Варианты синтаксических деревьев некоторый элемент в настоящий момент в множестве. Хорошая структура данных для словаря, такая как хеш-таблнца, выполняет каждую из указанных операций за константное нлн близкое к нему время, независимо от размера множества. Для построения хеш-таблицы для узлов ориентированного ациклического ~рафа требуется хеш-функция л, которая вычисляет индекс блока по сигнатуре (ор, (, т) способом, который равномерно распределяет сигнатуры по блокам, так что маловероятна ситуация, когда в одном блоке находится существенно больше узлов, чем в другом. Индекс блока и (ор, (, т) детерминированно вычисляется на основании значений ор, ( и т, так что сколько бы мы ни повторяли вычисления, для заданной тройки (ор, 1, т) мы всегда будем получать один и тот же индекс.
Блоки могут быть реализованы в виде связанных списков, как показано на рис. 6.7. Массив, проиндексированный хеш-значениями, хранит заголовки блоков, каждый из которых указывает на первую ячейку списка. Внутри связанного списка блока каждая ячейка хранит номер значения одного из узлов, хешированных в данный блок, т.е, узел (ор, (, т) может быть найден в списке, заголовок которого имеет в массиве индекс и (ор, 1, т). Массив заголовков 9 блоков, проиндексироеенный хеш-значениями 20 Рис. 6.7. Структура данных для поиска блоков Таким образом, для данных ор, ( и т мы вычисляем индекс блока и (ор, (, т) и ищем заданный узел в списке ячеек этого блока.
Обычно блоков достаточно для того, чтобы списки состояли всего лишь из нескольких узлов. Однако при поиске может потребоваться просканировать все ячейки блока, и для каждого номера значения о, найденного в ячейке списка, следует проверить соответствие сигнатуры искомого узла (ор,(, т) узлу в списке (как показано на рис. 6.7). Если соответствие найдено, мы возвращаем о, если нет, то, поскольку нам известно, что в других блоках данный узел храниться не может, мы создаем новую ячейку, добавляем ее к списку ячеек блока с индексом Ь(ор,(,т) и возвращаем номер значения этой новой ячейки. 450 Глава б.
Генерация промежуточного кода 6.1.3 Упражнения к разделу 6.1 Упражнение 6.1.1. Постройте ориентированный ациклический граф для выра- жения ((х + у) — ((х + у) к (х — у))) + ((х+ у) я (х — у)) Упражнение 6.1.2. Постройте ориентированный ациклический граф и идентифицируйте номера значений для подвыражений следующих выражений, считая + левоассоциативным оператором: а) а+ Ь+ (а+ Ь); б) а+Ь+а+Ь; в) а+ а+ (а+ а+ а+ (а+ а+ а+ а)).
6.2 Трехадрееный код В трехадресном коде в правой части команды имеется не более одного оператора, т.е. не допускаются никакие встроенные арифметические выражения. Таким образом, выражение на исходном языке наподобие к+у*в может быть транслировано в трехадресные команды тг=у*2 т,=х+тг Здесь 11 и тз — временные имена„сгенерированные компилятором. Такая развертка многооператорных арифметических операций и вложенных инструкций управления потоком делает трехадресный код особенно подходящим для генерации целевого кода и оптимизации, как вы узнаете из глав 8 и 9.
Использование имен для промежуточных значений, вычисляемых программой, позволяет легко выполнять перестановки в трехадресном коде. Пример 6.4. Трехадресный код представляет собой линеаризованное представление синтаксического дерева или ориентированного ациклического графа, в котором явные имена соответствуют внутренним узлам графа. Ориентированный ациклический граф, показанный на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
