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

Содержание

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

Подготовка программы начинается с редактирования файла, содержащего  текст этой программы, который имеет  стандартное расширение для данного  языка. Затем выполняется его  трансляция, которая включает в себя несколько фаз: лексический, синтаксический, семантический анализ, генерация  кода. В результате трансляции получается объектный модуль  -  некий "полуфабрикат" готовой программы, который потом участвует в ее сборке. Файл объектного модуля имеет стандартное расширение ".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)  Классификация лексем на  терминалы, идентификаторы, литералы. - если распознанная лексема   –терминал, то необходимо произвести  её поиск в таблице терминальных  символов и в случае обнаружения   –записать в таблицу терминалов;

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

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