Page 22 - 4761

2.6 Таблиці ідентифікаторів. Організація ТІ

Перевірка правильності генерації коду вимагає знань характеристик змінних,
констант, функцій та інших елементів, які зустрічаються в програмі на вхідній мові (ці
елементи – ідентифікатори). Виділення ідентифікаторів та інших елементів відбувається
на фазі лексичного аналізу. Їхні характеристики визначаються на фазах синтаксичного
розбору, семантичного аналізу і підготовки до генерації коду. Склад можливих
характеристик і методи їх визначення залежать від семантики вхідної мови.
Для того, щоб компілятор мав можливість зберігати всі знайдені ідентифікатори і
їхні характеристики протягом всього періоду компіляції, використовуються ТІ.
Будь-яка ТІ складається з набору полів, кількість яких рівна числу різних
ідентифікаторів, знайдених у вхідній програмі. Кожне поле містить певну інформацію про
даний елемент таблиці.
Компілятор може працювати з однією або декількома ТІ – їхня кількість залежить
від реалізації компілятора.
В ТІ може зберігатися наступна інформація:
 Для змінних:
o Ім’я змінної;
o Тип даних її;
o Область пам’яті, пов’язана зі змінною.
 Для констант:
o Назва (якщо є);
o Значення;
o Тип даних.
 Для функцій:
o Ім’я;
o Кількість і типи формальних аргументів;
o Тип результату;
o Адреса коду функції.
o
Компілятору приходиться виконувати пошук необхідного елемента в таблиці
ідентифікаторів по імені частіше ніж поміщати новий елемент в таблицю, тому що кожен
елемент може бути описаний тільки один раз, а використаний – декілька.
Звідси маємо висновок, що ТІ мають бути організовані таким чином, щоб
компілятор мав можливість максимально швидкого пошуку необхідного йому елемента.

2.7 Методи побудови ТІ

Найпростіший спосіб організації ТІ в тому, щоб додавати елементи в порядку їх
поступлення. Тоді ТІ буде являти собою невпорядкований масив інформації, кожна
комірка якого буде містити дані про відповідний елемент таблиці.
Пошук потрібного елемента буде заключатися в послідовному порівнянні
шуканого елемента з кожним елементом таблиці, поки не буде знайдено потрібний. Тоді,
якщо за одиницю часу прийняти час, який затрачено компілятором на порівняння двох
елементів, то для таблиці, яка містить N елементів, в середньому буде виконано N/2
порівнянь.
Заповнення такої таблиці елементарно просте – додаємо новий елемент в її кінець і
час, потрібний для додавання елемента (Т З) не залежить від числа елементів у таблиці.
Але якщо N дуже велике, то пошук вимагає значних затрат часу.
Час пошуку Т П можна оцінити як Т П=О(N) . Оскільки пошук в ТІ є найбільш часто
виконувана операція, а кількість різних ідентифікаторів досить велика, то такий спосіб
організації ТІ є неефективним.

20