Теория языков программирования методов трансляции (стр. 36 )

7.2.  Работа с таблицей символов

Поскольку синтаксические анализаторы обычно используют контекстно – свободную грамматику, необходимо найти метод определения контекстно – зависимых частей языка. Например, во многих языках идентификаторы не могут применяться, если они ранее не описаны, и имеются ограничения в отношении способов употребления в программе значений различного типа. Кроме того, в языках программирования имеются ограничения на употребление различных знаков. Для запоминания описанных идентификаторов и их типов большинство компиляторов использует таблицу символов. В принятой формализации описания

int a

является определяющей реализацией а, а использование а в другом контексте

a=4 или a+ b или read(a)

говорит, что имеется прикладная реализации а.

Во многих языках программирования один и тот же идентификатор может использоваться для представления в различных частях программы различных объектов (например, в «голове» int, а в подпрограмме char). В этом случае в таблице символов - это два разных объекта.

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

1)  определяющая реализация идентификатора появляется раньше любой прикладной реализации;

2)  все описания в блоке помещаются раньше всех операторов и предложений;

3)  при наличии прикладной реализации идентификатора, соответствующая определяющая реализация находится в наименьшем включающем блоке, в котором содержится описание этого идентификатора;

4)  в одном и том же блоке идентификатор не может описываться более одного раза.

Пусть синтаксис описания идентификаторов задается правилами:

а блок определяется как

,

где

В этом случае структуру таблицы символов можно представить в виде

Levno

levno

levno

		Type				type				type
		Type				type
						type

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

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

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

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

Рассмотренный метод иллюстрируется следующим примером

Вид программы
begin int a, b . begin int c, d . end begin int e, f . end end
f	int
e	int
b	int
a	int

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

Контрольные вопросы

1.  Технология включения действий в грамматику.

2.  Получение четверок, грамматика для четверок.

3.  Разбор арифметического выражения с одновременной генерацией кода.

4.  Метод определения контекстно – зависимых частей языка.

5.  Синтаксис описания идентификаторов и блоков.

6.  Структура таблицы символов.

7.  Программная реализация таблицы символов.

8.  Проектирование компиляторов

8.1.  Число проходов

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

Определение.

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

Проходы бывают прямыми или обратными, т. е. за один проход исходный текст можно считать слева направо или справа налево.

Большинство языков, использующих идею описания переменных до их первого использования (Pascal, C++ и др.), либо использующих принцип умолчания, в принципе могут быть однопроходными. Однако есть ряд особенностей, которые не позволяют обеспечить компиляцию за один проход. Особенно ясно это можно продемонстрировать на проблеме компиляции взаимно рекурсивных процедур. Допустим, что тело процедуры А содержит вызов процедуры В, а процедура В содержит вызов процедуры А. Если процедура А объявляется первой, то компилятор не будет генерировать код для вызова В внутри А, не зная типов параметров В, и в случае процедуры, возвращающей результат, тип этого результата может потребоваться для идентификации обозначения операции. Единственное разумное решение данной проблемы – позволить компилятору сделать дополнительный проход перед генерацией кода.

Часто увеличение числа проходов компилятора используется искусственно - для уменьшения памяти, занимаемой компилятором в оперативном запоминающем устройстве (ОЗУ). Кроме того, количество проходов зависит не только от особенностей транслируемого языка, но и от используемой ЭВМ и операционного окружения.

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

8.2.  Таблицы символов

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

Как уже отмечалось, для простых языков (Fortran, Basic и др.), имеющих конечное число типов, каждый из них может быть представлен целым числом. Например, тип integer - посредством 1, а тип real – посредством 2. В этом случае таблица символов имеет вид массива с элементами

Identifier, type.

В языках, имеющих ограничение на число литер в идентификаторе, обычно в таблице символов хранятся сами идентификаторы, а не какое-либо их представление, полученное посредством лексического анализа.

С таблицей символов ассоциируются следующие действия.

1)  Идентификатор, встречающийся впервые, помещается в таблицу символов, его тип определяется по соответствующему описанию.

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

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