7 Організація таблиць символів - СтудІзба

7. Лекція: Організація таблиць символівУ цій лекції розглядається організація таблиць символів. Розглядаються деякі основні способи організації таблиць символів у компіляторі: таблиці ідентифікаторів, таблиці розміщення, двійкові дерева та реалізація блокової структури. Наведено також приклади програмного коду та графічну інтерпретацію таблиць символів та ідентифікаторів.

У процесі роботи компілятор зберігає інформацію про об'єкти програми у спеціальних таблицях символів. Як правило, інформація про кожен об'єкт складається з двох основних елементів: імені об'єкта та опису об'єкта. Інформація про об'єкти програми має бути організована таким чином, щоб пошук її був якомога швидше, а необхідна пам'ять якомога менше.

З іншого боку, мови програмування можуть бути додаткові вимоги до організації інформації. Імена можуть мати певну область видимості. Наприклад, поле запису має бути унікальним у межах структури (або рівня структури), але може збігатися з ім'ям об'єкта поза записом (або іншого рівня запису). У той же час ім'я поля може відкриватися оператором приєднання, і тоді може виникнути конфлікт імен (або неоднозначність трактування імені). Якщо мова має блокову структуру, необхідно забезпечити такий спосіб зберігання інформації, щоб, по-перше, підтримувати блоковий механізм видимості, а по-друге - ефективно звільняти пам'ять при виході з блоку. У деяких мовах (наприклад, Аде) одночасно (в одному блоці) можуть бути видимі кілька об'єктів з одним ім'ям, в інших ситуація неприпустима.

Ми розглянемо деякі основні способи організації таблиць символів у компіляторі: таблиці ідентифікаторів,таблиці розміщення, двійкові дерева та реалізацію блокової структури.

Як було зазначено, інформацію про об'єкт зазвичай можна розділити на частини: ім'я (ідентифікатор) і опис. Якщо довжина ідентифікатора обмежена (або ім'я ідентифікується за обмеженим числом перших символів ідентифікатора), таблиця символів може бути організована у вигляді простого масиву рядків фіксованої довжини, як це зображено на рис. 7.1. Деякі входи можуть бути зайняті, деякі – вільні.

Зрозуміло, що, по-перше, розмір масиву має бути не меншим за кількість ідентифікаторів, які можуть реально з'явитися в програмі (інакше виникає переповнення таблиці); по-друге, як правило, потенційна кількість різних ідентифікаторів істотно більша за розмір таблиці.

Зауважимо, що у більшості мов програмування символьне уявлення ідентифікатора може мати довільну довжину. Крім того, різні об'єкти в одній або різних областях видимості можуть мати однакові імена, і немає великого сенсу займати пам'ять для повторного зберігання ідентифікатора. Таким чином, зручне ім'я об'єкта та його опис зберігати окремо. І тут ідентифікатори зберігаються у окремій таблиці - таблиці ідентифікаторів. У таблиці символів зберігається покажчик на відповідний вхід до таблиці ідентифікаторів. Таблицю ідентифікаторів можна організувати, наприклад, як суцільний масив. Ідентифікатор у масиві закінчується спеціальним символом EOS (рис. 7.2). Другий можливий

студізба

таблиць

варіант - як перший символ ідентифікатора масив заноситься його довжина.

Одним із ефективних способів організації таблиці символів є таблиця розміщення (або хеш-таблиця). Пошук у такій таблиці може бутиорганізований методом повторного розміщення. Суть його полягає у наступному.

Таблиця символів є масивом фіксованого розміру N. Ідентифікатори можуть зберігатися як у самій таблиці символів, так і в окремій таблиці ідентифікаторів.

Нехай ми хочемо знайти у таблиці ідентифікатор id. Якщо елемент таблиці з номером h1(id) не заповнений, це означає, що ідентифікатора в таблиці немає. Якщо ж зайнятий, це ще не означає, що ідентифікатор id в таблицю занесений, оскільки (взагалі кажучи) багато ідентифікаторів можуть мати те саме значення функції розстановки. Щоб визначити, чи знайшли ми потрібний ідентифікатор, порівнюємо id з елементом таблиці h1(id). Якщо вони рівні – ідентифікатор знайдено, якщо ні – треба продовжувати пошук далі.

Для продовження пошуку застосовується наступна функція розміщення h3(h2), h4(h3) і т.д. Як правило, hi = h2 для i 2. Аргументом функції h2 є ціле діапазоні [0, N - 1] і може бути влаштована по-різному. Наведемо три варіанти.

  1. h2(i) = (i + 1) mod N. Береться наступний (циклічно) елемент масиву. Цей варіант поганий тим, що зайняті елементи "групуються", утворюють послідовні зайняті ділянки і в межах цієї ділянки пошук стає по-суті лінійним.
  2. h2(i) = (i + k) mod N де k і N взаємно прості. По-суті, це попередній варіант, але елементи накопичуються не в послідовних елементах, а "розносяться".
  3. h2(i) = (a * i + c) mod N - "псевдовипадкова послідовність". Тут c і N повинні бути взаємно прості, b = a-1 кратно p для будь-якого простого p, що є дільником N, b кратно 4, якщо N кратно 4 [6].

Пошук у таблиці розміщення можна описати такою функцією:

void Search(String Id,boolean *Yes, int * Point)