Рисунок 3.1 – Общая схема работы компилятора
|
|
3.3 Хранение и поиск данных в таблицах[4,7]
|
|
Главной характеристикой любого элемента исходной программы является его имя. Задачей любого транслятора является необходимость хранения и доступа к информации, связанной с каждым элементом исходной программы. Для решения этой задачи транслятор организует специальные хранилища данных, называемые таблицами идентификаторов или таблицами символов. Количество элементов в таблицах велико и поэтому время поиска информации в них существенно влияет на общее время трансляции. Поэтому таблицы идентификаторов должны быть организованы таким образом, чтобы транслятор выполнял операции поиска информации в таблицах с максимальной эффективностью. Для этого используются следующие способы организации таблиц [4,7]:
‑ бинарные деревья;
‑ хеш-адресация с открытым(случайным) перемешиванием;
‑ хеш-адресация с цепочками переполнения;
‑ упорядоченные списки.
Древовидные таблицы являются улучшенным вариантом неупорядоченных таблиц. Новые записи в древовидную таблицу по-прежнему поступают неупорядоченно. Но на этот раз место, занимаемое этими записями среди других записей в таблице, определяется значением ключевого поля. Принцип здесь такой же, как и в сортировке с помощью дерева. В общем случае каждая запись в древовидной таблице сопровождается двумя указателями:
‑один указатель хранит адрес записи с меньшим значением ключа (адрес узла-предка);
‑второй указатель хранит адрес записи с большим значением ключа (адрес узла-сына).
Процесс добавления нового элемента в древовидную таблицу производится следующим образом. Значение ключа нового элемента сравнивается со значением ключа первого элемента дерева. По результатам сравнения ключей новый элемент «поступает» в левое или правое поддерево первого элемента дерева. Далее процесс сравнения и поступления в левое или правое поддерево очередного узла продолжается аналогичным образом и до тех пор, пока не будет найден пустой элемент в нужном направлении просмотра.
|
|
Новая запись помещается в данный пустой элемент, при этом настраивается указатель с адресом узла-предка. Преимущества древовидной структуры таблицы проявляются на этапе поиска нужного элемента. Поиск прекращается либо при совпадении ключевого поля, либо при обнаружении пустого указателя.
Таблицы с вычисляемыми входами (хеш-таблицы) подробно рассмотрены в [7] на страницах 47-53.
3.4 Упорядочивание данных в таблицах
Упорядочивание данных в таблицах производится с использованием одного из алгоритмов сортировки. В трансляторах наиболее широко применяются алгоритмы Шелла и Хоара [8,9]. Алгоритм Шелла – сортировка с убывающим шагом. При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии . После этого процедура повторяется для некоторых меньших значений , пока не станет отрицательным. Структурная диаграмма (диаграмма Несси-Шнейдермана) для алгоритма Шелла представлена на рис. 3.2. Алгоритм Хоара подробно рассмотрен в [8] на страницах 114 – 124.
Рисунок 3.2 – Структурная диаграмма для алгоритма Шелла
Трансляция выражений
Польская инверсная запись (ПОЛИЗ) названа в честь польского математика Яна Лукашевича, который впервые использовал эту форму для представления выражений в математической логике. Она обладает следующими свойствами:‑ операнды располагаются в том же порядке, что в исходном выражении;‑ знаки операций располагаются в том порядке, в котором вычисляется выражение;‑ знак каждой операции записывается после соответствующих операндов.
Для построенияПОЛИЗ можно использовать приведенные выше свойства. На практике широко используется метод, который предложен в 1960 году голландским ученым Е.В.Дейкстрой [7]. Этот метод основан на использовании стека с приоритетами, позволяющего изменить порядок следования знаков операций в выражении так, что получается ПОЛИЗ. Простейший вариант этого метода применим только к простым арифметическим и логическим выражениям, содержащим простые переменные, знаки арифметических и логических операций, знаки операций отношения и круглые скобки. Каждому ограничителю, входящему в выражение, присваивается приоритет. Для знаков операции приоритеты возрастают в порядке, обратном старшинству операций. Скобки имеют низший приоритет. Арифметическое или логическое выражение рассматривается как входная строка символов. Входная строка рассматривается слева направо. Операнды переписываются в выходную строку, а знаки операций помещаются вначале в стек операций. Если приоритет входного знака равен нулю или больше приоритета знака, находящегося в вершине стека, то новый знак добавляется к вершине стека. В противном случае из стека "выталкивается" и переписывается в выходную строку знак, находящийся в вершине, а также следующие за ним знаки с приоритетами большими или равными приоритету входного знака. После этого входной знак добавляется к вершине стека.
|
|
Особенности имеет лишь обработка скобок. Открывающаяся круглая скобка, имеющая "особый" приоритет нуль, просто записывается в вершину стека и не выталкивает ни одного знака. В то же время ее не может вытолкнуть ни один знак, кроме закрывающей скобки.
Закрывающая скобка имеет приоритет 1, не превосходящий приоритет любой операции. Поэтому появление закрывающей скобки вызывает выталкивание всех знаков до ближайшей открывающей скобки включительно. В стек закрывающая скобка не записывается. Открывающая и закрывающая скобки как бы взаимно уничтожаются и в выходную строку не переносятся.
После просмотра всех символов входной cтроки происходит выталкивание всех оставшихся в стеке символов и дописывание их к выходной строке.
В контрольной работе в вариантах заданий в выражениях используются переменные с индексами и указатели функций.
Для перевода выражений, содержащих переменные с индексами, также применим стек с приоритетами. Индексные скобки [ и ] в некотором смысле играют ту же роль, что и круглые скобки. Действие этих скобок на стек, как и действие круглых скобок, состоит прежде всего в следующем. Открывающая индексная скобка всегда записывается в вершину стека, а закрывающая индексная скобка выталкивает из стека все знаки до ближайшей открывающей индексной скобки включительно.
Однако в отличие от круглых скобок одновременно с записью в стек открывающей индексной скобки туда записывается также начальное (минимальное) значение счетчика операндов операции адрес элемента массива (АЭМ), равное 2. Кроме того, после выталкивания из стека знаков закрывающей индексной скобкой и переписи их в выходную строку туда же переписывается значение счетчика операндов, а затем и сама закрывающая скобка.
Запятая, разделяющая индексные выражения, играет одновременно роль закрывающей скобки для предыдущего индексного выражения и роль открывающей скобки ‑ для последующего. Поэтому запятой можно назначить приоритет 1 как закрывающей скобке, дополнив алгоритм условием, что запятая выталкивает из стека все знаки операции до ближайшей открывающей индексной скобки исключительно. Сама запятая, как и любая закрывающая скобка, в стек не записывается. Появление запятой равносильно появлению еще одного индекса, поэтому каждая запятая добавляет в счетчик операндов операции АЭМ единицу.
Алгоритм перевода в ПОЛИЗ функции, имеющий не менее одного параметра, тот же, что для переменной с индексом. Различие состоит лишь в том, что в момент прихода закрывающей круглой скобки в выходную строку записывается символ Ф. Чтобы отличить открывающую круглую скобку в начале списка фактических параметров от открывающей круглой скобки в начале выражения, можно использовать переменную состояния F (признак функции). Эта переменная обычно имеет значение нуль. В момент появления идентификатора функции она принимает значение 1, а после занесения в стек круглой скобки и начального значения счетчика операндов, равного 2, вновь принимает значение 0. Закрывающая скобка, встретив в стеке открывающую круглую, записанную вместе со значением счетчика операндов, занесет это значение в выходную строку, запишет туда знак Ф и уничтожит в стеке круглую скобку и значение счетчика операндов.
Примеры перевода арифметических выражений рассмотрены в [7] на страницах 130 – 144.