Разработка, отладка и тестирование транслятора для учебного языка высокого уровня

Министерство образования и  науки Украины

Севастопольский национальный технический  Университет

 

 

 

 

 

 

 

 

Кафедра КиВТ

 

 

 

 

 

 

 

 

 

Пояснительная записка

к курсовому проекту

«Разработка, отладка и тестирование транслятора для учебного языка  высокого уровня»

по дисциплине

«Системное программное обеспечение»

 

 

 

 

 

 

Выполнили: студенты гр. М-32д

Исаев Виталий

Проверила: доцент Шаталова Ю.Г.

 

 

 

 

 

 

 

 

 

Севастополь 2011

Содержание

Введение 3

1 Постановка задачи 4

2 Разработка  метода решения 5

2.1 Лексический  анализатор 5

2.2 Синтаксический  анализатор 5

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

2.4 Таблица  символов 7

2.5 Генератор  кода 8

3 Описание программы 9

3.1 Назначение программы 9

3.2 Требования к программному и техническому обеспечению 9

3.3 Используемые переменные и спецификация методов 9

4 Руководство оператора 11

5 Программа и методика испытаний 12

Заключение 15

Библиографический список 16

Приложение 17

 

 

 

Введение

 

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

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

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

 

1. Постановка задачи

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

Исходными данными является программа на языке  PL0.

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

Грамматика языка PL0

<программа>::=<блок>.

<блок>::=<декларация констант><декларация переменных><декларация процедур>

<декларация констант>::=CONST<список  определений констант>

<декларация переменных>::=VAR<список  переменных>;|$

<декларация процедур>::=<список описаний процедур>

<список описаний процедур>::=<список описаний процедур><описание процедуры>;|$

<список определений констант>::=<список определений констант>,

                                 <определение константы>|<определение  константы>

<определение константы>::=<имя константы>=<число>

<список переменных>::=<список  переменных>,<переменная>|<переменная>

<переменная>::=<идентификатор>

<список описаний процедур>::=PROCEDURE<имя  процедуры>;<блок>

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

                            CALL<имя процедуры>|

                            BEGIN<список операторов>END|

                            IF<условие>THEN<оператор>|

                            WHILE<условие>DO<оператор>|$

<имя процедуры>::=<идентификатор>

<список операторов>::=<список  операторов>;<оператор>|<оператор>

<условие>::=<выражение>|<выражение>==<выражение>

             <выражение><><выражение>

             <выражение><<<выражение>

             <выражение>>><выражение>

             <выражение>>=<выражение>

             <выражение><=<выраа%ние>

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

0терм>::=<слагаемое>|<терм>+<слагаемое>|<терм>-< лагаемое>

<слагаемое>::=<множитель>|<слагаемое>*<множитель>|

               <слагаемое>/<множитель>

<множитель>::=<переменная>|<число>|<(выражение)>

<идентификатор>::=<буква>|<идентификатор><буква>|

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

<число>::=<натуральное число>|+<натуральное число>|

           -<натуральное  число>

<натуральное число>::=<цифра>|<натуральное число><цифра>

<буква>::=A|B|C|D|E|F|G|N|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

<цифра>::=0|1|2|3|4|5|6|7|8|9

2  Разработка метода  решения

 

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

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

Таблица типов лексем:

while	ttWHILE	=	ttDEFINE	<<	ttLESS
do	ttDO	:=	ttASSIGN	<=	ttLEQU
begin	ttBEGIN	+	ttPLUS	>=	ttGEQU
end	ttEND	-	ttMINUS	<>	ttNEQU
const	ttCONST	*	ttMUL	.	ttDOT
var	ttVAR	/	ttDIV	(	ttLBRACKET
call	ttCALL	==	ttEQUAL	)	ttRBRACKET
procedure	ttPROCEDURE	>>	ttGREATER	,	ttCOMMA
print	ttPRINT	?	ttUNKNOW	;	ttSEMICOLON
<eof>	ttEOF	число	ttNUMBER	идент	ttIDENT

 

Входные данные – имя файла с листингов PL0.

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

Обнаруживаемые  ошибки:

