Структура компиляторов

Введение
1 Основы компиляции ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4стр
2 Информационные таблицы ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5стр
2.1 Таблица индефикаторов ... ... ... ... ... ... ... ... ... ... ... ... ... ...6стр
3 Сканер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...6стр
4 Синтаксический и семантический анализаторы ... ... ... ... ... ... ... ... 6стр
5 Внутреннее представление исходной программы ... ... ... ... ... ... ... ..7стр
6 Подготовка к генерации команд ... ... ... ... ... ... ... ... ... ... ... ... ...7стр
6.1 Генерация команд ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...7стр
6.2 Генерация кода ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .10стр
7 Метод операторного предшествования ... ... ... ... ... ... ... ... ... ... .10стр
8 Рекурсивный спуск ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..12стр
9 Польская запись ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14стр
10 Метод четверок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .15стр
Заключение
Литература

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

Робин Хантер «Основные концепции компиляторов»
А.В. Велихов «Основы информатики и компьютерные техники»
Г.А.Сырецкий «Основы информационных и вычислительных технологий»

Дисциплина: Информатика, Программирование, Базы данных
Тип работы: Реферат
Бесплатно: Антиплагиат
Объем: 13 страниц
В избранное:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

КАЗАХСТАНСКИЙ ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ

Кафедра информационных технологий и связей

Курсовой проект

Тема: Структура компиляторов

Выполнил:

Студентка 3-го курса

Заочного отделения
Факультет Информатики

Емельбаева Ф.Р.

Принял:

Старший преподаватель
Голубева
Т.В.

Алматы 2006 г.

Содержание

Введение
1 Основы компиляции ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4 стр
2 Информационные таблицы ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5стр
2.1 Таблица индефикаторов ... ... ... ... ... ... ... ... ... ... ... ... ... ...6ст р
3 Сканер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6стр
4 Синтаксический и семантический анализаторы ... ... ... ... ... ... ... ... 6стр
5 Внутреннее представление исходной программы ... ... ... ... ... ... ... ..7стр
6 Подготовка к генерации команд ... ... ... ... ... ... ... ... ... ... ... ... ...7стр
6.1 Генерация команд ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...7стр
6.2 Генерация кода ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .10стр
7 Метод операторного предшествования ... ... ... ... ... ... ... ... ... ... .10стр
8 Рекурсивный спуск ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..12стр
9 Польская запись ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .14стр
10 Метод четверок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .15 стр
Заключение
Литература

Введение

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

1 Основы компиляции

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

рис.1

2. Информационные таблицы.

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

2.1 Таблица индефикаторов

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

3 Сканер

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

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

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

5 Внутреннее представление исходной программы

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

6. Подготовка к генерации команд

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

6.1 Генерация команд

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

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.