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


 

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

2408. Исследование нелинейной автономной двухкомпонентной системы с дискретным временем 1.18 MB
  Из проведенного анализа двухкомпонентной нелинейной автономной системы видно, что процессы, наблюдаемые в таких системах могут быть весьма разнообразными. Так в системе возможны периодические и хаотические колебания.
2409. Экономика как наука изучающая отношения в сфере производства 512.57 KB
  Экономика – совокупность отношений между людьми в сфере производства, распределения, обмена и потребления продуктов труда, соответствующая данной степени развития общества. Воспроизводство – неповторимо повторяющиеся процессы производства, а также распределения, обмена и потребления.
2410. Основы физики. Теория и практика 307.77 KB
  Закон сохранения заряда. Закон Кулона. Диэлектрическая проницаемость вещества. Применение теоремы Гаусса к расчёту некоторых электрических полей в вакууме. Проводники в электрическом поле. Распределение зарядов в проводнике. Закон Джоуля-Ленца в интегральной и дифференциальной формах. Магнитный момент кругового тока. Закон Ампера.
2411. Особенности системы автоматизированного проектирования 101.5 KB
  Неавтоматизированное проектирование - проектирование осуществляется человеком; автоматизированное проектирование, при котором отдельные этапы или задачи осуществляются взаимодействием человека и ЭВМ, автоматическое проектирование, при котором все этапы и задачи осуществляются ЭВМ без участия человека.
2412. Иновационные информационные технологии 96.36 KB
  Факторы, оказывающие сдерживающее влияние на процесс становления рынка программных продуктов. Технология ASP. Объекты ADO. Пакетная модификация. Перемещение между записями в результирующем множестве ADO. Специальные значения свойства ADO Recordset.
2413. Выбор методом анализа иерархий с помощью MathCAD по 4 видам и 4 признаком. Методы очистки сточных вод 3.72 MB
  Элементы задачи сравниваются попарно по отношению к их воздействию (весу, или интенсивности) на общую для них характеристику. Сравнивая набор составляющих проблемы друг с другом, получается квадратная матрица вида.
2414. Сучасні системи математичної обробки інформації. Система Mathcad. Програмування в середовищі Mathcad 327.72 KB
  Задачі обробки одновимірних та двовимірних масивів. Приклад розв'язування транспортної задачі в середовищі Mathcad. Локальний екстремум. Організація обчислень з розгалуженнями. Локальний оператор присвоєння. Принцип програмування в Mathcad. Панель програмування.
2415. Особенности использования автоматизированных и человекоуправляемых систем научных исследований 1.03 MB
  Научные исследования позволяют выявлять и исследовать неявные качества и закономерности свойственные исследуемым объектам. К таким объектам, наиболее часто относятся определенные системы и процессы. Особый интерес для науки и прикладных задач представляет автоматизация научных исследований, то есть создание автоматизированных систем научных исследований (АСНИ).
2416. Сущность организации и предприятия, их признаки и функции. Понятие экономики предприятия. 217.5 KB
  Экономика предприятия - это дисциплина изучающая, как определённые и ограниченные ресурсы для производства полезной продукции и услуг распределяются и используются в рамках отдельно взятого предприятия.