ЛАБОРАТОРНАЯ РАБОТА 1 ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ ТАБЛИЦ, ИСПОЛЬЗУЕМЫХ В ТРАНСЛЯТОРЕ Рейн Т. С.

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

Схема транслятора Лексичекий анализ Синтаксический анализ Семантический анализ Генерация промежуточного кода Оптимизация кода Генерация кода Диспетчер таблиц символов Обработчик ошибок Исходная программа Целевая программа

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

Постоянные таблицы таблицы, содержащие алфавит входного языка ; таблица зарезервированных слов ; таблицы, реализующие какой - либо из методов синтаксического анализа (LL- разбор, LR- разбор и др.).

Переменные таблицы таблица символов ( идентификаторов, имен ); таблица констант.

Определения Лексема – неделимая единица языка и ее атрибуты. Единица языка – константа, идентификатор, ключевое слово, разделитель, знак операции. Множество атрибутов определяется типом единицы языка и может включать : имя, значение, тип, параметры ( для функций ). Лексемы сохраняются в соответствующих таблицах лексем.

Функции компилятора Одной из важнейших функций компилятора является запись используемых в исходной программе идентификаторов и сбор информации о различных атрибутах каждого идентификатора. Эти атрибуты предоставляют сведения об отведенной идентификатору памяти, его типе, области видимости ( в какой части программы он может применяться ).

Состав лексхемы При использовании имен процедур атрибуты говорят о количестве и типе их аргументов, методе передачи каждого аргумента ( например, по ссылке ) и типе возвращаемого значения, если таковое имеется. Вся эта информация составляет лексему.

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

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

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

Механизм таблицы сиволов Механизм таблицы символов должен обеспечивать эффективный поиск и добавление символов в таблицу. Такими механизмами могут быть линейные списки и хеш - таблицы. Линейный список более прост в реализации, но его производительность невысока. Хеширование обеспечивает более высокую производительность, но за счет большего количества памяти и несколько больших усилий по программированию.

Работа с таблицей символов При работе с таблицей символов полезна возможность ее динамического роста в процессе компиляции. Для хранения лексем, образующих идентификаторы, не стоит отводить память фиксированного размера. Этой памяти может оказаться недостаточно для очень длинного идентификатора И слишком много для коротких идентификаторов ( например, i), что приводит к нерациональному использованию памяти.

Методы ТС Процедуры для работы с таблицей символов, ориентированы, в основном, на хранение и получение лексем. Класс, реализующий таблицу символов, должен содержать следующие основные функции : поиск / добавление идентификатора в таблице ; поиск / добавление атрибутов идентификатора в таблицу.

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

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