Розділ 2. Лексичний аналіз

Етап лексичної обробки тексту вихідної програми виділяється в окремий етап роботи компілятора, як з методичними цілями, так і з метою скорочення загального часу компіляції програми.

Завдання й функціонування блоку лексичного аналізу

Під лексичним аналізом будемо розуміти процес попередньої обробки вихідної програми, на якому основні лексичні одиниці програми — лексеми: ключові (службові) слова, ідентифікатори, мітки, константи приводяться до єдиного формату й заміняються умовними кодами або посиланнями на відповідні таблиці, а коментарі виключаються з тексту програми.

Виходами лексичного аналізу є потік образів лексем-дескрипторів і таблиці, в останні зберігаються значення виділених у програмі лексем.

Дескриптор — це пари виду: (,), де — це, як правило, числовий код класу лексеми, що означає, що лексема належить одному з кінцевої безлічі класів слів, виділених у мові програмування;

— це може бути або початкова адреса області основної пам’яті, у якій зберігається адреса цієї лексеми, або число, що адресує елемент таблиці, у якій зберігається значення цієї лексеми.

Найпоширенішими класами є: Q ідентифікатори; службові (ключові) слова; роздільники; константи.

У загальному випадку всі виділювані класи є або кінцевими (ключові слова, роздільники й ін.) — класи фіксованих для даної мови програмування слів, або нескінченними або дуже більшими (ідентифікатори, константи, мітки) — класи змінних для даної мови програмування слів.

Із цих позицій коди образів лексем (дескрипторів) з кінцевих класів завжди ті самі в різних програмах для даного компілятора. Коди ж образів лексем з нескінченних класів різні для різних програм і формуються щораз на етапі лексичного аналізу.

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

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

• · метод лінійного списку;
• · метод упорядкованого списку;
• · метод розміщення й інші.

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

Після проведення успішної ідентифікації лексеми формується її образ — дескриптор, він міститься у вихідний потік лексичного аналізатора. У випадку неуспішної ідентифікації формуються повідомлення про помилки в написанні слів програми.

У ході лексичного аналізу можуть виконуватися й інші види лексичного контролю, зокрема, перевіряється парність дужок і інших парних символів.