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

Содержание

Введение
Анализ  технического задания
Описание языка
Выбор и обоснование архитектуры системы
Выбор и обоснование алгоритма
Описание программы
Методика испытаний
Заключение
Список использованной  литературы
Приложение А(обязательное)
Приложение Б(обязательное)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Уже в ЭВМ первого поколения  появляется язык мнемокода (впоследствии – язык ассемблера) для более  понятного человеку представления  машинных команд. Программистам уже  не нужно тратить уйму времени  над загадочной последовательностью  нулей и единиц. Затем возникают  и занимают прочное место в  решение задач другие, более сложные  языки программирования, и дальнейшее развитие систем программирования идет именно в повешении дружественности  к человеку.

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

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

По классификации программного обеспечения ЭВМ компиляторы  относятся к системным обрабатывающим программам. Их функцией является перевод  программы с языка высокого уровня в машинный код.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Анализ технического задания

 

Задание можно разделить на 3 части: лексический анализ, синтаксический анализ, разработка компилятора в  целом.

Лексический анализ включает этапы:

- преобразование исходного текста  в длинную строку;

- выделение лексических единиц (лексем);

- распознавание типов лексем;

- добавление лексем в соответствующие  таблицы;

В данном языке используются следующие  типы лексем:

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

- ключевые слова;

- знаки операций;

- разделители.

Идентификаторы (имена).

Имя не может начинаться с цифры; в начале и в конце  имени подчерк недопустим; два  подчерка не могут стоять подряд; строчные буквы недопустимы. Кроме того, идентификаторы не могут совпадать со служебными словами.

Ключевые слова

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

Знаки операций.

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

Разделители.

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

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

В процессе синтаксического анализа  решаются две задачи:

1. распознавание предложений языка;
2. определение правильности конструкций.

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

Алфавит - набор допустимых символов и знаков, из которых строятся элементарные конструкции языка. Отдельные знаки  объединяются в лексемы.

Лексема - отдельная неделимая конструкция, имеющая смысл.

Слова (лексемы) объединяются в предложения (операторы) согласно правилам синтаксиса.

Синтаксис - описание правильных конструкций  языка или правил получения правильных конструкций языка.

Компиляция состоит из этапов анализа  и синтеза. В анализ

 

входит лексический, синтаксический и семантический анализ.

Лексический анализ состоит из распознавания  лексем, их классификации и определения  правильности.

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

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

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

Входные данные - таблица кодов  лексем, сформированная на стадии лексического анализа.

Выходные данные - сообщение об успешном завершении анализа или  сообщение об имеющихся ошибках.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Описание языка 

РАПИРА — Расширенный Адаптированный Поплан-Интерпретатор, Редактор, Архив — процедурный язык программирования, был разработан в начале 80-х годов в СССР в качестве средства перехода от более простых языков к языкам высокого уровня. Синтаксис построен на основе русской лексики. Язык использовался в школах для изучения информатики. Преподавание на Рапире велось в «Заочной школе программирования» в журнале «Квант» с начала 1980 г. 

Конструктор использует следующие  подмножества набора символов кода ASCII:

- Буквы алфавита от A до Z, от a до z, от А до Я, а до  я, символ подчеркивания

- Цифры - арабские от 0 до 9

- Пробелы - символ пробела  (ASCII 32)

Идентификаторы выступают  в качестве имен классов, переменных, процедур, функций. Идентификатор может  иметь любую длину. Идентификатор  должен начинаться с буквы и не должен содержать пробелов. После  первого символа допускаются  буквы, цифры и знак подчеркивания (ASCII 95). Как и зарезервированные  слова, идентификаторы безразличны  к регистру клавиатуры. 

В данном задании встречаются  следующие идентификаторы: ‘K’,’I’,’J’. Их следует записать в таблицу идентификаторов.

Ключевые (зарезервированные) слова: иначе, всё, кнц, до, от,.

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

Пример программы:

 

 

