Проектирование лексического и синтаксического анализаторов учебного языка. Правила преобразования логических выражений в ПОЛИЗ. Формирование триад, оптимизация их списка. Логическая структура программы. Тестирование модулей транслятора-интерпретатора.
Аннотация к работе
Простой интерпретатор анализирует и тут же выполняет (собственно интерпретация) программу покомандно (или построчно), по мере поступления ее исходного кода на вход интерпретатора. Недостаток - такой интерпретатор обнаруживает ошибки в тексте программы только при попытке выполнения команды (или строки) с ошибкой. Переводит команды языка высокого уровня в машинные коды последовательно в ходе работы программы. Затем можно будет создать интерпретатор, который решает задачу, анализируя предложения этого языка.Требуется разработать транслятор-интерпретатор по заданной грамматике языка. Модуль требуется реализовать на языке высокого уровня, а именно на языке программирования Java. Согласно данной грамматике необходимо разработать транслятор-интерпретатор, выполняющий следующие действия: 1) лексический анализ;В заданной грамматике выделим все типы лексем и определим их коды (Таблица 2.1) Граф переходов и выходов, согласно которому происходит разбор исходной грамматики на лексемы изображен в приложении А. По полученному графу построим таблицу переходов и выходов (Таблица 2.2) Кодировать состояния будем следующим образом: - Столбцу соответствует определенный символ; 5) Если следующее состояние: H, то переходим в начальное состояние, и в зависимости от полученного кода лексемы добавляем лексему к нужному спискуКаждая запись рабочего стека представляет собой пару: (символ, номер состояния). Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице 2.3. Номера состояний устанавливаются в правой части каждого правила: перед первым символом, между любыми двумя символами и после последнего символа. А если непосредственно слева от одного и того же символа в каких-либо правилах установлены одинаковые множества меток, то и непосредственно справа от этого символа в этих правилах следует поставить одну и ту же метку. Если метка j размещается за последним символом правой части правила номер i (если правая часть правила - "lambda", j совпадает с меткой состояния, непосредственно справа от которого находится не терминал левой части правила i), то определяется множество Q символов, которые в какой-либо сентенциальной форме могут следовать за не терминалом левой части правила номер i, и M(j,q)=i для всех q, принадлежащих Q.ПОЛИЗ - форма записи математических выражений, в которой операнды расположены перед знаками операций. Приведем таблицу приоритетов: Операция ПриоритетТриады представляют собой запись операций в форме из трех составляющих: , и , при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Триады при записи будем последовательно номеровать для удобства указания ссылок одних триад на другие.В качестве метода оптимизации выбран метод удаления общих подвыражений. Прямой указатель триады, предшествующей удаляемой, равен ПУ удаляемой, а ОУ следующей за удаляемой, равен ОУ удаляемой;Интерпретация - анализ, обработка и тут же выполнение исходной программы или запроса (в отличие от компиляции, при которой программа транслируется без ее выполнения). Если индекс триады превышает размер списка триад, то к п. Берем триады по индексу текущей триады Берем триаду, которую необходимо выполнитьПроцесс трансляции разбивается на следующие основные блоки: 1. При наличии ошибок доступ к выполнению последующих блоков закрыт; При наличии ошибок доступ к выполнению следующих этапов закрыт; Формирование ПОЛИЗА - формирование такой цепочки лексем и операндов, в которой операции встречаются в порядке их выполнения; Формирование триад - формирование некоторого промежуточного кода, позволяющего в дальнейшем упростить перевод на машинный язык;По символу [V ] переходим в состояние: S1 По символу [R ] переходим в состояние: S3 По символу [] переходим в состояние: H0 По символу [] переходим в состояние: H99 Обнаружен идентификатор: A По символу [; ] переходим в состояние: S21Пример №1. Выходные данные: Начало синтаксического анализа: Поданный список лексем: [30, 11, 61, 10, 31, 11, 62, 10, 32, 11, 60, 10, 0, 32, 12, 31, 11, 63, 13, 31, 11, 64, 10, 32, 11, 31, 14, 30, 10, 30, 11, 32, 15, 31, 10, 31, 11, 31, 14, 30] Таблица разбора: Рабочий стек M(,a) Входной символ Правило Разбор был успешно завершенПример №1.Пример №1.Выходные данные: Оптимизация прошла успешно, удаленное количество триад: 1В ходе работы над курсовым проектом была изучена методика построения компилятора, прошло ознакомление с этапами интерпретации. Были получены практические навыки по созданию модулей компилятора для подмножества грамматики учебного языка Logic5. Проектирование проходило в несколько этапов: проектирование блока лексического анализатора, проектирование блока синтаксического анализатора, проектирование блока формирования ПОЛИЗА, проектирование блоков построения и оптимизации списка триад, проектирование блока интерпретации кода.
План
Оглавление
Введение
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 Тестирование модуля интерпретации
Заключение
Введение
Простой интерпретатор анализирует и тут же выполняет (собственно интерпретация) программу покомандно (или построчно), по мере поступления ее исходного кода на вход интерпретатора. Достоинством такого подхода является мгновенная реакция. Недостаток - такой интерпретатор обнаруживает ошибки в тексте программы только при попытке выполнения команды (или строки) с ошибкой.
Интерпретатор - программа трансляции, которая постоянно находится в памяти. Переводит команды языка высокого уровня в машинные коды последовательно в ходе работы программы.
Если некоторая задача возникает часто, то имеет смысл представить ее конкретные проявления в виде предложений на простом языке. Затем можно будет создать интерпретатор, который решает задачу, анализируя предложения этого языка.
Например, поиск строк по образцу - весьма распространенная задача. Регулярные выражения - это стандартный язык для задания образцов поиска. Вместо того чтобы программировать специализированные алгоритмы для сопоставления строк с каждым образцом, не проще ли построить алгоритм поиска так, чтобы он мог интерпретировать регулярное выражение, описывающее множество строк-образцов.
Процесс компиляции, как правило, состоит из нескольких этапов: лексического, синтаксического и семантического анализов, генерации промежуточного кода, оптимизации и генерации результирующего машинного кода.
В ходе данного курсового проекта будет разработан интерпретатор учебного языка программирования, в состав которого входят лексический, синтаксический анализ, а также посторонние триад, их оптимизация и интерпретация.