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


 

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

30625. Герои и проблематика сатиры М.Е. Салтыкова-Щедрина в романе «История одного города» 14.99 KB
  СалтыковаЩедрина в романе История одного города М. СалтыковаЩедрина по праву считается История одного города которую он начал писать в 1868 году а закончил в 1870 году.Цензура и некоторые критики поняли Историю одного города как сатиру относящуюся исключительно к прошлому России и главным образом к 18му веку.Главный герой Истории одного города народ обобщенный образ которого раскрывается из главы в главу все шире.
30626. Герои и сюжет баллады В.А. Жуковского «Светлана» 20.15 KB
  Жуковского Светлана В. Светлана самое знаменитое произведение Жуковского это переводпереложение баллады немецкого поэта Бюргера Леонора. Однако Светлана произведение радостное несмотря на присутствие в нем загробной жизни. Светлана молится о том чтобы вернулся ее возлюбленный в полночь во время гадания жених неожиданно появляется и зовет Светлану венчаться.
30627. Тема противостояния героя и толпы в ранней поэзии В.В. Маяковского 13.38 KB
  Люди исчезли и потому герой готов целовать умную морду трамвая чтобы забыть окружающих:Ненужных как насморки трезвых как нарзан.Лирический герой Маяковского одинок в этом мире. За своим амплуа хулигана герой скрывает тонкую ищущую любви душу защищая ее от тех кто грубее жестче сильнее. Это стихотворение – вдохновенная мечта о красоте мира:ПослушайтеВедь если звезды зажигают – значит это комунибудь нужноГерой тоскует видя беззвездное небо.
30628. Смысл названия драмы «Гроза» 18.37 KB
  С одной стороны гроза непосредственный участник действия пьесы с другой стороны символ идеи этого произведения. Гроза играет важную роль в композиции драмы. Почти сразу после этого надвигается гроза...
30629. Стихотворение Г.Р. Державина «Река времен в своем стремленье…». Восприятие, истолкование, оценка. Выразительное чтение наизусть 17.09 KB
  А если что и остаётся Чрез звуки лиры и трубы То вечности жерлом пожрётся И общей не уйдёт судьбы. Автор размышляет о вечности о том что абсолютно все человеческие дела и стремленья рано или поздно будут забыты. Экспрессия стихотворения создается концентрацией метафор река времён пропасть забвенья жерло вечности и фонетической организацией повтор [р] определяет напряженную тональность восьмистишия; последовательность ударных гласных в третьей и предпоследней строках о о э э о о. В стихотворении 2 образа: образы времени и вечности.
30630. «Диалектика души» героев романа Л.Н. Толстого «Война и мир» (на примере одного из персонажей по выбору экзаменуемого) 13.54 KB
  Толстой известен не только как гениальный писатель но и как удивительно глубокий и тонкий психолог. Лев Толстой делает акцент на искренности детской доверчивости доброте и чистоте помыслов своего героя. Толстой замечает: повиновение даже не представлялось ему добродетелью а счастьем. Толстой подчеркивает оптический самообман героя отчужденного от повседневной жизни: в обыденном он не способен рассмотреть великое и бесконечное видит только одно ограниченное мелкое житейское бессмысленное.
30631. Диалог времен и культур в стихотворении О.Э. Мандельштама «За гремучую доблесть грядущих веков…» 14.23 KB
  В своем творчестве поэт опирается на богатые традиции мировой культуры включая в свои произведения идеи и образы художников разных эпох и разных народов события многовековой давности и нетленного искусства. Поэт пишет в первом четверостишии:За гремучую доблесть грядущих вековЗа высокое племя людейЯ лишился и чаши на пире отцовИ веселья и чести своей. Жестокость этого выбора поэт выражает в эпитете векволкодав:Мне на плечи кидается векволкодавНо не волк я по крови своей. Поэтому лирический герой решает уйти от этого общества.
30632. Духовный облик любимых героев Л.Н. Толстого в романе «Война и мир» 14.35 KB
  В романе Война и мир Толстой очень четко разделяет героев на любимых нелюбимых и тех к кому он достаточно равнодушен.Толстой использует весь арсенал художественных средств и приемов позволяющих воссоздать сложную картину внутреннего мира героев диалектику души. Изображая главных героев писатель создает как бы ряд моментальных рентгеновских снимков их души.
30633. Евангельские мотивы в романе М. А. Булгакова «Мастер и Маргарита» 15.42 KB
  Евангельские истории художественно преображены Булгаковым в главах представляющих собою роман в романе произведение мастера о Понтии Пилате и Иешуа ГаНоцри. Многие из них измененные имена Нового и Ветхого Завета: Иешуа Понтий Пилат Иуда Марк Аврелий Кот Бегемот имеет параллель своего имени в Библии Азазелло падший ангел в Ветхом завете.Свобода и несвобода в философском аспекте поставлена в спорах Иешуа и ГаНоцри с могущественным римским прокуратором Понтием Пилатом в душе которого происходит борьба человеческого и...