- •6. Генерация команд в компиляторе 44
- •1. Языки и грамматики
- •1.1. Язык как множество
- •1.2. Порождающая грамматика
- •1.3. Процесс порождения
- •1.4. Классификация грамматик по Хомскому
- •1.5. Классификация языков по Хомскому
- •1.6. Задача распознавания цепочек языка
- •2. Принципы трансляции языков программирования
- •3. Лексический анализ
- •3.1. Конечный автомат
- •3.2. Построение детерминированного конечного автомата
- •3.3. Недетерминированный конечный автомат
- •3.4. Преобразование неоднозначной а-грамматики к однозначной
- •3.5. Удаление из грамматики бесполезных нетерминалов
- •3.6. Лексический анализатор
- •4. Синтаксический анализ
- •4.1. Дерево порождения для кс-грамматики
- •4.2. Автомат с магазинной памятью
- •4.4. Левая рекурсия и ее устранение
- •4.5. Преобразование кс-грамматики к обобщенной нормальной форме Грейбах
- •4.6. Детерминированный ll-разбор
- •5. Обратная польская строка, как промежуточная форма программы
- •5.1. Обратная польская строка для арифметических выражений
- •5.2. Генерация опс для арифметических выражений
- •5.3. Вычисление опс для присваиваний и арифметических выражений с индексами
- •5.4. Генерация опс для присваиваний и арифметических выражений с индексами
- •5.5. Опс для условных, циклических и составных операторов
- •5.6. Опс для стандартных операторов
- •5.7. Распределение памяти и описание переменных
- •5.8. Обработка ошибок
- •6. Генерация команд в компиляторе
- •6.1. Распределение памяти при генерации команд
- •6.2. Генерация команд для присваиваний и арифметических выражений
- •6.3. Генерация команд с индексными выражениями
- •6.4. Генерация команд сравнения и перехода
6.3. Генерация команд с индексными выражениями
Вначале рассмотрим генерацию команд, реализующих операцию выделения памяти для динамических массивов.
Пример 21. Пусть, кроме рассмотренных команд, в процессоре имеется команда прерывания, которая передает управление в особую область оперативной памяти, где располагается операционная система. Пусть также, кроме регистра сумматора, имеется еще один регистр, называемый регистром адреса. Формат команды прерывания:
Itr <номер прерывания>
Вместо операнда в команде записан код – номер прерывания. Эта команда передает управление в операционную систему, причем в ту ее область, которая определяется номером прерывания. Кроме того, при этом в регистре адреса запоминается адрес команды, которая расположена следом за командой прерывания. Это необходимо для того, чтобы после обработки прерывания операционная система вернула управление в программу. Перед тем, как выполнить команду прерывания, необходимо, чтобы в регистр сумматора был записан параметр, смысл которого определяется номером прерывания. Так, для прерывания, требующего выделение памяти, в регистре сумматора должен быть записан размер области в байтах, а после обработки прерывания и возврата в программу – в регистре сумматора будет находиться адрес начала выделенной области памяти.
Рассмотрим генерацию команд, реализующей операцию выделения памяти для одномерного массива. Пусть имеется ОПС:
M n <m1>
где M – ссылка на таблицу, содержащую описание массива M, а n – количество элементов. Паспорт массива должен содержать:
M1 – адрес нулевого элемента массива;
d – длину одного элемента массива;
n1 – количество элементов массива.
Все эти три части паспорта располагаются в памяти подряд, и тогда вместо d надо писать операнд в команде M1 + v, а вместо n1 – M1 + 2v, где v – длина в байтах целого значения.
При работе генератора команд в магазин будут последовательно записаны M и n, после чего будет интерпретироваться операция <m1>. В результате будут генерироваться команды:
Load n
St M1 + 2v
Mul <длина элемента>
Itr <выделение памяти>
St M1
Load <длина элемента>
St M1 + v
Операнд <длина элемента> – константа, определяемая типом таблицы, содержащей описание массива M.
Аналогично, ОПС с операцией выделения памяти для двумерного массива:
M n m <m2>
где M – ссылка на таблицу с описанием массива M, а n, m – количество строк и столбцов в массиве. Паспорт двумерного массива содержит:
M2 – адрес нулевого элемента массива;
d – длина одного элемента массива (M1 + v);
n1 – количество строк в массиве (M1 + 2v);
n2 – количество столбцов в массиве (M1 + 3v).
При работе генератора команд будет создана последовательность:
Load n
St M2 + 2v
Mul m
Mul <длина элемента>
Itr <выделение памяти>
St M2
Load <длина элемента>
St M1 + v
Load m
St M1 + 3v
Конец примера.
А теперь рассмотрим генерацию команд, реализующих операцию индексирования.
Пример 22. Расширим модель процессора. Пусть в командах, кроме кода операции и операнда, записывается признак косвенной адресации, который может быть нулем или единицей:
<код операции> <признак> <операнд>
Если этот признак равен 0, то команда выполняется обычным образом, а если 1, то используется косвенная адресация, когда операнд в команде – это адрес в памяти, где находится адрес, ссылающийся на другую ячейку памяти, содержащую значение операнда.
При генерации команд с использованием косвенной адресации необходимо, чтобы в магазине интерпретатора для каждой ячейки магазина дополнительно записывался признак (0 или 1). Тогда, при генерации любой команды с операндом из магазина, в команду записывается операнд и этот признак.
Правила генерации команд, реализующих операцию <i1>, следующие. Обозначим два верхних операнда в магазине как a и b. В переменной k находится ссылка на элемент магазина, содержащий 0. Операнд а содержит ссылку на паспорт массива, b – индекс элемента массива. В командах используются t1, t2 – дополнительные временные переменные.
Если b = 0, то генерируются команды:
Mul 0 a + v
Add 0 a
St 0 t1
Если b ≠ 0, k = 0, то генерируются команды:
Load 0 b
Mul 0 a + v
Add 0 a
St 0 t1
В обоих случаях после генерации команд в магазин записывается t1 и признак для нее 1, а в переменную k – нуль.
Если b ≠ 0, k ≠ 0, то генерируются команды:
St 0 t1
Load 0 b
Mul 0 a + v
Add 0 a
St 0 t2
После генерации команд в элемент магазина по ссылке k записывается t1, в верхний элемент магазина записывается t2 и признак для него 1, а в переменную k – нуль.
А теперь рассмотрим правила генерации команд, реализующих операцию <i2>. Обозначим три верхних операнда в магазине как a, b и c. В переменной k находится ссылка на элемент магазина, содержащий 0. Операнд а содержит ссылку на паспорт массива, b – 1-й индекс элемента массива, c – 2-й индекс элемента массива. В командах используются t1, t2 – дополнительные временные переменные.
Если b = 0, то генерируются команды:
Mul 0 a + 3v
Add 0 c
Mul 0 a + v
Add 0 a
St 0 t1
Если c = 0, то генерируются команды:
St 0 t1
Load 0 b
Mul 0 a + 3v
Add 0 t1
Mul 0 a + v
Add 0 a
St 0 t1
Если b ≠ 0, c ≠ 0, k = 0, то генерируются команды:
Load 0 b
Mul 0 a + 3v
Add 0 c
Mul 0 a + v
Add 0 a
St 0 t1
Во всех случаях после генерации команд в магазин записывается t1 и признак для нее 1, а в переменную k – нуль.
Если b ≠ 0, c ≠ 0, k ≠ 0, то генерируются команды:
St 0 t1
Load 0 b
Mul 0 a + 3v
Add 0 с
Mul 0 a + v
Add 0 a
St 0 t2
После генерации команд в элемент магазина по ссылке k записывается t1, в верхний элемент магазина записывается t2 и признак для него 1, а в переменную k – нуль.
Рассмотрим пример генерации команд. Пусть задана ОПС:
M i j a + <i2> L i d – <i1> :=
что соответствует оператору:
M[i, j + a] := L[i – d]
Шаги работы генератора команд будут такими (пропущены действия по записи в магазин операндов):
-
Операция + , k = 0, в магазине:
0
0
0
0
M
i
j
a
генерируемые команды: Load 0 j
Add 0 a
k := 3
-
Операция <i2> , k = 3, в магазине:
0
0
0
M
i
0
генерируемые команды: St 0 t1
Load 0 i
Mul 0 M + 3v
Add 0 t1
Mul 0 M + v
Add 0 M
St 0 t1
k := 0
-
Операция – , k = 0, в магазине:
1
0
0
0
t1
L
i
d
генерируемые команды: Load 0 i
Sub 0 d
k := 3
-
Операция <i1> , k = 3, в магазине:
1
0
0
t1
L
0
генерируемые команды: Mul 0 L + v
Add 0 L
St 0 t2
k := 0
-
Операция := , k = 0, в магазине:
1
1
t1
t2
генерируемые команды: Load 1 t2
St 1 t1
k := 0, магазин пуст.
В результате получится такая программа:
Load 0 j
Add 0 a
St 0 t1
Load 0 i
Mul 0 M + 3v
Add 0 t1
Mul 0 M + v
Add 0 M
St 0 t1
Load 0 i
Sub 0 d
Mul 0 L + v
Add 0 L
St 0 t2
Load 1 t2
St 1 t1
Конец примера.
Замечания.
1. По аналогии с рассмотренными примерами реализации операций индексации одно и двумерных массивов можно реализовать индексацию массивов большей размерности.
2. Перед вычислением величины смещения относительно адреса нулевого элемента массива, для безопасности, желательно генерировать также команды проверки того, что индекс неотрицателен и меньше количества элементов по соответствующему измерению. И если такая проверка даст отрицательный результат, то нужно предусмотреть команду прерывания, которая бы передала в операционную систему признак ошибки «неверный индекс», так как при этом дальнейшее исполнение программы невозможно.