РЕФЕРАТ НА ТЕМУ: Основи побудови трансляторів - Технічні науки - Реферати - Каталог статей

«Основи побудови трансляторів». Організація лексичного аналізу. Зміст. Вступ. 1.Транслітератор. 2.Граматика та розпізнавачі для лексичного аналізу. 3.Звязок між діаграмою Вірта і кінцевим автоматом. Висновок. Список використаної літератури. Вступ. Лексичний аналіз - перша фаза процесу трансляції, призначена для групування символів вхідного ланцюжка в більші конструкції, названі лексемами. З кожною лексемою зв'язано два поняття: клас лексеми, що визначає загальну назву для категорії елементів, що володіють загальними властивостями (наприклад, ідентифікатор, ціле число, рядок символів і т.д.); значення лексеми, що визначає підрядок символів вхідного ланцюжка, що відповідають розпізнаному класу лексеми. Залежно від класу, значення лексеми може бути перетворене у внутрішнє подання вже на етапі лексичного аналізу. Так, наприклад, чинять із числами, перетворюючи їх у двійкове машинне подання, що забезпечу більше компактне зберігання й перевірку правильності діапазону на ранній стадії аналізу. У принципі, завдання, розв'язувані сканером, можна покласти на синтаксичний аналізатор. Але такий підхід незручний по наступних причинах: - Заміна, ланцюжків символів, що представляють елементарні конструкції мови, робить внутрішньо подання програми більш зручним для подальшого аналізу розпізнавачем. Останній маніпулює не окремими символами, а закінченими елементарними конструкціями, що полегшує їхнє загальне сприйняття й подальший семантичний аналіз. Крім цього, при побудові лексем може здійснюватися найпростіша семантична обробка. Наприклад, перетворення й перевірка числових констант. - Зменшується довжина програми, що надходить у синтаксичний аналізатор, за рахунок усунення з її несуттєвих для подальшого аналізу пробілів, коментарів, ігнорованих символів. Зменшення розміру тексту підвищує продуктивність розпізнавачів, особливо для багато прохідних компіляторів. -Та сама мова програмування може мати різні зовнішні подання елементарних конструкцій. Тому, наявність декількох лексичних аналізаторів, що породжують на виході ту саме безліч лексем, дозволяє не переписувати синтаксичний аналізатор. Написати новий лексичний аналізатор набагато простіше, ніж синтаксичний. Прикладом мови, що має різні вхідні набори символів, є PL/1. Для нього визначені 48-символьний і 60-символьний алфавіти. -Лексичний аналізатор використовує більше прості, у порівнянні із синтаксичним аналізатором, методи розбору. Отже, на тих самих ланцюжках і при виконанні розбору тих самих конструкцій його продуктивність буде вище. - Блок лексичного аналізу природно вписується в ієрархічну структуру компілятора, що теж важливо при системному підході до розробки трансляторів. 1.Транслітератор. Незважаючи на те, що лексичний аналізатор обробляє вхідний ланцюжок, зручніше на його вхід подавати не просто окремі символи, а символи, згруповані по категоріях. Тому, перед лексичним аналізатором здійснюється додаткова обробка, що зіставляє з кожним символом його клас, що дозволяє сканеру маніпулювати єдиним поняттям для цілої групи символів, іноді досить великий. Пристрій, що здійснює зіставлення класу з кожним окремим символом, називається транслітератором. Найбільш типовими класами символів є: -буква - клас, з яким зіставляється безліч букв, причому необов'язково тільки одного алфавіту; -цифра - безліч символів, що ставляться до цифр, найчастіше від 0 до 9; -роздільник - пробіл, переклад рядка, повернення каретки переклад формату; -ігнорований - може зустрічатися у вхідному потоці, але ігнорується й тому просто відфільтровується з нього (наприклад, невидимий код звукового сигналу й інші аналогічні коди); -заборонений - символи, що не відносяться до алфавіту мови, але зустрічається у вхідному ланцюжку; -інші - символи, що не ввійшли в жодну з певних категорій. Пари, клас символу і його значення, надходять на вхід сканера, що вибирає для аналізу той її елемент, що найбільш зручний у цей момент. Наприклад, при аналізі ідентифікатора зручніше маніпулювати поняттям "буква", тоді як при аналізі дійсного числа можна відразу дивитися значення букви "E" або "e", що означає початок порядку. Слід також зазначити, що у всіх подальших міркуваннях будемо вважати, що поняття "буква" і "цифра" є терміналами, як отримані в транслітераторі до початку лексичного аналізу. У попереднім трактуванні ці поняття вважалися нетермінальними символами. 2.Граматики й розпізнавачі для лексичного аналізу. Лексичні аналізатори звичайно використовуються для розпізнавання елементарних конструкцій, синтаксичний опис яких можна здійснити із застосуванням праволінійних граматик. Це найбільш простий клас граматик, еквівалентних по потужності детермінованим кінцевим автоматам. Використання праволінійних граматик для побудови автоматів широко висвітлюється в літературі [Ахо78, Льюис]. Простота лексичного аналізу полягає також у тім, що лексеми - це єдині нетермінали, використовувані в ході розпізнавання. Навіть, якщо в граматиці, використовуваної для опису лексем, існують проміжні нетермінали, вони зникають при побудові кінцевого автомата, перетворюючись у його стани. Вхідними символами кінцевого автомата є термінальні символи і їхні класи символів, формовані транслітератором. 3.Зв'язок між діаграмою Вірта й кінцевим автоматом. Побудова кінцевого автомата можна здійснити також з використанням ряду граматик з лівою рекурсією й діаграм Вірта. На практиці, замість праволінійної граматики, зручніше використовувати діаграми Вірта. Вони набагато наочніше при описі правил. Крім цього, між діаграмами Вірта, що не містять нетерміналів, і кінцевими автоматами існує однозначна відповідність. Практично це два еквівалентних способи подання однієї моделі, що одночасно може служити як механізмом породження, так і механізмом розпізнавання. Кінцевий автомат, еквівалентний діаграмі Вірта, що складається тільки з терміналів, будується в такий спосіб: - Початкова дуга діаграми перетвориться в початковий стан кінцевого автомата. - Кінцева дуга діаграми утворить заключний стан кінцевого автомата. - Виходи окремих дуг, що з'єднують символи, і крапки розгалуження інших дуг діаграми утворять безліч інших станів кінцевого автомата. -Кінцеві стани діаграми є допустимими станами кінцевого автомата. -Термінальний символ діаграми Вірта, розташований між дугами, перетвориться у зв'язок між відповідними станами, позначену вхідним символом, рівним цьому терміналу. -Зв'язки, що забезпечують перехід у допустимі стани, позначаються безліччю символів, що залишилися. Це безліч не перетинається з безліччю символів, що забезпечують інші переходи з поточні в інші стани (позначені як "інші"). Побудова кінцевого автомата відповідно до даних правил можна розглянути на прикладі опису ідентифікатора. Діаграма Вірта для ідентифікатора й отриманий по ній кінцевий автомат наведені на рисунку 5.1 Рисунок 5.1- Перетворення діаграми Вірта в еквівалентний кінцевий автомат Для наочності на дугах відзначені точки, що відповідають станам кінцевого автомата. Вони позначені тими ж номерами, що й стану. Заключний стан відзначений міткою "end". Треба ще раз відзначити, що буква й цифра на діаграмі розглядаються як термінали, тому що ці поняття формуються транслітератором. Діаграми Вірта можуть використовуватися й для того, щоб мінімізувати загальне подання правил, що відповідає методам мінімізації, застосовуваним до кінцевих автоматів. Ця мінімізація здійснюється за рахунок об'єднання однакових підграфів діаграм. Приклад можливої мінімізації поняття "ідентифікатор представлений на рисунку .2 Рисунок 5.2- Мінімізована діаграма Вірта, що задає ідентифікатор Висновок. Слід зазначити, що не завжди мінімізація діаграми Вірта веде до мінімізації відповідні їй кінцевого автомата. Наведений малюнок показує, що, незважаючи на скорочення загального числа символів, розмітка, що відповідає станам кінцевого автомата, залишилася незмінною. Наявність однозначного й легко зрозумілої відповідності між діаграмами Вірта й кінцевими автоматами дозволяє не будувати останні, а переходити до написання програми лексичного аналізатора безпосередньо від діаграм Вирта. Це скорочує технологічний ланцюжок, що зв'язує формальний опис елементів мови програмування і їхню програмну реалізацію. Список_використаної_літератури. 1. Грис Д. Конструювання компіляторів для цифрових обчислювальних машин. 2. Хантер Р. Проектування і конструювання компіляторів. 3. Ахо А., Сети Р., Ульман Дж. Компілятори. Принципи, технології, інструменти. М.: Вид-во «Вільямс», 2001.–768 с. 4. Ахо А., Ульман Дж. Теорія синтаксичного аналізу, перекладу і компіляції. Том 1,2. М., Світ. 5. Льюис Ф., Розенкранц Д., Стирна Р. Теоретичні основи проектування компіляторів. 6. Пратт Т. Мови програмування: розробка і реалізація.
1 2 3 4 5 Категория: Технічні науки \| Добавил: DoceNt (09.12.2014)
Просмотров: 342 \| Рейтинг: 0.0/0

Всего комментариев: 0


Имя *:
Email *:

Код *: