Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методичні вказівки до лабораторних робот по СПЗ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Системне програмне забезпечення
Частина тексту файла (без зображень, графіків і формул):
Короткий зміст
Вступ…………………………………………………..............................10
Лабораторна робота № 1
Організація таблиць ідентифікаторів ...............................................13
Лабораторна робота № 2
Проектування лексичного аналізатора .............................................39
Лабораторна робота № 3
Побудова простого дерева виведення…………………….................60
Лабораторна робота № 4
Генерація і оптимізація об'єктного коду............................................95
Зміст
Вступ…………………………………………………………..................10
ЛАБОРАТОРНА РОБОТА № 1
Організація таблиць ідентифікаторів................................................13
Мета роботи ..................................................13
Короткі теоретичні відомості ..................................................13
Призначення таблиць ідентифікаторів ..................................................13
Принципи організації таблиць ідентифікаторів ...................................14
Прості методи побудови таблиць
ідентифікаторів .................................................15
Побудова таблиць ідентифікаторів за методом
бінарного дерева .....................................................................................17
Хэш-функції і хэш-адресація .................................................19
Хэш-адресація з рехешуванням……………………………..................21
Хэш-адресація з використанням методу ланцюжків ...........................23
Комбіновані способи побудови таблиць
ідентифікаторів ..................................................25
Вимоги до виконання роботи ..................................................27
Порядок виконання роботи ..................................................27
Вимоги до оформлення звіту ..................................................27
Основні контрольні питання ..................................................28
Варіанти завдань ...................................................................................28
Приклад виконання роботи ..................................................29
Завдання для прикладу .................................................29
Вибір і опис хэш-функції ..................................................30
Опис структур даних таблиць ідентифікаторів.....................................31
Організація таблиць ідентифікаторів .................................................34
Текст програми .................................................35
Висновки по виконаній роботі .................................................37
ЛАБОРАТОРНА РОБОТА № 2
Проектування лексичного аналізатора .............................................39
Мета роботи ..................................................39
Короткі теоретичні відомості ...................................................39
Призначення лексичного аналізатора ………………………..............39
Проблема визначення меж лексем ..................................................40
Таблиця лексем і інформація, що міститься в ній ................................42
Побудова лексичних аналізаторів (сканерів).........................................43
Вимоги до виконання роботи ..................................................45
Порядок виконання роботи ..................................................45
Вимоги до оформлення звіту ..................................................46
Основні контрольні питання ..................................................46
Варіанти завдань ..................................................46
Приклад виконання роботи ..................................................48
Завдання для прикладу ..................................................48
Граматика вхідної мови ..................................................48
Опис кінцевого автомата для розпізнавання лексем
вхідної мови ..................................................49
Реалізація лексичного аналізатора ……………………..................53
Текст програми розпізнавача ..................................................57
Висновки по виконаній роботі ..................................................59
ЛАБОРАТОРНА РОБОТА № 3
Побудова простого дерева виведення................................................60
Мета роботи .................................................60
Короткі теоретичні відомості .................................................60
Призначення синтаксичного аналізатора .............................................60
Проблема розпізнавання ланцюжків КС-мов .....................................62
Види розпізнавачів для КС-мов ............................................................63
Побудова синтаксичного аналізатора....................................................65
Граматики передування .............................................................69
Алгоритм «зсув-згортка» для граматик операторного передування .74
Вимоги до виконання роботи .................................................76
Порядок виконання роботи ................................................76
Вимоги до оформлення звіту ..............................................................77
Основні контрольні питання .................................................78
Варіанти завдань ...................................................................................76
Варіанти вихідних граматик……………………………………………78
Вихідні граматики і типи допустимих лексем ……………………….79
Примітка ……………………………….60
Приклад виконання роботи . ……………………………….80
Завдання для прикладу ………………………………..80
Побудова матриці операторного передування ………………………..81
Реалізація синтаксичного розпізнавача……………………………….88
Текст програми розпізнавача…………………………………………..91
Висновки по виконаній роботі…………………………………………93
ЛАБОРАТОРНА РОБОТА № 4
Генерація і оптимізація об'єктного коду……………………………95
Мета роботи ………………………………..95
Короткі теоретичні відомості ………………………………..95
Загальні принципи генерації коду ………………………………..95
Синтаксично керований переклад ………………………………..97
Способи внутрішнього представлення програм……………………...99
Багатоадресний код з неявно іменованим результатом (тріади) ..... 100
Схеми СУ-перекладу ………………………………..101
Загальні принципи оптимізації коду ………………………………..103
Принципи оптимізації лінійних ділянок …………………………….107
Згортка об'єктного коду ………………………………..107
Виключення зайвих операцій ………………………………..110
Загальний алгоритм генерації і оптимізації об'єктного коду……….112
Вимоги до виконання роботи ………………………………..113
Порядок виконання роботи ……………………………….113
Вимоги до оформлення звіту ………………………………………..114
Основні контрольні питання ………………………………..114
Варіанти завдань ……………………………….115
Приклад виконання роботи ………………………………..115
Завдання для прикладу ………………………………..115
Побудова схем СУ-перекладу ……………………………….115
Приклад генерації списку тріад ……………………………….118
Реалізація генератора списку тріад ……………………………….120
Текст програми генератора списку тріад ……………………………128
Висновки по виконаній роботі ……………………………….131
Вступ
Методичні вказівки можуть виявитися корисною не тільки студентам, але і фахівцям, чия діяльність безпосередньо пов'язана із створенням засобів обробки текстів і структурованих текстових команд. Деякі практичні прийоми, описані в книзі і проілюстровані в прикладах програмного коду, будуть корисні не тільки тим, хто створює або вивчає транслятори, компілятори або будь-які інші розпізнавачі для формальних мов, але і взагалі всім розробникам програмного забезпечення.
Для розуміння практичних прикладів необхідне знання мови програмування Object Pascal і хоча б загальне уявлення про систему програмування Delphi, а також знання мови асемблера процесорів типу Intel 60x86. У ряді випадків для порівняння і розуміння прикладів синтаксичних конструкцій рекомендується знати мову програмування С. Відповідні відомості можна почерпнути в додатковій літературі, приведеній в кінці книги [13, 23-25, 28,31,32,37,39,41,44].
Всі практичні приклади створені автором в системі програмування Delphi 5 на мові Object Pascal з використанням примітивних класів з бібліотеки VCL. Але автор приклав всі зусилля, щоб вони не були прив'язані ні до версії системи програмування, ні до особливостей вихідної мови. Тому охочі без проблем можуть перенести їх під будь-яку версію Delphi, а при необхідності переписати, наприклад на C++, для чого потрібні тільки самі елементарні знання мови.
Програмний код, що приводиться в прикладах, жодною мірою не претендує на високу ефективність. При його створенні автор в першу чергу думав про ілюстративність коду, про його здатність наочно відображати ті теоретичні посилки, які є в книзі. І проте використані методи і прийоми, на думку автора, можуть служити не тільки прикладом реалізації елементів компілятора, але і ілюстрацією хорошого стилю програмування — але хай про це краще судять самі читачі. Можливості подальшого вдосконалення коду найчастіше спеціально закладені в прикладах, а в тексті книги вказано, в чому ці можливості полягають. При проведенні занять викладачі можуть використовувати ці моменти для додаткових завдань по темі книги.
Структура книги проста: вона містить описи чотирьох лабораторних робіт і однієї курсової роботи. Кожна лабораторна робота включає в себе короткі теоретичні викладення, має перелік варіантів завдань, рекомендації по виконанню і оформленню результатів роботи, а також приклад виконання. У кожній лабораторній роботі автор звертає увагу на основні складнощі, пов'язані з її виконанням, а також на можливі типові помилки і недоліки, дає рекомендації по можливостях програмної реалізації, відмінних від коду, що приводиться в прикладах.
Всі лабораторні роботи пов'язані з реалізацією складових частин компілятора. Перша робота присвячена організації таблиць ідентифікаторів, друга — створенню лексичного аналізатора, третя — створенню синтаксичного аналізатора і четверта — генерації і оптимізації результуючого коду. Роботи мають різну складність виконання: на думку автора, перші дві роботи елементарно прості, третя — складніша і, нарешті, четверта має максимальну складність. Це слід враховувати викладачам при плануванні виконання робіт і те, що вивчається при їх виконанні. Крім того, всі чотири роботи взаємозв'язані — кожна подальша робота використовує матеріал попередньої, тому для тих, що навчаються, бажано мати один номер варіанту на виконання всіх робіт (взаємозв'язок робіт і переваги такого підходу наочно проілюстровані в прикладах їх виконання).
ЛАБОРАТОРНА РОБОТА № 1
Організація таблиць ідентифікаторів
Мета роботи
Мета роботи: вивчити основні методи організації таблиць ідентифікаторів, одержати уявлення про переваги і недоліки, властиві різним методам організації таблиць ідентифікаторів.
Для виконання лабораторної роботи потрібно написати програму, яка одержує на вході набір ідентифікаторів, організовує таблиці ідентифікаторів за допомогою заданих методів, дозволяє здійснити багатократний пошук довільного ідентифікатора в таблицях і порівняти ефективність методів організації таблиць. Список ідентифікаторів вважати заданим у вигляді текстового файлу. Довжина ідентифікаторів обмежена 32 символами.
Короткі теоретичні відомості. Призначення таблиць ідентифікаторів
При виконанні семантичного аналізу, генерації коду і оптимізації результуючої програми компілятор повинен оперувати характеристиками основних елементів початкової програми — змінних, констант, функцій і інших лексичних одиниць вхідної мови. Ці характеристики можуть бути одержані компілятором на етапі синтаксичного аналізу вхідної програми (найчастіше при аналізі структури блоків описів змінних і констант), а також доповнені на етапі підготовки до генерації коду (наприклад при розподілі пам'яті).
Набір характеристик, відповідний кожному елементу початкової програми, залежить від типу цього елементу, від його сенсу (семантики) і, відповідно, від тієї ролі, яку він виконує в початковій і результуючій програмах. У кожному конкретному випадку цей набір характеристик може бути свій залежно від синтаксису і семантики вхідної мови, від архітектури цільової обчислювальної системи і від структури компілятора. Але є типові характеристики, які найчастіше властиві тим або іншим елементам початкової програми. Наприклад для змінної — це її тип і адреса елементу пам'яті, для константи — її значення, для функції - кількість і типи формальних аргументів, тип результату, що повертається, адреса виклику коду функції. Докладнішу інформацію про характеристики елементів початкової програми, їх аналіз і використання можна знайти в [ 1,3, 7].
Головною характеристикою будь-якого елементу початкової програми є його ім'я. Саме з іменами змінних, констант, функцій і інших елементів вхідної мови оперує розробник програми - тому і компілятор повинен уміти аналізувати ці елементи по їх іменах.
Ім'я кожного елементу повинне бути унікальним. Багато сучасних мов програмування допускають збіги (неунікальність) імен змінних і функцій залежно від їх області видимості і інших умов початкової програми. В цьому випадку унікальність імен повинен забезпечувати сам компілятор - про те, як вирішується ця проблема, можна дізнатися в [1 - 3, 7], тут же вважатимемо, що імена елементів початкової програми завжди є унікальними.
Таким чином, завдання компілятора полягає в тому, щоб зберігати деяку інформацію, пов'язану з кожним елементом початкової програми, і мати доступ до цієї інформації по імені елементу. Для вирішення цього завдання компілятор організовує спеціальні сховища даних, звані таблицями ідентифікаторів, або таблицями символів. Таблиця ідентифікаторів складається з набору полів даних (записів), кожне з яких може відповідати одному елементу початкової програми. Запис містить всю необхідну компілятору інформацію про даний елемент і може поповнюватися у міру роботи компілятора. Кількість записів залежить від способу організації таблиці ідентифікаторів, але у будь-якому випадку їх не може бути менше, ніж елементів в початковій програмі. В принципі, компілятор може працювати не з однією, а з декількома таблицями ідентифікаторів - їх кількість і структура залежать від реалізації компілятора [1,2].
Принципи організації таблиць ідентифікаторів
Компілятор поповнює записи в таблиці ідентифікаторів по мірі аналізу початкової програми і виявлення в ній нових елементів, що вимагають розміщення в таблиці. Пошук інформації в таблиці виконується кожен раз, коли компілятору необхідні відомості про той або інший елемент програми. Причому слід відмітити, що пошук елементу в таблиці виконуватиметься компілятором істотно частіше, ніж переміщення в неї нових елементів. Так відбувається тому, що описи нових елементів в початковій програмі, як правило, зустрічаються набагато рідше, ніж ці елементи використовуються. Крім того, кожному додаванню елементу в таблицю ідентифікаторів у будь-якому випадку передуватиме операція пошуку — щоб переконатися, що такого елементу в таблиці немає.
На кожну операцію пошуку елементу в таблиці компілятор витрачатиме час, і оскільки кількість елементів в початковій програмі велика (від одиниць до сотень тисяч залежно від об'єму програми), цей час істотно впливатиме на загальний час компіляції. Тому таблиці ідентифікаторів повинні бути організовані так, щоб компілятор мав можливість максимально швидко виконувати пошук потрібного йому запису в таблиці по імені елементу, з яким пов'язаний цей запис.
Можна виділити наступні способи організації таблиць ідентифікаторів:
прості і впорядковані списки;
бінарне дерево;
хэш-адресація з рехешуванням;
хеш-адресація по методу ланцюжків;
комбінація хш-адресації із списком або бінарним деревом.
Далі буде дано короткий опис всіх вище перелічених способів організації таблиць ідентифікаторів. Докладнішу інформацію можна знайти в [3.7].
Прості методи побудови таблиць ідентифікаторів
У простому випадку таблиця ідентифікаторів є лінійним неврегульованим списком, або масивом, кожен осередок якого містить дані про відповідний елемент таблиці. Розміщення нових елементів в такій таблиці виконується шляхом запису інформації в чергову чарунку масиву або списку по мірі виявлення нових елементів в початковій програмі. Пошук потрібного елементу в таблиці в цьому випадку виконуватиметься шляхом послідовного перебору всіх елементів і порівняння їх імені з ім'ям шуканого елементу, поки не буде знайдений елемент з таким же ім'ям. Тоді якщо за одиницю часу прийняти час, що витрачається компілятором на порівняння двох рядків (у сучасних обчислювальних системах таке порівняння найчастіше виконується однією командою), то для таблиці, що містить N елементів, в середньому буде виконано N/2 порівнянь.
Час, потрібний на додавання нового елементу в таблицю (ТД), не залежить від числа елементів в таблиці (N). Але якщо N велике, то пошук буде вимагати значних витрат часу. Час пошуку (Тп) в такій таблиці можна оцінити як Тп=О(N). Оскільки саме пошук в таблиці ідентифікаторів є найбільш часто виконуваною компілятором операцією, такий спосіб організації таблиць ідентифікаторов є неефективним. Він застосовується тільки для найпростіших компіляторів, що працюють з невеликими програмами.
Пошук може бути виконаний ефективніше, якщо елементи таблиці відсортовані (впорядковані) природним чином. Оскільки пошук здійснюється по імені, найбільш природним рішенням буде розташувати елементи таблиці в прямому або зворотному алфавітному порядку. Ефективним методом пошуку у впорядкованому списку з N елементів є бінарний, або логарифмічний пошук.
Алгоритм логарифмічного пошуку полягає в наступному: шуканий символ порівнюється з елементом (N+1)/2 в середині таблиці; якщо цей елемент не є шуканим, то ми повинні проглянути тільки блок елементів, пронумерованих від 1 до (N + 1) /2-1, або блок елементів від (N+1) /2+1 до N залежно від того, менше або більше шуканий елемент того, з яким його порівняли. Потім процес повторюється над потрібним блоком в два рази меншого розміру. Так продовжується до тих пір, поки або шуканий елемент не буде знайдений, або алгоритм не дійде до чергового блоку, що містить один або два елементи (з якими можна виконати пряме порівняння шуканого елементу). Оскільки на кожному кроці число елементів, які можуть містити шуканий елемент, скорочується в два рази, максимальне число порівнянь рівне 1 + 1оg2N. Тоді час пошуку елементу в таблиці ідентифікаторів можна оцінити як Tп=О(1оg2N). Для порівняння: при N=128 бінарний пошук вимагає найбільше 8 порівнянь, а пошук в неврегульованій таблиці — в середньому 64 порівняння. Метод називають «бінарним пошуком», оскільки на кожному кроці об'єм даної інформації скорочується в два рази, а «логарифмічним» — оскільки час, що витрачається на пошук потрібного елементу в масиві, має логарифмічну залежність від загальної кількості елементів в ньому. Недоліком логарифмічного пошуку є вимога впорядковування таблиці ідентифікаторів. Оскільки масив інформації, в якому виконується пошук, повинен бути впорядкований, час його заповнення вже залежатиме від числа елементів в масиві. Таблиця ідентифікаторів часто є видимим компілятором ще до того, як вона наповнена, тому потрібно, щоб умова впорядкованості виконувалася на всіх етапах звернення до неї. Отже, для побудови такої таблиці можна користуватися тільки алгоритмом прямого впорядкованого включення елементів.
Якщо користуватися стандартними алгоритмами, які використовуються для організації впорядкованих масивів даних, то середній час, необхідний на занесення всіх елементів в таблицю, можна оцінити таким чином:
Тд =О(N•log2N) + k•O(N2).
Тут k - деякий коефіцієнт, що відображає співвідношення між часом, що витрачається комп'ютером на виконання операції порівняння і операції занесення даних.
При організації логарифмічного пошуку в таблиці ідентифікаторів забезпечується істотне скорочення часу пошуку потрібного елементу за рахунок збільшення часу на додавання нового елементу в таблицю. Оскільки додавання нових елементів в таблицю ідентифікаторів відбувається істотно рідше, ніж звернення до них, цей метод слід визнати ефективнішим, ніж метод організації неврегульованої таблиці. Проте в реальних компіляторах цей метод безпосередньо також не використовується, оскільки існують ефективніші методи.
Побудова таблиць ідентифікаторів по методу бінарного дерева
Можна скоротити час пошуку шуканого елементу в таблиці ідентифікаторів, не збільшуючи значно час, необхідний на її заповнення. Для цього треба відмовитися від організації таблиці у вигляді безперервного масиву даних. Існує метод побудови таблиць, при якій таблиця має форму бінарного дерева. Кожен вузол дерева є елементом таблиці, причому кореневим вузлом стає перший елемент, який зустрінеться компілятором при заповненні таблиці. Дерево називається бінарним, оскільки кожна вершина в ньому може мати не більше двох гілок. Для визначеності називатимемо дві гаілки: «права» і «ліва».
Розглянемо алгоритм заповнення бінарного дерева. Вважатимемо, що алгоритм працює з потоком вхідних даних, що містить ідентифікатор. Перший ідентифікатор, як вже було сказано, поміщається у вершину дерева. Всі подальші ідентифікатори потрапляють в дерево по наступному алгоритму:
Вибрати черговий ідентифікатор з вхідного потоку даних. Якщо чергового ідентифікатора немає, то побудова дерева закінчена.
Зробити поточним вузлом дерева кореневу вершину.
Порівняти ім'я чергового ідентифікатора з ім'ям ідентифікатора, що міститься в поточному вузлі дерева.
Якщо ім'я чергового ідентифікатора менше, то перейти до кроку 5, якщо рівне — припинити виконання алгоритму (двох однакових ідентифікаторів бути не повинно!), інакше — перейти до кроку 7.
Якщо у поточного вузла існує ліва вершина, то зробити її поточним вузлом і повернутися до кроку 3, інакше - перейти до кроку 6.
Створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити цю нову вершину лівою вершиною поточного вузла і повернутися до кроку 1.
Якщо у поточного вузла існує права вершина, то зробити її поточним вузлом і повернутися до кроку 3, інакше — перейти до кроку 8.
Створити нову вершину, помістити в неї інформацію про черговий ідентифікатор, зробити цю нову вершину правою вершиною поточного вузла і повернутися до кроку 1.
Розглянемо як приклад послідовність ідентифікаторів Ga, D1, M22, Е, А12, ВС, F. На мал. 1.1 проілюстрований весь процес побудови бінарного дерева для цієї послідовності ідентифікаторів.
Мал. 1.1. Заповнення бінарного дерева для послідовності ідентифікаторів Ga, D1, М22, Е, A12, BС, F
Пошук елементу в дереві виконується по алгоритму, схожому з алгоритмом заповнення дерева:
Зробити поточним вузлом дерева кореневу вершину.
Порівняти ім'я шуканого ідентифікатора з ім'ям ідентифікатора, що міститься в поточному вузлі дерева.
Якщо імена співпадають, то шуканий ідентифікатор знайдений, алгоритм завершується, інакше треба перейти до кроку 4.
Якщо ім'я чергового ідентифікатора менше, то перейти до кроку 5, інакше — перейти до кроку 6.
Якщо у поточного вузла існує ліва вершина, то зробити її поточним вузлом і повернутися до кроку 2, інакше - шуканий ідентифікатор не знайдений, алгоритм завершується.
Якщо у поточного вузла існує права вершина, то зробити її поточним вузлом і повернутися до кроку 2, інакше - шуканий ідентифікатор не знайдений, алгоритм завершується.
Для даного методу число необхідних порівнянь і форма дерева, що вийшло, залежать від того порядку, в якому надходять ідентифікатори. Наприклад, якщо в розглянутому вище прикладі замість послідовності ідентифікаторів Ga, D1, M22, Е, А12, ВС, F узяти послідовність А12, ВС, D1, E, F, Ga, M22, то дерево виродиться у впорядкований однонаправлений зв'язний список. Ця особливість є недоліком даного методу організації таблиць ідентифікаторів. Іншими недоліками методу є: необхідність зберігати два додаткові посилання на ліву і праву гілку в кожному елементі дерева і робота з динамічним виділенням пам'яті при побудові дерева.
Якщо припустити, що послідовність ідентифікаторів в початковій програмі є статистично неврегульованою (що в цілому відповідає дійсності), то можна вважати, що побудоване бінарне дерево буде невиродженим. Тоді середній час на заповнення дерева (Тд) і на пошук елементу в нім (Тп) можна оцінити таким чином [3, 7]:
Tд=N•О(1оg2N);
Tп=О(1оg2N).
Не дивлячись на вказані недоліки, метод бінарного дерева є досить вдалим механізмом для організації таблиць ідентифікаторів. Він знайшов своє застосування у ряді компіляторів. Іноді компілятори будують декілька різних дерев для ідентифікаторів різних типів і різної довжини [1,2,3,7].
Хэш-функції і хэш-адресація
У реальних початкових програмах кількість ідентифікаторів така велика, що навіть логарифмічну залежність часу пошуку від їх числа не можна визнати задовільною. Необхідні ефективніші методи пошуку інформації в таблиці ідентифікаторів. Кращих результатів можна досягти, якщо застосувати методи, зв'язані з використанням хэш-функцій і хэш-адресації.
Хэш-функцією F називається деяке відображення безлічі вхідних елементів R на безліч цілих ненегативних чисел Z: F(r)=n, r є R, N є Z. Сам термін «хэш-функція» походить від англійського терміну «hash function» (hash — «заважати», «змішувати», «плутати»).
Безліч допустимих вхідних елементів R називається областю визначення хэш-функції. Безліччю значень хэш-функції F називається підмножина М з безлічі цілих ненегативних чисел Z: M є Z, що містить всі можливі значення, які повертаються функцією F: rIR: F(r) є М і m є M: r є R: F(r)=m. Процес відображення області визначення хэш-функції на безліч значень називається хешуванням.
При роботі з таблицею ідентифікаторів хэш-функція повинна виконувати відображення імен ідентифікаторів на безліч цілих ненегативних чисел. Областю визначення хэш-функції буде безліч всіх можливих імен ідентифікаторів.
Хэш-адресація полягає у використанні значення, яке повертається хэш-функцією, як адреса осередку з деякого масиву даних. Тоді розмір масиву даних повинен відповідати області значень використовуваної хэш-функції.
Отже, в реальному компіляторі область значень хэш-функції ніяк не повинна перевищувати розмір доступного адресного простору комп'ютера.
Метод організації таблиць ідентифікаторів, заснований на використанні хэш-адресації, полягає в додаванні кожного елементу таблиці в чарунку, адресу якої повертає хэш-функція, обчислена для цього елементу. Тоді в ідеальному випадку для додавання будь-якого елементу в таблицю ідентифікаторів досить тільки обчислити його хэш-функцію і звернутися до потрібної чарунки масиву даних. Для пошуку елементу в таблиці також необхідно обчислити хэш-функцію для шуканого елементу і перевірити, чи не є задана нею чарунка масиву порожньою (якщо вона не порожня — елемент знайдений, якщо порожня — не знайдений). Спочатку таблиця ідентифікаторів повинна бути заповнена інформацією, яка дозволила б говорити про те, що всі її чарунки є порожніми. Цей метод вельми ефективний, оскільки як час розміщення елементу в таблиці, так і час його пошуку визначаються тільки часом, що витрачається на обчислення хэш-функції, яке в загальному випадку незіставно менше часу, необхідного для багатократних порівнянь елементів таблиці. Метод має два очевидні недоліки. Перший з них — неефективне використання об'єму пам'яті під таблицю ідентифікаторів: розмір масиву для її зберігання повинен відповідати всій області значень хэш-функції, тоді як ідентифікаторів, що реально зберігаються в таблиці, може бути істотно менше. Другий недолік — необхідність відповідного розумного вибору хэш-функції. Цей недолік є настільки істотним, що не дозволяє безпосередньо використовувати хэш-адресацію для організації таблиць ідентифікаторів.
Проблема вибору хэш-функції не має універсального рішення. Хешування зазвичай відбувається за рахунок виконання над ланцюжком символів деяких простих арифметичних і логічних операцій. Найпростішою хэш-функцією для символу є код внутрішнього уявлення в комп'ютері літери символу. Цю хэш-функцію можна використовувати і для ланцюжка символів, вибираючи перший символ в ланцюжку.
Очевидно, що така примітивна хэш-функція буде незадовільною: при її використанні виникне проблема - двом різним ідентифікаторам, що починаються з однієї і тієї ж букви, відповідатиме одне і те ж значення хэш-функції. Тоді при хэш-адресації в одну і ту ж чарунку таблиці ідентифікаторів повинні бути поміщені два різні ідентифікатори, що явно неможливо. Така ситуація, коли двом або більше ідентифікаторам відповідає одне і те ж значення хэш-функції, називається колізією.
Природно, що хэш-функція, що допускає колізії, не може бути використана для хэш-адресації в таблиці ідентифікаторів. Причому досить одержати хоча б один випадок колізії на всій множині ідентифікаторів, щоб такою хэш-функцією не можна було користуватися. Але чи можливо побудувати хэш-функцію, яка б повністю виключала виникнення колізій? Для повного виключення колізій хэш-функція повинна бути взаємно однозначною: кожному елементу з області визначення хэш-функції повинне відповідати одне значення з її множини значень, і навпаки — кожному значенню з множини значень цієї функції повинен відповідати тільки один елемент з її області визначення. Тоді будь-яким двом довільним елементам з області визначення хэш-функції завжди відповідатимуть два різних її значення. Теоретично для ідентифікаторів таку хэш-функцію побудувати можна, оскільки і область визначення хэш-функції (всі можливі імена ідентифікаторів), і область цих значень (цілі ненегативні числа) є нескінченними рахунковими множинами, тому можна організувати взаємнооднозначне відображення однієї множини на іншу.
Але на практиці існує обмеження, що робить створення взаємнооднозначної хэш-функції для ідентифікаторів неможливим. Річ у тому, що в реальності область значень будь-якої хэш-функції обмежена розміром доступного адресного простору комп'ютера. Множина адрес будь-якого комп'ютера з традиційною архітектурою може бути велика, але завжди скінченна. Організувати взаємно однозначне відображення нескінченної множини на кінцеве навіть теоретично неможливо. Можна, звичайно, врахувати, що довжина частини імені ідентифікатора, що приймається до уваги, в реальних компіляторах на практиці також обмежена — зазвичай вона лежить в межах від 32 до 128 символів (тобто і область визначення хэш-функції кінцева). Але і тоді кількість елементів в кінцевій множині, що становить область визначення хэш-функції, перевищуватиме їх кількість в кінцевій множині області її значень (кількість всіх можливих ідентифікаторів більше кількості допустимих адрес в сучасних комп'ютерах). Таким чином, створити взаємно однозначну хэш-функцію на практиці неможливо. Отже, неможливо уникнути виникнення колізій.
Тому не можна організувати таблицю ідентифікаторів безпосередньо на основі однієї тільки хэш-адресації. Але існують методи, що дозволяють використовувати хэш-функції для організації таблиць ідентифікаторів навіть за наявності колізій.
Хэш-адресація з рехешуванням
Для вирішення проблеми колізії можна використовувати багато способів. Одним з них є метод рехешування (або розстановки). Згідно цього методу, якщо для елементу A адреса n0=h(A), обчислена за допомогою хэш-функції h, вказує на вже зайняту чарунку, то необхідно обчислити значення функції n1=h1(A) і перевірити зайнятість чарунки за адресою n1. Якщо і вона зайнята, то обчислюється значення h2(A), і так до тих пір, поки або не буде знайдена вільна чарунка, або чергове значення hi(A) не співпаде з h(A). У останньому випадку вважається, що таблиця ідентифікаторів заповнена і місця в ній більше немає — видається інформація про помилку розміщення ідентифікатора в таблиці. Тоді пошук елементу А в таблиці ідентифікаторів, організованій таким чином, виконуватиметься але наступному алгоритму:
Обчислити значення хэш-функції n=h(A) для шуканого елементу А.
2.Якщо чарунка за адресою n порожня, то елемент не знайдений, алгоритм завершений, інакше необхідно порівняти ім'я елементу в чарункі n з ім'ям шуканого елементу А. Якщо вони співпадають, то елемент знайдений і алгоритм завершений, інакше i:=1 і перейти до кроку 3.
3. Обчислити ni = hi(A). Якщо чарунка за адресою nі порожня або n=ni, то елемент не знайдений і алгоритм завершений, інакше - порівняти ім'я елементу в чарунці ni з ім'ям шуканого елементу А. Якщо вони співпадають, то елемент знайдений і алгоритм завершений, інакше i:=i + 1 і повторити крок 3.
Алгоритми розміщення і пошуку елементу схожі по виконуваних операціях. Тому вони матимуть однакові оцінки часу, необхідного для їх виконання.
При такій організації таблиць ідентифікаторів у разі виникнення колізії алгоритм поміщає елементи в порожні елементи таблиці, вибираючи їх певним чином. При цьому елементи можуть потрапляти в чарунки з адресами, які потім співпадатимуть із значеннями хэш-функції, що приведе до виникнення нових, додаткових колізій. Таким чином, кількість операцій, необхідних для пошуку або розміщення в таблиці елементу, залежить від заповненої таблиці.
Для організації таблиці ідентифікаторів по методу рехешування необхідно визначити всі хэш-функції hi для всіх i. Найчастіше функції hi визначають як деякі модифікації хэш-функцій h. Наприклад, найпростішим методом обчислення функції hi(A) є її організація у вигляді hi(A)=(h(A)+рi)modNm, де рi — деяке обчислюване ціле число, а Nm — максимальне значення з області значень хэш-функції h. У свою чергу, найпростішим підходом тут буде покласти рi=i. Тоді одержуємо формулу hi(A)=(h(A)+i)modNm . В цьому випадку при збігу значень хэш-функції для яких-небудь елементів пошук вільної чарунки в таблиці починається послідовно від поточної позиції, заданою хэш-функцією h(A).
Цей спосіб не можна визнати особливо вдалим: при збігу хэш-адрес елементи в таблиці починають групуватися навколо них, що збільшує число необхідних порівнянь при пошуку і розміщенні. Але навіть такий примітивний метод рехешування є достатньо ефективним засобом організації таблиць ідентифікаторів при неповному заповненні таблиці. Середній час на додавання одного елементу в таблицю і на пошук елементу в таблиці можна понизити, якщо застосувати більш довершений метод рехешування. Одним з таких методів є використання як pi для функції hi(A)=(h(A)+рi)modNm послідовності псевдовипадкових цілих чисел р1, р2…pk. При хорошому виборі генератора псевдовипадкових чисел довжина послідовності k=Nm .
Існують і інші методи організації функцій рехешування hi(A), засновані на квадратичних обчисленнях або, наприклад, на обчисленні піднесення за формулою: hi(A)=(h(A)N•i)mod N’m де N’m —найближче просте число, менше Nm. В цілому рехешування дозволяє добитися непоганих результатів для ефективного пошуку елементу в таблиці (кращих, ніж бінарний пошук і бінарне дерево), Але ефективність методу сильно залежить від заповненої таблиці ідентифікаторів і якості використовуваної хэш-функції — чим рідше виникають колізії, тим вище ефективність методу. Вимога неповного заповнення таблиці веде до неефективного використання об'єму доступної пам'яті.
Оцінки часу розміщення і пошуку елементу в таблицях ідентифікаторів при використанні різних методів рехешування можна знайти в [1,3,7].
Хэш-адресація з використанням методу ланцюжків
Неповне заповнення таблиці ідентифікаторів при застосуванні рехешування веде до неефективного використання всього об'єму пам'яті, доступного компілятору. Причому об'єм невживаної пам'яті буде тим вище, чим більше інформації зберігається для кожного ідентифікатора. Цього недоліку можна уникнути, якщо доповнити таблицю ідентифікаторів деякою проміжною хэш-таблицею.
В чарунках хэш-таблиці може зберігатися або порожнє значення, або значення вказівника на деяку область пам'яті з основної таблиці ідентифікаторів. Тоді хэш-функція обчислює адресу, по якій відбувається звернення спочатку до хэш-таблиці, а потім вже через неї за знайденою адресою — до самої таблиці ідентифікаторів. Якщо відповідний елемент таблиці ідентифікаторів порожній, то чарунка хэш-таблиці міститиме порожнє значення. Тоді зовсім не обов'язково мати в самій таблиці ідентифікаторів чарунку для кожного можливого значення хэш-функції - таблицю можна зробити динамічною, так щоб її об'єм ріс по мірі заповнення (спочатку таблиця ідентифікаторів не містить жодної чарунки, а всі чарунки хэш-таблиці мають порожнє значення).
Такий підхід дозволяє добитися двох позитивних результатів: по-перше, немає необхідності заповнювати порожніми значеннями таблицю ідентифікаторів - це можна зробити тільки для хэш-таблиці; по-друге, кожному ідентифікатору відповідатиме строго одна чарунка в таблиці ідентифікаторів. Порожні чарунки у такому разі будуть тільки в хэш-таблиці, і об'єм невживаної пам'яті не залежатиме від об'єму інформації, що зберігається для кожного ідентифікатора, — для кожного значення хэш-функції витрачатиметься тільки пам'ять, необхідна для зберігання одного вказівника на основну таблицю ідентифікаторів.
На основі цієї схеми можна реалізувати ще один спосіб організації таблиць ідентифікаторів за допомогою хэш-функції, який називається методом ланцюжків. В цьому випадку в таблицю ідентифікаторів для кожного елементу додається ще одне поле, в якому може міститися посилання на будь-який елемент таблиці. Спочатку це поле завжди порожнє (нікуди не вказує). Також необхідно мати одну спеціальну змінну, яка завжди вказує на перший вільний елемент основної таблиці ідентифікаторів (спочатку вона вказує на початок таблиці). Метод ланцюжків працює по наступному алгоритму:
1. У всі чарунки хэш-таблиці помістити порожнє значення, таблиця ідентифікаторів порожня, змінна FreePtr (вказівник першої вільної чарунки) вказує на початок таблиці ідентифікаторів.
Обчислити значення хэш-функції n для нового елементу А. Якщо чарунка хэш-таблиці за адресою n порожня, то помістити в неї значення змінної FreePtr і перейти до кроку 5; інакше перейти до кроку 3.
Вибрати з хэш-таблиці адресу елементу таблиці ідентифікаторів m і перейти до кроку 4.
Для елементу таблиці ідентифікаторів за адресою m перевірити значення поля посилання. Якщо воно порожнє, то записати в нього адресу змінної FreePtr і перейти до кроку 5; інакше вибрати з поля посилання нову адресу m і повторити крок 4.
Додати в таблицю ідентифікаторів нову чарунку, записати в неї інформацію для елементу А (поле посилання повинне бути порожнім), в змінну FreePtr помістити адресу за кінцем доданої чарунки. Якщо більше немає ідентифікаторів, які треба помістити в таблицю, то виконання алгоритму закінчене, інакше перейти до кроку 2.
Пошук елементу в таблиці ідентифікаторів, організованій таким чином, виконуватиметься по наступному алгоритму:
Обчислити значення хэш-функції n для шуканого елементу А. Якщо чарунка хэш-таблиці за адресою n порожня, то елемент не знайдений і алгоритм завершений, інакше вибрати з хэш-таблиці адресу елементу таблиці ідентифікаторів m.
Порівняти ім'я елементу в елементі таблиці ідентифікаторів за адресою m з ім'ям шуканого елементу А. Якщо вони співпадають, то шуканий елемент знайдений і алгоритм завершений, інакше перейти до кроку 3.
Перевірити значення поля посилання в чарунці таблиці ідентифікаторів за
14.05.2018 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора