Реферат: Проектирование трансляторов

прогона, статическая же может распределяться во время компиляции.

Объем статической рабочей памяти, который должен выделяться  каж-

дой рамке, определяться не рабочей  памятью,  требуемой  в  конце

каждого блока (обычно она является нулем), а  МАКСИМАЛЬНОЙ  рабо-

чей памятью, требуемой в любой точке внутри блока. Для  статичес-

кой рабочей памяти эту величину можно установить в процессе  ком-

пиляции, если в фазе распределения памяти мы ассоциируем с  рабо-

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

них указывает на текущую границу статической  рабочей  памяти,  а

другой - на максимальный размер, до которого она выросла при  ра-

боте с текущим блоком. Именно значение  этого  второго  указателя

при выходе из блока и дает  объем  статического  рабочего  стека,

включаемого в соответствующую рамку.

                    2. ПРЕДСТАВЛЕНИЕ МАССИВОВ

                    2.1 Прямоугольные массивы

     Простейшие массивы  (одномерные) естественно  представляются

векторами, т.к. они хорошо согласуются в том смысле, что для  по-

лучения относительного адреса элемента массива в векторе надо вы-

честь нижнюю границу по измерению из индекса элемента.

     Из многомерных массивов рассмотрим сначала прямоугольные. Их

также возможно представлять векторами. Для реализации выборки или

засылки в массив надо получить относительный адрес  нужного  эле-

мента в векторе по значениям индексов этого элемента.

     Предполагая линейное расположение всех точек n-мерного прос-

транства (n - размерность), соответствующего  массиву,  мы  можем

считать первые измерения старшими  и  тогда  рядом  располагаются

элементы, соседние  по  последнему  измерению  -  так  называемый

ПРЯМОЙ порядок, либо наоборот -  ОБРАТНЫЙ  порядок.  Например,  в

языке Алгамс поддерживается прямой порядок, в Фортране  -  обрат-

ный, а в АЛГОЛе-60 представление многомерных  массивов  никак  не

фиксируется.

     Когда в программе выбирается конкретный элемент массива, его

адрес внутри динамической части  должен  вычисляться  в  процессе

прогона. Рассмотрим массив:

     [1:10,-5:5] int Table

     Будем считать, что элементы  записаны  в  лексикографическом

порядке индексов, т.е. элементы хранятся в следующем порядке:

     Table[1,-5], Table[1,-4]  ......... Table[1,5],

     Table[2,-5], Table[2,-4]  ......... Table[2,5],

                                   .

                                   .

                                   .

     Table[10,-5], ...................... Table[10,5]

     Адрес конкретного элемента вычисляется как смещение по отно-

шению к базовому адресу (адресу первого элемента) массива:

     ADDR(Table[I,J])=ADDR(Table[l1,l2])+(u2-l2+1)*(I-l1)+(J-l2)

     Здесь l1 и u1 - нижняя и верхняя границы первой  размерности

и т.д. и считается, что каждый элемент массива  занимает  единицу

объема памяти.

     Для трехмерного массива соответствующая формула имеет вид:

     ADDR(Table[I,J,K])=ADDR(Table[l1,l2,l3])+

                        (u2-l2+1)*(u3-l3+1)(I-l1)+

                        (u3-l3+1)*(J-l2)+K-l3

     Выражение (ui-li+1) задает число различных  значений,  кото-

рые может принимать i-индекс.

     Значение произведения (u2-l2+1)*(u3-l3+1)  представляет  со-

бой число различных пар значений, которые могут принимать  второй

и третий индексы, а также расстояние  между  элементами  массива,

отличающимися только на одну единицу в первом индексе.

     Расстояние между элементами, отличающимися на 1 в i-индексе,

известно как i-й шаг. Так, в приведенном выше примере первый  шаг

s1 состовляет (u2-l2+1)*(u3-l3+1). Второй шаг s2 равен (u3-l3+1).

Третий шаг s3 составляет 1.

     Ясно, что вычисление адресов элементов  массива  в  процессе

