48984 (666135), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Крок 3. Перевірити значення поля посилання в комірці таблиці ідентифікаторів за адресою m_j . Якщо воно порожнє, то шуканий елемент не знайдений і алгоритм завершений ; інакше j:=j+l, вибрати з поля посилання адреса m_j і перейти до кроку 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. Способи внутрішнього представлення програм

Усі внутрішні представлення програми звичайно містять у собі дві принципово різні речі — оператори й операнди. Розходження між формами внутрішнього представлення полягають лише в тому, як оператори й операнди з'єднуються між собою. Також оператори й операнди повинні відрізнятися один від іншого, якщо вони зустрічаються в будь-якому порядку. За розрізнення операндів і операторів, як уже було сказано вище, відповідає розроблювач компілятора, що керується семантикою вхідної мови.

Відомі наступні форми внутрішнього представлення програм:

зв'язані облікові структури, що представляють синтаксичні дерева;

багатоадресний код з явно іменованим результатом (тетради);

багатоадресний код з неявно іменованим результатом (тріади);

обернений (постфиксна) польський запис операцій;

асемблерний код або машинні команди.

Синтаксичні дерева

Синтаксичні дерева – це структура, що представляє собою результат роботи синтаксичного аналізатора. Вона відображає синтаксис конструкцій вхідної мови і явно містить у собі повний взаємозв'язок операцій. Очевидно також, що синтаксичні дерева — це машинно-незалежна форма внутрішнього представлення програми.

Недолік синтаксичних дерев полягає в тому, що вони являють собою складні зв'язні структури, а тому не можуть бути тривіальним чином перетворені в лінійну послідовність команд результуючої програми. Проте вони зручні при роботі з внутрішнім представленням програми на тих етапах, коли немає необхідності безпосередньо звертатися до команд результуючої програми.

Синтаксичні дерева можуть бути перетворені в інші форми внутрішнього представлення програми, що представляють собою лінійні списки, з урахуванням семантики вхідної мови. Алгоритми такого роду перетворень розглянуті далі. Ці перетворення виконуються на основі принципів СК-компіляції.

Багатоадресний код з явно іменованим результатом (тетради)

Тетради являють собою запис операцій у формі з чотирьох складових: операції, двох операндів і результату операції. Наприклад, тетради можуть виглядати так: (,,).

Тетради являють собою лінійну послідовність команд. При обчисленні виразу, записаного у формі тетрад, вони обчислюються одна за іншою послідовно. Кожна тетрада в послідовності обчислюється так: операція, задана тетрадою, виконується над операндами і результат її виконання міститься в змінній, заданій результатом тетради. Якщо якийсь з операндів (чи оба операнда) у тетраді відсутні (наприклад, якщо тетрада являє собою унарну операцію), то він може бути опущений чи замінений порожнім операндом (у залежності від прийнятої форми запису і її реалізації).

Тетради являють собою лінійну послідовність, а тому для них нескладно написати тривіальний алгоритм, що буде перетворювати послідовність тетрад у послідовність команд результуючої грами (або послідовність команд асемблера). У цьому їхня перевага перед синтаксичними деревами. На відміну від команд асемблера тетради не залежать від архітектури обчислювальної системи, на яку орієнтована результуюча програма. Тому вони являють собою машинно-незалежну форму внутрішнього представлення програми.

Тетради вимагають більше пам'яті для свого представлення, ніж тріади, вони також не відображають явний взаємозв'язок операцій між собою. Крім того, є складності з перетворенням тетрад у машинний код, тому що вони погано відображаються в команди асемблера і машинні коди, оскільки в наборах більшості сучасних комп'ютерів рідко зустрічаються операції з трьома операндами.

Багатоадресний код з неявно іменованим результатом (тріади)

Тріади являють собою запис у формі трьох складових:

(;)

Їх особливістю є те, що один або обидва операнди можуть бути посиланнями на іншу тріаду. Це в тому випадку, якщо в якості операнда даної тріади виступає результат виконання іншої тріади. Тому тріади при записі нумерують послідовно для зручності посилань.

Кожна тріада обчислюється таким чином: операція, яка задана тріадою, виконується над операндами, якщо в якості одного із операндів або двох є посилання на іншу тріаду, то береться результат обчислення тієї тріади. Результат обчислення кожної тріади потрібно зберігати в тимчасовій пам’яті, так як він може знадобитися наступним тріадам. Якщо один операнд відсутній, він може бути упущений.

Переваги:

легке написання алгоритму;

легко перевести в асемблер ний код.

Недолік: необхідний алгоритм для зберігання в пам’яті проміжного результату.

Тріади є машинно незалежні, вимагають менше пам’яті ніж тетради.

Обернений польський запис

Перевага: ефективний для обчислення математичних виразів.

Недоліки:

необхідно використовувати стек

важко робити оптимізацію

Нехай задано арифметичний вираз виду: (A+B)*(C+D)-E

Представимо цей вираз у вигляді польського запису: AB+CD+*E-

Обернений польський запис володіє властивостями, які перетворюють його в ідеальну проміжну мову при трансляції:

1. обчислення виразу може проводитися шляхом одноразового перегляду, що зручно для генерації коду

2. отримання польського запису просто здійснити на основі алгоритму DX3.

13. Визначення формальної мови і граматики

Формальні мови - це математичний апарат, що дозволяє математично грамотно створити мови програмування і писати компілятори для них.

Формальну мову можна задати як послідовність слів. Слово – це послідовність символів. Тоді навіть програму можна вважати просто словом.

Словами даної мови може бути не довільний набір символів, а лексично і синтаксично правильно побудований. Для того, щоб задати граматику, треба задати множини термінальних і не термінальних символів.

Термінальні – це символи, які використовуються в мові, а проміжні або нетермінальні – це символи, які використовуються для створення слів мови. Створюються слова за граматичними правилами. Застосування правила полягає в заміні в перетворюваному рядку якоїсь послідовності символів, що співпадає з лівою або правою частиною правила.

Компілятор, отримавши на вхід програму, робить зворотну роботу. Він згортає за граматичними правилами від правої до лівої частини початкові символи.

Кінцева множина символів, яка є неподільною, називається словником або алфавітом, а символи, що входять в множину – буквами алфавіту. Послідовність букв алфавіту називається словом або ланцюжком цього алфавіту, число букв, що входить у слово, називається його довжиною.

Якщо задано алфавіт А, то А^* - це множина всіх ланцюжків, які можна побудувати з алфавіту А. $ - порожній рядок (рядок, що не містить жодної букви) також входить в А. Для позначення всіх ланцюжків алфавіту А, що не містять порожнього використовується А⁺.

Характеристики

Список файлов реферата