Содержание

Содержание 2

Задание 3

Описание входного языка 4

Структура программы и секции объявлений 4

Используемые типы данных 4

Тип 5

Представление операторов во входном языке 5

Представление выражений во входном языке 6

Приоритет операций 7

Описание компилятора 8

Общая схема компиляции 8

Разработка лексического анализатора 9

Типы выделяемых лексем 9

Описание ключевых слов и идентификаторов 9

Описание целочисленных, вещественных и строковых констант 10

Описание разделителей 10

Описание комментариев и незначащих символов 10

Диаграмма лексического анализатора 11

Спецификация лексического анализатора 12

Множество токенов лексического анализатора 12

Формат используемых таблиц лексем 14

Представление потока токенов на выходе лексического анализатора 15

Разработка синтаксического анализатора 17

Назначение синтаксического анализатора 17

Стратегии проектирования синтаксического анализатора 17

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

Пример использования вспомогательных средств генерации таблиц 19

Спецификация синтаксического анализатора 20

Подготовка полной грамматики входного языка 22

Описание схемы атрибутной трансляции 24

Представление атрибутов в памяти ЭВМ 29

Описание промежуточного представления программы 30

Обработка ошибок 31

Разработка генератора кода 33

Назначение генератора кода 33

Стратегия проектирования генератора кода 33

Разработка библиотеки поддержки 33

Спецификация генератора кода 35

Формат текста программы на языке ассемблера 35

Генерация команд по промежуточному коду 36

Компоновка исполняемого модуля 38

Выполнение контрольного примера 39

Содержание контрольного примера 39

Выполнение лексического анализа 39

Выполнение синтаксического анализа 40

Выполнение генерации кода 40

Выполнение программы 43

Выводы по результатам выполнения курсовой работы 44

Приложения 45

Приложение 1 45

Приложение 2 51

Задание

Разработать компилятор, реализующий перевод текста программы на некотором подмножестве языка ПАСКАЛЬ в соответствующий текст на языке ассемблера.

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

- базовый синтаксис входного языка - язык ПАСКАЛЬ;

- в языке должны быть представлены следующие базовые типы:

- целый integer

- вещественные real

- булевский boolean

- символьный char

- в языке должны быть представлены следующие структурные типы:

- строка string

- стек stack

- в языке должны быть представлены следующие структурные операторы:

- оператор условия if–then–else

- оператор цикла с параметром for–to–do

- оператор следования begin-end

- также в языке должны присутствовать дополнительные операторы:

- оператор присваивания;

- оператор вывода на терминал;

- оператор вводы с терминала

Требования :

- алгоритм синтаксического анализа для SLR(1)-грамматик;

- внутреннее представление в виде тетрад.

Описание входного языка

Для описания синтаксиса входного языка используем формулы Бэкуса-Наура (БНФ), основанные на следующих упрощения :

• необязательные элементы заключаются в квадратные скобки [ и ]

• повторяющиеся ноль и более раз элементы заключаются в фигурные скобки { и }

Также отметим следующее:

чтобы квадратные, фигурные скобки и различные знаки, являющиеся метасимволами, отличались от терминальных символов определяемого языка – квадратные, фигурные скобки и другие знаки последних записываем в кавычках (например, “]”). Зарезервированные слова определяемого языка записываем с использованием полужирного шрифта (например, program).

Структура программы и секции объявлений

Программы на входном языке может быть представлена в виде БНФ следующим образом:

<программа> ::= [program <идентификатор>;]

{ <описание констант> | <описание переменных> }

<структурный оператор>.

<описание констант> ::= const <идентификатор> = <выражение>;

{ <идентификатор> = <выражение>; }

<описание переменных> ::= var <идентификатор>: <тип>;

{<идентификатор>:<тип>; }

<тип> ::= <простой> | <структурированный>

<простой> ::= integer | real | boolean | char

<структурированный> ::= string | stack

Как следует из определения, программа может предваряться необязательным ключевым словом «program» за которым следует идентификатор и точка с запятой. Далее располагается произвольное количество секций объявлений переменных и констант, а затем – тело программы, завершённое точкой.

В рамках данной формы Бэкуса-Наура накладываются следующие семантические ограничения:

- все используемые идентификаторы должны быть уникальны;

- значения выражений в объявлениях констант должны быть вычислимы к моменту объявления константы. Значение, присвоенное константе в момент объявления, не может изменяться.

Используемые типы данных

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

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

Таблица 1

Тип	Представление	Диапазон значений
integer	2 байтами, ведущий бит - знаковый	-32768 до 32767
real	4 байтами, формат представления числа с плавающей точкой - IEEE	модуля: 1.5 . 10-45 до 3.4 . 1038
char	1 байтом без знака	0 до 255, может представлять символьный код ASCII
boolean	1 байтом без знака	0 до 255, причем значение 0 соответствует FALSE, остальные значения - TRUE
string	256 байтами	содержит строку формата ASCII с завершающим нулём (null-terminated string), таким образом, реальная длина хранимой строки не должна превышать 255 символов
stack	256 байтами	содержит стек байтовых значений, каждое из которых может принимать значения от 0 до 255. Первый (младший) байт хранит количество элементов в стеке, поэтому действительное количество элементов в стеке не может превосходить 255