прогона может занимать много времени. Поэтому  рекомендуется  при

программировании по возможности  избегать  выборки  из  массивов,

особенно из многомерных. Тем не  менее,  шаги  могут  вычисляться

только один раз и храниться в статической части массива наряду  с

границами. Такая статическая информация часто называется описате-

лем массива. В этой же части массива наряду с  нижней  и  верхней

границами и шагом для каждой размерности может  храниться  указа-

тель на элементы массива. Нижняя и верхняя границы требуются  для

проверки правильности нахождения индексов в  пределах  границ,  а

шаги и нижние границы - при обращении к конкретным элементам мас-

сива.

   2.2 Обращение к элементам массива с помощью векторов Айлифа

     Айлиф разработал свой способ обращения к элементам массивов.

Этот способ требует для хранения массива больше памяти,  но  зато

обращение к элементу выполняется быстрее. Вместе с каждым  масси-

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

ный как

     B[4:6,-2:1,0:1]

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

20.6.

              ┌──────┐                              ─ ─ ─ ─   i

            С │    ──┼───────────────────────────> │       │ (0)

              └──────┘                         D    ─ ─ ─ ─

                                                   │       │ (1)

                                                    ─ ─ ─ ─

                                                   │       │ (2)

                                                    ─ ─ ─ ─

                                                   │       │ (3)

                                                   ┌───────┐

                     ┌─────────────────────────────┼──     │  4

                     │                             ├───────┤

                     │                    ┌────────┼──     │  5

                     │                    │        ├───────┤

                     │                    │        │       │  6

                     │                    │        └────┼──┘

                     │                    │             │

                     │                    │             │ j

                     │                    │             │

                     │                    │             │

                     │                    │             └──────┐

       E             │       F            │     G              │

            ┌─────┐  │           ┌─────┐  │           ┌─────┐  │

  ┌─────────┼─    │  │ ┌─────────┼─    │  │ ┌─────────┼─    │  │-2

  │         ├─────┤  │ │         ├─────┤  │ │         ├─────┤  │

  │   ┌─────┼─    │  │ │   ┌─────┼─    │  │ │   ┌─────┼─    │  │-1

  │   │     ├─────┤  │ │   │     ├─────┤  │ │   │     ├─────┤  │

  │   │   ┌─┼─    │<─┘ │   │   ┌─┼─    │<─┘ │   │   ┌─┼─    │<─┘ 0

  │   │   │ ├─────┤    │   │   │ ├─────┤    │   │   │ ├─────┤

  │   │   │ │   │ │    │   │   │ │   │ │    │   │   │ │   │ │    1

  │   │   │ └───┼─┘    │   │   │ └───┼─┘    │   │   │ └───┼─┘

  │   │   │     │      │   │   │     │      │   │   │     │

H┌─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬────┬───┐

 │ │ │ │ │ │ │   │    │ │ │ │ │ │ │   │    │ │ │ │ │ │ │    │   │

k└─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴────┴───┘

  0 1 0 1 0 1  0    1  0 1 0 1 0 1  0    1  0 1 0 1 0 1   0   1

     Рис. 20.6 Схема обращения к элементам массива с помощью век-

торов Айлифа

     Пусть запись вида (B+5) означает содержимое по  адресу  B+5.

Тогда к элементу B[i,j,k] можно обратиться следующим образом:

     (((C)+i)+j)+k

     При этом выбирается содержимое ячейки C и к нему прибавляет-

ся значение индекса i, затем по полученному  в  результате  этого

адресу выбирается содержимое, которое дает указатель  на  следую-

щий более низкий уровень, и т.д.

     Важно отметить, что при данном способе обращения к  элементу

массива не требуется выполнения операций умножения. Вместе с  тем

в рассмотренном примере, кроме вектора для хранения массива, тре-

буется еще один вектор длины 3 и три вектора длины 4, и таким об-

разом, вместо 24 элементов требуется 39. Этот  метод  оказывается

наиболее экономичным, когда диапазоны изменения индексов увеличи-

ваются от первого к последнему. Наименее всего этот метод  эффек-

тивен, когда первый индекс имеет наибольший диапазон изменения.

     В приведенном примере не производилось проверки  корректнос-

ти индекса. Это может быть достигнуто  путем  хранения  вместе  с

каждым элементом вектора Айлифа граничной пары для  соответствую-

щего индекса. Правда, в случае прямоугольного массива  это  могло

бы оказаться неэкономичным. У каждого из элементов векторов E,F и

G в рассматриваемом примере были бы  одинаковые  граничные  пары.

Однако следует обратить внимание на то, что с каждым из этих эле-

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

ло бы возможность, используя векторы Айлифа, обращаться к  масси-

вам со значительно более сложной структурой.

     Так, например, на рис. 20.7 показан набор  векторов  Айлифа,

позволяющих обращаться к трехмерному массиву,  элементы  которого

хранятся в следующем порядке:

     B[4,-1,-1]      B[5,1,2]      B[6,0,0]

     B[4,-1, 0]      B[5,2,2]      B[6,0,1]

     B[4,-1, 1]      B[5,2,3]      B[6,0,2]

     B[4,-1, 2]      B[5,3,2]      B[6,0,3]

     B[4, 0, 0]      B[5,3,3]      B[6,0,4]

     B[4, 0, 1]      B[5,3,4]      B[6,0,5]

     B[4, 0, 2]      B[5,3,5]

     B[4, 0, 3]

     B[4, 0, 4]

     B[4, 0, 5]

     B[4, 0, 6]

                ┌─────┬─┬─┐

                │     │4│6│

                └──┼──┴─┴─┘                        ─ ─ ─ ─ ─

                   └────────────────────────────> │          │

                                                   ─ ─ ─ ─ ─

                                                  │          │

                                                   ─ ─ ─ ─ ─

                                                  │          │

                                                   ─ ─ ─ ─ ─

                                                  │          │

                                                  ┌────┬──┬──┐

                   ┌──────────────────────────────┼──  │-1│ 0│

                   │                              ├────┼──┼──┤

                   │                     ┌────────┼──  │ 1│ 3│

                   │                     │        ├────┼──┼──┤

                   │                     │        │    │ 0│ 0│

                   │                     │        └─┼──┴──┴──┘

                   │                     │          │

                   │                     │          │

                   │      ─ ─ ─ ─ ─ ─    │    ┌─────┘

                   │     │           │<──┘    │

                   │     ┌─────┬──┬──┐        │

                   │ ┌───┼─    │ 2│ 2│        │

     ┌─────┬──┬──┐ │ │   ├─────┼──┼──┤     ┌─────┬───┬──┐

   ┌─┼─    │-1│ 2│ │ │┌──┼─    │ 2│ 3│    ┌┼─    │  0│ 5│

   │ ├─────┼──┼──┤ │ ││  ├─────┼──┼──┤    │└─────┴───┴──┘

   │ │     │ 0│ 6│<┘ ││  │     │ 2│ 5│    │

   │ └───┼─┴──┴──┘   ││  └─┼───┴──┴──┘    │

   │     │         ┌─┘│    │              │

   │     │         │ ┌┘  ┌─┘         ┌────┘

   │     │         │ │   │           │

   │     │         │ │   │           │

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐

│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │

└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

     Рис. 20.7 Пример векторов  Айлифа  для  трехмерного  массива

сложной структуры

         2.3 Замечания по поводу "разреженных" массивов

     В некоторых случаях, при хранении массивов по  схеме  векто-

ров Айлифа или подобной ей схеме  с  использованием  дескрипторов

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

ний элементов. В этих случаях можно рассматривать пару  "информа-

ционный элемент" - "значения индексов" как элемент информационно-

го множества, а задание значения (нетривиального) элементу масси-

ва - как пополнение множества,  а  задание  неопределенного  (или

тривиального) значения - как удаление элемента из множества.

     Представление таких "неполных" (или "разреженных")  массивов

