оти служити Деяк внутрішнє представлення програми, зрозуміле компілятору.
На етапі синтезу на підставі внутрішнього представлення програми й ІНФОРМАЦІЇ, что містіться в табліці (таблиця) ідентіфікаторів, породжується текст результуючої програми. Результатом цього етапу є об'єктній код. br/>
7. Призначення й Особливості побудова таблиць ідентіфікаторів
Призначення ї Особливості побудова таблиць ідентіфікаторів
Компілятор повинною мати можлівість зберігаті ВСІ знайдені ідентіфікаторі и зв'язані з ними характеристики на протязі Всього процеса компіляції, щоб мати можлівість використовуват їх на різніх фазах компіляції. p> Для цієї мети у компіляторах Використовують СПЕЦІАЛЬНІ Сховище даніх, назівані таблицю сімволів або таблицю ідентіфікаторів .
Будь-яка таблиця ідентіфікаторів Складається з набору полів, кількість якіх дорівнює числу різніх ідентіфікаторів, знайдення у вхідній Програмі. Кожне поле містіть у Собі повну інформацію про Данії елемент табліці. Компілятор может працювати з однією або декількома таблицями ідентіфікаторів - їхня кількість покладів від реалізації компілятора. p> У таблицях ідентіфікаторів может зберігатіся наступна інформація:
для змінніх:
имя змінної;
тип даніх змінною;
область пам'яті, зв'язана Із змінною;
для констант:
назва Константі (ЯКЩО воно є),
Значення Константі;
тип даніх Константи (ЯКЩО нужно),
для функцій:
имя Функції;
кількість и тіпі формальних аргументів Функції;
тип результату, что повертається;
адреси кодом Функції.
Як правило, КОЖЕН елемент у вхідній Програмі однозначно ідентіфікується своим іменем. Тому компілятору часто доводитися Виконувати поиск на необхідного елемента в табліці ідентіфікаторів по его имени, у тієї годину як процес Заповнення табліці віконуються нечасто - Нові ідентіфікаторі опісуються в Програмі набагато рідше одного, чем Використовують. Звідсі можна сделать Висновок, что табліці ідентіфікаторів повінні буті організовані таким чином, щоб компілятор МАВ можлівість максимально Швидкого поиска потрібного Йому елемента.
Найпростіші методи побудова таблиць ідентіфікаторів
Найпростішій способ організації табліці Полягає в тому, щоб додаваті елєменти в порядку їх надходження. Тоді таблиця ідентіфікаторів буде представляті невпорядкованій масив ІНФОРМАЦІЇ, шкірних комірка Якого буде містіті дані про відповідній елементі табліці.
Поиск потрібного елемента в табліці буде в цьом випадка полягаті в послідовному порівнянні Шуканов елемента з шкірними елементом табліці, пока не буде знайдення Придатний. Тоді, ЯКЩО за одиницю Прийняти годину, затрачуваній компілятором на порівняння двох ЕЛЕМЕНТІВ (як правило, це порівняння рядків), то для табліці, что містіть N ЕЛЕМЕНТІВ, у СЕРЕДНЯ буде Виконання N/2 порівнянь.
Заповнення Такої табліці буде відбуватіся елементарно просто - додаванням нового елемента в ее Кінець, і Час, необхідній на додавання елемента (Тз), не якщо залежаться від числа ЕЛЕМЕНТІВ у табліці N. Альо ЯКЩО N Дуже ровері, то поиск на зажадає значний витрат годині. Такий способ організації таблицю ідентіфікаторів є неефективно. p> Поиск может буті Виконання більш Ефективно, ЯКЩО елєменти табліці впорядковані (відсортовані) в прямому чг зворотнього Алфавітному порядку. Ефективно методом поиска в упорядкованому списку з N ЕЛЕМЕНТІВ є бінарній або логаріфмічній поиск на. Символ, Який Варто знайте, порівнюється з елементом (N + l)/2 всередіні табліці. Если цею елемент НЕ є Шуканов, то ми повінні переглянути Тільки блок ЕЛЕМЕНТІВ, пронумеровані від 1 до (N + l)/2-l, чі блок ЕЛЕМЕНТІВ від (N + l)/2 +1 до N у залежності від того, менше чі больше Шуканов елемент від того, з яким его порівнялі. Потім процес повторюється над потрібнім блоком у два рази Меншем розміру. Так продовжується Доті, поки або елемент не якщо знайдення, або алгоритм перестав дійде до Чергова блоку, что містіть один чг два елєменти (з Якими вже можна віконаті Пряме порівняння Шуканов елемента).
Тому що на кожнім кроці число ЕЛЕМЕНТІВ, что могут містіті Шуканов елемент, скорочується наполовину, то максимальне число порівнянь дорівнює l + log 2 (N).
Недоліком методу є Вимога впорядкування табліці ідентіфікаторів. p> Таким чином, при організації логаріфмічного поиска в табліці ідентіфікаторів ми отрімуємо істотне СКОРОЧЕННЯ годині поиска потрібного елемента за рахунок Збільшення годині на размещения нового елемента в таблиці. Оскількі додавання новіх ЕЛЕМЕНТІВ у Таблицю ідентіфікаторів відбувається істотно рідше одного, чем звертання до них, то цею метод Варто Визнати більш ефективного, чім метод організації невпорядкованої табліці.
8. Призначення й Особливості побудова таблиць ідентіфікаторів
Хеш-функціею F назівається Деяк відображ...
