68827

Генерація машинного коду

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-26

79.5 KB

0 чел.

Лекція 15

Генерація машинного коду

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

Надалі розглянемо питання  пов’язані  з  використанням  пам’яті машини у процесі компіляції.

Робота з таблицею символів методом хеширування

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

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

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

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

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

Суть методу хеширування можна пояснити так. На множині  І  усіх можливих  ідентифікаторів  задається  функція   h   відображення   множини  І  у множину  N  індексів масиву,  h: I  N.

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

| І | = 26i .

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

Наведемо  приклад  функції   хеширування.   Візьмемо   довільну функцію,  що  визначає  номер  кожного   можливого   ідентифікатора. Позначимо її як                               ord(id). Якщо  пронумерувати  усі  символи,  що   використовуються   для уявлення ідентифікаторів, то ord(id)  можна  визначити,  наприклад, як суму номерів символів, з  яких  складається id.  Нехай  довжина масиву для реалізаціїї таблиці символів дорівнює  n, тобто  | N | = n. Тоді функцію хеширування можна означити як  h(id) = ord(id)mod n, тобто  значення  індексу  масиву  визначається  як   порядковий   номер ідентифікатора за модулем  n.

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

Якщо ж функція хеширування черговому  ідентифікатору  ставить  у відповідність індекс, який використано раніше, то виникає так званий конфлікт. Для розв’язання конфліктів застосовують декілька  методів. Очевидний і  досить  ефективний  за  часом  метод  -  зв’язування  у лінійний список усіх ідентифікаторів з однаковими первинними  індексами  h(id). Цей метод називають безпосереднім зчепленням. Його недолік  - додаткові витрати пам’яті на покажчики для утворення списків.

Інший метод вирішування конфліктів полягає у тому, що за деяким правилом проглядаються один за одним елементи таблиці доки  не  буде знайдено потрібний елемент, або не зустрінеться  вільне  місце.  Цей метод називається відкритою адресацією. Не слід вважати, що у методі відкритої  адресації  послідовно   проглядувані   елементи   повинні обов’язково також послідовно  розташовуватись  у  таблиці.  Навпаки, положення кожного  наступного  елементу  визначається  за  допомогою спеціальної функції  rh, що  називається  функцієй  перехеширування. Сформулюємо основну властивість,  яку  повинна  мати  функція   rh. Нехай для вхідного ідентифікатора  id   k0  = h(id) - індекс, що вже використано. Тоді послідовне застосування функції  rh  повинно давати послідовність індексів  k1 = rh(k0 ), k2 = rh (k1 ), … , kn-1 =rh (kn-2 ), rh (kn-1 ) =  k0,  у якій для усіх  i  j   ki   kj.

Простішою функцією  перехеширування  є  функція,  що  додає  до поточного  індексу  одиницю  за  модулем   n.  Ця  функція   генерує послідовність індексів  ki = (k0  + i)mod n , i  = 1,2, … , n.

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

ki = (k0  + i2)mod n , i  = 1,2, … , [n/2].

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

ki+1 = (k0  + (i+1)2) mod n = (k0  + i2 + 2i + 1) mod n   = ( ki  + 2i + 1) mod n.

Позначивши  di = 2i + 1, одержуємо рекурентне співвідношення

ki+1 = (ki  + di) mod n,  di+1 = di + 2,  d0 = 1.

Недолік цього методу полягає у тому, що квадратична функція  не має основної властивості функції  перехеширування,  і  в  результаті проглядаються не усі елементи  таблиці.  Однак,  якщо   n  -  просте число, принаймні половина таблиці проглядається. Дійсно, якщо   i-та і  j-та спроби дають один і той же елемент таблиці, то  i2 = j2 mod n,  або  i2 - j2 = 0 mod n.   Звідки маємо      (i + j)(i - j) = 0 mod n.  Оскільки  i  j, та  n - просте, то  i + j   n ,  а  це  означає,  що хоча б одне з чисел  i  чи  j  не менше ніж  n/2.  

На  практиці  цей  недолік  не  має   великого   значення,   бо необхідність  виконання   n/2  повторних   спроб   для   вирішування конфліктів зустрічається дуже рідко і лише тоді, коли  таблиця  майже заповнена.

Метод перехеширування, що  розподіляє  ідентифікатори  по  усій таблиці майже рівномірно і проглядає  усю  таблицю  при  конфліктах, полягає у застосуванні формули

