Крок 3. Покласти j:=l, вибрати з хеш-таблиці адреса комірки таблиці ідентифікаторів mj і перейти до кроку 4.
Крок 4. Для комірки таблиці ідентифікаторів за адресою mj перевірити значння поля посилання. Якщо воно порожнє, то записати в нього адресу з перемінної FreePtr і перейти до кроку 5; інакше j:=j+l, вибрати з поля посилання адресу mj і повторити крок 4.
Крок 5. Додати в таблицю ідентифікаторів нову комірка, записати в неї інформацію для елемента Aі (поле посилання повинне бути порожнім), у змінну FreePtr помістити адресу за кінцем доданої комірки. Якщо більше немає ідентифікаторів, які треба розмістити в таблиці, то виконання алгоритму закінчене, інакше і:=і+1 і перейти до кроку 2.
Пошук елемента в таблиці ідентифікаторів, організованої в такий спосіб буде виконуватися по наступному алгоритму.
Крок 1. Обчислити значення хеш-функції n для шуканого елемента А. Якщо комірка хеш-таблиці за адресою n порожня, то елемент не знайдений і алгоритм завершений, інакше покласти j:=l, вибрати з хеш-таблиці адресу комірки таблиці ідентифікаторів mj=n.
Крок 2. Порівняти ім'я елемента в комірки таблиці ідентифікаторів за адресою mj з ім'ям елемента А. Якщо вони співпадають, то шуканий елемент знайдений і алгоритм завершений, інакше - перейти до кроку 3.
Крок 3. Перевірити значення поля посилання в комірці таблиці ідентифікаторів за адресою mj . Якщо воно порожнє, то шуканий елемент не знайдений і алгоритм завершений ; інакше j:=j+l, вибрати з поля посилання адреса mj і перейти до кроку 2.
При такій організації таблиць ідентифікаторів у випадку виникненні колізії алгоритм розміщає елементи в комірках таблиці, зв'язуючи їх один з одним послідовно через поле посилання. При цьому елементи не можуть попадати в комірки з адресами, що потім будуть співпадати зі значеннями хеш-функції. Таким чином, додаткові колізії не виникають. У підсумку, у таблиці виникають своєрідні ланцюжки зв'язаних елементів.
10. Призначення й особливості побудови таблиць ідентифікаторів. Комбіновані способи побудови таблиць ідентифікаторів
У реальних компіляторах практично завжди так чи інакше використовується хеш-адресація. Звичайно при розробці хеш-функції творці компілятора прагнуть звести до мінімуму кількість виникаючих колізій не на всій множині можливих ідентифікаторів, а на тих їхніх варіантах, що найбільше часто зустрічаються у вхідних програмах. Звичайно, узяти до уваги всі припустимі вхідні програми неможливо. Найчастіше виконується статистична обробка імен ідентифікаторів, що зустрічаються, на деякій множині типових вихідних програм, а також приймаються в увагу угоди про вибір імен ідентифікаторів, загальноприйняті для вхідної мови. Гарна хеш-функція — це крок до значного прискорення роботи компілятора, оскільки звертання до таблиць ідентифікаторів виконуються багаторазово на різних фазах компіляції.
Те, який конкретно метод застосовується в компіляторі для організації таблиць ідентифікаторів, залежить від реалізації компілятора. Той самий компілятор може мати навіть декілька різних таблиць ідентифікаторів, організованих на основі різних методів.
Як правило, застосовуються комбіновані методи. У цьому випадку, як і для методу ланцюжків, у таблиці ідентифікаторів організується спеціальне додаткове поле посилання. Але на відміну від методу ланцюжків воно має трохи інше значення. При відсутності колізій для вибірки інформації з таблиці використовується хеш-функція, поле посилання залишається порожнім. Якщо ж виникає колізія, то через поле посилання організується пошук ідентифікаторів, для яких значення хеш-функції збігаються по одному з розглянутих вище методів: неупорядкований список, упорядкований список або бінарне дерево. При добре побудованій хеш-функції колізії будуть виникати рідко, тому кількість ідентифікаторів, для яких значення хеш-функції збіглися, буде не настільки велике. Тоді і час пошуку одного серед них буде незначним (у принципі при високій якості хеш-функції підійде навіть перебір неупорядкованому списку).
Такий підхід має переваги в порівнянні з методом ланцюжків: для збереження ідентифікаторів зі співпадаючими значеннями хеш-функції використовуються області пам'яті, що не перетинаються з основною таблицею ідентифікаторів, а виходить, їхнє розміщення не приведе до виникнення додаткових колізій. Недоліком методу є необхідність роботи з динамічно поділюваними областями пам'яті. Ефективність такого методу, очевидно, у першу чергу залежить від якості застосовуваної хеш-функції, а в другу - від методу організації додаткових сховищ даних.
Хеш-адресація — це метод, що застосовується не тільки для організації таблиць ідентифікаторів у компіляторах. Даний метод знайшов своє застосування й в операційних системах, і в системах керування базами даних.
11. Хеш-функція і хеш-адресація
Хеш-функціею F називається деяке відображення множини вхідних елементів R на множину цілих невід’ємних чисел Z: F(r) = n, r Î R, n Î Z. Сам термін «Хеш-функція» походить від англійського терміна «hash function» (hash — «заважати», «змішувати», «плутати»).
Множина припустимих вхідних елементів R називається областю визначення хеш-функції. Множиною значень хеш-функції F називається підмножина М з множини цілих невід’ємних чисел Z: M Í Z (M є підмножиною Z, М вкючене в Z), що містить усі можливі значення, які повертаються функцією F: "r Î R: F(r) ÎМ (Для всіх r, які належ R; F(r) належ M. )
Процес відображення області визначення хеш-функції на безліч значень називається «хешуванням». При роботі з таблицею ідентифікаторів хеш-функція повинна виконувати відображення імен ідентифікаторів на множину цілих невід’ємних чисел. Областю визначення хеш-функції буде множина усіх можливих імен ідентифікаторів.
Хеш-адресація полягає у використанні значення, що повертається хеш-функцією, як адресу комірки з деякого масиву даних . Тоді розмір масиву даних повинний відповідати області значень використовуваної хеш-функціи. Отже, у реальному компіляторі область значень хеш-функціи ніяк не повинна перевищувати розмір доступного адресного простору комп'ютера.
Метод організації таблиць ідентифікаторів, заснований на використанні хеш-адресації, полягає в розміщенні кожного елемента таблиці в комірку, адресу якого повертає хеш-функція, обчислена для цього елемента. Тоді в ідеальному випадку для розміщення будь-якого елемента в таблиці ідентифікаторів досить тільки обчислити його хеш-функцію і звернутися до потрібної комірки масиву даних. Для пошуку елемента в таблиці необхідно обчислити хеш-функцію для шуканого елемента і перевірити, чи не є задана нею комірка масиву порожньою (якщо вона не порожня — елемент знайдений, якщо порожня — не знайдений).
Цей метод дуже ефективний — як час розміщення елемента в таблиці, так і час його пошуку визначаються тільки часом, затрачуваним на обчислення хеш-функції, що у загальному випадку незрівнянно менше часу, необхідного на багаторазові порівняння елементів таблиці.
Метод має два очевидних недоліки. Перший з них – неефективне використання обсягу пам'яті під таблицю ідентифікаторів: розмір масиву для її збереження повинний відповідати області значень хеш-функції, у той час як реально збережених у таблиці ідентифікаторів може бути істотно менше. Другий недолік – необхідність відповідного розумного вибору хеш-функції.
12. Способи внутрішнього представлення програм
Усі внутрішні представлення програми звичайно містять у собі дві принципово різні речі — оператори й операнди. Розходження між формами внутрішнього представлення полягають лише в тому, як оператори й операнди з'єднуються між собою. Також оператори й операнди повинні відрізнятися один від іншого, якщо вони зустрічаються в будь-якому порядку. За розрізнення операндів і операторів, як уже було сказано вище, відповідає розроблювач компілятора, що керується семантикою вхідної мови.
Відомі наступні форми внутрішнього представлення програм:
зв'язані облікові структури, що представляють синтаксичні дерева;
багатоадресний код з явно іменованим результатом (тетради);
багатоадресний код з неявно іменованим результатом (тріади);
обернений (постфиксна) польський запис операцій;
асемблерний код або машинні команди.
Синтаксичні дерева
Синтаксичні дерева – це структура, що представляє собою результат роботи синтаксичного аналізатора. Вона відображає синтаксис конструкцій вхідної мови і явно містить у собі повний взаємозв'язок операцій. Очевидно також, що синтаксичні дерева — це машинно-незалежна форма внутрішнього представлення програми.
Недолік синтаксичних дерев полягає в тому, що вони являють собою складні зв'язні структури, а тому не можуть бути тривіальним чином перетворені в лінійну послідовність команд результуючої програми. Проте вони зручні при роботі з внутрішнім представленням програми на тих етапах, коли немає необхідності безпосередньо звертатися до команд результуючої програми.
Синтаксичні дерева можуть бути перетворені в інші форми внутрішнього представлення програми, що представляють собою лінійні списки, з урахуванням семантики вхідної мови. Алгоритми такого роду перетворень розглянуті далі. Ці перетворення виконуються на основі принципів СК-компіляції.
Багатоадресний код з явно іменованим результатом (тетради)
Тетради являють собою запис операцій у формі з чотирьох складових: операції, двох операндів і результату операції. Наприклад, тетради можуть виглядати так: <операція>(<операнд1>,<операнд2>,<результат>).
Тетради являють собою лінійну послідовність команд. При обчисленні виразу, записаного у формі тетрад, вони обчислюються одна за іншою послідовно. Кожна тетрада в послідовності обчислюється так: операція, задана тетрадою, виконується над операндами і результат її виконання міститься в змінній, заданій результатом тетради. Якщо якийсь з операндів (чи оба операнда) у тетраді відсутні (наприклад, якщо тетрада являє собою унарну операцію), то він може бути опущений чи замінений порожнім операндом (у залежності від прийнятої форми запису і її реалізації).