ла достойного воплощения1. Чтобы охватывать широкий класс языков, объектный язык должен быть написан на довольно низком уровне с целью его эффективной реализации на всех машинах. Однако было бы лучше, если бы объектный язык предназначался для трансляции конкретного языка высокого уровня или для реализации на конкретной машине. Так, большинство компиляторов, работающих на машине М1Л5, в качестве объектного языка применяют СТЬ (общий объектный язык). С другой стороны, на некоторых машинах, где в качестве объектного языка употреблялись ОСООЕ или 1ЫТСООЕ, реализован ВСР1. [49], а Бранкар и др.-[10] спроектировали объектный язык для Алгола 68, который можно реализовать на многих машинах. В последнем случае фронтальной части компилятора нужно иметь кое-какую информацию об объектной машине, в частности сведения о том, сколько места требуется для целочисленного значения, вещественного значения и т. д. Это связано с тем, что распределение памяти происходит до выработки объектного языка. Можно, конечно, распределять память и без этой зависимой от машины информации, но тогда обращение с адресами во время прогона, неоправданно усложнятся.

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

Упражнении

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

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

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

7.4. Назовите языковое средство, удобное для применения при проходе компилятора, выполняемого в обратном порядке.

7.5. Приведите аргументы -зав и <протнв> удобочитаемых промежуточных языков.

7.6. Как вы дчмаете, должен ли компилятор выдавать сообщение о проходе, в котором пи обнаружил ищнбку программирования?

7.7. Компилятор Алгола 68 для МС15 имее> .переменное» число проходов. Приведите аргументы против такого подхода.

7.8- Как чожеп повлиять на проект компилятора машина, для которой он предназначается?

7.9. Сели бы основном целью при проектировании компилятора было обеспечение его переносимое!к, то как яп могло бы отразиться на его обшей структуре?

7.10. Гели бы основной целью при проектировании компилятора было обеспечение его на дежности, то как зго могло бы отразиться на ею обшей структуре?

Можно указать на одни из ранних объектных языков ДЛМО. разработанный к использованный для создания переносимых компиляторов в Институте прикладной мате матики АН СССР в 1%Э- 1973 гг. с языков АЛГАМС, Алгол 60. Фортран на ЭВМ М-20. БЭСМ-6, и ряд специализированных ЭВМ. - Примеч. р*. ,

Глава 8

ТАБЛИЦЫ СИМВОЛОВ И ВИДОВ

Информацию о типе (или виде) идентификаторов и т. п. синтаксический анализатор хранит с помощью таблиц, символов. Ими также пользуется генератор кода для хранения адресов значений во время прогона. В языках, имеющих конечное число типов, информацией о типе может быть просто целое число, представляющее этот тип, а в языках, имеющих потенциально бесконечное число типов (видов), таких, как Алгол 68 или Паскаль, - указатель на таблицу видов, элементами которой являются структуры, представляющие вид. В настоящей главе мы сначала рассмотрим таблицы симнолов, а затем таблицы видов.

8.1. ТАБЛИЦЫ СИМВОЛОВ

Таблица символов для таких языков, как Фортран или Бейсик, довольно проста. В Фортране, например, имеется только конечное (и небольшое) число типов, и каждый из них может быть представлен целым числом. Например, тип «целый» представляется посредством /, а тип «вещественный» *>- посредством 2. В этом случае таблица символов имеет вид массива с элементами

В Фортране идентификаторы не должны превышать шести (а в Бейсике двух) литер, так что в таблице символов хранятся сами идентификаторы, а не какое-либо их представление, полученное после лексического анализа.

С таблицей символов ассоциируются следующие действии:

1. Идентификатор, встречающийся впервые (т. с. его еще нет н таблице), помещается в таблицу вместе со своим типом. Если иденти фикатору не предшествует явное описание, такое, как

КЕМ X

его тип, можно вынести на основании начальной буквы (с / по Л/ включительно подразумевается целый, в других случаях - вещественный).

