«Основи побудови трансляторів».

Організація лексичного аналізу.

Зміст.
Вступ.
1.Транслітератор.
2.Граматика та розпізнавачі для лексичного аналізу.
3.Звязок між діаграмою Вірта і кінцевим автоматом.
Висновок.
Список використаної літератури.

Вступ.
Лексичний аналіз - перша фаза процесу трансляції, призначена для групування символів вхідного ланцюжка в більші конструкції, названі лексемами. З кожною лексемою зв'язано два поняття:

клас лексеми, що визначає загальну назву для категорії елементів, що володіють загальними властивостями (наприклад, ідентифікатор, ціле число, рядок символів і т.д.);

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

У принципі, завдання, розв'язувані сканером, можна покласти на синтаксичний аналізатор. Але такий підхід незручний по наступних причинах:

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

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

-Та сама мова програмування може мати різні зовнішні подання елементарних конструкцій. Тому, наявність декількох лексичних аналізаторів, що породжують на виході ту саме безліч лексем, дозволяє не переписувати синтаксичний аналізатор. Написати новий лексичний аналізатор набагато простіше, ніж синтаксичний. Прикладом мови, що має різні вхідні набори символів, є PL/1. Для нього визначені 48-символьний і 60-символьний алфавіти.

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

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

1.Транслітератор.

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

-буква - клас, з яким зіставляється безліч букв, причому необов'язково тільки одного алфавіту;

-цифра - безліч символів, що ставляться до цифр, найчастіше від 0 до 9;

-роздільник - пробіл, переклад рядка, повернення каретки переклад формату;

-ігнорований - може зустрічатися у вхідному потоці, але ігнорується й тому просто відфільтровується з нього (наприклад, невидимий код звукового сигналу й інші аналогічні коди);

-заборонений - символи, що не відносяться до алфавіту мови, але зустрічається у вхідному ланцюжку;

-інші - символи, що не ввійшли в жодну з певних категорій.

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

2.Граматики й розпізнавачі для лексичного аналізу.

Лексичні аналізатори звичайно використовуються для розпізнавання елементарних конструкцій, синтаксичний опис яких можна здійснити із застосуванням праволінійних граматик. Це найбільш простий клас граматик, еквівалентних по потужності детермінованим кінцевим автоматам. Використання праволінійних граматик для побудови автоматів широко висвітлюється в літературі [Ахо78, Льюис]. Простота лексичного аналізу полягає також у тім, що лексеми - це єдині нетермінали, використовувані в ході розпізнавання. Навіть, якщо в граматиці, використовуваної для опису лексем, існують проміжні нетермінали, вони зникають при побудові кінцевого автомата, перетворюючись у його стани. Вхідними символами кінцевого автомата є термінальні символи і їхні класи символів, формовані транслітератором.

3.Зв'язок між діаграмою Вірта й кінцевим автоматом.

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

Кінцевий автомат, еквівалентний діаграмі Вірта, що складається тільки з терміналів, будується в такий спосіб:

- Початкова дуга діаграми перетвориться в початковий стан кінцевого автомата.

- Кінцева дуга діаграми утворить заключний стан кінцевого автомата.

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

-Кінцеві стани діаграми є допустимими станами кінцевого автомата.

-Термінальний символ діаграми Вірта, розташований між дугами, перетвориться у зв'язок між відповідними станами, позначену вхідним символом, рівним цьому терміналу.

-Зв'язки, що забезпечують перехід у допустимі стани, позначаються безліччю символів, що залишилися. Це