реализуется как представление множеств.

            3. ОРГАНИЗАЦИЯ ПАМЯТИ ВО ВРЕМЯ ТРАНСЛЯЦИИ

                3.1 Проблемы распределения памяти

     Распределение памяти для определенных программистом перемен-

ных в языках высокого уровня обычно  бывает  простым.  Часто  ло-

кальные переменные размещаются  в  памяти  непосредственно  после

соответствующей программной единицы. Однако для современных ЭВМ и

ОС, требующих разделения неизменяемой и изменяемой  частей  прог-

раммы, возникает необходимость помещать  локальные  переменные  в

отдельные области памяти.

     Основные проблемы возникают тогда, когда нужно  распределить

память для временных переменных, т.е. промежуточных  результатов,

потребность в которых появляется при компиляции.  Эти  переменные

определяются не в программе на входном языке, а компилятором. Ре-

шение о том, сколько для них требуется памяти и как ее  распреде-

лить, полностью зависит от компилятора.  Поэтому  нужен  алгоритм

как можно более эффективного размещения в памяти этих переменных.

Здесь под эффективностью обычно понимается стремление минимизиро-

вать объем используемой памяти.

     Распределение памяти становится нетривиальной задачей в  том

случае, когда у ЭВМ существует более чем один уровень памяти.

     У многих машин имеются ограниченные  наборы  быстрых  регис-

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

доступом, либо иными, более удобными свойствами. Эффективное  ис-

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

алгоритмы оптимального размещения переменных в быстрых регистрах.

        3.2 Распределение памяти для временных переменных

     Алгоритмы генерации команд не касаются распределения  памяти

для временных переменных. Можно считать, что эти алгоритмы  берут

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

имен каждый раз, когда, согласно алгоритму, требуется новая  вре-

менная переменная. Алгоритм распределения памяти  должен  размес-

тить эти переменные  в  памяти  так,  чтобы  потребовалось  мини-

мальное число ячеек памяти.

     ИНТЕРВАЛОМ для переменной называется отрезок  времени  между

начальным определением этой переменной и ее последним использова-

нием. Очевидно, переменные, интервалы для которых совсем не  свя-

заны, могут быть совмещены в памяти.

     Рассмотрим набор переменных V1, V2, V3, ..., Vn. Для  каждой

переменной Vi определена команда ST Vi, которая присваивает  этой

переменной начальное значение и означает начало интервала для Vi.

     Определяется также команда U Vi, которая означает  очередное

использование этой переменной. Последняя команда этого вида,  ис-

пользующая Vi, означает конец интервала для Vi. Команда  U  будет

применяться для обозначения таких команд, как ADD, SUB и т.д.

     Для вычисления значения выражения  (a+b*c)/(f*g-(d+e)/(h+k))

генератор команд по дереву разбора сформировал следующую последо-

вательность машинных команд:

     L    h

     ADD  k

     ST   V1

     L    d

     ADD  e

     DIV  V1

     ST   V2

     L    f

     MPY  g

     SUB  V2

     ST   V3

     L    b

     MPY  c

     ADD  a

     DIV  V3

     Имена V1, V2 и V3 были взяты из  множества  неиспользованных

имен. Алгоритм распределения памяти, который мы хотим определить,

должен показать, что фактически эти три переменные могут быть по-

мещены в одну и ту же ячейку памяти T1.

     Поскольку этот алгоритм распределения памяти касается  опре-

деленных частей последовательности, можно написать

     ST   V1

     U    V1

     ST   V2

     U    V2

     ST   V3

     U    V3

     Так как последнее использование каждой переменной встречает-

ся до определения следующей переменной, то легко видеть, что дос-

таточно одной ячейки памяти.

     Предположим, что имеется стек неиспользованных ячеек  памяти

[T1, T2, T3, ...]. Предположим далее, что каждый раз, когда  нуж-

на ячейка, она берется из вершины стека и что сразу после послед-

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16