2. Если встречается идентификатор, который уже был помещен в таблицу, его тип определяется по соответствующей з-аписн в эти таб лице.

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

5 З..Н 17з.ч

тификатора а таблице нет. то требуется ее полный просмотр (элемент за элементом); но даже в тех случаях, когда идентификатор находится в таблице, поиск в среднем охватывает ее половину. Такой поиск в таблице обычно называют линейным. Линейный поиск в больших таблицах может оказаться длительным процессом. Если бы идентификаторы были расположены в алфавитном порядке, то поиск выполнялся бы гораздо быстрее за счет последовательного разбиения таблицы пополам до тех пор, пока соответствующий идентификатор не будет найден или не будет показано его отсутствие (двоичный метод поиска). Однако на сортировку записей по порядку каждый раз при добавлении новой записи уходило бы очень много времени, что, по-видимому, существенно снизило бы достоинства этого метода (конечно, если число поисков не превышало бы намного число включений в таблицу). Другое решение проблемы - использование метода хеширования.

Чтобы познакомиться с идеей хеширования, предположим, что Фортран допускает использование идентификаторов, содержащих только одну букву. Тогда число возможных идентификаторов составит 26, и таблица символов примет вид массива, состоящего из 26 элементов - по одному на каждый идентификатор. Это означает, что для проверки наличия записи в таблице для какого-либо конкретного идентификатора никакого поиска не требуется, поскольку любая запись для идентификатора А служит первым элементом таблицы к т. д. Такой метод подошел бы для Бейсика, в котором вс"е-ндентнфикаторы имеют обычно одну из следующих форм:

