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.  Усі  ці  данні   підтверджують   високу ефективність методу хеширування.


 

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

68085. Прогулянка до лісу. Диференціація звуків л-р-л’-р’ 35.5 KB
  Мета: вчити дітей розрізняти звуки (л-р-л′-р′), автоматизувати ці звуки у зв’язному мовленні; розвивати у дітей слухову увагу, пам'ять; розвивати дрібну моторику; розвивати міміку дітей; удосконалювати мовну моторику, фонематичний слух, фонематичне сприймання, фонематичний аналіз та синтез.
68087. Дослідження творчого спадку М.В. Ломоносова в області природознавчих наук 10.63 MB
  У пропонованій роботі наведено результати дослідження й аналізу творчого спадку М.В.Ломоносова в області геології, ґрунтознавства, біології, екології. Головну увагу приділено впливу праць М.В.Ломоносова на сучасний стан цих наук. На конкретних прикладах показано пріоритетну роль М.В.Ломоносова...
68088. Визначні місця Лондона. Урок для 4 класу 49.5 KB
  Мета: закріпити знання лексики з теми «Споруди»; практикувати у вживанні спеціальних питань, вчити правильно на них відповідати; вдосконалювати навички аудіювання, читання та письма; розвивати навички усного мовлення; сприяти розвитку пам’яті, логічного мислення учнів...
68089. Подорож історією Лондона 181.5 KB
  В процесі викладання іноземної мови дуже важливе місце займають позакласні заходи. Вони є дієвим методом підтримки зацікавленості учнів у вивченні англійської мови. Важливу роль відіграє підготовчий етап до заходів. Вчитель повинен підготовити сценарій і ознайомити учнів з ним, розподілити...
68090. Цінність людини – в її унікальності! 48.5 KB
  Мета: довести ідею неповторності й унікальності кожної особистості, допомогти кожному з учнів знайти в собі те, що відрізняє їх від інших. Обладнання: стікери, постери-самореклами
68091. ЛИКИ ТОЛЕРАНТНОСТИ 39.5 KB
  Усовершенствовать умения толерантного общения в практических упражнениях Информационное сообщение: Современный мир жесток жестокими стали и дети. Именно поэтому мировая общественность в качестве всеобъемлющего средства борьбы за выживание выбрала толерантность как основополагающий...
68092. Культура поведінки 28.5 KB
  Поговорімо діти про культуру про те як треба звертатись до людей щоб кожному було приємно з вами спілкуватись і щоб про кожного з нас люди могли сказати що ви людина вихована культурна. Для цього треба вміти поводитися серед людей знати правила поведінки вживати у у своїй мові чарівні слова які...
68093. Культурное наследие 151.52 KB
  Беседа Какое время года Какой месяц Что вы знаете об этом месяце Последний месяц зимы самый короткий високосный 29 дней небо голубое увеличивается световой день в народе называют лютый бокогрей. Что следует делать если подарок сладости или фрукты а поблагодарить...