Планування і диспетчеризація процесів і задач в ОС
Способи виділення пам’яті під новий розділ. Їх переваги і недоліки
Дисципліни заміщення сегментів. Організація, переваги і недоліки
Транслятори, компілятори й інтерпретатори — загальна схема роботи
Призначення й особливості побудови таблиць ідентифікаторів
Призначення й особливості побудови таблиць ідентифікаторів. Комбіновані способи побудови таблиць ідентифікаторів
Способи внутрішнього представлення програм
Навигация
Призначення й особливості побудови таблиць ідентифікаторів. Комбіновані способи побудови таблиць ідентифікаторів
Системне програмне забезпечення
61090
знаков
3
таблицы
11
изображений
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. )
Процес відображення області визначення хеш-функції на безліч значень називається «хешуванням». При роботі з таблицею ідентифікаторів хеш-функція повинна виконувати відображення імен ідентифікаторів на множину цілих невід’ємних чисел. Областю визначення хеш-функції буде множина усіх можливих імен ідентифікаторів.
Хеш-адресація полягає у використанні значення, що повертається хеш-функцією, як адресу комірки з деякого масиву даних . Тоді розмір масиву даних повинний відповідати області значень використовуваної хеш-функціи. Отже, у реальному компіляторі область значень хеш-функціи ніяк не повинна перевищувати розмір доступного адресного простору комп'ютера.
Метод організації таблиць ідентифікаторів, заснований на використанні хеш-адресації, полягає в розміщенні кожного елемента таблиці в комірку, адресу якого повертає хеш-функція, обчислена для цього елемента. Тоді в ідеальному випадку для розміщення будь-якого елемента в таблиці ідентифікаторів досить тільки обчислити його хеш-функцію і звернутися до потрібної комірки масиву даних. Для пошуку елемента в таблиці необхідно обчислити хеш-функцію для шуканого елемента і перевірити, чи не є задана нею комірка масиву порожньою (якщо вона не порожня — елемент знайдений, якщо порожня — не знайдений).
Цей метод дуже ефективний — як час розміщення елемента в таблиці, так і час його пошуку визначаються тільки часом, затрачуваним на обчислення хеш-функції, що у загальному випадку незрівнянно менше часу, необхідного на багаторазові порівняння елементів таблиці.
Метод має два очевидних недоліки. Перший з них – неефективне використання обсягу пам'яті під таблицю ідентифікаторів: розмір масиву для її збереження повинний відповідати області значень хеш-функції, у той час як реально збережених у таблиці ідентифікаторів може бути істотно менше. Другий недолік – необхідність відповідного розумного вибору хеш-функції.
Похожие работы
... , що вхідна мова і системне забезпечення такого пакету можуть бути достатньо легко реалізовані силами прикладного програміста. Тому у разі, коли подібний пакет задовольняє конкретних користувачів, його розробка є цілком виправданою. 3. ВИСНОВОК Сучасний український ринок прикладного програмного забезпечення є, значною мірою, ринком піратського ПО. Це пов'язано з тим, що український спожива
... і MS Excel загальні відомості про електронні таблиці, призначення і можливості, вікно електронної таблиці, вікна книг Термін «електронна таблиця» вживається для позначення простої у використанні комп'ютерної програми Excel, що призначена для обробки інформаційних даних за допомогою таких операцій, як: ■ проведення різних обчислень із використанням потужного апарату функцій і формул; &# ...
... процедур, правил і документації, необхідних для використання програмних продуктів. Усі програми, з якими працюють на сучасних комп’ютерах, можна розділити на 3 категорії: Програмне забезпечення Системні програми Інструментальні системи Прикладні програми · СИСТЕМНІ ПРОГРАМИ- ті, що використовуються для забезпечення працездатності комп’ютера, експлуатації інших програмних продукт ...
... також усі індійські цифри (0–9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл та синтаксичні знаки (!,?,,/, %,$,@,^,_). 3. Розробка транслятора вхідної мови програмування 3.1 Вибір технології програмування Необхідно вибрати ефективні методи розв’язку загальних задач, таких як розпізнавання лексем, синтаксичний розбір, семантичний аналіз та ...
0 комментариев