Разработка компилятора

Оглавление

1 ТЕХНИЧЕСКОЕ ЗАДАНИЕ. 4

2 ОПИСАНИЕ ПРОГРАММЫ. 7

3 ТЕКСТ ПРОГРАММЫ. 17

4 КОНТРОЛЬНЫЙ ПРИМЕР ИСПОЛЬЗОВАНИЯ 47

ЗАКЛЮЧЕНИЕ 64

 

 

1 ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

1.1 Введение

Наименование  программного продукта – «Компилятор».

Область применения программного продукта –  разработка программного обеспечения, трансляция с языка высокого уровня на язык ассемблера.

1.2 Основания  для разработки.

Разработка  данного рода программного средства ведется в рамках курсовой работы на основании «Задания на курсовую работу» от 19 марта 2012 года, утвержденного Зав. Кафедрой «Вычислительная техника и автоматизированные системы управления» Е.Г. Шепиловой. Руководитель доцент В.В. Жуков.

1.3 Назначение  разработки.

Разработка  предназначена для компиляции программы  из исходного  кода в код на языке  ассемблера.

1.4 Требования  к программе.

1.4.1 Требования  к функциональным характеристикам  программного продукта.

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

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

- типы  данных (простые типы – логический, целые числа без знака, символы);

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

- Операторы (оператор ввода, оператор вывода, оператор присваивания, условный оператор, оператор цикла с предусловием, оператор цикла ‘do’ по типу Бэйсика).

Способ  реализации лексического и синтаксического  анализаторов остается на усмотрение разработчика.

2. Требования к надежности.

Лексический анализатор должен производить разбор текста любого содержания и произвольной длины. При нахождении символа, не относящегося ни к одному из классов лексем, должна быть вызвана ошибка и работа алгоритма должна быть остановлена. Данное требование не относится к содержимому литералов и символьных констант, в которых содержимое ничем не ограничено.

Синтаксический  анализатор должен контролировать выход  за границы таблицы лексем, чтобы  избежать возникновения критических  ошибок, останавливать работу алгоритма  разбора и выдавать соответствующее  сообщение об ошибке.

3. Условия эксплуатации.

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

4. Требования к составу и параметрам технических средств.

Минимальные требования к аппаратному обеспечению  компьютера для обеспечения стабильной работы программы должны быть следующими:

– центральный  процессор – версии Intel ® Pentium III и старше;

– совместимая  видеокарта;

– оперативное  запоминающее устройство емкостью не менее 256 Мб;

– устройство ввода-вывода.

5. Требования к информационной и программной совместимости.

Программа должна быть спроектирована и разработана  для использования под управлением  операционных систем семейства Microsoft ® Windows версии MS Windows XP и старше.

1.4.6 Требования  к маркировке и упаковке.

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

 

1.4.7 Требования  к транспортировке и хранению.

Требований  к транспортировке и хранению не предъявляется.

1.5 Требования  к программной документации.

Программная документация должна включать в себя следующие разделы:

- текст программы;

- описание  программы.

1.6 Технико-экономические  показатели.

Расчет технико-экономических  показателей не требуется.

1.7 Стадии  и этапы разработки.

Разработка  должна быть разделена на три стадии:

- разработка  лексического анализатора;

- разработка  синтаксического анализатора;

- разработка  генератора кода.

1.8 Порядок  контроля и приемки.

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

 

 

2 ОПИСАНИЕ ПРОГРАММЫ.

2.1 Общие сведения.

Программа написана на языке Паскаль. Графический  интерфейс не реализован. Для запуска  программы необходимо будет запустить  Паскаль и исходный текс программы  для компиляции записать в файл «primer.txt».

2.2 Лексический анализатор.

Лексический анализатор не является обязательной частью компилятора, однако при разработке данного проекта было принято  решение выделить лексический анализатор отдельной процедурой leksich и сам процесс лексического анализа производить за отдельный проход.

Лексический анализатор (сканер) предназначен для выделения из входного текста лексем – неделимых единиц программы. Лексемами являются имена переменных, процедур и функций, зарезервированные слова, числа, разделители, знаки операций, символьные константы и литералы (строковые константы).

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

Приведем список зарезервированных слов: Program,begin,end,write,read, var,then,for,If,do,while,Repeat,Until,else,to,Boolean,integer,byte,char,array, of,

True,false,not,and,of,or,procedure,loop

Приведем  список однолитерных разделителей (состоящих из одного символа): ‘(‘, ‘)’, ‘+’, ‘-‘, ‘*’, ‘/’, ‘<’, ‘>’, ‘=’, ‘”’, ‘;’, ‘[‘, ‘]’, ‘:’, ‘,’, ‘|’, ‘.’.

Приведем список двулитерных разделителей (состоящих из двух символов): ‘<>’, ‘>=’, ‘<=’, ‘:=’.

Лексемы разделены на классы, называемые токенами. Таким образом, существует токен имен переменных, зарезервированных слов, чисел, разделителей, символьных констант и литералов. Токены имен, чисел, литералов и символьных констант заполняются в процессе лексического анализа, остальные же токены заполняются на этапе инициализации лексического анализатора и их состав и положение элементов в них не меняется.

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

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