ki+1 = (ki  + m) mod n,

де  m  та  n  взаємно прості числа, і  m < n. У даному  випадку  для двох спроб  i  та  j  (i < j), що дають одне і те ж значення індексу  (ki = kj ), маємо  l = ji, lm = 0 mod n.

Оскільки  m  та  n  взаємно прості, то l = 0 mod n, а враховуючи, що i < j, тобто  l > 0, і  l  n (кількість повторних спроб не більше  n), одержуємо  l = n.

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

Окремим предметом  досліджень  є  питання  про  очікуваний  час звертання до таблиці символів при застосуванні  методу  хеширування. Цей час звичайно оцінюють середньою кількістю спроб.

Аналіз трудомісткості методу хеширування

Припустимо,  що  усі  можливі  ідентифікатори  мають   однакову ймовірність, і функція хеширування  р  рівномірно розподіляє  їх  по всьому  інтервалу  індексів.  Далі  припустимо,  що  треба  уставити ідентифікатор у таблицю розміром  n, яка вже містить  k   елементів. Ймовірність попадання на вільне місце у першій спробі дорівнює  1 - k/n. Позначимо її через  з p1. Ймовірність  p2  того,  що  треба  буде виконати дві спроби, дорівнює добутку ймовірності конфлікта у першій спробі і ймовірності попадання на вільне місце у другій, тобто

p2  = (k/n)(n-k)/(n-1).

Для ймовірності виконання  i  спроб одержуємо

pi  = (k/n)(л-1)(k-1)/(n-1)…(k-i+2)/(n-i+2)(n-k)/(n-i+1) =

= (n-k)k!(n-i)!/(n!(k-i+1)!).

Підрахуємо  математичне  сподівання   Мk+1  кількості   спроб   для включення у таблицю  k+1-го ідентифікатора. Маємо 

Мk+1     = ipi = pi = pi + … + pi = pi =

= ((n-k)k!/n!) (n-i)!/(k-i+1)!.

Позначивши  q = i – j,  одержуємо

Мk+1= ((n-k)k!/n!) (n-j-q)!/(k-j-q+1)!.

Знайдемо суму вигляду

(n-i)!/(k-i)!.

Маємо

(n-i)!/(k-i)! =  (n-i)!/(k-i)! + (n-k+1)! + (n-k)! =

= (n-i)!/(k-i)! + (n-k+2)!/ (n-k+1) =

=(n-i)!/(k-i)! + (n-k+2)!/2! + (n-k+2)!/ (n-k+1) =

        =(n-i)!/(k-i)! + (n-k+3)!/(n-k+1)2!) =

=  (n-k+k+1)!/((n-k+1)k!) = (n+1)!/((n-k+1)k!).

Застосувавши цю формулу для Мk+1, одержуємо

                              Мk+1 = ((n-k)k!/n!) (n+1-j)!/((k+1-j)!(n-k)).

.Після заміни індексу  l = j – 1  маємо

Мk+1 = (k!/n!) (n-l)!/((k-l)!.

Знов застосувавши отриману формулу для суми, нарешті одержуємо

Мk+1 = k!(n+1)!/(n!k!(n-k+1)) = (n+1)/(n-k+1).

Тепер знайдемо середню кількість   М   спроб  при  включенні  у

таблицю розміром  n  m  ідентифікаторів.

М = (1/m) Мk = (n+1)/m) l/(n-k+2) = ((n+1)/m)(Hn+1  - Hn-m+1),

е  Hn = 1 + 1/2 + … + 1/n  -  гармонічна  функція.  Функцію   Нn ,  як відомо  [4], можна апроксимувати таким чином   Hnln(n) + ,  де  - ейлерова константа. Якщо  увести позначення    = m/(n+1), то можна одержати формулу для підрахування  М.

      М = (1/)(ln(n+1) - ln(n-m+1)) = (1/)ln((n+1)/(n-m+1)) = - (1/)ln(1- ). 

Розрахунки згідно з цією формулою показують, що при коефіцієнті заповнення таблиці  0,75  середня кількість спроб приблизно дорівнює  1,85, а при  0,9 - всього  2,56. Для порівняння можна вказати, що за подібними розрахунками для методу  лінійного  опробування  одержують при коефіцієнті заповнення  таблиці  0,75  середню  кількість  спроб  2,5,  а  при   0,9  -  5,5.  Усі  ці  данні   підтверджують   високу ефективність методу хеширування.


 

