Разработка транслятора (компилятора) с языка Милан

Для построения компилятора с языка МИЛАН необходимо определить выходной язык - язык команд некоторой ЭВМ. Определим ЭВМ, как некоторую стековую машину, имеющую три вида памяти:

линейная память для хранения программ;

линейная память для хранения данных;

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

Память адресуется пословно. В слове памяти для хранения программ может храниться одна одноадресная команда (код операции и ад­рес операнда). В слове памяти для хранения данных и в слове стеко­вой памяти может помещаться одно число. Определим систему команд процессора машины:

LDA, a - (load - загрузить) содержимое слова памяти с адресом a помещается в стек.

STA, а - (store - запомнить) из стека читаются данные, и поме­щается в ячейку памяти с адресом а.

INP - (input - ввод) число с устройства ввода помешается в стек.

OUT - (output - вывод) из стека читается число и выдается на устройство вывода.

JMP, m - (Jump - перейти) безусловная передача управления ко­манде с номером (адресом) m.

JMT, m - (Jump-true - перейти, если истина) условная передача управления: из стека читается данное, если оно TRUE (равно 0), то управление передается команде с номером m. Иначе выполняется сле­дующая команда.

JMF, m - (Jump-false - перейти, если ложь) условная передача управления: из стека читается число, если оно FALSE (равно 1), то передается управление команде с номером т. Иначе выполняется сле­дующая команда.

HLT - (halt - остановиться) останов процессора.

ADD - (add - сложить) сложение: со стека снимается 2 числа, эти числа складываются, и результат засылается в стек.

SUB - (subtract - вычесть) вычитание; со стека снимается 2 числа, из второго числа вычитается первое и результат засылается в стек.

MUL - (multiply - умножить) умножение: со стека снимается 2 числа, эти числа перемножаются, и результат засылается в стек.

DIV - (divide - разделить) деление: со стека снимаются 2 чис­ла, второе число делится на первое и результат засылается в стек.

INV - (invert - инвертировать) инвертирование числа: со стека снимается число, умножается на -1 и результат засылается в стек.

Все арифметические команды безадресные. Они выбирают аргумен­ты из стека и результат посылают в стек. Верхний элемент стека -всегда второй операнд. Следующий за ним - первый операнд.

CMP, s - (compare - сравнить) сравнение: со стека снимается 2 числа b и а, производится операция сравнения a s b c кодом s и результат заносится в стек. Коды операции сравнения определяются в таблице лексем (табл. 1.1).

Сканер передает блоку генерации массив лексем, массив иденти­фикаторов и массив констант.

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

А+1 - адрес слова со значением i-ой константы;

В+j.- адрес слова со значением j-ого идентификатора;

хС - глобальная переменная - счетчик генерируемых команд (слова в памяти команд имеют адреса 1, 2, 3 и т.д.); начальное зна­чение хС=0;

GEN(x, y) - функция генерации команды с кодом х и операндом у (операнд в некоторых командах может отсутствовать); счетчик команд хС увеличивается на 1, формируется слово с командой и записывается по адресу хС в память команд;

k, m, n, s - локальные переменные.

Опишем семантические функции компилятора:

z1: GEN(HLT,0) - сгенерировать команду останова.

z2: GEN(CMP, s) - сгенерировать команду сравнения.

z3: GEN(STA, B+k) - вершина стека - результат вычисления, пе­ресылается в слово памяти, отведенное для k-ого идентификатора.

z4: GEN(OUT) - сгенерировать команду вывода результата вычис­ления Е.

z5: Запомнить хC+1 - адрес, с которого начинается вычисление условия, в локальной переменной n.

z6: GEN(JMF, 0) - команда обхода конструкции L ври значении условия FALSE. Адрес перехода пока не известен. Он будет вычислен после окончания распознавания всего оператора. В переменной m запоминается адрес этой команды.

z7: GEN(JMP, n) - генерация команды возврата на проверку условия повторения цикла. Значение хС+1 заслать в поле операндов команды, адрес которой был запомнен в переменной m.

Рис.3.1. Синтаксические диаграммы компилятора

z8: GEN(JMP, 0) - генерация команды выхода из конструкции выбо­ра. Адрес перехода пока не известен. Значение хС - адрес этой ко­манды, запомнить в переменной n. В поле операнда команды, адрес которой был запомнен в m, заслать значение хС+1.

z9: В поле операнда команды, адрес которой в n, заслать хС+1 - адрес команды, с которой будет начинаться реализация следующей конструкции.

z10: В поле операнда команды, адрес которой в m. заслать хС+1 - адрес команды, с которой будет начинаться реализация следующее конструкции.

z11: GEN(LDA, B+k) - сгенерировать команду загрузки в стек значения k-ого идентификатора.

z12: GEN(LDA, A+k) - сгенерировать команду загрузки в стек значения k-ой константы.

z13: GEN(INP, 0) - сгенерировать команду ввода числа с уст­ройства ввода.

z14: Если k=0, то GEN(MUL), иначе GEN(DIV).

z15: Если k=0, то GEN (ADD), иначе GEN(SUB).

z16: k=0.

z17: Если k=1, то GEN(INV).