Deitel C - Задачи - Глава 12+

Deitel C - Задачи

Группы и результаты

8 А

8 Б

8 В

8 Г

SIMPLE

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

Сначала определим наш высокоуровневый язык Simple. Он будет похож на ранние версии языка Basic.

Каждое выражение языка Simple состоит из номера строки и инструкции языка.

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

Каждая из инструкций начинается с одной из команд:

• rem
• input
• let
• print
• goto
• if ... goto
• end

Все команды кроме end могут быть использованы многократно.

Simple оперирует только целыми числами и имеет только 4 оператора: +, -, *, /.

Эти операторы имеют такой же приоритет как и в языке Си. В выражениях могут быть использованы скобки.

• rem - команда для ввода комментариев в коде. Не компилируется в машинный код.
• input - команда для ввода числа от пользователя. Выводит символ вопроса, чтобы показать что ожидается ввод. В качестве параметра ожидает имя переменной.
• let - присваивает переменной результат вычисления выражения
• print - выводит значение переменной
• goto - переводит программу к исполнению строки программы указанной в параметре
• if ... goto - переводит программу к исполнению строки программы указанной в параметре в случае выполнения условия

Язык Simple распознаёт только строчные (маленькие) буквы.

Имя переменной может быть только из одной буквы.

Все переменные в Simple целые числа.

Simple не требует объявления переменных. Появление переменной в программе объявляет и инициализирует её нулём.

В условных операторах допускаются операторы сравнения <, >, <=, >=, ==, !=.

Сравнивать можно только 2 переменные или переменную с константой. Оценка выражений не поддерживается.

Рассмотрим несколько программа на языке Simple.

Сумма 2 чисел

10 rem determine and print the sum of two integers
15 rem
20 rem input the two integers
30 input a
40 input b
45 rem
50 rem add integers and store result in c
60 let c = a + b
65 rem
70 rem print the result
80 print c
90 rem terminate program execution
99 end

Определение большего из 2-х чисел

10 rem determine the larger of two integers
20 input s
30 input t
32 rem
35 rem test if s >= t
40 if s >= t goto 90
45 rem
50 rem t is greater than s, so print t
60 print t
70 goto 99
75 rem
80 rem s is greater than or equal to t, so print s
90 print s
99 end

В Simple нет циклов, но он может эмулировать такое поведение через операторы if ... goto.

Например следующая программа рассчитывает квадрат вводимых чисел пока не будет введено число -9999.

10 rem calculate the squares of several integers
20 input j
23 rem
25 rem test for sentinel value
30 if j == -9999 goto 99
33 rem
35 rem calculate square of j and assign result to k
40 let k = j * j
50 print k
53 rem
55 rem loop to get next j
60 goto 20
99 end

Компилятор

Программа на языке Simple сохраняется в файл. Компилятор на его основе создаёт файл с инструкциями SML по одной на строке.

Затем файл загружается в симулятор Simpletron'а. Симулятор должен быть модифицирован, чтобы загружать инструкции не с клавиатуры, а из файла при запуске программы.

Компилятор выполняет 2 прохода Simple программы для преобразования её в SML-инструкции.

В первый проход создаётся таблица символов в которой хранятся каждая строка программы, все имена переменных и константы с типом и адресом памяти в итоговом наборе инструкций SML.

Первый проход также переводит команды языка в инструкции SML.

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

Второй проход дополняет эти инструкции и выводит результат в файл.

Первый проход

Изначально программа считывает строки программы из файла.

Затем строка разбивается (с помощью функции strtok) на части (token/токены) для обработки и компиляции.

Каждое выражение языка Simple начинается с номера строки и продолжается командой.

Если мы находим переменную или константу, то мы помещаем их в нашу таблицу символов.

Номер строки помещается в таблицу символов только если он первый токен в строке.

Таблица символов - это массив структур описывающих символы программы.

struct tableEntry {
 int symbol;
 char type; /* 'C', 'L' or 'V' */
 int location; /* 00 to 99 */
};

Каждый элемент таблицы символов содержит 3 элемента:

	C	L	V