Неизвестная лексема

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

По иерархии грамматик Хомского выделяют 4 основные группы языков (и описывающих их грамматик). При этом наибольший интерес  представляют регулярные и контексно-свободные (КС) грамматики и языки. Они используются при описании синтаксиса языков программирования. С помощью регулярных грамматик можно описать лексемы языка - идентификаторы, константы, служебные слова и прочие. На основе КС-грамматик строятся более крупные синтаксические конструкции - описания типов и переменных, арифметические и логические выражения, управляющие операторы, и, наконец, полностью вся программа на исходном языке.

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

Входные данные – лексический анализатор

Выходные  данные – синтаксическое дерево

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

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

Входные данные – синтаксическое дерево

Выходные  данные – список сообщений

 

 

Обнаруживаемые ошибки:

Идентификатор уже объявлен

Неизвестная процедура

Неизвестная переменная

Деление на ноль

Переменная  не инициализирована

 

Подсказки:

Идентификатор не используется

 

2.4 Таблица символов

В процессе работы компилятор хранит информацию об объектах программы в  специальных таблицах символов. Как  правило, информация о каждом объекте  состоит из двух основных элементов: имени объекта и описания объекта. Информация об объектах программы должна быть организована таким образом, чтобы  поиск ее был по возможности быстрее, а требуемая память по возможности  меньше.

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

Реализована на основе хеш-таблицы.

 

Структура символа:

• Имя
• Значение
• Флаг использования
• Тип
• Указатель на узел синтаксического дерева

 

2.5 Генератор кода

Генерация объектного кода - это перевод компилятором внутреннего представления исходной программы в результирующую объектную  программу на языке ассемблера или  непосредственно на машинном языке (машинных кодах).

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

Входные данные – синтаксическое дерево

Выходные  данные – объектный код

 

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

3.1 Назначение программы

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

3.2 Требования к программному  и техническому обеспечению

Для функционирования программы  необходимо:

• ЭВМ типа IBM PC с процессором Pentium с тактовой частотой от 866 МГц и выше;
• Минимум 10 МБ свободного дискового пространства;
• Не менее 32 МБ оперативной памяти;
• Операционная система семейства Windows.

3.3 Используемые переменные и спецификация методов

 

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

Реализован классом «Lexer». Возвращает следующую лексему

Public Token nextToken();

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

Реализован классом «Parser». Строит абстрактное синтаксическое дерево.

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

Реализован одним классом «SemanticCheck». Выполняет семантический анализ.

Public void visit(DivedeOpNode divideOpNode);

                   DivideOpNode – оператор деления

Интерпретатор.

Реализован классом «PL0». Интерпретирует синтаксическое дерево.

public void run();

Генератор кода.

Реализован классом «CodeGenerator». Генерирует код по синтаксическому дереву

public CodeGenerator(List<String> listing);

List<String> listing – список команд

Node – реализация абстрактного синтаксического дерева

SyntaxVisitor – реализация абстрактного синтаксического дерева. Реализован с помощью шаблона проектирования – “Посетитель” для удобного обхода всех ветвей дерева.

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

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

 

 

4 Руководство оператора

 

Пользовательский интерфейс имеет  вид:

 

 

Назначение  панелей управления:

1. Редактор кода. Данные можно загрузить из файла или ввести вручную.
2. Окно сообщений. Сюда выводятся сообщения об ошибках, подсказки и системные сообщения.
3. Окно с вкладками позволяет просматривать результат работы транслятора.

 

С помощью меню “Файл” можно открыть, сохранить листинг исходной программы.

В меню “Проект” скомпилировать или настроить проект.

Также, основные функции вынесены на главную панель.

 

5 Программа и методика испытаний

 

Пример №1 Лексическая ошибка

Специально  введем лексическую ошибку

Ошибка  обнаружена.

Пример №2 Синтаксическая ошибка

Пример №3 Семантические ошибки

Ошибки  обнаружены.

 

Пример №4 Числа Фибоначчи

Попробуем вывести несколько чисел Фибоначчи

Программа отработала корректно.

Пример №5

Вычисление  факториала