Проектирование лексического и синтаксического анализаторов учебного языка. Правила преобразования логических выражений в ПОЛИЗ. Формирование триад, оптимизация их списка. Логическая структура программы. Тестирование модулей транслятора-интерпретатора.
Краткое сожержание материала:

Размещено на

Оглавление

Введение

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

2. Описание методов решения задачи

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

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

2.3 Формирование ПОЛИЗа

2.4 Формирование триад

2.5 Оптимизация списка триад

2.6 Интерпретация программы

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

4. Тестовые примеры

4.1 Тестирование лексического анализатора

4.2 Тестирование синтаксического анализатора

4.3 Тестирование модуля формирования ПОЛИЗа

4.4 Тестирование модуля формирования триад

4.5 Тестирование модуля формирования триад

4.6 Тестирование модуля интерпретации

Заключение

Введение

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

Интерпретатор - программа трансляции, которая постоянно находится в памяти. Переводит команды языка высокого уровня в машинные коды последовательно в ходе работы программы.

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

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

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

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

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

Требуется разработать транслятор-интерпретатор по заданной грамматике языка. Модуль требуется реализовать на языке высокого уровня, а именно на языке программирования Java.

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

<prog>::=<block>

<block>::=<oper>|<oper>;<block>

<oper>::=<ident>:=<vur>

<oper>::=if<ident>?<oper>:<oper>

<vur>::=<fact>|<vur>#<fact>

<fact>::=<perv>|<fact>&<perv>

<perv>::=<ident>|<c.const>|(<vur>)

<c.const>::=<num>|+<num>|-<num>

<num>::=<dig>|<num><dig>

<dig>::=0|1|2|3|4|5|6|7|8|9

<ident>::=<lett>|<ident><lett>

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

Метод синтаксического анализа - нисходящий синтаксический анализ методом LR(1).

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

1) лексический анализ;

2) синтаксический анализ;

3) преобразование грамматики в ПОЛИЗ;

4) построение триад и их оптимизация;

5) выполнение программы.

2. Описание методов решения задачи

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

В заданной грамматике выделим все типы лексем и определим их коды (Таблица 2.1)

Таблица 2.1 - Типы и коды лексем

Лексема	Код
Ключевое слово	-
IF	0
Ограничители	-
;	10
:=	11
?	12
:	13
#	14
&	15
(	16
)	17
+	18
-	19
Идентификаторы	-
A...Z	30...54
Константы:	-
0...9	60...70

Граф переходов и выходов, согласно которому происходит разбор исходной грамматики на лексемы изображен в приложении А.

По полученному графу построим таблицу переходов и выходов (Таблица 2.2)

Таблица 2.2 - Таблица переходов и выходов

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

- Столбцу соответствует определенный символ;

- Строке соответствуют состояния переходов.

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

Алгоритм работы:

1) Начальное состояние H;

2) Берем следующий символ;

3) По таблице определяется номер следующего состояния;

4) Если следующее состояние: S, то присваиваем текущему состоянию номер найденного состояния;

5) Если следующее состояние: H, то переходим в начальное состояние, и в зависимости от полученного кода лексемы добавляем лексему к нужному списку

6) Если следующее состояние: E, переходим в начальное состояние, выставляем флаг ошибки

7) Если есть еще лексемы, то переходим к пункту 2, иначе к пункту 8

8) Конец

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

Алгоритм синтаксического анализа на основе LR(k)-грамматики относится к классу алгоритмов восходящего разбора.

Строкам управляющей таблицы М (LR-таблицы разбора) ставятся в соответствие состояния, в которых может находиться анализатор, столбцам - элементы множества.

Каждая запись рабочего стека представляет собой пару: (символ, номер состояния). Перед началом работы алгоритма в рабочий стек заносится пара ($,1).

Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 2.3.

Таблица 2.3

N п/п	Значение элемента таблицы	Интерпретация алгоритмом разбора
1	Номер i порождающего правила грамматики	Удаление из рабочего стека n записей (n - количество символов в правой части правила номер i); имитация считывания в качестве следующего входного символа нетерминала левой части правила номер i.
2	("Сдвиг", номер j состояния)	Запись текущего входного символа в выходной стек и в паре с номером j - в рабочий стек; если этот символ нетерминал, установка указателей на него в ближайших к нему n записях выходного стека с пустыми указателями.
3	“допуск”	конец работы
4	"ошибка"	Вывод сообщения об ошибке; Другие файлы: Разработка учебного транслятора с упрощенного текстового языка высокого уровня Методы грамматического разбора при разработке учебного транслятора. Проектирование лексического анализатора и магазинного автомата. Программная реализ... Учебный транслятор Разработка учебного транслятора на языке программирования C# в среде объектно-ориентированного программирования Visual Studio 2012. Выделение лексем и... Учебный транслятор Методы грамматического разбора. Разработка структуры учебного транслятора на базовом языке программирования Object Pascal в среде объектно-ориентирова... Разработка текстового редактора для русскоязычного интерпретатора языка программирования Аналоги текстовых редакторов с русскоязычным интерфейсом. Разработка и тестирование программного продукта, позволяющего работать с текстом и файлами в... Написание транслятора для языка С Методика разработки и частичная реализация транслятора для языка "С" с использованием языка "С++", производящего разбиение на минимальные неделимые ко...