береження ідентіфікаторів Зі співпадаючімі значень хеш-Функції Використовують области пам'яті, что НЕ перетінаються з основною таблицею ідентіфікаторів, а виходе, їхнє размещения не наведено до Виникнення Додатковий колізій. Недоліком методу є необхідність роботи з дінамічно поділюванімі областями пам'яті. Ефективність такого методу, очевидно, у Першу Черга поклади від якості застосовуваної хеш-Функції, а в другу - від методу організації додаткова Сховище даніх.
Хеш-адресація - це метод, что застосовується НЕ Тільки для організації таблиць ідентіфікаторів у компіляторах. Даній метод нашел свое! Застосування ї в операційніх системах, и в системах Керування базами даніх. br/>
11. Хеш-функція и хеш-адресація
В
Хеш-функціею F назівається Деяк відображення множини вхідніх ЕЛЕМЕНТІВ R на множини ціліх невід'ємніх чисел Z: F (r) = n, r ГЋ R, n ГЋ Z. Сам Термін В«Хеш-функціяВ» походити від англійського терміна В«hash functionВ» (hash - В«заважатіВ», В«змішуватіВ», В«ПлутатіВ»). p> множини Припустиме вхідніх ЕЛЕМЕНТІВ R назівається ОБЛАСТЬ визначення хеш-Функції. Множини значень хеш-Функції F назівається підмножіна М з множини ціліх невід'ємніх чисел Z: M ГЌ Z (M є підмножіною Z, М вкючене в Z), что містіть УСІ Можливі значення, а Які повертаються функцією F: "r ГЋ R: F (r) ГЋМ (Для всіх r, Які належиться R; F (r) належиться M. ) p> Процес відображення области визначення хеш-Функції на безліч значень назівається В«ХешуваннямВ». При роботі з таблицею ідентіфікаторів хеш-функція винна Виконувати відображення імен ідентіфікаторів на множини ціліх невід'ємніх чисел. Областю визначення хеш-Функції буде множини усіх можливіть імен ідентіфікаторів.
Хеш-адресація Полягає у вікорістанні значення, а что повертається хеш-функцією, як адресою коміркі з Деяк масиву даніх. Тоді розмір масиву даніх повинною відповідаті области значень вікорістовуваної хеш-функціі. Отже, у реальному компіляторі область значень хеш-функціі Ніяк не винних перевіщуваті розмір доступного адресного простору комп'ютера.
Метод організації Таблицю ідентіфікаторів, Заснований на вікорістанні хеш-адресації, Полягає в розміщенні шкірного елемента табліці в комірку, адресою Якого повертає хеш-функція, Обчислено для цього елемента. Тоді в ідеальному випадка для размещения будь-якого елемента в табліці ідентіфікаторів й достатньо Тільки обчісліті его хеш-функцію и звернута до потрібної коміркі масиву даніх. Для поиска елемента в табліці звітність, обчісліті хеш-функцію для Шуканов елемента и перевіріті, чи не є задана нею комірка масиву порожніх (ЯКЩО вона НЕ порожня - Елемент знайдення, ЯКЩО порожня - не знайдення). p> цею метод Дуже Ефективний - як годину размещения елемента в табліці, так і Час его поиска візначаються Тільки годиною, затрачуванім на обчислення хеш-Функції, что у Загальне випадка незрівнянно менше годині, необхідного на Багаторазові порівняння ЕЛЕМЕНТІВ табліці.
Метод має два Очевидність Недоліки. Перший з них - неефективно Використання ОБСЯГИ пам'яті под Таблицю ідентіфікаторів: розмір масиву для ее Збереження повинною відповідаті области значень хеш-Функції, у тієї годину як реально Збереження у табліці ідентіфікаторів может буті істотно менше. Другий недолік - необхідність відповідного розумного Вибори хеш-Функції. br/>
12. Способи внутрішнього представлення програм
УСІ внутрішні представлення програми звичайна містять у Собі Дві принципова Різні РЕЧІ - оператори й операнди. Розходження между формами внутрішнього представлення полягають позбав в тому, як оператори й операнди з'єднуються между собою. Такоже оператори й операнди повінні відрізнятіся один від Іншого, ЯКЩО смороду зустрічаються в будь-якому порядку. За розрізнення операндів и Операторів, як вже Було сказано Вище, відповідає розроблювачів компілятора, что керується Семантика вхідної мови. p> відомі наступні форми внутрішнього представлення програм:
зв'язані облікові Структури, что представляються синтаксичні дерева;
багатоадресній код з явно іменованім результатом (зошити);
багатоадресній код з неявно іменованім результатом (тріади);
Обернений (Постфіксний) польський запис операцій;
асемблерній код або машінні команді.
синтаксичні дерева
синтаксичні дерева - це структура, что представляет собою результат роботи синтаксичного аналізатора. Вона відображає синтаксис конструкцій вхідної мови и явно містіть у Собі повний Взаємозв'язок операцій. Очевидно такоже, что синтаксичні дерева - це машинно-незалежна форма внутрішнього представлення програми. p> Недолік синтаксичних дерев Полягає в тому, что смороду являютя собою складні зв'язні структурою, а тому не могут буті трівіальнім чином перетворені в лінійну послідовність команд результуючої програми. Прото смороду зручні при роботі з внутрішнім представлених програми на тихий етапах, коли немає необхідності без...
