- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
4.6. Представление результатов сканирования
В процессе работы сканера должна быть сформирована таблица имен для хранения информации о лексемах. Эта информация используется в дальнейшем для двух целей.
Во-первых, с целью семантического контроля исходного текста программы. Например, если в программе есть оператор вида
go to met,
то компилятор должен проверить , что идентификатор met встречается в программе в качестве метки соответствующего оператора ( а не в другом качестве).
Во-вторых, информация в таблице имен используется при генерации кода. Например, если в программе есть оператор вида
a:= b+c,
то генерируемый код для операции “+” будет зависеть от атрибутов
идентификаторов b и c ( в частности, от типа a,b,c и т.п.)
Таким образом, после распознавания каждой лексемы, сканер должен занести в таблицу имен их характеристики (атрибуты). К этим атрибутам относятся: класс лексемы (обозначаемый обычно во внутреннем представлении целым числом), фактическое значение лексемы (фактическое символическое имя), дополнительная информация. Для внутреннего представления лексем может использоваться табл.4.3.
Таблица 4.3
Класс лексемы |
Внутреннее представление |
Фактическое значение |
Не определен |
0 |
... |
Идентификатор |
1 |
... |
Целое число |
2 |
... |
Действительное число |
3 |
имена лексем |
Знак операции |
4 |
... |
Зарезервированное слово |
5 |
... |
Вещественный массив |
6 |
... |
Метки |
7 |
... |
и т.д. |
и т.д. |
... |
Дополнительная информация о лексеме обычно помещается в отдельную область памяти, на которую делается ссылка. Эта ссылка (адрес) также является атрибутом лексемы. Пусть, например, дан сегмент программы
a:= b * c +0.15,
тогда после ее сканирования в таблице имен должна быть сформирована информация представленная на рис. 4.3.
Р ис.4.3
Дополнительная информация, связанная с каждой конкретной
лексемой, зависит от ее смыслового значения и может содержать большое количество атрибутов. Например, возможно, что для идентификатора надо знать его тип ( вещественный, целый, строковый и т.д.); был ли он меткой, именем процедуры, переменной, формальным параметром процедуры; должен ли он распределяться в статической или динамической памяти и т.д.
Ясно, что количество атрибутов для каждой лексемы будет различным, поэтому доступ к этим данным удобно осуществлять путем ссылок на соответствующие адреса памяти.
Всякий раз, когда сканер распознает лексему, он проверяет в таблице имен, встречалась ли ранее такая же лексема. Если нет, то сканер заносит в таблицу имен значение этой лексемы вместе с соответствующей информацией. Если же лексема уже есть в некоторой ячейке n таблицы имен, то сканер вырабатывает на выходе пару (имя лексемы, n).
Таким образом, чтобы сконструировать эффективный компилятор, надо уметь по данному имени лексемы быстро определять, отведена ли для нее ячейка в таблице имен, вставлять при необходимости эту лексему, вычислять адреса ячеек в других таблицах, содержащих дополнительную информацию о каждой лексеме.
Рассмотрение методов организации информационных таблиц и работы с ними мы выносим за рамки этой книги для более серьезного их изучения в других курсах.