Рис. 8.9

как на рис. 8.10. С помощью такой двумерной структуры можно представить все семь вариантов видов. Вернемся к простому случаю. Вид

гс( I ге( т!

Рж- В. 10

\ Ьоо!

легко представить так, как показано на рис. 8.11.

На практике каждая ячейка имеет два (возможно, пустых) указателя; вертикальный указатель используется в случае структурных, объединенных и процедурных видов.

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

1) нахождение вида результата процедуры;

2) выбор поля структуры;

3) разыменование значения, т. е. замену адреса значением в ад

ресе;

4) векторизацию, т. е. преобразование значения кода т! в [ ] т! как в

/ 1 /т1 а -.- Я

Компилятор должен проверить допустимость всех видов в программе. Точное определение допустимого» видя читатель может найти в пересмотренном сообщении об Алголе 68 (55]. Помимо контекстно-свободной грамматики, генерирующей описатели видов, имеются так-

же контекстно-зависимые ограничения. Некоторые из них приводятся ниже.

1. Вид не может быть таким, чтобы его значение потребовало бесконечного объема памяти, например

пики а=>51гис( (а }ив1, !п( зесош!)

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

2. Вид не может определяться как ряд ге( н ргос, за которым сле дует он сам, например

<ло<]е Ь = геГ геГ Ь тойс Ь = ге( ргос Ь

3. Виды, составляющие объединения, не могут иметь определен ных связей, например -

т(, ге! 1п1)

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

пю(1е а=$1шс1 (&п( /, Ь Ып]) тойе Ь = к1гис( 1Ьоо1 Ь. ге! а КпЬ)

а и Ь являются примерами правильно построенных видов, но проверить это до тех пор, пока не будут встречены оба описания видов, невозможно. Следующие два описания видов представляют недопустимые виды:

тойе с = (1 л( I, Л ;) то<1е Л = 1опк с

Из изложенного ясно, что в программе один н тот же вид может быть представлен по-разному. Например, в

а н Ь имеют один и тот же вид. Аналогично виды И ишоп (геа!, т1) илЕоп (геа1, ишол (геа1, 1л1) )

Рнс. 8.11

одинаковы. Такое представление вида, как

называется написанием. Если два разных написания представляют один и тот же вид, они считаются эквивалентными. Компилятор Алгола 68 должен уметь проверять эквивалентность видов (или, точнее, их написаний). Алгоритм проверки эквивалентности видов приводится в [39].

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

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

а + Ь

значение + зависит от видов а к Ь, которые можно определить в таблице видов с помощью таблицы символов. Таблица видов может применяться также в одном из последующих проходов, связанном с комплексными видами, где требуется просматривать структуру данных, представляющую вид.

Упражнения

8.1. Каковы а) преимущества и б) недостатки Ограниченной фирмы, которую могуг иметь идентификаторы в Бейсике?

8.2. В Фортране тил идентификатора можно определить по его перкой букве. Делает ли это таблицу символов необходимой? Обоснуйте свои ответ.

8.3. Кэн упростилась бы проблема «несения идентификаторов в таблицу хеширования, если бы не было прохода, во время которого выполняется лексический анализ?

8.4. В некоторых языка* имеются такие стандартные идентификаторы, как 51 N и СО5. Опишите, каким образом эти идентификаторы могут вноситься

а) в простую таблицу хеширования;

б в таблицу символов, имеющую блочную структуру.

8.5. Рассмотрите все аргументы «з» и лпротнн» использования указателей в таблице хеширования. как это описано в разд. 8.1.

8.6. Идентификаторы хранятся в алфавитном порядке в одномерном массиве строк. Как построить уравновешенное бинарное дарено, в котором эти идентификаторы являлись бы всршиначн, чтобы при его обходе изнутри идентификаторы генерировались бы в

8.7. 8.8. 8.9.

алфавитном порядке?

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

В таблице видов компилятора Алгола (5В для каждого вида, используемою о программе. должно быть точно одно представление. Обсудите это положение. Укажите и обоснуйте, какие из следующих описаний видов нвляются в Алголе 68 недопустимыми:

(а) тойе х - ип1оп (геа1, ге( геа!)

(б) т<к!с у - иптп (ип!оп (геа1, спаг). спаг (в тойе 1 = 5(гис! (г г, !п! по)

И. 10. Правильно ли построены следующие виды длн Алгола 68:

птойе а = ге! ге! Ь гпойе Ь - ргос а

Обоснуйте гной ответ.

ГЛАВА 9 РАСПРЕДЕЛЕНИЕ ПАМЯТИ

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

9.1. СТЕК ВРЕМЕНИ ПРОГОНА

Почти каждой программе требуется какой-либо объем памяти для хранения значений переменных и промежуточных значений выражений. Например, если идентификатор описывается как

т( х

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

Б1гис{ (1п( питЬег, геа! тге, Ъоо( п } у

то компилятор обеспечивает для значения у память с объемом, достаточным для хранения в нем целого, вещественного и логического значения. В обоих этих случаях компилятор не должен испытывать затруднений в вычислении требуемого объема памяти. Точно так же, если 2 описывается как

[/ : 10] гп( г

объем памяти, необходимой для хранения всех элементов г, в 10 раз превышает объем памяти для записи одного целого значения. Однако если бы а> был описан в виде

а значение л оказалось бы неизвестным во время компиляции (возможно, оно должно быть считано программой), то компилятор не знал бы, какой объем памяти ему нужно выделить для да. Обычно да называют динамическим массивом. Такие массивы могут описываться в большинстве языков с блочной структурой: в Алголе 60, Алголе 68, ПЛ/1, но не в Паскале. Память для да должна выделяться во время прогона, и на этой стадии требуется, чтобы п имело значение. Память, выделяемая во время компиляции, обычно называется статической, а во время прогона - динамической. В большинстве компиляторов память для массивов (даже имеющих ограничения констант) выделяется во время прогона, поэтому она считается динамической.

Память нужна также для промежуточных результатов и констант. Например, при вычислении выражения а + схй сначала вычисляется СХ(1, причем значение запоминается в машине, а затем выполняется сложение. Память, используемая для хранения промежуточных результатов, называется рабочей. Рабочая память может быть статической или динамической.

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

ШТЕОЕК А. В, X. V

выделяется память, как это показано на рис. 9.1. Такая схема не учитывает тот факт, что рабочая память используется неоднократно и весьма неэффективна (н смысле использования объема памяти) для языка с блочной структурой.

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

А В X Г

заны

этапах ее выполнен н

снимки> стека

пР° гРкаммь с :омощыо рис. 9.2, где пока-ека времени прогона на различных

»

т геа! л.

Ьсрв 1*п11-, II

епй;

Ь*яш сЬаг/7.

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

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

]ис. 9.3

ДИСПЛЕЙ

СТЕК

Р!!С. 9.1