1е(1ег регсеп!

Это дает только 338 возможных идентификаторов. Для Фортрана число возможных идентификаторов, хотя и конечно, но очень велико, -а для Алгола 60, Алгола б8 или Паскаля - бесконечно.

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

ся таблицей хеширования, а функция отображения - функцией хеширования. Таблица хеширования обрабатывается циклично, т. е. если поиск не завершается к моменту достижения конца таблицы, он должен быть продолжен с ее начала.

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

САК 1ЮО САВ Л55

Таблица 81

САК 000

САВ ЕСС

таблица принимает вид табл. 8,1; позиции идентификаторов зависят от порядка их внесения в таблицу. Если идентификатор не может быть внесен в ту позицию, которая задается функцией хеширования, происходит так называемый конфликт. Чем больше таблица (и меньше число идентификаторов, отображающихся на каждую запись), тем меньше вероятность конфликтов. При наличии в программе только вышеперечисленных идентификаторов и использовании рассмотренной функции хеширования таблица заполнялась бы неравномерно, и имела бы место кластеризация. Программисты иногда употребляют идентификаторы, начинающиеся с определенных букв алфавита. В этом случае функция хеширования может создавать конфликты, и поэтому она весьма проста. Функция, которая зависела бы от последней литеры идентификатора, вероятно, меньше способствовала бы кластеризации или же функция хеширования могла бы использовать все литеры [1 идентификаторе для вычисления соответствующего элемента таблицы. Конечно, чем сложнее функция, тем больше времени потребуется для ее вычисления при внесении в таблицу идентификатора или при поиске конкретного идентификатора в таблице, и это следует соотносить со временем, которое экономится за счет более коротких поисков в результате меньшей кластеризации.

До сих пор мы выходили из конфликтов, просто проверяя один за другим элементы таблицы (цикличным образом) до тех пор, пока не находили идентификатор или пустой элемент. Чтобы найти другой элемент в таблице, когда тот, на,который указывает функция хеширования, уже заполнен, можно воспользоваться и иными методами. Нам нужно правило, последовательное применение которого позволило бы (при необходимости) просмотреть все записи таблицы, прежде чем какая-либо из них встретится вторично. Действие, выполняемое функ-

цией хеширования, обычно называется первичным хешированием, а вычисление .последующих адресов в таблице - вторичнгм хешированием, или перехешированием. Функция перехешнрования, рассматриваемая до сих пор, предполагает просто добавление единицы (циклично) к адресу таблицы. Эта функция, как и все функции перехеширования, обладает следующим свойством: если п *- некий адрес в таблице, а р - число элементов в таблице,

а. гейаяЛ (л). все являются разными адресами, и

(л) = п

Описанная выше функция перехешировання определяется процедурой

ргос геЛтЛ = (Ы п) !п1: И п<р (Ьеп п + 1 <1ке / М

У этой функции есть тенденция создавать в таблице кластеры в той же мере, в какой вероятность кластеризации возрастает в связи с перехешнрованием. Весьма желательно, чтобы функция перехеширования могла бы находить адрес подальше от того, с которого она начала. Если бы число элементов в таблице было простым числом, то вместо единицы функция пере хеширования добавляла бы к адресу любое положительное целое число Н, такое, что й<р; в результате мы бы имели

ргос геАа$А/=(т( «) т(:

II п + й<р (Ьеп п + А

• е!я п + Л-р И

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

Более подробную информацию о хешировании и перехешировании читатель может найти в [24]. Мы объяснили лишь основной принцип, а теперь рассмотрим другие подходы к решению данной проблемы. Например, можно полностью избежать перехеширования путем сцепления элементов, которые переполняют таблицу (см. рис. 8.1), однако при этом придется выделять место для указателей.

Еще одна структура для записи упорядоченных элементов-бинарное дерево. Бинарное дерево, показанное на рис. 8.2, состоит из Пяти элементов (или вершин), каждый из которых содержит идентификатор, его тип и т. д., и двух указателей на другие вершины. Это дерево может и не иметь указателей (в случае вершин, содержащих

виз, НАОООСК. и мои&Е).

По определению бинарное дерево включает конечное множество вершин. Оно может быть пустым или состоять из корни (вершина, содержаш.ая ЬЕМОК) и двух отдельных бинарных деревьев, которые называются соответственно левым и правым поддеревьями корня. Бинарное дерево, не имеющее вершин, называется пустым бинарным деревом и на схеме обозначается как перечеркнутый прямоугольник. Поддерево вершины обозначается с помощью указателя.

О бинарном дереве, изображенном на рис. 8.2, говорят, что оно имеет глубину 2, а вершина, содержащая В1/5, находится на расстоя-

Рис. 8.1

!нс. 8.2

нии 2 от вершины, содержащей /ГМОМ Вершину, содержащую ЕОО. называют наследником вершины; содержащей ЕМОЫ.

Это бинарное дерево упорядочено (в алфавитном порядке) слева направо, точнее, его вершины располагаются по алфавиту в порядке их обхода изнутри. Кнут [3-7] приводит следующий (рекурсивный) алгоритм для обхода дерева изнутри: пересечь левое поддерево, пройти корень, пересечь правое поддерево. К бинарному дереву всегда можно добавить новую вершину, поместив ее в соответствующее место. Время поиска вершины зависит только от глубины дерева. Это время минимально (в среднем) для дерева, содержащего заданное число вершин, если оно уравновешено, т. е. если расстояния от всех конечных вершин (вершин, не имеющих наследников) до корни отличаются не более чем ня одну вершину. Дерево на рис. 8.2 уравновешено, а дерево на рис. 8.3 - нет.

Бинарное дерево можно строить, добавляя по одной вершине. Первой вершиной служит корень. К нему справа или слева добавляется следующая вершина и т.д. Уравновешенность полученного дерева зависит от порядка включения вершин. Если дерево не уравновешено, то должно существовать другое уравновешенное бинарное дерево с тем же порядком обхода всришн. Существуют довольно эффективные алгоритмы уравновешивания деревьев (замены неуравновешенного дерева уравновешенным), и в некоторых случаях имеет смысл производить уравновешивание после каждого добавления вершины. В -основном это определяется относительной частотой поисков и добавлений.

Расплачиваться за использование бинарного дерева в качестве таблицы символов или словаря нам приходится дополнительным объе-