имена k,I,j;

для I от 1 до 10 ::

для j от 1 до 5 ::

к=k+i*j;

все;

все;

кнц.

Язык Рапира унаследовал  многие особенности языков Поплан и  Сетл. Так, например, в языке Рапира используются необъявляемые бестиповые переменные(переменная считается объявленной при первом использовании, тип переменной определяется типом присвоенного выражения, инициализированной переменной можно присваивать значения типов, отличающихся от первоначально присвоенного), поддерживаются высокоуровневые составные типы данных — кортежи и множества (последние являются частным случаем кортежа). Кортеж в Рапире, фактически — гетерогенный динамический массив, для него на уровне языка поддерживаются операции объединения, сравнения, получения размера и извлечения части.

 

 

 

 

 

 

 

 

 

 

3. Выбор и обоснование архитектуры  системы

Для решения поставленной задачи был  выбран язык Object  Pascal и, соответственно, среда программирования Delphi.

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

Данную программу можно разбить  на следующие модули:

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

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

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

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

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

Возможны два варианта реализации интерфейса данной программы: консольный или оконный.

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

Данный вариант не требует больших  объемов памяти и быстродействия системы.

Второй вариант обеспечивает работу пользователя с оконным интерфейсом. Текст, входной программы, может  быть загружен из файла в окно редактирования или непосредственно введен в  нем. Результат работы программы  - сообщение об ошибке выводятся  в другие окна редактирования. Для  получения имен файлов применяются  стандартные диалоговые окна. Можно  также реализовать вывод отладочной информации (лексемы, таблицы) в  отдельном  окне. Все действия (загрузка и сохранение файлов, компиляция) выполняются при  нажатии на соответствующие пункты меню.

Данный вариант требует более  высокой производительности системы  и объема оперативной памяти, но он имеет свои преимущества по сравнению  с консольным интерфейсом: большая  наглядность и удобство работы.

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

 

 

 

 

 

 

 

 

 

 

4. Выбор и обоснование алгоритмов

 

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

Задачу лексического разбора следует  разбить на две подзадачи:

1)  Сканирование исходного текста;

2)  Распознавание лексем;

3)  Классификация лексем на  терминалы, идентификаторы, литералы. - если распознанная лексема   –терминал, то необходимо произвести  её поиск в таблице терминальных  символов и в случае обнаружения   –записать в таблицу терминалов;

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

-  если распознанная лексема   –идентификатор, то необходимо произвести  её поиск в таблице терминальных  символов на предмет принадлежности  служебному слову и в случае  не  обнаружения произвести поиск  в таблице идентификаторов. Если  элемент не найден –добавить.

4)  Создание таблицы стандартных  символов

В таблицу стандартных символов записывается пары <таблица  –индекс  лексемы> в той последовательности, в которой элемент встречается  в тексте программы(Рисунок 1).

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

В техническом задании указано, что синтаксический разбор  осуществить LR-разбором. LR-разбор и детерминированная  грамматика представлены в пункте 2 пояснительной записки.

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

1.  Формируем польскую запись:

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

2.  Переводим польскую запись  в матричную форму: 

Читаем обратную польскую запись слева  направо. При чтении операнда  –  он записывается в стек ; при чтении операции  –извлекаем из стека  два  верхних операнда, формируем тройку (операция, операнды), записываем её в  матрицу; в стек E записываем элемент  матрицы, в котором будет результат  выполнения операции.

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

 

Таблица 3 –Таблица приоритетов.

(	0
)	1
+-	2
*/	3

Поясним описанный алгоритм разбора  сложного арифметического выражения  на примере. Разберем строку следующего вида:  d+(a+b)*c.

Таблица 4 –Таблица перевода арифметического выражения в ОПН:

