Основы разработки трансляторов в САПР. Коробова И.Л - 24 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

2. ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ
Проверка правильности семантики и генерация кода требуют знания характеристик идентификато-
ров, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из
того, как идентификаторы используются в программе. Вся информация накапливается в таблицах сим-
волов.
Таблицы всех типов имеют общий вид (табл. 6). В нашем случае аргументами таблицы являются
символы или идентификаторы, а значениями – их характеристики. Когда компилятор начинает трансля-
цию исходной программы, таблица символов пуста или содержит только несколько элементов для слу-
жебных слов и стандартных функций.
В процессе компиляции для каждого нового идентификатора элемент добавляется только один раз,
но поиск ведется всякий раз, когда встречается этот идентификатор. Так как на этот процесс уходит
много времени, важно выбрать такую организацию таблиц, которая допускала бы эффективный поиск.
Таблица 6
№ Аргумент Значение
1
2
… … …
… … …
… … …
N
2.1. УПОРЯДОЧЕННЫЕ И НЕУПОРЯДОЧЕННЫЕ ТАБЛИЦЫ
Простейший способ организации таблицы состоит в том, чтобы добавлять элементы в порядке их
поступления без каких-либо попыток упорядочения. Поиск в этом случае требует сравнения с каждым
элементом таблицы, пока не будет найден подходящий. Для таблицы, содержащей N элементов, в сред-
нем будет выполнено N/2 сравнений. Если N велико, такой способ неэффективен. Поиск может быть
выполнен более эффективно, если элементы таблицы упорядочены согласно некоторому естественному
порядку аргументов. В нашем случае, когда аргументами являются строки символов, наиболее естест-
венным является упорядочение по алфавиту. Эффективным методом поиска в упорядоченном списке
является так называемый бинарный поиск. Символ S, который следует найти, сравнивается с аргумен-
том (n + 1)/2 в середине таблицы. Если этот элемент не является требуемым, мы должны просмотреть
только блок элементов от (n + 1)/2 + 1 до n или от 1 до (n + 1)/2 – 1 в зависимости от того, больше эле-
мент S или меньше элемента, с которым его сравнивали. Затем мы повторяем процесс над блоком
меньшего размера.
Так как на каждом шаге число элементов, которые могут содержать S, сокращается наполовину,
максимальное число сравнений равно log
2
(n + 1). Если n = 2, нам потребуется самое большее 2 сравне-
ния; если n = 4 – то 3; если n = 8 – то 4. Для n = 128 бинарный поиск требует самое большее 8 сравне-
ний. В то время, как в неупорядоченной таблице в среднем потребуется 64 сравнения.
Сортировка таблицы производится методом упорядоченных вставок.
2.2. ХЕШ-АДРЕСАЦИЯ
Наиболее эффективный и широко применяемый в компиляторах метод при работе с таблицами
символов – хеш-адресация. Механизм расстановки состоит из таблицы и хеш-функции (табл. 7). Таб-

Страницы