7 Организиране на таблици със символи - StudIzba
7. Лекция: Организиране на таблици със символи Тази глава обсъжда организацията на таблици със символи. Обсъдени са някои основни начини за организиране на таблици със символи в компилатора: таблици с идентификатори, справочни таблици, двоични дървета и изпълнение на структурата на блока. Има и примери за програмен код и графична интерпретация на таблици със символи и идентификатори.
По време на работа компилаторът съхранява информация за програмни обекти в специални таблици със символи. Обикновено информацията за всеки обект се състои от два основни елемента: името на обекта и описанието на обекта. Информацията за програмните обекти трябва да бъде организирана по такъв начин, че нейното търсене да е възможно най-бързо, а необходимата памет да е възможно най-малка.
Освен това от страна на езика за програмиране може да има допълнителни изисквания за организацията на информацията. Имената могат да бъдат обхванати. Например, полето за запис трябва да е уникално в рамките на контур (или ниво на контур), но може да бъде същото като името на обект извън записа (или друго ниво на запис). В същото време името на полето може да бъде отворено от оператора за добавяне и тогава може да възникне конфликт на имена (или неяснота при тълкуването на името). Ако езикът има блокова структура, тогава е необходимо да се осигури такъв начин за съхраняване на информация, за да се поддържа, първо, механизмът за видимост на блока и второ, за да се освободи ефективно паметта при излизане от блока. В някои езици (например Ada) могат да се виждат едновременно няколко обекта с едно и също име (в един блок), в други тази ситуация е неприемлива.
Ще разгледаме някои от основните начини за организиране на таблици със символи в компилатора: таблици за идентичност, справочни таблици, двоични дървета и изпълнение на структурата на блока.
Както вече споменахме, информацията за даден обект обикновено може да бъде разделена на две части: име (идентификатор) и описание. Ако дължината на идентификатора е ограничена (или името се идентифицира от ограничения брой първи символи на идентификатора), тогава таблицата със символи може да бъде организирана като обикновен масив от низове с фиксирана дължина, както е показано на фиг. 7.1. Някои входове може да са заети, някои да са безплатни.
Ясно е, че първо, размерът на масива не трябва да бъде по-малък от броя на идентификаторите, които действително могат да се появят в програмата (в противен случай се получава препълване на таблица); второ, като правило потенциалният брой различни идентификатори е значително по-голям от размера на таблицата.