Стек оп-ий	Вход	Выход
E	D	D
+	+	D
+(	(	D
+(	A	DA
+(+	+	DA
+(+	B	DAB
+	)	DAB+
+*	*	DAB+
+*	C	DAB+C
E	$	DAB+C*+

Таблица 5 –Таблица ОПН в матричную форму:

Стек оп-ов	Вход	Выход
D	D
DA	A
DAB	B
DM1	+	M1:AB+
DM1C	C
DM2	*	M2:M1C*
M3	+	M3:DM2+

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

 

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

 

5.1 Общее описание

При разработке транслятора с подмножества языка Рапира  использовался язык программирования  Object Pascal и среда  программирования  Delphi2007.  Данный продукт  позволяет проводить  лексический анализ программы, состоящей  из определенного набора команд и  операторов, написанной на данном языке. Производится синтаксический анализ программы  и выводится на экран информация о том, какая именно ошибка допущена при написании программы на данном языке. В случае положительного результата разбора выводится сообщение, что  ошибок нет.

Установка программы - данное приложение не требует дополнительной установки. В комплект поставки включается исполняемый файл  Project4_XE3.exe.

Минимальные требования:

- Операционная система: Windows XP/Vista/Windows7;

- Процессор: Pentium 3 и выше;

- Оперативная память: 1,5 Мb;

- Видеокарта: VGA;

- Жесткий диск: 1,5 Мb свободного места;

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

 

 

 

 

 

 

 

6. Методика испытаний

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

имена k,i,j;

для i от 1 до 10::

для j от 1 до 5::

k=k+i*j;

все;

все;

кнц.

При компиляции получим сообщение, что ошибок нет(рисунок 1).

Рисунок 1-При компиляции нет ошибок

 

 

Текст программы:

имена k,i,j;

для i от 1 до 10::

для j от 1 до 5::

k=k+i*j;

все;

все

кнц.

При компиляции этого кода была найдена  ошибка и вывелось соответствующее  сообщение, что «; после цикла  не найдена» (Рисунок 2). Это обусловлено несходимостью с грамматикой цикла, описанной правилом  <цикл>::=от <оп> до <оп>::<спис_опер>все;

Рисунок 2- Ошибка в цикле

 

 

-проверка на описание переменных

Текст программы:

имена k,i,j;

для iyt от 1 до 10::

для j от 1 до 5::

k=k+i*j;

все;

все;

кнц.

Используемые переменные должны быть описаны, если она будет не описана, появится сообщение с ошибкой( Рисунок  3)

Рисунок 3 – переменная не описана

 

 

 

 

Заключение

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

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

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

В ходе выполнения курсового проектирования  были получены  навыки оформления программной  документации в соответствии с Единой Системой Программной Документации и повышен уровень практических навыков программирования в интегрированной  среде программирования  Borland  Delphi 2007. Также были углублены теоретические  знания по дисциплине  «Теория языков программирования и методы трансляции»  и развиты навыки самостоятельной  деятельности в области создания программных продуктов.

 

 

 

 

 

 

 

 

 

 

Список используемой литературы

1.  Фаронов В.В. Delphi. Программирование  на языке высокого

уровня: Учебник для вузов –Спб.: Питер, 2006. –640с.: ил.

2.  Архангельский А.Я. Программирование  в Delphi 7.  –М.: ООО «Би-ном-Пресс»,2003 г. –1152с.: ил.

3.  Разработка компиляторов: метод.  Указ. По курсовому проектированию. –Муром: ИПЦ МИВлГУ, 2007 –52с.

4.  Гордеев А.В., Молчанов А.Ю.  Системное программное обеспече-ние.  СПб: Питер, 2001г. -736с.

5.  Грис Д. Конструирование  компиляторов для ЦВМ. М.: Мир,

1975. -544, 1 экз.

6.  Петюшкин А.В.  HTML. Экспресс  курс.  –Спб.: БХВ-Петербург,

2003. –256с.

7.  Ахо А., Ульман Дж. Теория  синтаксического анализа, перевода  и

компиляции. –М.: Мир, 1978. Т.1, 612с. –Т.2, 487с.