Курсовая работа по информатике (стр. 3 )

2. 11 Проходы компилятора

При реализации компилятора одна или несколько фаз (этапов, а может и часть фазы) объединяются в программные модули. Их называют проходами. За каждый проход считываются файл с программой на алгоритмическом языке, а также результат предыдущего прохода. Во время каждого прохода происходит преобразование, заданное фазами, и записывается результат. Количество проходов определяется особенностями алгоритмического языка и ПЭВМ. Есть одно-, двух - и многопроходные компиляторы. Многопроходной компилятор занимает меньше оперативной памяти ПЭВМ, чем однопроходной, но работает медленно из-за необходимости многоразового чтения и записи файлов. В однопроходном компиляторе ведущей фазой является фаза синтаксического анализа. Она каждый раз, когда ей нужна лексема, запрашивает фазу лексического анализа, управляет генерацией промежуточного кода, заполняет таблицы и т. д.

3 Алгоритмический язык SPL

Используем основные методы компиляции для реализации однопроходного интерпретатора. Этот интерпретатор, написанный на языке Си, должен прочитать, перевести на язык промежуточных команд и выполнить программу, написанную на алгоритмическом языке SPL. SPL (Simple Programming Language) – простой язык программирования. Это учебный язык высокого уровня, который напоминает Паскаль и Си. Ему присущи все особенности алгоритмических языков высокого уровня, за исключением того, что работает он только с одним типом данных – с целыми числами.

Язык SPL, как и любой алгоритмический язык, являет собой набор символов и правил для ввода интерпретации в ЭВМ.

3. 1 Символы

·  Буквы: , (только латинского алфавита).

·  Цифры: .

·  Специальные символы: +, -, *, /, %, ( , ) , , ;, =, \n, \t – всего 13 символов.

3. 2 Идентификаторы

Это имена переменных, констант и функций. Идентификатор – это последовательность букв или букв и цифр, но первой должна быть буква. Количество символов от 1 до 40, символы пробела, перехода на новую строку (\n) и табуляции (\t) в идентификаторе недопустимы.

3. 3 Константы

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

Пример: сonst a=12, b=4, d=0;

3. 4 Переменные

Переменные могут быть только целого типа. Имеются глобальные и локальные переменные. Глобальные переменные могут использоваться всеми функциями, а локальные – только теми функциями, в которых описаны. Описание переменных имеет вид:

int имя_переменной_1, имя_переменной_2.

Пример: int x, y, z, teta.

3. 5 Выражения

В выражениях применяются знаки +, -, * (умножить), / (деление), % (остаток от деления).

3. 6 Служебные слова

Напомним, что это зарезервированные слова, которые нельзя использовать в качестве идентификаторов. Это следующие 11 слов: begin, end, read, print, return, if, then, while, do, int, const.

3. 7 Функции

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

Описание программы имеет вид:

Имя_функции (формальные_параметры)

begin

описание локальных констант и переменных;

операторы

end

В отличие от Паскаля после end в конце программы точка не ставится.

Операторы заканчиваются точкой с запятой. Однако перед end точку с запятой ставить нельзя. Оператор условной передачи управления if имеет вид:

if условие then последовательность операторов end

В качестве условия может быть имя переменной или выражение. Если значение переменной или выражения больше нуля, тогда выполняется последовательность операторов между then и end. Иначе переход на следующий за if оператор.

3. 8 Оператор цикла

while условие do

последовательность операторов

end

Как и для if, “условие” может представлять собой переменную или выражение. Если переменная или результат вычисления больше нуля, тогда вычисляется последовательность операторов между словами do и end. После этого вновь проверяется “условие”. Если результатом проверки условия оказалось число £ 0, то происходит выход из цикла.

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

Ниже приводится пример программы на SPL, в которой, кроме главной функции main( ), также используется функция возведения в степень аb. Назовем ее exp ( ).

exp (а, b)

begin

int z;

z=1;

while b do

if b %2 then

z=z*a

end;

a=a*a;

