Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лексичний аналіз
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
EMBED Equation.3 Лексичний аналіз
Етап лексичної обробки тексту вхідної програми виділяється у окремий етап роботи компілятора як з методичною метою, так і з метою скорочення загального часу компіляції програми. Це скорочення досягається за рахунок того, що програма користувача, яка на вході компілятора сприймається як неперервна послідовність символів, на етапі лексичної обробки перетворюється до деякого стандартного вигляду, що полегшує подальший аналіз. При цьому використовуються спеціалізовані алгоритми перетворення, теорія побудови, а також аспекти практичного застосування яких розроблені досить ґрунтовно.
Задачі і функціонування лексичного аналізатора
Під лексичним аналізом будемо розуміти процес попередньої обробки вхідної програми, під час якого зчитуються літери вхідної програми і будуються(розпізнаються) основні лексичні одиниці цієї програми − лексеми (символи, слова, атоми). Вибір конструкцій, які будуть виділятись як окремі лексеми, залежить від мови і точки зору розробників компілятора. Наприклад, можна розглядати у ролі лексеми як ціле, так і дійсне число вигляду
< ціле > . < ціле >
або розглядати ціле число як символ, а дійсне − як конструкцію вищого рівня. Зазвичай основними символами є службові слова, ідентифікатори, мітки, константи, одно- або двосимвольні розділювачі. Кожній лексемі будемо ставити у відповідність пару
( тип_лексеми, дані_про_лексему ).
Кожну таку пару будемо називати лексемою-дескриптором.
Отже, входом лексичного аналізатора є потік вхідних літер (рядок), а виходом − потік(послідовність) лексем-дескрипторів.
Тип_лексеми − це зазвичай, числовий або символьний код класу лексеми (синтаксична категорія), який показує, що лексема належить одному із скінченої множини класів слів, виділених у мові програмування. Дані_про лексему − це адреса області або покажчик на адресу області основної пам'яті, де зберігається інформація про дану лексему. Це може бути також індекс елементу таблиці, у якій зберігається значення цієї лексеми.
Кількість класів лексем ( тобто різних видів слів) у мовах програмування може бути різною. Найчастіше зустрічаються такі класи:
ідентифікатори;
службові (ключові) слова;
константи;
розділювачі (можуть бути віднесені до одного класу або декількох класів).
Можуть розглядатись і інші класи. Це обумовлено тою роллю, яку відіграють різні види слів при написанні вхідної програми і перекладі її на машинну програму. При цьому найбажанішим є розбиття всієї множини допустимих у мові слів на класи, що не перетинаються між собою. У цьому випадку лексичний аналіз буде ефективнішим. У загальному випадку всі виділені класи будуть або скінченними (службові слова, розділювачі) − класи фіксованих для даної мови програмування слів, або нескінченними чи дуже великими (ідентифікатори, константи, мітки) − класи змінних для даної мови програмування слів.
Лексеми-дескриптори для слів із скінченних класів завжди однакові у різних програмах для даного компілятора. Дескриптори для слів з нескінченних класів різні для різних програм і формуються щоразу на етапі лексичного аналізу.
Під час лексичного аналізу або паралельно з ним значення лексем із нескінченних класів записуються у відповідні таблиці. Скінченністю таблиць пояснюються обмеження, які існують у мовах програмування щодо довжини і кількості використовуваних у програмах ідентифікаторів і констант. Варто зауважити, що числові константи перед занесенням їх у таблицю можуть перетворюватись із зовнішнього символьного зображення у внутрішній машинний код. Вміст таблиць, а особливо таблиці ідентифікаторів, поповнюється на етапі семантичного аналізу програми і використовується на етапі генерації об'єктної програми.
Отже, лексичний аналізатор − це транслятор з вхідної мови на мову лексем-дескрипторів. Він також усуває несуттєві літери (пробіли, символи табуляції, переходу на новий рядок) і коментарі.
Розглянемо основні ідеї, які лежать у основі побудови лексичного аналізатора, проблеми, які при цьому виникають, і підходи до їх усунення.
Лексичний аналізатор повинен виділяти у тексті вхідної програми послідовність літер, яка вважається лексемою. Ця робота значно полегшується, якщо у тексті програми слова відокремлюються одне від іншого певними розділювачами (наприклад, пробілами). У мовах високого рівня така вимога відсутня. Полегшує роботу також можливість розпізнавання окремих класів слів за входженнями їх першої або останньої літери.
Надалі вважатимемо, що кожна лексема може відокремлюється від інших за допомогою знаків (літер), які самі є лексемами або є першими літерами інших лексем. У випадку, коли лексема складається більше, ніж з однієї літери, зчитування такого знаку буде трактуватись як маркер кінця аналізованої лексеми.
Наприклад,
xxx := abc + 256 * d – cx ;
Після цього (або паралельно з цим) проводиться ідентифікація лексеми. Вона полягає у збиранні лексеми з літер, починаючи з виділеної на попередньому етапі літері, і перевірці правильності запису лексем даного класу.
Ідентифікація правильності лексеми із скінченного класу виконується шляхом порівняння її з еталонним значенням. Основна проблема при цьому − мінімізація часу пошуку еталону. У загальному випадку може знадобитись повний перебір слів даного класу, особливо у випадку, коли виділене слово має помилку. Зменшити час пошуку можна, використовуючи вдалу організацію відповідних класів і ефективні способи пошуку.
Для ідентифікації лексем з нескінченних (дуже великих) класів використовуються спеціальні методи збирання лексем з одночасною перевіркою правильності їх написання. При побудові цих методів широко використовується теорія регулярних мов, граматик і скінченних автоматів.
При успішній ідентифікації значення лексеми з нескінченного класу записується у таблицю лексем даного класу (це може робитись лексичним аналізатором або іншими програмами компілятора). При цьому необхідно перевірити, чи не зберігається вже там значення даної лексеми, тобто потрібно проглядати елементи таблиці. Якщо значення лексеми у таблиці від сутнє, то воно записується у таблицю. Зрозуміло, для прискорення роботи потрібна спеціальна організація таблиць і відповідні ефективні методи роботи з таблицями.
Після проведення успішної ідентифікації лексеми формується дескриптор, який записується у вихідний потік лексичного аналізатора. У випадку неуспіху формується повідомлення про лексичну помилку.
Розглянемо приклад фрагменту програми і можливий варіант організації і вмісту таблиць і вихідного потоку лексичного аналізатора. При цьому використовуються такі числові коди типів лексем:
10 − службове слово;
20 − розділювач;
30 − ідентифікатор;
40 − константа.
Вхід лексичного аналізатора:
program pryclad ;
var x, y, z: real;
begin
x:=5;
y:=6;
z:=5*(x+y);
end;
Внутрішні таблиці компілятора
Таблиця розділювачів Таблиця службових слів
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора