Внешний и внутренний интерфейсы

Нетрудно заметить, что одни фазы компиляции в большей степени зависят от входного языка и в меньшей степени от целевого. Другие фазы, наоборот, в меньшей степени зависят от входного языка и в большей степени от целевого. Например, лексический, синтаксический, видозависимый анализ и некоторые оптимизации не слишком значительно зависят от целевого языка. Эти фазы иногда объединяют вместе под названием внешний интерфейс или front-end. Front-end подразумевает также обработку ошибок, которые могут встретиться на перечисленных фазах (вопросы обработки ошибок обсуждаются в лекции 9). Остальные фазы, несущие на себе отпечаток целевого языка, называются внутренним интерфейсом (back-end).

Таким образом, если мы хотим иметь компиляторы некоторого языка на разных платформах, то наша задача сводится к написанию нескольких back-end’ов без изменения front-end’а. С другой стороны, для создания многоязыкового компилятора достаточно написать несколько front-end’ов.

Просмотры

Обсудим еще один важный термин, а именно, просмотр (passes). Под просмотром (или проходом) компилятора понимается процесс обработки всего, возможно, уже преобразованного, текста исходной программы.

Одна или несколько фаз компиляции могут выполняться на одном просмотре. Например, лексический анализ и синтаксический анализ часто выполняются на одном просмотре, т.е. синтаксический анализатор может обращается к лексическому анализатору за очередной лексемой лишь по мере необходимости. С другой стороны, некоторые оптимизации могут выполняться на нескольких просмотрах.

Передача информации между просмотрами происходит в терминах так называемых промежуточных языков. Таким образом, если компилятор состоит из N просмотров, то должно быть определено N–1 промежуточных языков. Каков этот промежуточный язык, зависит от разработчиков компилятора. Обычно программа на промежуточном языке представляет собой синтаксическое дерево и, возможно, какие-то внутренние таблицы компилятора.

Желательно иметь относительно мало просмотров, т.к. для чтения программы на одном промежуточном языке и записи ее на другом промежуточном языке может занимать довольно много времени. С другой стороны, объединяя несколько фаз в один просмотр, мы должны помнить о том, что иногда мы не можем выполнить некоторую фазу, не получив информацию из предыдущих фаз. Например, C# позволяет использовать имя метода до того, как он был описан. Понятно, что мы не можем выполнить видозависимый анализ до тех пор, пока мы не будем знать имена и типы всех методов объектов. Таким образом, эти задачи должны решаться на разных просмотрах.

8.Прямые методы трансляции. Польская запись. Алгоритм получения обратной польской записи. Вычисление арифметических и логических выражений с использованием обратной польской записи.

Первые процедурно-ориентированные языки программирования высокого уровня предназначались для решения инженерных и научно-технических задач, в которых широко применяются методы вычислительной математики. Значительную часть программ реше­ния таких задач составляют арифметические и логические выраже­ния. Поэтому трансляцией выражений занимались, очень многие исследователи и разработчики трансляторов. Начиная с 1952 г., когда была опубликована работа Г. Рутисхаузера [51], в которой впервые предлагался метод трансляции арифметических выраже­ний, разработано много различных методов. Сейчас классическим стал метод трансляции выражений, основанный на использовании промежуточной обратной польской записи, названной так в честь польского математика Яна Лукашевича, который впервые исполь­зовал эту форму представления выражений в математической ло­гике. Однако в существующих трансляторах используются и дру­гие методы.

Рассмотрим сущность обратной польской записи на примере. Простое арифметическое выражение с вещественными перемен­ными

a + b´с — d/{а+Ь)

можно графически представить в виде дерева (рис. 4.1). Узлы дерева соответствуют операциям, а ветви—операндам. Левая ветвь, исходящая из узла, отвечает левому операнду, а правая—­правому. В каждой ветви операциям, которые выполняются рань­ше, соответствуют нижележащие узлы. Верхний узел (корень де­рева) отвечает операции, которая выполняется последней. С него начинается построение дерева.

Если, начав с нижнего листа самой левой ветви дерева, обойти все листья и узлы дерева так, чтобы ветви рассматривались слева направо, а узел рассматривался только после обхода всех исходящих из него вет­вей, как показано стрелками на рис. 4.1, то последовательность просмотра листь­ев и узлов даст обратную польскую запись исходного выражения:

abc´+dab+/-.

Эту бесскобочную запись называют также постфиксной записью, потому что знак каждой операции записан после соответствующих операндов. Заметим, что в обратной польской записи опе­ранды располагаются в том же порядке, что в исходном выражении, а знаки операций при просмотре записи слева направо встречаются в том порядке, в котором нужно выполнять соответствующие действия. Отсюда вытекает основное преимущество обратной польской записи перед обычной записью выражений со скобками: выра­жение можно вычислить в процессе однократного просмотра слева направо.

Правило вычисления выражения в обратной польской записи состоит в следующем. Обратная польская запись просматривается слева направо. Если рассматриваемый элемент—операнд, то рас­сматривается следующий элемент. Если рассматриваемый эле­мент—знак операции, то выполняется эта операция над операн­дами, записанными левее знака операции. Результат операции записывается вместо первого (самого левого) операнда, участвовавшего в операции. Остальные элементы (операнды и знак опера­ции), участвовавшие в операции, вычеркиваются из записи. Про­смотр продолжается.

В результате последовательного выполнения этого правила бу­дут выполнены все операции, имеющиеся в выражении, и запись сократится до одного элемента—результата вычисления выра­жения.

Выполнение правила для нашего примера приводит к последо­вательности строк, записанных во второй графе табл. 4.3. Рассмат­риваемый на каждом шаге процесса элемент строки отмечен круж­ком. В третьей графе таблицы записаны соответствующие действия, а в четвертой графе—эквивалентные команды трехадресной ма­шины.

Таблица 4.3

ПРИМЕР ВЫЧИСЛЕНИЯ ВЫРАЖЕНИЯ В ОБРАТНОЙ ПОЛЬСКОЙ ЗАПИСИ

Результат выполнения операции фиксируется в виде рабочей переменной вида r_j После очередной операции рабочая переменная r₁ или r₂ вычеркивается освободившуюся рабочую переменную можно использовать вновь для записи результата операции. Ис­пользование каждый раз свободной рабочей переменной с мини­мальным номером экономит количество занятых рабочих перемен­ных. Такой пример экономии рабочих ячеек приведен в табл. 4.3. Это же правило используют в трансляторах.

Аналогичным способом можно записывать и вычислять булев­ские выражения. Простое булевское выражение

а+b > — 5Ùz — d = 1+q­2

представляется деревом (рис. 4.2), обход которого по пути, пока­занному стрелками, дает обратную польскую запись

аb+5 ИЗ >zd—1q2­+=Ù,

в которой знак минус перед числом 5 в исходной записи, обозна­чающий одноместную операцию, заменен знаком операции ИЗ (из­менение знака). Вообще при трансляции во избежание ошибок нужно отличать знак минус как знак одноместной операции от того же знака, обозначающего двухместную операцию. В реаль­ных трансляторах выражения вида — а заменяются выражениями вида 0— а или знак минус в обратной польской записи снабжается признаком одноместной операции. Впредь минус, являющийся зна­ком одноместной операции, будем обозначать знаком операции ИЗ.

Рассматриваемое булевское выражение можно вычислить по общему правилу вычисления выражений в обратной польской за­писи. В табл. 4.4 выписаны только строки, отвечающие состояниям, в которых выполняются действия, и строка сокращается.

Существует еще одна форма бесскобочной записи выражений, которая также иногда применяется в трансляторах. На рис. 4.3 изображено то же дерево, что и на рис. 4.1. Если, начав с верхнего узла, обойти все узлы и листья дерева так, чтобы верхний узел рас­сматривался раньше нижнего и сразу после рассмотрения очеред­ного узла просматривались слева на­право исходящие из него ветви, как по­казано стрелками на рис. 4.3, то полу­чится следующая бесскобочная запись выражения

— + а ´ bc/d + ab.

Такую запись называют прямой поль­ской записью. Как и в обратной поль­ской записи, операнды расположены здесь в том же порядке, что в исходном выражении. Однако знаки операций те­перь записаны перед операндами, поэто­му такую запись называют также пре­фиксной. Выражение, записанное в пря­мой польской записи, вычисляется справа налево. Поскольку об­щий порядок работы компилятора обычно слева направо, прямую польскую запись применяют относительно редко.