Замечание:

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

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

Оператором является набор инструкций, выполняемых программой. Операторы выполняются последовательно, некоторые операторы могут изменять порядок выполнения других операторов. Допустимые операторы входного языка приведены в следующей форме Бэкуса-Наура:

<оператор>::=<оператор присваивания>

| <оператор ввода-вывода>

| <оператор стека>

| <оператор ветвления>

| <оператор цикла>

| <структурный оператор>

|<нет оператора>

<оператор присваивания>::=<идентификатор> := <выражение>

<оператор ввода-вывода>::=write( <выражение> )

| read( <идентификатор> )

| writeln

<оператор стека>::=push( <идентификатор>, <выражение> )

<оператор ветвления>::= if <выражение> then <оператор>

[ else <оператор> ]

<оператор цикла>::=for <оператор присваивания> to <выражение>

do <оператор>

<структурный оператор>::=begin <оператор> {; <оператор>} end

На используемые в программе операторы вводятся следующие семантические ограничения:

- идентификаторы, используемые во всех операторах, должны быть предварительно объявлены в секциях объявления переменных или констант;

- идентификатор в левой части оператора присваивания должен соответствовать переменной;

- тип переменной в левой части оператора присваивания и тип выражения в правой части оператора присваивания должны быть совместимы;

- выражение в операторе вывода должно иметь символьный, строковый, целый, либо вещественный тип;

- идентификатор в операторе ввода должен соответствовать переменной;

- переменная в операторе ввода может иметь символьный, строковый, целый, либо вещественный тип;

- идентификатор в операторе стека должен соответствовать переменной, имеющей тип стека;

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

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

- все выражения в операторе цикла с параметром должны иметь целый тип;

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

Представление выражений во входном языке

Выражения описываются в инфиксной форме (знак операции располагается между операндами, для унарной операции - слева от оператора.

<выражение> ::=<выражение> or <дизъюнктор>

| <дизъюнктор>

<дизъюнктор>::=<дизъюнктор> and <коньюнктор>

| <конъюнктор>

<конъюнктор>::=<конъюнктор> <знак отношения> <отношение>

| <отношение>

<знак отношения>::= = | > | >= | < | <= | <>

<отношение> ::=<отношение> <знак суммы> <слагаемое>

| <слагаемое>

<знак суммы>::= + | -

<слагаемое> ::= <слагаемое> <знак произведения> <множитель>

| <множитель>

<знак произведения>::= * | /

<множитель> ::= ( <выражение> )

| <знак суммы> <множитель>

| not <множитель>

| <атом выражения>

<атом выражения>::=<литерал>

| <идентификатор>

| <функция стека>

<функция стека>::=top( <идентификатор> )

В таблице 2 описаны допустимые типы:

Таблица 2

Операция	Описание
Логические операции (or, and, not)	Операнды должны иметь булевский тип. Возвращаемое значение имеет булевский тип.
Операции сравнения (=, >, >=, <, <=, <>)	Операнды должны иметь целый, либо вещественный тип. Возвращаемое значение имеет булевский тип
Арифметические операции (+, -, *, /)	Операнды должны иметь целый, либо вещественный тип. Возвращаемое значение имеет целый тип в случае, если все операнды целочисленные, и вещественный тип в противном случае. При делении целых чисел результат всегда вещественный
Функция стека (top)	Операнд должен иметь тип стека. Возвращаемое значение имеет символьный тип.

В качестве элементарных операндов (атомов) выражений могут выступать:

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

- идентификаторы, предварительно объявленные в секции объявления переменных, либо констант;

- функция стека, соответствующая значению на вершине стека, указанного в качестве параметра функции, - вызов функции не извлекает значение из стека. Он некорректен в случае, если количество элементов в стеке равно нулю

Приоритет операций

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

Таблица 3

Знак операции	Название операции	Порядок выполнения
* /	Арифметические операции: умножение деление	Слева направо Слева направо
+ -	Арифметические операции: сложение вычитание	Слева направо Слева направо
not	Логическое отрицание	Слева направо
and	Логическое И (конъюнкция)	Слева направо
or	Логическое ИЛИ (дизъюнкция)	Слева направо
< <= > >= = <>	Операции отношения: меньше меньше или равно больше больше или равно равно не равно	Слева направо Слева направо Слева направо Слева направо Слева направо Слева направо
+, -	Определение знака	Справа налево

Для изменения порядка вычисления можно использовать скобки(они могут быть вложенными).