26. Таблицы Идентификаторов.
Проверка правильности семантики и генерации кода требуют знания характеристик переменных, констант, функций и других элементов, встречающихся в программе на исходном языке. Все эти элементы в исходной программе, как правило, обозначаются идентификаторами (И). Выделение идентификаторов и других элементов исходной программы происходит на фазе ЛА. Их характеристики определяются на фазах СР, СА и подготовки к генерации кода. Состав возможных характеристик и методы их определения зависят от семантики входного языка.
В любом случае К должен иметь возможность хранить все найденные И и связанные с ними характеристики в течение всего процесса компиляции, чтобы иметь возможность использовать их на различных фазах компиляции. Для этой цели в К используются специальные хранилища данных, называемые таблицами символов, или ТИ.
ТИ – это специальным образом организованные наборы данных, служащие для хранения информации об элементах исходной программы, которые затем используются для порождения текста рез. программы.(м.б. как одна,так и неск.). Элементами исходной программы, информацию о которых необходмио хранить в процессе компиляции, яв-ся переменные, константы, функции и т.п.
Любая ТИ состоит из набора полей, количество которых равно числу различных И, найденных в исходной программе. Каждое поле содержит в себе полную информацию о данном элементе таблицы. К может работать с одной или несколькими ТИ – их кол-во зависит от реализации К. Напр., можно организовывать различные ТИ для различных модулей исходной программы или для различных типов элементов входного языка.
27. Способы организации таблиц идентификаторов.
28.Хэш-функция. Хэш-адресация.
29. Методы сортировки.
Сортировка массива методом пузырька - медленная, но если скорость не главное, можно применить и его.
Алгоритм очень прост - если два соседних элемента расположены не по порядку,
то меняем их местами. Так повторяем до тех пор, пока в очередном проходе не сделаем ни одного обмена,
т.е. массив будет упорядоченным. Ниже текст процедуры, реализующей алгоритм сортировки методом пузырька
(Arr - массив для сортировки с начальным индексом 0, n - размерность массива)
procedure SortPuz (var Arr : array of Integer; n : Integer);
var
i : Integer;
Temp : Integer;
Flag : Boolean;
begin
repeat
Flag := False;
for i := 0 to n - 1 do
if Arr [i] > Arr [i + 1] then begin
Temp := Arr [i];
Arr [i] := Arr [i + 1];
Arr [i + 1] := Temp;
Flag := True;
end;
until Flag = False;
end;
Сортировка методом нахождения минимального элемента
Ещё один вариант сортировки, более быстрый, чем метод пузырька.
Заключается он в следующем: при каждом просмотре массива находим
минимальный элемент и меняем местами его с первым на первом проходе,
со вторым - на втором и т.д. Не забудьте только, что первый элемент массива должен иметь индекс 0.
procedure SortMin (var Arr : array of Integer; n : Integer);
var
i, j : Integer;
Min, Pos, Temp : Integer;
begin
for i := 0 to n - 1 do begin
Min := Arr [i];
Pos := i;
for j := i + 1 to n do
if Arr [j] < Min then begin
Min := Arr [j];
Pos := j;
end;
Temp := Arr [i];
Arr [i] := Arr [Pos];
Arr [Pos] := Temp;
end;
end;
Сортировка массива вставками
Более быстрый и оптимальный метод сортировки - сортировка вставками.
Суть её в том, что на n-ном шаге мы имеем упорядоченную часть массива из n элементов,
и следующий элемент встаёт на подходящее ему место.
Имейте в виду - первый индекс массива - 0.
procedure SortInsert (var Arr : array of Integer; n : Integer);
var
i, j, Temp : Integer;
begin
for i := 1 to n do begin
Temp := Arr [i];
j := i - 1;
while Temp < Arr [j] do begin
Arr [j + 1] := Arr [j];
Dec (j);
if j < 0 then
Break;
end;
Arr [j + 1] := Temp;
end;
end;