Для анализа  текста реализована процедура leksich. Данная процедура представляет собой цикл с предусловием, из которого вызываются с помощью оператора case .. of процедуры для разбора отдельных.

Приведем  правила лексической грамматики для построения автоматов выделения  лексем:

<Лексема>  → <Имя>|<Число>|<Литерал>|<Символьная  константа>|<Однолитерный разделитель>|<Двулитерный разделитель>|<Комментарий>

<Имя>  → <Буква>{<Буква>|<Цифра>}

<Число>  → <Цифра>{<Цифра>}

<Литерал>  →’”’ {<Символ>|(‘”’’”’)}’”’

<Символьная  константа> → ‘<Символ>’

<Однолитерный разделитель> → ‘(‘ | ’)’ | ‘+’ | ‘-‘ | ‘*’ | ‘/’ | ‘<’ | ‘>’ | ‘=’ | ‘”’ | ‘;’ | ‘[‘ | ‘]’ | ‘:’ | ‘,’ | ‘|’ | ‘.’

<Двулитерный разделитель> → ‘<>’ | ‘>=’ | ‘<=’ | ‘:=’ | ‘..’

<Комментарий>  → //{<Символ>}<Конец строки> | ‘/*’{<Символ>}’*/’ | ‘{‘ {<Символ>} ‘}’

<Цифра>  → ‘0’ .. ‘9’

<Буква>  → ‘A’ .. ‘Z’ | ‘a’ .. ‘z’

<Конец  строки> → eoln

Приведем  графы работы автоматов для выделения  имен, чисел, и литералов, а также  автоматы для удаления комментариев

Граф  работы автомата для выделения имен, зарезервированных слов и чисел.

Рис. 1

Граф  работы автомата для выделения литералов.

Рис. 2

Граф  работы автомата, предназначенного для удаления комментариев.

Рис. 3

Граф  работы автомата для выделения простых и сложных разделителей.

Рис. 4

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

2.3 Синтаксический анализатор.

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

- найти  и выделить синтаксические конструкции  в тексте исходной программы;

- установить  тип и проверить правильность  каждой синтаксической конструкции.

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

Синтаксический  анализатор – это основная часть  компилятора.

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

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

Приведем  правила синтаксической грамматики, на основе которой построен синтаксический анализатор:

<программа>  → 'program' I <декларация> <блок операторов> ‘end’,'.'

<декларация > → 'var' ,{ I {‘,’I}’:’ ('integer'|'char'|’byte’|'boolean'|<mas>)

<mas> → 'array' '['C'..'C']' 'of' ('integer'|'char'|'boolean'|’byte’)

<блок операторов> → 'begin' { <оператор>‘;’} ‘end’

<оператор> → <присваивание>|<условный оператор>|<оператор цикла While>|<оператор ввода>|<оператор вывода>|<оператор цикла DO>

<присваивание> → I([E]| ε){‘,’I|[E]| ε}’:=’ E|L|CH

<оператор  цикла while> → ‘while’ L ‘do’ <оператор>

<оператор ввода> → ‘read’ ‘(‘I(|[E] ε)){‘,’ I([E]| ε)}

<оператор вывода> → ‘write’’(’{E|L|<литерал>}’)’

<условный  оператор> → ‘if’ L ‘then’ <оператор> (‘else’ <оператор>| ε)

<оператор цикла do> → ‘do’  {<оператор>} ‘loop’ ‘while|until’ L

L →Т L

ТL → FL {‘or’ TL}

FL → ‘true’ | ’false’ | I [‘[‘E’]’]  | ‘not ‘(‘FL’)’ | ’!’E <предикат сравнения> E’!’

<предикат  сравнения> → ‘=’|’<>’|’>’|’<’|’>=’|’<=’

E → T {‘+’ T | ‘-‘ T}

T → F {‘*’ F | ‘/’ F}

F → I [‘[‘E’]’] | ‘(‘E’)’

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

E – математическое выражение;

L – логическое выражение;

CH – символьное выражение;

C – число;

I – имя переменной.

На этапе  синтаксического анализа лексемы  воспринимаются как терминальные символы.

Синтаксический  анализатор реализован в отдельной процедуре sintax. Для осуществления синтаксического анализа необходимо импортировать из лексического анализатора выходной поток лексем, а также токены имен переменных, чисел, литералов и символьных констант, а также массив чисел для локализации местоположения ошибки. Импорт происходит путем использования глобальных переменных.

В данном случае был применен нисходящий синтаксический анализ путем рекурсивного спуска. Название данного метода происходит из его реализации, которая заключается  в последовательности рекурсивных  вызовов процедур разбора. Для начала разбора входной цепочки нужно  вызвать процедуру для целевого символа грамматики. В данном случае целевым символом грамматики является нетерминальный символ <program>.

Для каждого  нетерминала грамматики записывается отдельная распознающая процедура. При этом соблюдаются следующие  соглашения:

- Перед  началом работы процедуры текущим  является первый символ анализируемого  понятия.

- В процессе  работы процедура считывается  все символы входной цепочки,  относящиеся к данному нетерминалу  или сообщает об ошибке. Если  правила для данного нетерминала  содержат в правых частях другие  нетерминалы, то процедура обращается  к распознающим процедурам этих  нетерминалов для анализа соответствующих  частей входной цепочки.

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

Список  процедур разбора:

    procedure pr();