b=b/2

end;

return z

end

main ( )

begin

int x, y;

read x;

read y;

print exp (x, y)

end

В главной функции описаны и введены с клавиатуры две локальные переменные x, y. Затем в строке print exp (x, y) происходит вызов функции exp (), в которую вместо формальных параметров a и b подаются соответствующие фактические параметры x и y. Функция exp ( ) с помощью оператора return z возвращает в main ( ) результат, который выводится на экран.

Алгоритм возведения ab предлагается рассмотреть самостоятельно, например, вычисляя 27.

4 Лексический анализ

Сначала составим программу на языке Си, которая предназначена только лишь для распознавания лексем в тексте программы на языке SPL, а также для размещения идентификаторов в специальной таблице TNM. Эта таблица представляет собой глобальный одномерный массив char TNM[400].

В процессе лексического анализа распознаются лексемы:

·  служебные слова;

·  знаки операций и разделители;

·  целые числа;

·  идентификаторы;

·  признак конца файла.

В программе каждой лексеме ставится в соответствие целое число. Знаки операций и разделители закодированы литеральными константами ‘+’, ‘-‘, ‘*’, ‘/’, ‘%’, ‘=’, ‘(‘, ‘)’, ‘,’, ‘;’. Каждой из них соответствует целое число из таблицы кодов ASCII (М. Уэйт, С. Прата, Д. Мартин. Язык Си.- М.: Изд-во “Мир”, 1988.- 512 с.). В таблице кодов ASCII также закодированы целыми числами символы букв и цифр. Обычно в этой таблице приводятся коды 256 символов.

Для служебных слов имена лексем выбирает программист. Предлагается эти лексемы обозначать соответствующими заглавными буквами с буквой L в конце. Например: служебными словами if и while имена лексем соответственно IFL, WHILEL и т. д. А связь с целыми числами определяется с помощью перечисляемых констант целого типа.

enum {BEGINL=257, ENDL, READL, PRITL, RETRL, IFL, THENL, WHILEL, DOL, INTL, CONSTL, NUMB, IDEN },

где NUMB – лексема для целого числа;

IDEN – лексема для идентификатора.

Благодаря применению enum {}, лексема BEGINL получила числовое значение 257, ENDL – 258 и т. д. Таким образом, при написании программы нет необходимости помнить, что лексема BEGINL закодирована числом 257, а ENDL – 258. Везде, где нужно сослаться на эти лексемы, удобнее писать BEGINL, ENDL и т. д., а вместо них будут представляться числа 257, 258 и т. д.

Кроме перечисленных лексем, также используется признак конца файла EOF. В файле stdio.h есть директива препроцессора #define EOF – 1 . Из нее видно, что EOF закодирован – 1.

Текст программы на Си для лексического анализа программы на SPL приведен ниже. Целесообразно привести некоторые пояснения к этой программе. В ней используются глобальные переменные и приведенные выше в enum {} перечисленные константы:

int lex; //распознанная лексема (целое число);

int lval; // значение лексемы. Для константы – это числовое значение, а для идентификатора – адрес в таблице идентификаторов TNM;

int nst=0; // номер считываемой строки в программе на языке SPL;

char nch=’\n’; // считываемый символ из программы на SPL;

char TNM [400]; // таблица идентификаторов;

char * ptn=TNM; // указатель на первый свободный элемент в таблице идентификаторов. В самом начале он стоит на TNM [0], т. к. имя массива TNM в языке Си является адресом его самого первого (т. е. нулевого) элемента;

FILE * PF; // указатель на файл с текстом программы на SPL;

FILE * padres // указатель на файл, в который будут заноситься адреса идентификаторов в таблице TNM.

В программе лексического анализа при вызове функции main () используются параметры. Заголовок функции main ( ) имеет вид: void main (int av, char * av [ ]). Здесь ac – количество параметров (символьных строк); char* av [ ] – массив показателей. Конкретно, в av [0] автоматически заносятся имя файла с готовой для исполнения программой (например, part1.exe).