Виконання дій, пов'язаних з лексемами

Виконання дій в процесі розпізнавання лексем становить для Лексі ¬ тичного аналізатора набагато меншу проблему, ніж визначення меж лек ¬ род.Фактично кінцевий автомат, який лежить в основі лексичного ана ¬ лизатор, повинен мати не тільки вхідний мову, але й вихідний.Він повинен не тільки вміти розпізнати правильну лексему на вході, а й породити пов'язаний ¬ ву з нею послідовність символів на виході, В такій конфігурації ко ¬ нечний автомат перетворюється на кінцевий перетворювач {3, 4, т. 1, 28, 32].Для лексичного аналізатора дії по виявленню лексеми можуть Тракто ¬ тися трохи ширше, ніж тільки породження ланцюжка символів вихідного мови.Він повинен уміти виконувати такі дії, як запис знайденої лексем ¬ ми в таблицю лексем, пошук її в таблиці ідентифікаторів і запис нової лексем ¬ ми в таблицю ідентифікаторів. Набір дій визначається реалізацією ком ¬ пілятора.Зазвичай ці дії виконуються відразу ж при виявленні кінця розпізнається лексеми.

В кінцевому автоматі, що лежить в основі лексичного аналізатора, ці дії можна відобразити досить просто - досить мати можливість з кожним переходом на графі автомата (або у функції переходів автомата) зв'язати ви ¬ нання деякої довільної функції f (q, a),де q - поточний стан автомата,а - поточний вхідний символ.Функція f (q, a) може виконувати будь-які дії, доступні лексичному аналізатору:

□ поміщати нову лексему в таблицю лексем;

□ перевіряти наявність знайденої лексеми в таблиці ідентифікаторів;

1 наведені тут два оператора на мові FORTRAN, що розрізняються тільки на один символ - «> (точка) або«, »(кома), - є не стільки проблему для компілятора, скільки для програміста, оскільки дозволяють допустити дуже непри ¬ ятную і важко виявляємо помилку [6].

□ додавати нову лексему в таблицю ідентифікаторів;

□ видавати повідомлення користувачеві про знайдені помилки та попередження про виявлені неточності в програмі;

□ переривати процес компіляції.

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

Регулярні мови та граматики

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

Регулярні та автоматні граматики Регулярні граматики

До регулярних, як уже було сказано, відносяться два типи граматик: леволіней Цінні та праволінейние.

Леволінейние граматики G (VT, VN, P, S), V = VNuVT можуть мати правила двох видів: А -> By або А - »у, де A, BeVN, yeVT.

У свою чергу, праволінейние граматики G (VT, VN, P, S), V = VNuVT можуть мати правила також двох видів: А уВ або А у, де A, BeVN, yeVT *. Доведено, що ці два класи граматик еквівалентні.Для будь-якого регулярного мови, заданого праволінейной граматикою, може бути побудована леволіней-ная граматика, яка визначає еквівалентний мова;і навпаки - для будь-якого регулярного мови, заданого леволінейной граматикою, може бути побудови ¬ на праволінейная граматика, що задає еквівалентний мову.Різниця між леволінейнимі і праволінейнимі граматиками полягає в основному в тому, в якому порядку будуються пропозиції мови: зліва направо для леволінейних, або справа наліво для праволінейних.Оскільки предло ¬ вання мов програмування будуються, як правило, в порядку зліва напра ¬ во, то надалі в розділі регулярних граматик буде йти мова в першу чергу про леволінейних граматиках.