Введение в теорию компиляции Основные принципы построения трансляторов

Определения Транслятор – это программа, которая переводит программу на исходном (входном) языке в эквивалентную ей программу на результирующем (выходном) языке 1) Входные данные – программа на исходном языке программирования 2) Выходные данные – программа на результирующем языке, или сообщение об ошибках 3) Эквивалентность – совпадение смысла исходной и результирующей программ с точки зрения семантики входного и семантики выходного языка Транслятор исходная программа результир. программа сообщение об ошибках

Определения Компилятор – это транслятор, переводящий исходную программу в эквивалентную ей результирующую программу на языке машинных команд или на языке ассемблера 1)Компилятор – частный случай транслятора 2)Результирующая программа называется объектной программой 3)Результирующая программа предназначена для выполнения на вычислительной системе определенной архитектуры – на целевой вычислительной системе

Определения Интерпретатор – это программа, которая воспринимает исходную программу на входном языке и выполняет ее 1) Не порождает результирующую программу 2)Результат работы интерпретатора – результат выполнения исходной программы 3)Исходная программа преобразовывается в язык машинных команд, но команды порождаются, выполняются и уничтожаются интерпретатором по мере надобности и невидимы для пользователя

Общая схема работы компилятора Основные этапы компиляции: - анализ - синтез Основные этапы компиляции: - анализ - синтез Основные фазы компиляции: - лексический анализ - синтаксический разбор - семантический анализ - подготовка к генерации кода - генерация кода Основные фазы компиляции: - лексический анализ - синтаксический разбор - семантический анализ - подготовка к генерации кода - генерация кода

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

Понятие прохода Проход – процесс обработки всего, возможно, уже преобразованного, текста исходной программы, т.е. выполнение одной или нескольких фаз компиляции Количество проходов – важная техническая характеристика компилятора Результат прохода – внутреннее представление исходной программы (кроме последнего), которое хранится в оперативной памяти или во временных файлах на диске Зависимость: Количество проходов Скорость работы Объем необходимой памяти Количество проходов зависит от грамматики и семантических правил исходного языка

Понятие прохода (пример) Лексический анализ Синтаксический разбор + семантический анализ Генерация и оптимизация кода 1-ый проход 2-ой проход 3-ий проход Таблица лексем Семантическое дерево (ОПЗ, тетрады, триады) Исходная программа Объектная программа

Таблицы идентификаторов Назначение – хранение идентификаторов и их характеристик Особенности: 1)возможно значительный объем хранимой информации 2)может быть одна ТИ или несколько (например, для различных модулей или различных типов элементов) 3)состав информации, хранимой в ТИ, зависит от семантики входного языка и типа элемента 4)информация в ТИ заполняется не сразу, а по мере того, как становится известна – на различных фазах компиляции 5)принцип работы с ТИ – многократное обращение компилятора для поиска информации и записи новых данных на различных фазах компиляции ТИ должны быть организованы таким образом, чтобы обеспечить максимально быстрый поиск нужного элемента

Таблицы идентификаторов Неупорядоченные Массив/список Бинарное дерево поиска На основе хэш- функции Комбинированные методы Рехэширование Метод цепочек Упорядоченные Методы организации ТИ по способу разрешения коллизий

Хэш-адресация

Разрешение коллизий: рехеширование (метод открытой адресации)

Разрешение коллизий: метод цепочек

Комбинированные методы