int symbol	значение константы	номер команды Simple	целое число, являющееся ASCII - кодом символа представляющего имя переменной
char type	С - константа/constant	L - номер строки/line number	V - переменная/variable
int location	адрес константы в итоговой программе SML	адрес SML-инструкции соответствующей команде строки Simple	SML-адрес хранения переменной

Память для переменных и констант выделяется в памяти Simpletron'а с конца.

Команды Simple соответствуют инструкциям SML, например:

• input(Simple) - 10(Read SML)
• print(Simple) - 11(Write SML)

В случае команды чтения необходимо указать в какую ячейку памяти необходимо записать введённое пользователем значение.

Компилятор ищет в таблице символов элемент указывающий, на адрес памяти соответствующей переменной.

Компиляция строки зависит от команды. Например если компилятор встречает команду rem остальная часть строки игнорируется.

Команды input, print, goto и end переводятся напрямую в инструкции read, write, branch и halt. (Команда goto может содержать ссылку на недоступный ещё в таблице будущий элемент, который будет заполнен при втором проходе компилятора)

При неполной компиляции инструкция должна быть помечена для второго прохода компилятора. Для этого используем массив целых чисел flags размером с память Simpletron'а и инициированные значением -1.

Если положение инструкции в памяти SML строки программы Simple ещё не известно номер строки сохраняется в массиве флагов под индексом соответствующим адресу неполной инструкции.

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

Компиляция условных переходов (if...goto) и команды let представляет большую сложность.

Компиляция условных переходов производится с помощью инструкций branch zero или branch negative или их комбинации.

Для команды let компилятор создаёт код для оценки арифметического выражения и/или констант.

В выражении операторы и операнды должны быть разделены пробелами.

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

В стек при оценке вставляются адреса памяти вместо реальных значений.

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

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

Дальше генерируется SML инструкция присваивающая результат переменной из левой части команды let.

Второй проход

Во время второго прохода компилятор выполняет 2 задачи: разрешает неопределённые ссылки и выводит SML инструкции в файл.

Для всех элементов в таблице флагов (flags) не равных -1 найти в таблице символов нужный элемент с типом L - номер строки и дополнить инструкцию адресом SML.

После уточнения всех необходимых инструкций они выводятся в файл по одной инструкции на строку.

Пример: Программа вводящая число x и рассчитывающая сумму чисел от 1 до x

Команда Simple	Адрес SML + инструкция	Описание
5 rem sum 1 to x	none	rem ignored
10 input x	00 +1099	read x into location 99
15 rem check y == x	none	rem ignored
20 if y == x goto 60	01 +2098	load y (98) into accumulator
	02 +3199	sub x (99) from accumulator
	03 +4200	branch zero to unresolved location
25 rem increment y	none	rem ignored
30 let y = y + 1	04 +2098	load y into accumulator
	05 +3097	add 1 (97) to accumulator
	06 +2196	store in temporary location 96
	07 +2096	load from temporary location 96
	08 +2198	store accumulator in y
35 rem add y to total	none	rem ignored
40 let t = t + y	09 +2095	load t (95) into accumulator
	10 +3098	add y to accumulator
	11 +2194	store in temporary location 94
	12 +2094	load from temporary location 94
	13 +2195	store accumulator in t
45 rem loop y	none	rem ignored
50 goto 20	14 +4001	branch to location 01
55 rem output result	none	rem ignored
60 print t	15 +1195	output t to screen
99 end	16 +4300	terminate execution

Таблица символов

Символ	Тип	Адрес
5	L	00
10	L	00
'x'	V	99
15	L	01
20	L	01
'y'	V	98
25	L	04
30	L	04
1	C	97
35	L	09
40	L	09
't'	V	95
45	L	14
50	L	14
55	L	15
60	L	15
99	L	16

При компиляции команды на строке 20 в таблице символов нет SML-адреса команды со строки 60, поэтому учитывая, что инструкция условного перехода расположена по адресу 03 в SML-памяти, мы помещаем номер Simple строки (60), куда должен быть сделан переход в ячейку 03 массива flags, для заполнения на втором проходе компилятора.

При компиляции надо следить за текущим адресом вывода команд, т.к. некоторые команды SML компилируются в несколько SML-инструкций.

При компиляции надо следить чтобы не случилось переполнение памяти Simpletron'а.

Первый проход компилятора

