- •Визначення меж лексем
- •1 Паралельний метод роботи лексичного аналізатора і синтаксичного зовсім не означає, що вони повинні будуть виконуватися як паралельні взаємодіючі процеси. Такий варіант можливий, але не обов'язковий.
- •Виконання дій, пов'язаних з лексемами
- •Автоматні граматики
- •Перетворення регулярної граматики до автоматному увазі
- •Приклад перетворення регулярної граматики до автоматному увазі
- •Кінцеві автомати Визначення кінцевого автомата
- •Граф переходів кінцевого автомата
- •3.3 Є недетерміновані ка.
- •Перетворення кінцевого автомата до детермінованому увазі
- •Регулярні вирази. Властивості регулярних виразів
- •Рівняння з регулярними коефіцієнтами
- •Властивості регулярних мов Основні властивості регулярних мов
- •Проблеми, розв'язні для регулярних мов
- •Лемма про розростанні для регулярних мов
1 Паралельний метод роботи лексичного аналізатора і синтаксичного зовсім не означає, що вони повинні будуть виконуватися як паралельні взаємодіючі процеси. Такий варіант можливий, але не обов'язковий.
Для більшості мов програмування кордону лексем розпізнаються за заданими термінальним символів. Ці символи - прогалини, знаки операцій, символи коментарів, а також роздільники (коми, крапки з комою і т. п.). Набір таких термінальних символів залежить від синтаксису вхідної мови.Важ ¬ но зазначити, що знаки операцій самі також є лексемами, і необхідно не пропустити їх при розпізнаванні тексту.
|
|
/ |
|
Идентификаторы |
|
Исходная |
|
Лексический |
Таблица |
||
программа |
|
анализ (сканер) |
|
идентификаторов |
|
|
|
|
) |
|
(таблица имен) |
|
Очередная лексема |
А | Обращение ; за лексемой |
|
||
|
|
/ |
|
|
|
|
|
Синтаксический |
|
|
|
|
|
раз |
эор (анализ) |
|
|
|
|
ч |
У |
|
|
Рис. 3.1. Паралельне взаємодія лексичного і синтаксичного аналізаторів
Але для багатьох мов програмування на етапі лексичного аналізу може бути недостатньо інформації для однозначного визначення типу і меж черговий лексеми. Проте навіть і тоді розробники компіляторів прагнуть уникнути паралельної роботи лексичного і синтаксичного аналізаторів.У ряді випадків допомагає принцип вибору з усіх можливих лексем лексеми найбільшої довжини: черговий символ з вхідного потоку даних додається в лексему завжди, коли він може бути туди додано.Як тільки символ не може бути додано до лексему, то вважається, що він є кордоном лексеми і на ¬ чалому наступної лексеми (якщо символ не є порожнім роздільником - пробілом, символом табуляції або переведення рядка, знаком комментария).Такий принцип не завжди дозволяє правильно визначити межі лексем в тому випадку, коли вони не розділені порожніми символами. Наприклад, наведена вище рядок мови С k = 1 +++++ J: буде розбита на лексеми наступним чином: <= -,++++ + j. _ І ет0 розбиття невірне.Лексичний аналізатор, розбираючи рядок з 5 знаків +, двічі вибрав лексему найбільшою можливої довжини - знак операції інкремента (збільшення значення змінної на 1) + +, хоча це неправильно.Компілятор повинен буде видати користувачеві повідомлення про помилки ¬ ке, при тому що правильний варіант розпізнавання цього рядка існує. Розробники компіляторів свідомо йдуть на те, що відтинають деякі правильні, але не цілком читаються варіанти вихідних програм. Спроби -.'Складно лексичний распознаватель неминуче призведуть до необхідності його взаємозв'язку з синтаксичним розбором. Це зажадає організації їх па-заллельной роботи і неминуче знизить ефективність роботи всього компіля ¬ тора.Виниклі накладні витрати ніяк не виправдовуються досягається ефектом - розпізнаванням рядків із сумнівними лексемами. Досить: бязать користувача явно вказати за допомогою прогалин (або інших незнач-лих символів) межі лексем, що значно проще1.
Не для всіх вхідних мов тгекой підхід можливий. Наприклад, для рассмот ¬ програвання вище прикладу з мови FORTRAN неможливо застосувати зазначений метод - різниця між оператором циклу і оператором присвоювання слиш ¬ ком істотна, щоб нею можна було знехтувати.Тут доведеться вдатися До зв'язку з синтаксичним разбором1. У такому випадку доводиться організовувати паралельну роботу лексичного і синтаксичного аналізаторів.Очевидно, що послідовний варіант організації взаємодії лексіче ¬ ського і синтаксичного аналізаторів є більш ефективним, оскільки він не вимагає організації складних механізмів обміну даними і не потребує ¬ ся у повторному прочитанні вже розібраних лексем.Цей метод є і більш простим. Однак не для всіх мов програмування можливо організувати таку взаємодію. Це залежить в основному від синтаксису мови, заданого його граматикою.Більшість сучасних широко поширених мов програмування, таких як С і Pascal, проте, дозволяють побудувати лексичний аналіз по більш простому, послідовному методу.