Создание компилятора.

1. ВВЕДЕНИЕ Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке. Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера. Таким образом, компилятор является частным случаем транслятора. Процесс компиляции можно разделить на два основных этапа: анализ и синтез. На этапе анализа выполняется распознавание текста исходной программы, создание и заполнение таблиц идентификаторов и т.д. Результатом его работы служит некоторое внутреннее представление программы, понятное компилятору. На этапе синтеза на основании внутреннего представления программы и информации, содержащейся в таблице идентификаторов, порождается текст результирующей программы. Результатом этого этапа является объектный код. Кроме того, в составе компилятора присутствует часть, ответственная за анализ и исправление ошибок. Этапы анализа и синтеза, в свою очередь, состоят из более мелких этапов, называемых фазами компиляции. Так фазами анализа являются: лексический анализ, синтаксический анализ, семантический анализ. Этапами синтеза являются: оптимизация, генерация кода, оптимизация полученного кода. Лексический анализ – это фаза, в которой формируются символы (tokens) входного языка. Лексема (token) – лексическая единица языка. Это структурная единица языка, которая состоит из элементарных символов языка и не содержит в своем составе других лексем. Задачей фазы лексического анализа или лексического анализатора является переход от последовательности знаков к символам языка (лексем), с которыми в дальнейшем будут работать синтаксическая и семантическая фазы. Наряду с преобразованием последовательности знаков в символы, лексический анализатор также обрабатывает пробелы и удаляет комментарии и любые другие символы, не имеющие смысловой нагрузки для последующих этапов анализа. Важно отметить, что лексический анализатор всего лишь формирует символы – их последовательность не имеет для него никакого значения. Синтаксический анализ – это основная часть компиляции на этапе анализа. Синтаксический анализатор получает на вход результат работы лексического анализатора и разбирает его в соответствии с некоторой грамматикой. Основная задача синтаксического анализа – определить, принадлежит ли исходная цепочка символов (лексем) входному языку, т.е. является правильным (с точки зрения синтаксиса) предложением входного языка. Результатом работы синтаксического анализатора является некоторое промежуточное представление программы, обычно в виде дерева синтаксического разбора. Семантический анализ – обычно заключается в проверке правильности типов данных, используемых в программе. Кроме того, на этом этапе компилятор должен также проверить, соблюдается ли определенные контекстные условия входного языка. В современных языка программирования одним из примеров контекстных условий может служить обязательность описания переменных: для каждого использующего вхождения идентификатора должно существовать единственное определяющее вхождение. Другой пример контекстного условия: число и атрибуты фактических параметров вызова процедуры должны быть согласованы с определением этой процедуры. Такие контекстные условия не всегда могут быть проверены во время синтаксического анализа и потому обычно выделяются в отдельную фазу. Оптимизация заключается в преобразовании промежуточного представления программы с целью повышения эффективности результирующего объектного кода. Генерация кода – фаза, непосредственно связана с порождением команд, составляющих предложением выходного языка и в целом тест результирующей программы. Это основная фаза на этапе синтеза результирующей программы. Синтаксически управляемая трансляция подразумевает, что основным управляющим элементом компилятора является синтаксический анализатор. Лексический анализатор служит неким «поставщиком» потока лексем для синтаксического анализатора. Семантические процедуры, а также процедуры генерации кода применяются к построенному синтаксическим анализатором дереву разбора и под его управлением.

СОДЕРЖАНИЕ 1 ВВЕДЕНИЕ 3 2. ТЕХНИЧЕСКОЕ ЗАДАНИЕ 5 3. ОПИСАНИЕ ПРОГРАММЫ 6 3.1 Описание входного алфавита 6 3.2 Описание грамматических правил 6 4. ИСПОЛЬЗОВАННЫЕ АЛГОРИТМЫ И СТРУКТУРЫ 8 4.1 Конечный автомат (фаза лексического анализа) 8 4.2 Алгоритм рекурсивного спуска с возвратами (фаза синтаксического анализа) 8 4.3 Представление синтаксического дерева в виде ПОЛИЗ’а (вычисление константных выражений, фаза генерации кода) 8 5. ИСПОЛЬЗОВАННЫЕ ИНСТУМЕНТАЛЬНЫЕ СРЕДСТВА 9 5.1 Использованные средства 9 5.2 Диаграмма классов 10 6. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ 11 6.1 Входной код 11 6.2 Выходной код 11 7. ПРИМЕРЫ РАБОТЫ ПРОГРАММЫ 13 7.1 Пример 1 13 7.2 Пример 2 14 8. ЗАКЛЮЧЕНИЕ 17 9. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 18 ПРИЛОЖЕНИЕ 1. ЛИСТИНГ ПРОГРАММЫ 19

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1) Н.Н. Смирнова, С.Д. Тарасов «Основы Построения Компиляторов: учебно-практическое пособие», изд. БГТУ-СПб. 2000. 2) В. И. Юров «Assembler», «Питер Пресс», Санкт-Петербург, 2007.