5 rem sum 1 to x

strtok отделяет номер строки программы, а функция atoi переводит символ в число 5.

Таблица символов дополняется элементом с типом L - номер строки и SML-адресом = 0.

Несмотря на то, что команда является комментарием запись в таблице символов позволит в дальнейшем использовать оператор goto или if...goto для перехода на эту строку.

Для комментариев не генерируется SML-инструкций и счётчик инструкций остаётся без изменений.

10 input x

Номер строки 10 также помещается в таблицу символов с типом L и адресом 0.

Команда input имеет в качестве параметра переменную x.

Компилятору необходимо найти адрес переменной в памяти SML. Он ищется в таблице символов и не находится, поэтому в таблицу добавляется запись ASCII-кода буквы x, с типом V и адресом 99 (место для переменных и констант выделяется с конца памяти Simpletron'а).

После этого генерируется инструкция SML. 10 - код ввода + 99 - адрес переменной формируют итоговую инструкцию.

Итоговая инструкция сохраняется в массиве SML по адресу 00 и счётчик инструкций увеличивается.

15 rem check y == x

Номер строки 15 помещается в таблицу символов с типом L и адресом 1.

20 if y == x goto 60

Номер строки 20 помещается в таблицу символов с типом L и адресом 1.

Команда if обозначает необходимость оценки условия.

Переменная y не существует в таблице символов, следовательно она добавляется: ASCII-код буквы y с типом V и адресом 98.

Далее создаются инструкции чтобы выполнить оценку условия. Для этого мы вычисляем разность y - x и используем инструкцию branch zero.

Загружаем y в аккумулятор (01 +2098). Затем вычитаем из аккумулятора x (02 +3199).

Затем добавляем инструкцию условного перехода (branch zero - 42). Из-за того, что SML-адрес строки 60 отсутствует в таблице символов на первом проходе инструкция будет неполной и адрес будет представлен нулём = 4200.

По индексу соответствующему SML-адресу неполной инструкции в массив flags мы помещаем номер строки программы Simple, SML-адрес которой надо будет добавить в инструкцию на втором проходе.

Увеличиваем счётчик инструкций до 4.

25 rem increment y

Номер строки 25 помещается в таблицу символов с типом L и адресом 4.

30 let y = y + 1

Номер строки 30 помещается в таблицу символов с типом L и адресом 4.

Команда let обозначает присваивание.

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

Константа (число 1) добавляется в таблицу символов с типом C и адресом 97.

Далее правая сторона команды let преобразуется из инфиксной в постфиксную нотацию (y + 1 => y 1 +) и оценивается с генерацией соответствующих инструкций.

При оценке мы помещаем в стек адреса переменной (y) и константы (1) вместо реальных значений.

Когда обрабатывается оператор сложения из стека извлекаются оба адреса и генерируется инструкции сложения.

04 +2098 (загружается y)
05 +3097 (добавляется 1)

Результат помещается во временную переменную по адресу 96 и этот адрес добавляется в стек.

06 +2196

Затем временная переменная загружается в аккумулятор и выгружается в переменную стоящую в левой части команды let, т.е. в нашем случае в переменную y.

07 +2096 (загружаем результат из временной переменной)
08 +2198 (сохраняем результат в y)

Достаточно очевидна избыточность последних двух инструкций.

35 rem add y to total

Номер строки 35 помещается в таблицу символов с типом L и адресом 9.

40 let t = t + y

Номер строки 40 помещается в таблицу символов с типом L и адресом 9. Команда похожа на команду строки 30.

Переменная t вставляется в таблицу символов с типом V и SML-адресом 95.

Инструкции следуют той же логике.

09 +2095 (загружаем t) t/95
10 +3098 (добавляем y) y/98
11 +2194 (сохраняем результат во временную переменную 94)
12 +2094 (загружаем результат обратно в аккумулятор)
13 +2195 (записываем результат в переменную t) t/95

45 rem loop y

Номер строки 45 помещается в таблицу символов с типом L и адресом 14.

50 goto 20

Номер строки 50 помещается в таблицу символов с типом L и адресом 14.

Аналогом команды безусловного перехода goto в SML-инструкциях является инструкция unconditional branch(40), которая передаёт управление инструкции с адресом полученным в качестве параметра.

В таблице символов существует элемент для строки 20 с SML-адресом равным 1.

Соответственно формируемая инструкция будет = 14 +4001

55 rem output result

Номер строки 55 помещается в таблицу символов с типом L и адресом 15.

60 print t

Номер строки 60 помещается в таблицу символов с типом L и адресом 15.

Команда вывода переводится в соответствующую инструкцию write(11)/

Адрес в SML-памяти переменной t находится в таблице символов = 95.

15 +1195

99 end

Конец программы соответствует инструкции остановки

16 +4300

Второй проход компилятора

В массиве flags мы ищем значения отличные от -1.

Элемент с индексом 3 содержит число 60. Это означает, что инструкция по SML-адресу 3 должна содержать в качестве оператора SML-адрес команды соответствующей строке 60 программы Simple.

Найдя в таблице символов элемент с типом L SML-адрес строки 60 равный 15 мы дополняем инструкцию 4200 адресом до состояния 4215.

Оптимизации компилятора

Оптимизация команды let

Попробуйте избавится при вычислении выражения командой let от двух избыточных инструкций и излишней временной переменной которые образуются при окончании вычислений.

Вместо

04 +2098 (load)
05 +3097 (add)
06 +2196 (store)
07 +2096 (load)
08 +2198 (store)

получить

04 +2098 (load)
05 +3097 (add)
06 +2198 (store)

Пары операций LOAD / STORE

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

12 +2196 (store)
13 +2096 (load)

Введение оператора вычисления остатка от деления

Введите в язык Simple уже доступный в SML оператор вычисления остатка от деления.

Введение оператора возведения в степень

Введите в язык Simple уже доступный в SML оператор возведения в степень.

Буквы верхнего регистра

Добавьте возможность распознания букв верхнего регистра в качестве имён переменных. 'A' как аналог 'a'.

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

Модифицируйте команду input для ввода значений нескольких переменных.

Например: input x, y

Вывод нескольких значений

Модифицируйте команду print для вывода нескольких значений.

Например: print x, y

Ошибки компилятора

Дополните компилятор возможностями анализа ошибок в неправильно написанных командах Simple и вывода соответствующих ошибок компилятора.

Массивы целых чисел

Дополните язык Simple возможностью объявлять и использовать массивы целых чисел.

Подпрограммы

Дополните язык Simple возможностью вызывать подпрограммы командой gosub и возвращать поток выполнения назад командой return.

Цикл for

Дополните возможности языка Simple возможностями цикла вида:

for x = 2 to 10 step 2
 rem Simple statements
next
или вида
for x = 2 to 10 
 rem Simple statements
next

с инкрементом по умолчанию равным +1

Строки

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

Числа с плавающей точкой

Дополните Simple и SML возможностями работы с числами с плавающей точкой.

Базовый набор инструкций SML

Определите макросы препроцессора для определения инструкций.

Операции ввода/вывода:
#define READ 10 - ввести число с клавиатуры в определённый адрес памяти
#define WRITE 11 - вывести число из определённого адреса памяти на экран

Операции загрузки и выгрузки:
#define LOAD 20 - загрузить число из определённого адреса памяти в аккумулятор
#define STORE 21 - выгрузить число из аккумулятора в определённый адрес памяти

Арифметические операции:
#define ADD 30 - добавить число из определённого адреса памяти в аккумулятор (результат остаётся в аккумуляторе)
#define SUBTRACT 31 - отнять число из определённого адреса памяти из аккумулятора (результат остаётся в аккумуляторе)
#define DIVIDE 32 - разделить число из определённого адреса памяти на значение аккумулятора (результат остаётся в аккумуляторе)
#define MULTIPLY 33 - умножить число из определённого адреса памяти на значение аккумулятора (результат остаётся в аккумуляторе)

Операции передачи контроля:
#define BRANCH 40 - Безусловный переход к исполнению инструкции по указанному адресу
#define BRANCHNEG 41 - Переход к исполнению инструкции по указанному адресу в случае если аккумулятор содержит отрицательное число
#define BRANCHZERO 42 - Переход к исполнению инструкции по указанному адресу в случае если аккумулятор содержит ноль
#define HALT 43 - остановка компьютера