А также другие работы, которые могут Вас заинтересовать

43133. Поиск неисправностей в СВ 1.17 MB
  Анализ неисправности на структурном уровне По структурной схеме СВ устанавливаем вероятный неисправный блок. Согласно внешним признакам проявления неисправности очевидно что неисправен может быть либо сам ПОУ СВ либо блок ВчУ структурный уровень так как только эти устройства участвуют в записи информации с ПОУ СВ на ВчУ. Анализ неисправности на функциональном уровне По функциональной схеме устанавливаем вероятные неисправные устройства блока ПОУ СВ и ВчУ. Учитывая внешний признак проявления неисправности очевидно что этими устройствами...
43134. Проектирование привода ленточного транспортера 7.63 MB
  Расчет вала на выносливость Выбор муфты для выходного вала. Выбор муфты для ведомого вала. Редуктор имеет три вала: горизонтально расположенный ведущий быстроходный вал на котором установлена коническая шестерня и два горизонтальных вала перпендикулярных ведущему валу.
43135. Проектування корпуса фільтра вертикального однокамерного 1.3 MB
  Графічна частина виконується у обсязі двох аркушів формату А1: один аркуш складального креслення апарату загальний вигляд; один аркуш формату А2 зі складальним кресленням вузлів апарату за вказівкою викладача керівника проекту після виготовлення креслення першого аркуша; один аркуш формату А2 з робочими кресленнями деталей різноманітного призначення за вказівкою викладача керівника проекту після розробки складальних креслень формат А2 ділиться за необхідністю на декілька менших форматів. Розрахунковопояснювальна записка...
43137. Какова сущность, функции и структура морали 35.5 KB
  Всем известно, что человек — это индивид, умеющий себя ограничивать. Все мы живем в мире сплошных ограничений. Можно с уверенностью сказать, что человек и человеческое общество возникли тогда, когда научились себя ограничивать. Так, например первыми законами были законы, запрещающие браки между родственниками.
43138. Методика викладання теми “Основні поняття алгоритмізації” у 8 класах 2.21 MB
  У житті ми постійно складаємо опис деякої послідовності дій для досягнення бажаного результату, тому поняття алгоритму не є для нас чимось новим і незвичайним. Кожен із нас використовує сотні різних алгоритмів. Але рішення завдання на комп'ютері неможливо без створення алгоритму. Вміння виконувати завдання, розробляти стратегію її вирішення, висувати і доводити гіпотези досвідченим шляхом, прогнозувати результати своєї діяльності, аналізувати і знаходити раціональні способи вирішення завдання шляхом оптимізації, деталізації створеного алгоритму дозволяють судити про рівень розвитку алгоритмічного мислення школярів. Тому необхідно особливу увагу приділяти алгоритмічному мисленню підростаючого покоління.
43139. Програмування. Методичні вказівки 206 KB
  Тема першого завдання використання візуальних компонентів із вкладок компонентів Stndrt System dditionl при роботі з масивами даних. Оброблений масив список даних вивести в таблицю MS Word створену за допомогою Delphi. Друге завдання створення баз даних та обробка інформації з них. База даних створюється за допомогою утілити Dtbse Desktop або за допомогою інших програм створення баз даних наприклад MS ccess.
43140. Синтез автомата по заданому алгоритму роботи 1.49 MB
  Система з чотирьох перемикальніх функцій задана таблицею 2.1 таблиця істиності заданих функцій Необхідно виконати сумісну мінімізацію функцій f1 f2 f3. Отримати операторні представлення для реалізації системи функцій на програмувальних логічних матрицях. 4 Етапи проектування і терміни їх виконання 1 Розмітка станів автомата 2 Формування вхідного та вихідного алфавітів 3 Побудова графа автомата 4 Побудова таблиці переходів 5 Побудова структурної таблиці автомата 6 Синтез комбинаційних схем для функцій збудження тригерів і вихідних...
43141. Туристский потенциал Вологодской области 108 KB
  Эмпирическую базу курсовой работы составили российские правовые акты; нормативные документы; отчетность и аналитические материалы региональных органов власти (Департамента развития муниципальных образований Вологодской области, Департамента культуры и охраны культурного наследия Вологодской области, Департамента международных, межрегиональных связей и туризма Вологодской области); официальные статистические данные в сфере туризма.