Ноу Інти, лекція, організація таблиць символів
Анотація: У даній лекції розглядається організація таблиць символів. Рассмaтріваются деякі основні способи організації таблиць символів в компіляторі: таблиці ідентифікаторів, таблиці розстановки, двійкові дерева і реалізація блокової структури. Наведено також приклади програмного коду і графічна інтерпретація таблиць символів і ідентифікаторів.
В процесі роботи компілятор зберігає інформацію про об'єкти програми в спеціальних таблицях символів. Як правило, інформація про кожен об'єкт складається з двох основних елементів: імені об'єкта і опису об'єкта. Інформація про об'єкти програми повинна бути організована таким чином, щоб пошук її був по можливості швидше, а необхідна пам'ять по можливості менше.
Крім того, з боку мови програмування можуть бути додаткові вимоги до організації інформації. Імена можуть мати певну область видимості. Наприклад, поле запису повинна бути унікальною в межах структури (або рівня структури), але може збігатися з ім'ям об'єкта поза записи (або іншого рівня запису). У той же час ім'я поля може відкриватися оператором приєднання, і тоді може виникнути конфлікт імен (або неоднозначність в трактуванні імені). Якщо мова має блокову структуру, то необхідно забезпечити такий спосіб зберігання інформації, щоб, по-перше, підтримувати блоковий механізм видимості, а по-друге - ефективно звільняти пам'ять при виході з блоку. У деяких мовах (наприклад, Аді) одночасно (в одному блоці) можуть бути видимі декілька об'єктів з одним ім'ям, в інших така ситуація є неприпустимою.
Ми розглянемо деякі основні способи організації таблиць символів в компіляторі: таблиці ідентифікаторів, таблиці розстановки, двійкові дерева і реалізацію блокової структури.
таблиці ідентифікаторів
Як вже було сказано, інформацію про об'єкт зазвичай можна розділити на дві частини: ім'я (ідентифікатор) і опис. Якщо довжина ідентифікатора обмежена (або ім'я ідентифікується по обмеженому числу перших символів ідентифікатора), то таблиця символів може бути організована у вигляді простого масиву рядків фіксованої довжини, як це зображено на рис. 7.1. Деякі входи можуть бути зайняті, деякі - вільні.
Ясно, що, по-перше, розмір масиву повинен бути не менше числа ідентифікаторів, які можуть реально з'явитися в програмі (в іншому випадку виникає переповнення таблиці); по-друге, як правило, потенційне число різних ідентифікаторів істотно більше розміру таблиці.
варіант - в якості першого символу ідентифікатора в масив заноситься його довжина.
таблиці розстановки
Одним з ефективних способів організації таблиці символів є таблиця розміщення (або хеш-таблиця). Пошук в такій таблиці може бути організований методом повторної розстановки. Суть його полягає в наступному.
Таблиця символів являє собою масив фіксованого розміру N. Ідентифікатори можуть зберігатися як в самій таблиці символів, так і в окремій таблиці ідентифікаторів.
Нехай ми хочемо знайти в таблиці ідентифікатор id. Якщо елемент таблиці з номером h1 (id) не заповнений, то це означає, що ідентифікатора в таблиці немає. Якщо ж зайнятий, то це ще не означає, що ідентифікатор id в таблицю занесений, оскільки (взагалі кажучи) багато ідентифікаторів можуть мати одне і те ж значення функції розстановки. Для того щоб визначити, чи знайшли ми потрібний ідентифікатор, порівнюємо id з елементом таблиці h1 (id). Якщо вони рівні - ідентифікатор знайдений, якщо немає - треба продовжувати пошук далі.
Для продовження пошуку застосовується наступна функція розстановки h3 (h2), h4 (h3) і т.д. Як правило, hi = h2 для i> = 2. Аргументом функції h2 є ціле в діапазоні [0, N - 1] і вона може бути бути влаштована по-різному. Наведемо три варіанти.
- h2 (i) = (i + 1) mod N. Береться наступний (циклічно) елемент масиву. Цей варіант поганий тим, що зайняті елементи "групуються". утворюють послідовні зайняті ділянки і в межах цієї ділянки пошук стає по-суті лінійним.
- h2 (i) = (i + k) mod N. де k і N взаємно прості. По-суті це попередній варіант, але елементи накопичуються не в послідовних елементах, а "розносяться".
- h2 (i) = (a * i + c) mod N - "псевдослучайная послідовність". Тут c і N повинні бути взаємно прості, b = a-1 кратно p для будь-якого простого p. є дільником N. b кратно 4. якщо N кратно 4 [6].
Пошук в таблиці розстановки можна описати наступною функцією:
Функція IdComp (H, Id) порівнює елемент таблиці на вході H з ідентифікатором і виробляє 0. якщо вони рівні. Функція Empty (H) виробляє NULL. якщо вхід H порожній. Функція Search привласнює параметрам Yes і Pointer відповідно наступні значення:
false, NULL - якщо шуканий ідентифікатор не знайдений, причому в таблиці немає вільного місця, і
false, P - якщо шуканий ідентифікатор не знайдений, але в таблиці є вільний вхід P.
Занесення елемента в таблицю можна здійснити наступною функцією: