Кіріспе
Тіл аудармашысы, мысалы, компилятор немесе интерпретатор қолданатын деректер құрылымы. Компьютер ғылымында символдар кестесі – тіл аудармашысы (мысалы, компилятор немесе интерпретатор) қолданатын деректер құрылымы, онда бағдарламаның бастапқы кодындағы әрбір идентификатор (немесе символ), тұрақты, процедура және функция оның жариялануына немесе бастапқы кодтағы пайда болуына қатысты ақпаратпен байланыстырылады. Яғни, символдар кестесінің жазбалары сәйкес символға қатысты ақпаратты сақтайды.
In computer science, a symbol table is a data structure used by a language translator such as a compiler or interpreter, where each identifier (or symbol), constant, procedure and function in a program's source code is associated with information relating to its declaration or appearance in the source. In other words, the entries of a symbol table store the information related to the entry's corresponding symbol.
Өмірбаян
Символдар кестесі аударма процесінде ғана жадта сақталуы мүмкін, немесе ол аударма нәтижесіне, мысалы, кейінірек қолдану үшін ABI объектілік файлына кіріктірілуі мүмкін. Мысалы, ол интерактивті түзету сеансы барысында, немесе бағдарлама орындалған кезде немесе одан кейін диагностикалық есеп дайындау үшін қолданылуы мүмкін.
Сипаттама
Аудармашы және аралық өрнек (IR) қолданатын символдар кестесінде міндетті түрде символдың атауы мен оның орны немесе мекенжайы болады. Қайта орналастыру (relocatability) тұжырымдамасы бар платформаға бағытталған компилятор үшін, ол қайта орналастыру атрибуттарын (абсолютті, қайта орналастырылатын және т.б.) және қайта орналастырылатын символдар үшін қажетті қайта орналастыру туралы ақпаратты да қамтиды. Жоғары деңгейлі бағдарламалау тілдерінің символдар кестелері символдың түрін: жол, бүтін сан, қалқыма нүкте және т.б., оның мөлшерін, өлшемдерін және шектерін сақтауы мүмкін. Бұл ақпараттың бәрі шығыс файлына енгізілмейді, бірақ түзету жұмыстарында пайдалану үшін берілуі мүмкін. Көп жағдайда символдың өзара сілтеме ақпараты символдар кестесімен бірге сақталады немесе оған байланысты болады. Көптеген компиляторлар аударманың соңында символдар кестесі мен өзара сілтеме тізімдерінде осы ақпараттың бір бөлігін немесе барлығын басып шығарады.
Іске асыру
Кестелерді іске асыру үшін көптеген деректер құрылымдары қол жетімді. Ағаштар, сызықтық тізімдер және өздігінен ұйымдастырылатын тізімдер символдар кестесін іске асыру үшін пайдаланылуы мүмкін. Символдар кестесіне компилятордың көптеген кезеңдері кіреді, лексикалық талдаудан басталып, оңтайландырумен аяқталады. Компилятор барлық символдар үшін бір үлкен символдар кестесін пайдалана алады немесе әртүрлі ауқымдар үшін бөлек немесе иерархиялық символдар кестелерін пайдалана алады. Мысалы, Algol немесе PL/I сияқты ауқымды тілде "p" символы бірнеше процедурада, мүмкін, әртүрлі атрибуттармен бөлек жариялануы мүмкін. Әрбір жариялаудың ауқымы – бағдарламаның сол бөлігі, онда "p" сілтемесі осы жариялауға қатысты болады. Әрбір жариялау бірегей идентификатор "p" болып табылады. Символдар кестесі әртүрлі "p" сілтемелерін ажыратудың қандай да бір жоbына ие болуы керек. Символдар кестелерін іске асыру үшін қолданылатын ең көп таралған деректер құрылымы – хэш-кесте. Хэш-кестедегі іздеу уақыты кестеде сақталған элементтер санына тәуелсіз болғандықтан, ол көптеген элементтер үшін тиімді. Бұл хэш кілтін есептеуге классификацияны қосу арқылы кестелік форматтағы литералдарды жіктеуді де жеңілдетеді. Лексикалық талдаушы уақытының көп бөлігін символдар кестесін іздеуге жұмсайтындықтан, бұл операция компилятордың жалпы жылдамдығына маңызды әсер етеді. Символдар кестесі жазбаларды мүмкіндігінше жылдам табуға мүмкіндік беретіндей етіп ұйымдастырылуы тиіс. Символдар кестесін ұйымдастыру үшін әдетте хэш-кестелер қолданылады, онда кілт сөз немесе идентификатор массивтің индексін алу үшін хэштелді. Хэш-кестеде қақтығыстар болмай қоймайды, оларды басқарудың ең көп қолданылатын тәсілі – синонимді кестедегі келесі бос орынға сақтау.
A common data structure used to implement symbol tables is the hash table. The time for searching in hash tables is independent of the number of elements stored in the table, so it is efficient for a large number of elements. It also simplifies the classification of literals in tabular format by including the classification in calculation of the hash key. As the lexical analyser spends a great proportion of its time looking up the symbol table, this activity has a crucial effect on the overall speed of the compiler. A symbol table must be organised in such a way that entries can be found as quickly as possible. Hash tables are usually used to organise a symbol table, where the keyword or identifier is 'hashed' to produce an array subscript. Collisions are inevitable in a hash table, and a common way of handling them is to store the synonym in the next available free space in the table.
Қолданбалар
Объект файлында ол құрамындағы сырттан көрінетін идентификаторлардың символдар кестесі болады. Әр түрлі объект файлдарын байланыстыру кезінде, байланыстырушы осы символ сілтемелерін анықтап, шешеді. Әдетте, барлық анықталмаған сыртқы символдар бір немесе бірнеше объект кітапханаларында ізделеді. Егер осы символды анықтайтын модуль табылса, ол бірінші объект файлымен бірге байланыстырылады және кез келген анықталмаған сыртқы идентификаторлар іздеу тізіміне қосылады. Бұл процесс барлық сыртқы сілтемелер шешілгенге дейін жалғасады. Егер процесс соңында бір немесе бірнеше символ шешілмеген болып қалса, ол қате болып саналады. Орындалатын файлды кері инжинирингтеу кезінде көптеген құралдар жаһандық айнымалылар мен белгілі функцияларға тағайындалған мекенжайларды тексеру үшін символдар кестесіне жүгінеді. Егер символдар кестесі орындалатын файлға айналдырылғанға дейін жойылған немесе тазартылған болса, құралдар мекенжайларды анықтауды немесе бағдарлама туралы ақпарат алуды қиындатады.
Мысал: Python символдар кестесі
Python бағдарламалау тілі символдар кестелерін жасау және өңдеу үшін кең мүмкіндіктерді ұсынады. Сұрау арқылы алуға болатын қасиеттерге символдың еркін айнымалы немесе байланыстырылған айнымалы екендігі, оның блоктық немесе жаһандық ауқымы, импортталғандығы және ол қай атау кеңістігіне жататындығы жатады.
Мысал: Динамикалық символдар кестесі
Кейбір бағдарламалау тілдері символдар кестесін орындау барысында манипуляциялауға мүмкіндік береді, соның арқасында символдарды кез келген уақытта қосуға болады. Racket мұндай тілдің мысалы. LISP және Scheme бағдарламалау тілдері әрбір символға кез келген, жалпылама қасиеттерді тағайындауға рұқсат береді. Prolog бағдарламалау тілі, негізінен, символдар кестесін манипуляциялау тілі болып табылады; символдар атомдар деп аталады, және символдар арасындағы қатынастарды логикалық тұрғыдан қарастыруға болады. Сол сияқты, OpenCog та динамикалық символдар кестесін ұсынады, ол атомдық кеңістік деп аталады және білімді ұсыну үшін қолданылады.