А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 103
Текст из файла (страница 103)
Отслеживать о можно с помощью таблицы символов, чтобы отображать специальный идентификатор Ьгеа(г на узел охватывающей инструкции цикла о'. Такой подход пригоден также и для обработки помеченных инструкций Ьгеа1с в )ача, поскольку таблица 512 Глава 6. Генерация промежуточного кода символов может использоваться и для отображения метки на узел синтаксического дерева помеченной конструкции. Вместо использования таблицы символов для обращения к узлу Я можно поместить указатель на Ялехг11хг в саму таблицу символов.
В этом случае по достижении инструкции Ьгеа)с мы генерируем незаполненную команду перехода, ищем в таблице символов лехИ(хг и добавляем этот переход в список, в котором позже он будет исправлен так, как описывалось в разделе 6.7.3. Инструкции сопйппе можно обработать аналогично инструкциям Ьгеа(г. Основное отличие между ними — в различных целевых метках генерируемых команд перехода. 6.7.5 Упражнения к разделу 6.7 Упражнение 6.7.1. Используя схему на рис. 6.43, выполните трансляцию каждого из следующих выражений. Приведите списки для истинного и ложного значений для каждого подвыражения. Для определенности можно считать, что адрес первой генерируемой команды равен 100. а) а==Ь йй (с==с( !! е==й) б) (а==Ь 1( с==с() !( е==й в) (а==Ь йй с==с() йй е==й Упражнение 6.7.2. На рис.
6.47, а приведен набросок программы, а на рис. 6.47, б — структура генерируемого трехадресного кода при использовании трансляции с обратными поправками на рис. 6.46. Здесь (1 ... (а — метки генерируемых команд, с которых начинаются фрагменты "Код для... ". При реализации данной трансляции для каждого булева выражения поддерживаются два списка мест в коде Е; это списки ЕЛ ие и Е~а(хе. Места в списке Елене — это те места, куда в конечном счете будет помещена метка, в которую передается управление при истинности Е; аналогично в списке Е,га(хе перечисляются места, в которые надо поместить метку, в которую передается управление прн ложности Е. Кроме того, для каждой инструкции Я поддерживается список мест, в которые надо поместить метку, соответствующую потоку управления по завершении вычисления Я.
Дпя каждого из приведенных списков укажите значение (одно из (1... (а), которое помещается в команды из этого списка. а) Ез,(аде б) Бз.пехг в) Ел~а(ге 513 6.7. Обратные поправки г) Я4шех7 д) Езхгпе зт)4))е (Е1) ( 4! (Е2) иЫ!е (Ез) Я1, е!зе ( )! (Е4) Я2, Яз )8. б) а) Рис. 6.47. Структура управления потоком к упражнению 6.7.2 Упражнение 6.7.3. При выполнении трансляции приведенного на рис. 6.47 фрагмента с использованием схемы на рис. 6.46, для каждой инструкции создается список Я.пех7, начиная с инструкций присваивания Яы Яз и Яз и переходя ко все большим инструкциям К )!'-е)зе, тк)п(е.
Всего на рис. 6.47 имеется пять инструкций таюго вида: Я4 ' ч'Ь|1е (Ез) Я4 Яз 4! (Е4) Я2 Яа . 'БЛОК, Состояшии из ЯЬ и ЯЗ Я7 ° Инструкция )! (Е2) Я4 е!зе Яа Яз . Вся программа Для каждой из указанных инструкций существует правило, позволяюшее постРоить Яопех7 нз дРУгих списков Яэ.пех7 и списков Еьлгие и Еь.)ОЬе длЯ выРажений в программе. Приведите эти правила для а) Я4 пехц б) Яз.пехц в) 5а,пехц г) Ят,пехб д) Яз.пег<.
47. Код для Е7 42.' Код для Е2 4з' Код для Ез 44. Код для Я7 4ь' Код для Е4 4е. Код для Я2 47. Код для Яз 514 Глава 6. Генерация промежуточного кода 6.8 Инструкции выбора Инструкции выбора (ввч1сЬ) доступны во многих языках. Рассматриваемый нами синтаксис инструкции выбора показан на рис. 6.48. Имеется вычисляемое выражение-селектор Е, за которым следуют и константных значений $'ы 1:з,..., 'г'„, которые может принимать выражение, а также, возможно, "значение" ло умолчанию (оеГац11), которое считается всегда соответствующим значению Е в том случае, когда оно не равно ни одному другому значению.
язт11сй (Е) 1 саяе 1'1 . Я1 саве Ъ~: Яа саяе 1Г„ 1: Я„ 1 пе$'ацИ: Я„ Рис. 6.48. Синтаксис инструкции выбора 6.8.1 Трансляция инструкций выбора Трансляция инструкции выбора должна состоять в следующем. 1. Вычисление выражения Е. 2. Поиск в списке вариантов значения)', которое равно значению выражения. Вспомните, что значение по умолчанию соответствует выражению, если ему не соответствует ни одно явно указанное значение Ь'. 3.
Выполнение инструкции Яз связанной с найденным значением. Шаг 2 представляет собой п-путевое ветвление, которое может быть реализовано одним из нескольких способов. Если количество вариантов невелико, скажем, не более 10, то имеет смысл воспользоваться последовательностью условных переходов, каждый из которых выполняет проверку на равенство одному из значений и передает управление соответствующему коду при совпадении. Компактный способ реализации такой последовательности условных переходов состоит в создании таблицы пар, каждая из которых состоит из значения и метки кода соответствующей инструкции. Вычисленное значение самого выражения в паре с меткой для инструкции по умолчанию помещается в конце таблицы во время выполнения программы.
Затем компилятором генерируется простой цикл, который сравнивает значение выражения с каждым значением из таблицы, 515 6.8. Инструкции выбора которая гарантирует, что если не найдется другого соответствующего значения, то будет выполнена инструкция по умолчанию. Если количество значений превышает 1О или около того, более эффективным способом является построение хеш-таблицы значений с метками для разных значений в качестве записей. Если в таблице не находится запись для вычисленного значения, генерируется переход к инструкции по умолчанию. Существует распространенный частный случай, который может быть реализован еше более эффективно, чем п-путевое ветвление. Если все возможные значения лежат в некотором небольшом диапазоне, скажем, от тт до тах, и количество различных значений представляет собой существенную долю от шах — тт, то можно построить массив из шах — тГп блоков, где блок 1 — т1л содержит метку инструкции для значения 1; все блоки, которые остаются незаполненными при этом процессе, заполняются метками инструкции по умолчанию.
Для выполнения выбора вычисляется значение выражения з. Затем убеждаемся в том, что это значение находится в диапазоне от иип до шах, и выполняем косвенный переход с использованием записи таблицы со смещением 1' — оил. Например, если выражение имеет символьный тип, может быть создана таблица из, скажем, 128 записей (зависит от используемого множества символов), и переход может выполняться даже без проверки вычисленного значения на принадлежность диапазону. 6.8.2 Синтаксически управляемая трансляция инструкций выбора Промежуточный код на рис. 6.49 представляет собой трансляцию инструкции выбора на рис.
6.48. Все проверки вынесены в конец, так что простой генератор кода в состоянии распознать многопутевое ветвление и сгенерировать для него эффективный код с использованием наиболее подходящей реализации, предложенной в начале данного раздела. Более прямой способ, показанный на рис. 6.50, требует от компилятора проведения интенсивного анализа для поиска наиболее эффективной реализации. Заметим, что в случае однопроходного компилятора размещение инструкций ветвления в начале оказывается неудобным, поскольку компилятор не может генерировать код для каждой инструкции Я; сразу же, как только встретит ее.
Для трансляции в вид, показанный на рис. 6.49, встретив ключевое слово язг11сн, следует сгенерировать две новые метки, ~ев~ и пехт, и новую временную переменную г.. Затем при синтаксическом анализе Е генерируются код для вычисления значения Е во временную переменную г. и команда безусловного перехода алого ген~. После этого, когда встречается каждое из ключевых слов саяе, создается новая метка Ео которая вносится в таблицу символов.
В очередь, использующуюся 51б Глава 6. Генерация промежуточного кода Код для вычисления Е в т. дото тент. Код Яг дото пехт. Код Я2 дото цех~ Код Я„ 1 дото пехт. Код Я„ дото пехт. 1б т. = Р~ до~о Ь, 1й т. = 1"2 до1о Ь2 1Й т. = 1г„г дот.о Ь„ до~о 1„ пехт.: Рис. 6.49. Трансляция инструкции выбора Код для вычисления Е в ~ 1й т != 'гг досо 1г Код Яг дог.о пехТ 1й ~ != 12 до~о Т2 Код Е2 дото цех~ Ы ~ .= 1„, дото 1,„ г Код Я„г досо пехТ Код Я„ ь„ ,: пехт.: Рис. 6.50.
Епге одна трансляция инструкции выбора 517 6.9. Промежуточный код процедур саяе г. 'к'1 1.з саяе с Ъг Ьг саяе Г $н з саяе т. ~ Ь„ цех~: Рнс. 6.51. Трехадресные команды саяе, использующи- еся при трансляции инструкции выбора для хранения вариантов саяе, помещается пара "значение — метка", состоящая из значения константы варианта У; и А, (или указателя на запись для Тч в таблице символов). Обработка каждой инструкции саяе )ч: о, дает метку Л~ прикрепленную к коду Я;, за которым следует команда безусловного перехода доТс пехс. Когда мы добираемся таким образом до конца инструкции яти1сп, у нас все готово для генерации кода п-путевого ветвления. Считывая из очереди пары "значение — метка", можно сгенерировать последовательность трехадресных команд, показанных на рис. 6.51. Здесь с — временная переменная, хранящая значение выражения-селектора Е, а Лп — метка для инструкции по умолчанию.
Команда саяе с $; ~, представляет собой синоним для 1й т. = У, досс Ь; на рис. 6.49, но при использовании команд саяе генератору кода проще определить, что перед ним кандидат для обработки особым способом. На стадии генерации кода такая последовательность инструкций саяе может быть транслнрована в и-путевое ветвление наиболее эффективным способом в зависимости от количества значений и их диапазона. 6.8.3 Упражнения к разделу 6.8 ! Упражнение 6.8.1. Для трансляции инструкции выбора в последовательность команд саяе, как показано на рис. 6.51, транслятор должен создать список пар "значение — метка" при обработке исходного текста инструкции выбора. Это можно сделать с помощью дополнительной трансляции, которая накапливает такие пары. Набросайте синтаксически управляемое определение, которое создает список пар, генерируя при этом код инструкций Я„представляющих собой действия для каждого нз вариантов саяе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