Поскольку существует относительно несложный алгоритм пе­ревода обратной польской записи в машинные команды, для пол­ного решения задачи трансляции выражений в языках высокого уровня типа Алгол-60 и Фортран достаточ­но перевести выражение в обратную поль­скую запись.

Известно несколько методов получения обратной польской записи. Обзор различ­ных методов дан в книге Б. Ренделла и Л. Рассела «Реализация Алгола-60» [26]. Один из наиболее эффективных методов предложен в 1960 г. голландским ученым Е. В. Дикстрой.

Метод Е. В. Дейкстра основан на исполь­зовании стека с приоритетами, позволяю­щего изменить порядок следования знаков операций в выражении так, что получается обратная польская запись. Простейший ва­риант этого метода применим только к про­стым арифметическим и логическим выра­жениям, содержащим простые переменные, знаки арифметических и логических опера­ций, знаки операций отношения и круглые скобки.

Каждому ограничителю, входящему в выражение, присваивает­ся приоритет (табл. 4.5). Для знаков операций приоритеты возра­стают в порядке, обратном стар­шинству операций. Скобки имеют низший приоритет.

Арифметическое или логиче­ское выражение рассматривается как входная строка символов. Входная" строка просматривается слева направо. Операнды перепи­сываются в выходную строку, а знаки операций помещаются вна­чале в стек операций (рис. 4.5). Если приоритет входного знака равен нулю или больше приори­тета знака, находящегося в вер­шине стека, то новый знак добав­ляется к вершине стека. В противном случае из стека «выталки­вается» и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами,большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека.

Особенности имеет лишь обработка скобок. Открывающая круг­лая скобка, имеющая «особый» приоритет нуль, просто записы­вается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки.

ПЕРЕВОД В ОБРАТНУЮ ПОЛЬСКУЮ ЗАПИСЬ АРИФМЕТИЧЕСКОГО ВЫРАЖЕНИЯ

Закрывающая скобка имеет приоритет 1, не превосходящий приоритета любой операции. Поэтому появление закрывающей скобки вызывает выталкивание всех знаков до ближайшей откры­вающей скобки включительно. В стек закрывающая скобка не за­писывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся.

После просмотра всех символов входной строки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.

Пример 1. Перевести в обратную польскую запись выражение a+b´c—d/(a+b).

Решение. Решение показано в табл. 4.6.

Окончательная выходная строка в табл. 4.6, как нетрудно убедиться, совпадает с обратной польской записью того же вы­ражения, полученной обходом дерева, изображенного на рис. 4.1.

9.Структуры хранения информации. Организация таблиц символов. Поиск в таблицах. Хеш функции и методы хешимирования. Списки и цепочки перемешивания.

Наиболее употребительной структурой данных в трансляторах являются таблицы. В частности, в таблицах хранят основные символы входного языка,используемые для распознавания синтаксических конструкций, а также коды операций машины или «заготовки» машинных команд, необходимые для генерирования команд объектной программы. Это постоянные таблицы, составляемые заблаговременно. Одной из основных таблиц при трансляции является таблица имен, иногда ее заменяют две таблицы: таблица переменных и таблица меток. Все это временные таблицы, составляемые в ходе трансляции.

Обычно таблицы отображаются в памяти машины вектором, но иногда используют также списки или комбинацию векторов со списками. Напомним, что записи включаются в таблицу и выбираются из таблицы по ключу. До половины всего времени работы транслятора, а иногда и больше, расходуется на поиск в таблицах. Достаточно вспомнить, что в трансляторе ТА-2М, структура которого рассматривалась в 1.3, только постоянные таблицы имеют объем 3000 машинных слов из общего объема транслятора 20000 слов. В некоторых трансляторах объем постоянных таблиц еще больше. Например, синтаксический транслятор СТ-2 для языка Алгэм на машине «Минск-22» имеет объем синтаксических таблиц 6000 слов при 4000 командах, составляющих программу транслятора.

Задача поиска состоит в определении по заданному ключу адреса хранения табличной записи, если имеется такая запись в таблице. Эта задача решается по-разному в различных таблицах в зависимости от способа организации таблицы. Основной характеристикой способа организации таблицы является среднее время поиска одной записи. Это время пропорционально средней длине

поиска, под которой понимают среднее количество записей, просматриваемых для отыскания требуемой записи.