Разработка синтаксического анализатора для заданного фрагмента кода
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
.
СИНТАКСИЧЕСКИ ОРИЕНТИРОВАННАЯ ТРАНСЛЯЦИЯ
.1
Общие понятия
.2
Транслятор, интерпретатор, препроцессор
.3
Трансляция, основанная на структуре текста. Идея Н. Хомского
.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
.1
Описание заголовочных файлов
.2
Организация программы
.3
Реализация программы
ЗАКЛЮЧЕНИЕ
СПИСОК
ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Построение трансляторов является областью
информатики, в которой глубокие теоретические результаты привели к решению
важных практических проблем. Эта область объединяет идеи, методы и алгоритмы
синтаксического, лексического и семантического анализа искусственных языков, а
также огромный накопленный практический опыт техники и технологии разработки
трансляторов для различных языков программирования высокого уровня, для
различных архитектур процессоров и разнообразных операционных систем.
Основной практической целью разработки
трансляторов является построение программных систем специфического назначения -
языковых процессоров. Эта область базируется на своем фундаменте - теории
формальных языков. И методы построения трансляторов являются областью знаний,
нужных не только разработчикам языков программирования высокого уровня: идеи и
методы этой области используются во все возрастающем числе приложений
компьютеров
1. СИНТАКСИЧЕСКИ ОРИЕНТИРОВАННАЯ ТРАНСЛЯЦИЯ
.1 Общие понятия
Транслятор - это программа, которая переводит
входной текст в некоторый выход. Например, входом транслятора может быть
программа, написанная на языке программирования высокого уровня, таком как Паскаль
или C, или каком-нибудь
специализированном языке. Выходом транслятора может быть целевая программа на
языке ассемблера, промежуточном языке или машинном языке, либо просто
последовательность некоторых действий, предписанных входным предложением. Основной
мыслью является, что для любых преобразований <вход-выход> современные
трансляторы используют идею синтаксически ориентированной трансляции, состоящую
в том, что для любого преобразования предложения входного языка транслятор
должен использовать структуру этого предложения. Такой подход является обычным
в науке: анализ и понимание сложной системы всегда явно или неявно опирается на
структуру этой системы.
.2 Транслятор, интерпретатор, препроцессор
Задачей транслятора является выполнить перевод,
преобразования текста, написанного на некотором языке L,
в некоторый выход. Если входной язык - алгоритмический, то входной текст
называют входной программой.
Рисунок 1. Метод работы транслятора
При трансляции языков программирования, от
транслятора может требоваться выполнение разных задач. Если задачей транслятора
является трансляция в язык низкого уровня, например в машинный язык, или язык
ассемблера, то такой транслятор называется компилятором. Другая возможная
задача при трансляции программы на алгоритмический язык - непосредственное
выполнение транслятором операторов исходного кода. В этом случае транслятор
называется интерпретатором. Интерпретация используется для “командных языков”,
каждый оператор которых - это вызов некоторой программы, например редактора
исходного текста. Отличие компилятора от интерпретатора в том, что
интерпретатор непосредственно выполняет последовательность команд, а компилятор
построит и выдаст последовательность команд объектного языка, осуществляющих
непосредственно вычисление значения.
.3 Трансляция, основанная на структуре текста.
Идея Н. Хомского
Синтаксисом языка называется совокупность правил
построения текста - предложений и отдельных их составных частей, иными словами
это правила построения конструкций языка. Синтаксис языка определяет, как
правильно строить предложения и их части. Семантикой языка называется
совокупность правил интерпретации предложений и конструкций языка. Семантика
определят смысловую нагрузку предложений. Транслятор можно считать
преобразователем информации, формирующим выход в соответствии с входным текстом
на исходном языке.
Первым идею синтаксически ориентированной
трансляции выдвинул американский лингвист Ноам Хомский. В своих работах, он
исследовал механизмы понимания человеком, смысла фраз естественного языка. Одна
из основных его идей заключалась в том, что в понимании смысла, главное
структура предложения, и именно эта структура далее используется для вычисления
смысла, заключенного в предложение. Н. Хомский считал, что смысл фразы
изменяется при изменении группировки слов, иными словами, смысл меняется при
изменении структуры предложения.
синтаксический трансляция языковый
процессор
2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
.1 Описание заголовочных файлов.
Программа написана на языке С++ и разбита на
несколько модулей. Каждый модуль отвечает за конкретный этап анализа входного
текста:
1. “fail.h”
- данный заголовочный файл отвечает за открытие исходного файла с кодом
программы, исходного куска программы который нам надо проанализировать.
2. “leksik.h”
- в данном заголовочном файле реализован лексический анализ, и присутствуют
задатки синтаксического анализа.
. “sintaksis.h”
- в данном заголовочном файле реализован синтаксический анализ.
. “prototype.h”
- в данном заголовочном файле хранится функция, реализующая проверку на
корректность содержимого файла.
.2 Организация программы
Структура реализации программы является
последовательной. Вначале производится проверка на корректность данных из файла
(существуют ли они и тому подобное), далее работает лексический анализатор и
последний осуществляет проверку синтаксический анализатор.
Рисунок 2. Структура организации
программы
Рисунок 2 полностью отражает все организацию
программы и последовательность выполнения.
.3 Реализация программы
Программа проходит в три этапа и при успешном
выполнении каждого из них, выводится соответствующее уведомление. Если же, в
каком либо из этапов обнаруживается ошибка, программа выполняет соответствующий
этап до конца, после чего выводится сообщение с описанием ошибки, но следующий
этап не выполняется!
Рисунок 3. Удачно законченный первый
этап
Второй этап это лексический анализ. Эта часть
программы проходит в несколько этапов. Вначале нам нужно составить таблицу
лексем. В данной программе эта таблица является перечислением и вспомогательная
таблица, является массивом символов. Считывая посимвольно из файла, мы делаем
проверку, считываемый символ сравниваем с символами из нашей таблицы. Каждой
лексеме присвоен свой уникальный номер, именно благодаря ему мы отличаем
ключевые слова от идентификаторов, переменных или знаков операций. Считав
символ, мы “отправляем” его в функцию, и в ней определяется, к какому типу
лексем относится данный символ. Идентификатор или ключевое слово может состоять
из нескольких символов, функция распознавания производит проверку и этого.
После распознавания происходит проверка на корректность данных. Если все прошло
без ошибок, выводится соответствующее уведомление:
Все символы или их последовательность заносятся
в контейнер “list”, и при
работе синтаксического анализатора, чтение даны будет осуществляться именно из
этого контейнера. При помещении в него элементов, все пробелы и табуляции
удаляются, в виду ненадобности.
Если же, в ходе проверке будет выявлена ошибка,
недопустимая последовательность символов, то пользователь увидит
соответствующее уведомление об ошибке. Уведомление состоит из номера строки, в
котором произошла ошибка (номер строки мы получаем из счетчика, счетчик
отдельная структура в которой хранится номер строки и текст ошибки).
Данная программа распознает, как лексическую
ошибку неправильное расположение символ, в имени переменной. Имя переменной не
может начинаться с цифры. Именно это является лексической ошибкой.
Рисунок 4. Ошибка во время
лексического анализа
Третий этап это синтаксический анализ. Здесь
происходит проверка на корректность данных считанных с контейнера. Каждый
считанный элемент из list’а
обрабатывается с помощью функции, которая работает по принципу автомата. С
помощью набора условий и флагов, которые имеют только два состояния 0 и 1,
программа методом рекурсивного спуска с возвратом определяет возможную
правильную комбинацию элементов, при этом изменяются состояния флагов.
На данном этапе так же имеется счетчик строк,
благодаря которому мы узнаем, в какой строке находится ошибка. Как и в
лексическом анализе, здесь существует своя структура, в которой хранится номер
строки, в которой совершена ошибка и текст с описанием ошибки. Для каждого из
ключевых слов имеется свой алгоритм рекурсивного спуска с возвратом. На
рисунках 5 и 6 показано, что выдается пользователю на экран при успешном
выполнении синтаксического анализа и соответственно всей программы и при
обнаружении синтаксическим анализатором ошибки.
Рисунок 5 Синтаксический анализатор
не обнаружил ошибок
Рисунок 6. Синтаксический анализатор
обнаружил ошибку
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсовой работы, был
разработан синтаксический анализатор для заданного фрагмента кода. Программа
реализована на языке С++, с обоснованным использованием стандартной библиотеки
шаблонов STL. Программа
работает в консольном режиме и сообщает пользователю информацию о ходе
выполнения алгоритмов и функции.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1.
Ю.Г Карпов Основы построения трансляторов 2005 г.
2. Библиотека MSDN