Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лекції по СПЗ
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2014
Тип роботи:
Конспект лекцій
Предмет:
Системне програмне забезпечення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Кіровоградський національний технічний університет
КОНСПЕКТ ЛЕКЦІЙ
з курсу „Системне програмне забезпечення”
розробив викл. каф. ПЗ
Бісюк В.А.
Кіровоград 2014
Семестр 7-8
Лекція №1 Основи процесу компіляції програмного коду.
Місце компілятора в програмному забезпеченні
Компілятори складають одну з найважливіших частин програмного забезпечення ЕОМ. Це зв'язано з тим, що мови високого рівня стали основним засобом розробки програм. Тільки дуже незначна частина програмного забезпечення, що вимагає особливої ефективності, програмується за допомогою асемблеру. У дійсний час поширені досить багато мов програмування. З іншого боку, постійно зростаюча потреба в нових компіляторах зв'язана з бурхливим розвитком архітектури ЕОМ. Цей розвиток йде по різних напрямках. Удосконалюються старі архітектури як у концептуальному відношенні, так і по окремим, конкретним лініям. Це можна проілюструвати на прикладі мікропроцесора Intel-80X86. Послідовні версії цього мікропроцесора 8086, 80186, 80286, 80386, 80486, 80586, Pentium і т.д. відрізняються не тільки технічними характеристиками, але і, що більш важливо, новими можливостями і, виходить, зміною (розширенням) системи команд. Природно, це вимагає нових компіляторів (чи модифікації старих). .компілятори ля багатьох мов програмування. Тут необхідно також відзначити, що нові архітектури вимагають розробки зовсім нових підходів до створення компіляторів, так що поряд із власне розробкою компіляторів ведеться і велика наукова праця по створенню нових методів трансляції.
Структура компилятора
На фазі лексичного аналізу (ЛА) вхідна програма, яка представляє собою потік символів, розбивається на лексеми - слова відповідно до визначень мови. Основним формалізмом, що лежить в основі реалізації лексичних аналізаторів, є кінцеві автомати і регулярні вираження. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, викликувана синтаксичним аналізатором за черговою лексемою, або як повний прохід, результатом якого є файл лексем. У процесі виділення лексем ЛА може як самостійно будувати таблиці імен і констант, так і видавати значення для кожної лексеми при черговому звертанні до нього. У цьому випадку таблиця імен будується в наступних фазах (наприклад, у процесі синтаксичного аналізу.
На етапі ЛА виявляються деякі (найпростіші) помилки (неприпустимі символи, неправильний запис чисел, ідентифікаторів і ін.). Основна задача синтаксичного аналізу - розбір структури програми. Як правило, під структурою розуміється дерево, відповідне розбору в контекстно-вільній граматиці мови. В даний час найчастіше використовується або LL(1)-аналіз (і його варіант - рекурсивний спуск), або LR(1)-аналіз і його варіанти (LR(0), SLR(1), LALR(1) і інші). Рекурсивний спуск частіше використовується при ручному програмуванні синтаксичного аналізатора, LR(1) - при використанні систем автоматизації побудови синтаксичних аналізаторів. Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблицю імен. У процесі синтаксичного аналізу також виявляються помилки, зв'язані зі структурою програми. На етапі контекстного аналізу виявляються залежності між частинами програми, що не можуть бути описані контекстно- вільним синтаксисом. Це в основному зв'язку "опис- використання", зокрема аналіз типів об'єктів, аналіз областей видимості, відповідність параметрів, мітки й інші. У процесі контекстного аналізу будується таблиця символів, яку можна розглядати як таблицю імен, поповнену інформацією про описи (властивостях) об'єктів. Основним формалізмом, що використовується при контекстному аналізі, є атрибутные граматики. Результатом роботи фази контекстного аналізу є атрибутированное дерево програми. Інформація про об'єкти може бути як розосереджена в самім дереві, так і зосереджена в окремих таблицях символів. У процесі контекстного аналізу також можуть бути виявлені помилки, зв'язані з неправильним
Рисунок 1.1 – Структура компілятору
використанням об'єктів. Потім програма може бути переведена у внутрішнє представлення. Це робиться для цілей оптимізації і/чи зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати стерпний компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. У якості внутрішнього представлення може використовуватися префиксний чи постфиксний запис, орієнтований граф, трійки, четвірки й інші. Фаз оптимізації може бути кілька. Оптимізації звичайно поділяють на машинно-залежні і машинно-незалежні, локальні і глобальні. Частина машинно-залежної оптимізації виконується на фазі генерації коду. Глобальна оптимізація намагається прийняти в увагу структуру всієї програми, локальна - тільки невеликих її фрагментів. Глобальна оптимізація ґрунтується на глобальному потоковий аналізі, що виконується на графі програми і представляє власне кажучи перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як межпроцедурный аналіз, межмодульный аналіз, аналіз областей життя перемінних і т.д. Нарешті, генерація коду - остання фаза трансляції. Результатом її є або ассемблерный модуль, або об'єктний (чи завантажувальний) модуль. У процесі генерації коду можуть виконуватися деякі локальні оптимізації, такі як розподіл регістрів, вибір довгих чи коротких переходів, облік вартості команд при виборі конкретної послідовності команд. Для генерації коду розроблені різні методи, такі як таблиці рішень, зіставлення зразків, що включає динамічне програмування, різні синтаксичні методи. Звичайно, ті чи інші фази транслятора можуть бути або відсутні зовсім, або поєднуватися. У найпростішому випадку однопрохідного транслятора немає явної фази генерації проміжного представлення й оптимізації, інші фази об'єднані в одну, причому немає і явно побудованого синтаксичного дерева.
Лекція №2-3
Мови і їх уявлення
Алфавіти, ланцюжки та мови
Алфавіт, або словник - це кінцева множина символів. Для позначення символів ми будемо користуватися цифрами, латинськими літерами та спеціальними літерами типу #, $.
Нехай V - алфавіт. Ланцюжок в алфавіті V - це будь-який рядок кінцевої довжини, складена з символів алфавіту V. Синонімом ланцюжка є пропозиція, рядок і слово. Порожній ланцюжок (позначається e) - це ланцюжок, в яку не входить жоден символ.
Конкатенацією ланцюжків x і y називається ланцюжок xy. Зауважимо, що xe = ex = x для будь ланцюжка x.
Нехай x, y, z - довільні ланцюжки в деякому алфавіті. Ланцюжок y називається подцепочкой ланцюжка xyz. Ланцюжки x і y називаються, відповідно, префіксом і суфіксом ланцюжка xy. Зауважимо, що будь префікс або суфікс ланцюжка є подцепочкой цього ланцюжка. Крім того, порожній ланцюжок є префіксом, суфіксом і подцепочкой для будь ланцюжка.
Приклад 2.1. Для ланцюжка abbba префіксом є будь-яка ланцюжок з множинаі L1 = {e, a, ab, abb, abbb, abbba}, суфіксом є будь-яка ланцюжок з множинаі L2 = {e, a, ba, bba, bbba, abbba}, підланцюжком є будь-яка ланцюжок з множинаі L1 L2.
Довжиною ланцюжка w (позначається | w |) називається число символів в ній. Наприклад, | abababa | = 7, а | e | = 0.
Мова в алфавіті V - це деяка множина ланцюжків в алфавіті V.
Приклад 2.2. Нехай дано алфавіт V = {a, b}. Ось деякі мови в алфавіті V:
L1 = - порожній мову;
L2 = {e} - мова, що містить тільки порожню ланцюжок
(Зауважимо, що L1 і L2 - різні мови);
L3 = {e, a, b, aa, ab, ba, bb} - мова, що містить ланцюжки з a і b, довжина яких не перевершує 2;
L4 - мова, що включає всілякі ланцюжки з a і b, що містять парне число a і парне число b;
L5 = {an2 | n> 0} - мову ланцюжків з a, довжини яких представляють собою квадрати натуральних чисел.
Два останніх мови містять нескінченне число ланцюжків.
Введемо позначення V * для множинаі всіх ланцюжків в алфавіті V, включаючи порожню ланцюжок. Кожна мова в алфавіті V є підмножиною V *. Для позначення множинаі всіх ланцюжків в алфавіті V, крім порожнього ланцюжка, будемо використовувати V +.
Приклад 2.3. Нехай V = {0, 1}. Тоді V * = {e, 0, 1, 00, 01, 10, 11, 000, ...}, V + = {0, 1, 00, 01, 10, 11, 000, ...}.
Введемо деякі операції над мовами.
Нехай L1 і L2 - мови в алфавіті V. Конкатенацією мов L1 і L2 називається мова L1L2 = {xy | x L1, y L2}.
Нехай L - мову в алфавіті V. Ітерацією мови L називається мова L *, який визначається наступним чином:
L0 = {e};
Ln = LLn-1, n 1;
L * = n = 0Ln.
Приклад 2.4. Нехай L1 = {aa, bb} і L2 = {e, a, bb}. Тоді
L1L2 = {aa, bb, aaa, bba, aabb, bbbb}, і
L1 * = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ...}.
Більшість мов, що представляють інтерес, містять нескінченне число ланцюжків. При цьому виникають три важливих питання.
По-перше, як представити мову (тобто специфікувати вхідні в нього ланцюжка)? Якщо мова містить тільки кінцеве множина ланцюжків, відповідь проста. Можна просто перерахувати його ланцюжка. Якщо мова нескінченна, необхідно знайти для неї кінцеве уявлення. Це кінцеве представлення, в свою чергу, буде рядком символів над деякими алфавітом разом з деякою інтерпретацією, що зв'язує це подання з мовою.
По-друге, для будь-якого Чи мови існує кінцеве уявлення? Можна припустити, що відповідь негативна. Ми побачимо, що множина всіх ланцюжків над алфавітом лічильно. Мова - це будь-яке підмножина ланцюжків. З теорії множин відомо, що множина всіх підмножин рахункового множинаі незліченно. Хоча ми і не дали строгого визначення того, що є кінцевим представленням, інтуїтивно зрозуміло, що будь-яке розумне визначення кінцевого уявлення веде тільки до рахункового множинаі кінцевих уявлень, оскільки потрібно мати можливість записати таке кінцеве представлення у вигляді рядка символів кінцевої довжини. Тому мов значно більше, ніж кінцевих уявлень.
По-третє, можна запитати, яка структура тих класів мов, для яких існує кінцеве уявлення?
Представлення мови.
Процедура - це кінцева послідовність інструкцій, які можуть бути механічно виконані. Прикладом може служити машинна програма. Процедура, яка завжди закінчується, називається алгоритмом.
Один із способів подання мови - дати алгоритм, що визначає, чи належить ланцюжок мови. Більш загальний спосіб полягає в тому, щоб дати процедуру, яка зупиняється з відповіддю «так» для ланцюжків, що належать мові, і або зупиняється з відповіддю «ні», або взагалі не зупиняється для ланцюжків, які не належать мові. Кажуть, що така процедура або алгоритм розпізнає мову.
Такий метод являє мову з точки зору розпізнавання. Мова можна також представити методом породження. А саме, можна дати процедуру, яка систематично породжує в певному порядку ланцюжка мови.
Якщо ми можемо розпізнати ланцюжка мови над алфавітом V або за допомогою процедури, або за допомогою алгоритму, то ми можемо і генерувати мову, оскільки ми можемо систематично генерувати всі ланцюжки з V *, перевіряти кожну ланцюжок на приналежність мови та видавати список тільки ланцюжків мови. Але якщо процедура не завжди закінчується при перевірці ланцюжка, ми не зрушимо далі першої ланцюжка, на якій процедура не закінчується. Цю проблему можна обійти, організувавши перевірку таким чином, щоб процедура ніколи не продовжувала перевіряти один ланцюжок нескінченно. Для цього введемо наступну конструкцію.
Припустимо, що V має p символів. Ми можемо розглядати ланцюжки з V * як числа, представлені в базисі p, плюс порожній ланцюжок e. Можна занумерувати ланцюжка в порядку зростання довжини і в «числовому» порядку для ланцюжків однакової довжини. Така нумерація для ланцюжків мови {a, b, c} * наведена на рис. 2.1, а.
Нехай P - процедура для перевірки приналежності ланцюжка мови L. Припустимо, що P може бути представлена дискретними кроками, так що має сенс говорити про i-му кроці процедури для будь даного ланцюжка. Перш ніж дати процедуру перерахування ланцюжків мови L, дамо процедуру нумерації пар позитивних чисел.
Всі впорядковані пари позитивних чисел (x, y) можна відобразити на множина позитивних чисел наступною формулою:
Z=(x+y-1)(x+y-2)/2+y
Пари цілих позитивних чисел можна впорядкувати у відповідності зі значенням z (рис. 2.1, б).
Рисунок 2.1
Тепер можна дати процедуру перерахування ланцюжків L. Нумеруючи впорядковані пари цілих позитивних чисел - (1,1), (2,1), (1,2), (3,1), (2,2), ... . При нумерації пари (i, j) генеруємо i-ю ланцюжок з V * і застосовуємо до ланцюжку першою j кроків процедури P. Як тільки ми визначили, що згенерувала ланцюжок належить L, додаємо ланцюжок до списку елементів L. Якщо ланцюжок i належить L, це буде визначено P за j кроків для деякого кінцевого j. При перерахуванні (i, j) буде згенерована ланцюжок з номером i. Легко бачити, що ця процедура перераховує всі ланцюжки L.
Якщо ми маємо процедуру генерації ланцюжків мови, то ми завжди можемо побудувати процедуру розпізнавання речень мови, але не завжди алгоритм. Для визначення того, чи належить x мові L, просто нумеруючи пропозиції L і порівнюємо x з кожним реченням. Якщо згенеровано x, процедура зупиняється, розпізнавши, що x належить L. Звичайно, якщо x не належить L, процедура ніколи не закінчиться.
Мова, пропозиції якого можуть бути згенеровані процедурою, називається рекурсивно перечислимого. Мова рекурсивно перерахуємо, якщо мається процедура, що розпізнає пропозиції мови. Кажуть, що мова рекурсівен, якщо існує алгоритм для розпізнавання мови. Клас рекурсивних мов є власним підмножиною класу рекурсивно перечислимого мов. Мало того, існують мови, які не є навіть рекурсивно перечислимого.
Лекція №4-5 Граматики.
Формальне визначення граматики. Типи граматик і їх властивості.
Для нас найбільший інтерес представляє одна з систем генерації мов - граматики. Поняття граматики спочатку було формалізовано лінгвістами при вивченні природних мов. Передбачалося, що це може допомогти при їх автоматичної трансляції. Однак, найкращі результати в цьому напрямку досягнуто при описі не природних мов, а мов програмування. Прикладом може служити спосіб опису синтаксису мов програмування за допомогою БНФ - форми Бекуса-Наура.
Визначення. Граматика - це четвірка G = (N, T, P, S), де
N - алфавіт нетермінальних символів;
T - алфавіт термінальних символів, NT =;
P - кінцева множина правил виду, де (NT) * N (NT) *, (NT) *;
SN - початковий символ (або аксіома) граматики.
Ми будемо використовувати великі латинські літери для позначення нетермінальних символів, малі латинські букви з початку алфавіту для позначення термінальних символів, малі латинські букви з кінця алфавіту для позначення ланцюжків з T * і, нарешті, малі грецькі літери для позначення ланцюжків з (NT) *.
Будемо використовувати також скорочений запис A 1 | 2 | ... | n для позначення групи правил A 1, A 2, ..., A n.
Визначимо на множинаі (NT) * бінарне відношення виводимості таким чином: якщо P, то для всіх, (NT) *. Якщо 1 2, то говорять, що ланцюжок 2 безпосередньо виведена з 1.
Ми будемо використовувати також рефлексивно-транзитивне і транзитивне замикання відношення, а також його ступінь k 0 (позначаються відповідно *, + і k). Якщо 1 * 2 (1 +2, 1 k2), то говорять, що ланцюжок 2 виведена (нетривіально виведена, виведена за k кроків) з 1.
Якщо k (k 0), то існує послідовність кроків
де = 0 і = k. Послідовність ланцюжків 0, 1, 2, ..., k в цьому випадку називають виведенням з.
Сентенціальний формою граматики G називається ланцюжок, що виводиться з її початкового символу.
Мовою, породжуваною граматикою G (позначається L (G)), називається множина всіх її термінальних сентенціальних форм, тобто
Граматики G1 і G2 називаються еквівалентними, якщо вони породжують одну й ту саму мову, тобто L (G1) = L (G2).
Приклад 2.5. Граматика G = ({S, B, C}, {a, b, c}, P, S), де
P = {S aSBC, S aBC, CB BC, aB ab, bB bb, bC bc, cC cc}, породжує мову L (G) = {anbncn | n> 0}.
Дійсно, застосовуємо n-1 раз правило 1 і отримуємо an-1S (BC) n-1, потім один раз правило 2 і отримуємо an (BC) n, потім n (n-1) / 2 раз правило 3 і отримуємо anBnCn.
Потім використовуємо правило 4 і отримуємо anbBn-1Cn. Потім застосовуємо n-1 раз правило 5 і отримуємо anbnCn. Потім застосовуємо правило 6 і n - 1 раз правило 7 і отримуємо anbncn. Можна показати, що мова L (G) складається з ланцюжків тільки такого виду.
Приклад 2.6. Розглянемо граматику G = ({S}, {0, 1}, {S 0S1, S 01}, S). Легко бачити, що ланцюжок 000111 L (G), так як існує висновок
Неважко показати, що граматика породжує мову L (G) = {0n1n | n> 0}.
Приклад 2.7. Розглянемо граматику G = ({S, A}, {0, 1}, {S 0S, S 0A, A 1A, A 1}, S). Неважко показати, що граматика породжує мову L (G) = {0n1m | n, m> 0}.
Типи граматик і їх властивості
Розглянемо класифікацію граматик (запропоновану Н. Хомського), засновану на вигляді їх правил.
Визначення. Нехай дана граматика G = (N, T, P, S). Тоді
якщо правила граматики не задовольняють жодним обмеженням, то її називають граматикою типу 0, або граматикою без обмежень.
якщо
кожне правило граматики, крім S e, має вигляд, де | | | |, і
в тому випадку, коли S e P, символ S не зустрічається в правих частинах правил,
то граматику називають граматикою типу 1, або нескороченною.
якщо кожне правило граматики має вигляд A, де AN, (NT) *, то її називають граматикою типу 2, або контекстно-вільною (КС-граматикою).
якщо кожне правило граматики має вигляд або A xB, або A x, де A, BN, x T * то її називають граматикою типу 3, або праволінійною.
Легко бачити, що граматика в прикладі 2.5 - нескороченною, в прикладі 2.6 - контекстно-вільна, в прикладі 2.7 - праволінійна.
Мова, породжуванаграматикою типу i, називають мовою типу i. Мова типу 0 називають також мовою без обмежень, мова типу 1 - контекстно-залежним (КЗ), мова типу 2 - контекстно-вільним (КС), мова типу 3 - праволінейним.
Теорема 2.1. Кожна контекстно-вільна мова може бути породжений неукорачівающей контекстно-вільною граматикою.
Доказ. Нехай L - контекстно-вільна мова. Тоді існує контекстно-вільна граматика G = (N, T, P, S), що породжує L.
Побудуємо нову граматику G '= (N', T, P ', S') таким чином:
1. Якщо в P є правило виду A 0B11 ... Bkk, де k 0, Bi + e для 1 ik, і ні з одного ланцюжка j (0 jk) не виводиться e, то включити в P 'всі правила (крім A e) виду
де Xi - це або Bi, або e.
2. Якщо S + e, то включити в P 'правила S' S, S 'e і покласти N' = N {S '}. В іншому випадку покласти N '= N і S' = S.
Чи породжує граматика порожню ланцюжок можноо встановити наступним простим алгоритмом:
Крок 1. Будуємо множину N_0 = N | N --> e
Крок 2. Будуємо множину N_i = N | N-->α( Ni - 1*
Крок 3. Якщо N_i = N_i-1, перейти до кроку 4, інакше крок 2.
Крок 4. Якщо S -->Ni значить S --> e/
Легко бачити, що G '- неукорачівающая граматика. Можна показати по індукції, що L (G ') = L (G). __
Нехай Ki - клас всіх мов типу i. Доведено, що справедливо наступне (строге) включення:
K3( K2 (K1 (K0.
Зауважимо, що якщо мова породжується деякої граматикою, це не означає, що він не може бути породжений граматикою з більш сильними обмеженнями на правила. Наведений нижче приклад ілюструє цей факт.
Приклад 2.8. Розглянемо граматику G = ({S, A, B}, {0, 1}, {S AB, A 0A, A 0, B 1B, B 1}, S). . Ця граматика є контекстно-вільною. Легко показати, що L(G) = {0n1m|n, m > 0}.
Однак, в прикладі 2.7 наведено праволінейная граматика, що породжує ту ж мову.
Покажемо що існує алгоритм, що дозволяє для довільного КЗ-мови L в алфавіті T, і довільної ланцюжка w T * визначити, чи належить w мові L.
Теорема 2.2. Кожен контекстно-залежний мову є рекурсивним мовою.
Доказ. Нехай L - контекстно-залежний мову. Тоді існує деяка неукорачівающая граматика G = (N, T, P, S), що породжує L.
Нехай w T * і | w | = n. Якщо n = 0, тобто w = e, то приналежність w L перевіряється тривіальним чином. Так що будемо припускати, що n> 0.
Визначимо множина Tm як множина рядків u (N T)+довжини не більше n таких, що висновок S * u має не більше m кроків. Ясно, що T0 = {S}.
Легко показати, що Tm можна отримати з Tm-1 переглядаючи, які рядки з довжиною, меншою або рівною n можна вивести з рядків з Tm-1 застосуванням одного правила, тобто
Якщо S *u и |u| n, то u Tm для деякого m. Якщо з S не виводиться u або | u |> n, то u не належить Tm ні для якого m.
Очевидно, що Tm Tm-1 для всіх m 1. Оскільки Tm залежить тільки від m 1, якщо Tm = Tm-1, то Tm = Tm +1 = Tm +2 = ... . Процедура буде обчислювати T1, T2, T3,. . . поки для деякого m не виявиться Tm = Tm-1. Якщо w не належить Tm, то не належить і L (G), оскільки для j> m виконано Tj = Tm. Якщо w Tm, то S *w.
Покажемо, що існує таке m, що Tm = Tm-1. Оскільки для кожного i 1 справедливо Ti Ti-1, то якщо TiTi-1, то число елементів в Ti принаймні на 1 більше, ніж в Ti-1. Нехай |N T| = k. Тоді число рядків в (N T)+довжини меншою або рівною n одно k + k2 + ... + kn nkn. Тільки ці рядки можуть бути в будь-якому Ti. Значить, Tm = Tm-1 для деякого m nkn. Таким чином, процедура, що обчислює Ti для всіх i 1 до тих пір, поки не будуть знайдені два рівних множинаі, гарантовано закінчується, значить, це алгоритм.
Лекція №6-7 Основи лексичного аналізу.
Основне завдання лексичного аналізу - розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору поділяються на символи, що належать небудь лексемам, і символи, що розділяють лексеми (роздільники). У деяких випадках між лексемами може і не бути роздільників. З іншого боку, в деяких мовах лексеми можуть містити незначущі символи (наприклад, символ пробілу в Фортрані). У Сі розділову значення символів-роздільників може блокуватися («\» в кінці рядка всередині "...").
Зазвичай всі лексеми поділяються на класи. Прикладами таких класів є числа (цілі, вісімкові, шістнадцяткові, дійсні і т.д.), ідентифікатори, рядки. Окремо виділяються ключові слова та символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова - це деякий кінцеве підмножина ідентифікаторів. У деяких мовах (наприклад, ПЛ / 1) сенс лексеми може залежати від її контексту і неможливо провести лексичний аналіз у відриві від синтаксичного.
З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох сортів: для синтаксичного аналізатора, працюючого слідом за лексичним, істотна інформація про послідовності класів лексем, обмежувачів і ключових слів, а для контекстного аналізу, працюючого слідом за синтаксичним, важлива інформація про конкретних значеннях окремих лексем (ідентифікаторів, чисел і т.д.).
Таким чином, загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема (можливо, використовуючи символи-роздільники). Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його безлічі ключових слів.
Якщо виділена лексема є обмежувачем, то він (точніше, певний його ознака) видається як результат лексичного аналізу. Якщо виділена лексема є ключовим словом, то видається ознака відповідного ключового слова. Якщо виділена лексема є ідентифікатором - видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Нарешті, якщо виділена лексема належить якому-небудь з інших класів лексем (наприклад, лексема являє собою число, рядок і т.д.), то видається ознака відповідного класу, а значення лексеми зберігається окремо.
Лексичний аналізатор може бути як самостійною фазою трансляції, так і підпрограмою, що працює за принципом «дай лексему». У першому випадку (рис. 3.1, а) виходом аналізатора є файл лексем, у другому (рис. 3.1, б) лексема видається при кожному зверненні до аналізатора (при цьому, як правило, ознака класу лексеми повертається як результат функції «лексичний аналізатор» , а значення лексеми передається через глобальну змінну). З точки зору обробки значень лексем, аналізатор може або просто видавати значення кожної лексеми, і в цьому випадку побудова таблиць об'єктів (ідентифікаторів, рядків, чисел і т.д.) переноситься на більш пізні фази, або він може самостійно будувати таблиці об'єктів. У цьому випадку в якості значення лексеми видається покажчик на вхід у відповідну таблицю.
Робота лексичного аналізатора задається деяким кінцевим автоматом. Однак, безпосереднє опис кінцевого автомата незручно з практичної точки зору. Тому для завдання лексичного аналізатора, як правило, використовується або регулярний вираз, або праволінейная граматика. Всі три формалізму (кінцевих автоматів, регулярних виразів і праволінейних граматик) мають однакову виразну потужність. Зокрема, за регулярним виразом або праволінейной граматиці можна сконструювати кінцевий автомат, що розпізнає ту ж мову.
Регулярні множини і вирази
Введемо поняття регулярного безлічі, що грає важливу роль в теорії формальних мов.
Регулярне безліч в алфавіті T визначається рекурсивно таким чином:
(Порожня множина) - регулярне безліч в алфавіті T;
{е} - регулярне безліч в алфавіті T (e - порожній ланцюжок);
{а} - регулярне безліч в алфавіті T для кожного a T;
якщо P і Q - регулярні множини в алфавіті T, то регулярними є і безлічі
PQ (об'єднання),
PQ (конкатенація, тобто множину {pq|p P, q Q}),
P* (ітерація: P* = n=0Pn);
ніщо інше не є регулярним безліччю в алфавіті T.
Отже, безліч в алфавіті T регулярно тоді і тільки тоді, коли воно або, або {e}, або {a} для деякого a T, або його можна отримати з цих множин застосуванням кінцевого числа операцій об'єднання, конкатенації й ітерації.
Наведене вище визначення регулярного безлічі дозволяє ввести наступну зручну форму його записи, звану регулярним виразом.
Регулярний вираз у алфавіті T і позначається їм регулярне безліч в алфавіті T визначаються рекурсивно таким чином:
- Регулярний вираз, що позначає безліч;
e - регулярний вираз, що позначає множину {e};
a - регулярний вираз, що позначає множину {a};
якщо p і q - регулярні вирази, що позначають регулярні множини P і Q відповідно, то
(P | q) - регулярний вираз, що позначає регулярне безліч PQ,
(Pq) - регулярний вираз, що позначає регулярне безліч PQ,
(P *) - регулярний вираз, що позначає регулярне безліч P *;
ніщо інше не є регулярним виразом в алфавіті T.
Ми будемо опускати зайві дужки в регулярних виразах, домовившись про те, що операція ітерації має найвищий пріоритет, потім йде операції конкатенації, нарешті, операція об'єднання має найменший пріоритет.
Крім того, ми будемо користуватися записом p + для позначення pp *. Таким чином, запис (a | ((ba) (a *))) еквівалентна a | ba +.
Нарешті, ми будемо використовувати запис L (r) для регулярного безлічі, позначуваного регулярним виразом r.
Приклад 3.1. Кілька прикладів регулярних виразів і позначаються ними регулярних множин:
a (e | a) | b - позначає множину {a, b, aa};
a (a | b) * - позначає безліч всіляких ланцюжків, що складаються з a і b, що починаються з a;
(а | b) * (a | b) (a | b) * - позначає множину всіх непорожніх ланцюжків, що складаються з a і b, тобто множину {a, b} +;
((0 | 1) (0 | 1) (0 | 1)) * - позначає безліч всіх ланцюжків, що складаються з нулів і одиниць, довжини яких діляться на 3.
Ясно, що для кожного регулярного безлічі можна знайти регулярний вираз, що позначає це безліч, і навпаки. Більш того, для кожного регулярного безлічі існує нескінченно багато позначають його регулярних виразів.
Будемо говорити, що регулярні вирази дорівнюють або еквівалентні (=), якщо вони позначають одне і те ж регулярне безліч.
Існує ряд алгебраїчних законів, що дозволяють здійснювати еквівалентну перетворення регулярних виразів.
Лемма. Нехай p, q і r - регулярні вирази. Тоді справедливі наступні співвідношення:
(1)
p|q = q|p;
(7)
pe = ep = p;
(2)
* = e;
(8)
p = p = ;
(3)
p|(q|r) = (p|q)|r;
(9)
p* = p|p*;
(4)
p(qr) = (pq)r;
(10)
(p*)* = p*;
(5)
p(q|r) = pq|pr;
(11)
p|p = p;
(6)
(p|q)r = pr|qr;
(12)
p| = p.
Слідство. Для будь-якого регулярного виразу існує еквівалентне регулярний вираз , яке або є, або не містить у своєму записі .
Надалі будемо розглядати тільки регулярні вирази, що не містять у своєму записі .
При практичному описі лексичних структур буває корисно зіставляти регулярними виразами деякі імена, і посилатися на них по цим іменам. Для визначення таких імен ми будемо використовувати запис вигляду
d1 = r1
d2 = r2
...
dn = rn
де di - різні імена, а кожне ri - регулярний вираз над символами T{d1, d2, ..., di-1}, тобто символами основного алфавіту та раніше певними символами (іменами). Таким чином, для будь-якого ri можна побудувати регулярний вираз над T, повторно замінюючи імена регулярних виразів на позначаються ними регулярні вирази.
Приклад 3.2. Використання імен для регулярних виразів.
Регулярний вираз для безлічі ідентифікаторів.
Letter = a | b | c | ... | x | y | z
Digit = 0 | 1 | ... | 9
Identifier = Letter (Letter | Digit) *
Регулярний вираз для безлічі чисел у десятковому запису.
Digit = 0 | 1 | ... | 9
Integer = Digit +
Fraction =. Integer | e
Exponent
14.05.2018 22:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора