МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Київський національний університет імені Тараса Шевченка
Факультет кібернетики
МЕТОДТЧНІ РЕКОМЕНДАЦІЇ
Для лабораторного практикуму побудови мовних процесорів
з курсу «Системне програмування»
Київ-2015
Зміст
1. Мови програмування та мовні процесори........................................................................ 3
2. Лексичний аналіз в мовних процесорах........................................................................... 5
2.1 Скінчені автомати............................................................................................................. 6
2.2 Мінімізація детермінованих скінчених автоматів................................................. 8
2.3 Скінчені автомати та праволінійні граматики..................................................... 11
2.4 Регулярні множини та регулярні вирази................................................................. 13
2.5 Польський інверсний запис для регулярних виразів.......................................... 15
2.6 Інтерпретація ПОЛІЗ регулярного виразу.............................................................. 16
2.7 Застосування скінчених автоматів при розробці лексичних аналізаторів.. 16
2.8 Методика програмування лексичних аналізаторів на основі скінчених автоматів....................................................................................................................................... 22
3. Лабораторний практикум побудови лексичних аналізаторів............................... 23
4. Синтаксичний аналіз в мовних процесорах.................................................................. 25
3.1. Магазинні автомати........................................................................................................ 28
3.2. Синтаксичний аналіз без повернення назад.......................................................... 29
3.3. Синтаксичний аналіз на основі 
-граматик................................................... 36
3.4. LL(1)-синтаксичний аналізатор для мови Pascal................................................. 38
3.5. Метод рекурсивного спуску програмування синтаксичних аналізаторів... 40
Ai............................................................................................................................................................. 41
3.6. Побудова LL(k)-синтаксичного аналізатора (k>1)............................................. 45
5. Лабораторний практикум побудови синтаксичних аналізаторів......................... 48
Література............................................................................................................................................ 54
Мови програмування та мовні процесори
При вивченні мов програмування, як правило, виділяють три аспекти:
§ Прагматичний;
§ Семантичний;
§ Синтаксичний.
Прагматичний аспект (прагматика мови програмування) визначає клас задач, на рішення яких орієнтується мова програмування. Як правило, прагматичний аспект менш формалізований в порівнянні з семантичним та синтаксичним аспектами.
З урахуванням на рішення задач певного класу мови програмування можна поділити на процедурні та непроцедурні.
Процедурні мови програмування орієнтовані перш за все на опис (визначення) алгоритмів, тобто по суті використовуються для побудови процедур обробки даних. До таких мов ми відносимо всім відомі мови програмування, такі як Pascal, Fortran, C та ін.
Непроцедурні мови програмування на відміну від процедурних неявно визначають процедури обробки даних. Частіше всього такі мови використовуються для побудови завдань на обробку даних. При цьому, при допомозі інструкцій непроцедурної мови програмування визначається що необхідно зробити з даними і явно не визначається як (при допомозі яких алгоритмів) необхідно розв’язати задачу. До непроцедурних мов програмування ми відносимо командні мови операційних систем, мови управління в пакетах прикладних програм та ін.
Як процедурні, так і непроцедурні мови програмування можуть орієнтуватися як на декілька класів задач, так і конкретну предметну область. В першому випадку ми будемо говорити про універсальні мови програмування (Pascal, Fortran, C), в другому – про спеціалізовані мови програмування (Snobol, Lisp).
Семантичний аспект (семантика мови програмування) визначається шляхом конкретизації базових функцій обробки даних, набору конструкцій управління та методами побудови більш “складних” програм на основі “простих”.
Наприклад, визначивши як базовий тип даних “рядок” ми повинні запропонувати “традиційний” набір функцій обробки таких даних: порівняння рядків, виділення частини рядка, конкатенацію рядків та ін.
Семантика мови програмування має бути визначена формально, інакше в подальшому неможливо буде побудувати відповідний мовний процесор. На сьогодні існують два основних напрямки визначення семантики мов програмування: методи денотаційної семантики та методи операційної семантик. Методи денотаційної семантики базуються на відповідних алгебрах, методи операційної семантики базуються на синтаксичних структурах програм.
Синтаксичний аспект (синтаксис мови програмування) визначає набір синтаксичних конструкцій мови програмування, які використовуються для нотації (запису) семантичних одиниць в програмі. Про синтаксис мови програмування можна сказати як про форму, яка є суть похідною від семантики. Для визначення (опису) синтаксису мови програмування використовуються як механізми, що орієнтовані на синтез, так і механізми, орієнтовані на аналіз. Задачі аналізу та синтезу синтаксичних структур програм – це дуальні задачі. Їх конкретизацію ми будемо розглядати в наступних розділах.
Виходячи з вищенаведеного, щоб побудувати мову програмування потрібно:
- визначити клас (класи) задач, на розв’язок яких орієнтована мова програмування;
- виділити базові типи даних та функції їх обробки, указати конструкції управління в програмах. Побудувати механізми конструювання більш складних програм та структур даних на основі більш простих одиниць;
- визначити синтаксис мови програмування.
Мовні процесори реалізують мови програмування. Точніше, мовний процесор призначений для обробки програм відповідної мови програмування. З точки зору прагматики, мовні процесори діляться на транслятори та інтерпретатори.
Мовний процесор типу транслятор (транслятор) – це програмний комплекс, котрий на вході отримує текст програми на вхідній мові, а на виході видає версію програми на вихідній мові, що називається об’єктною мовою. В більшості випадків як об’єктна мова виступає мова команд деякої обчислювальної машини. Серед трансляторів можна виділити дві програмні системи:
§ компілятори – транслятори з мов програмування високого рівня;
§ асемблери – транслятори машинно-орієнтованих мов програмування.
Мовний процесор типу інтерпретатор (інтерпретатор) – це програмний комплекс, котрий на вході отримує текст програми на вхідній мові та вхідні дані, які в подальшому обробляються програмою, а на виході видає результати обчислень (вихідні дані).
Оскільки транслятори та інтерпретатори реалізують мови програмування, вони мають спільні риси: їх структура досить схожа, в основу їх реалізації покладено спільні теоретичні результати та практичні методи реалізації.
Структура транслятора
| Вхідний текст програми | è | Лексичний аналіз | è | Синтаксичний аналіз | è | Семантичний аналіз | è | Оптимізація проміжного коду | è |
| 
| 
| 
| ||||||
| Бази даних (таблиці) мовного процесора | |||||||||
| |||||||||
| è | Генерація коду | è | Вихідний (об’єктний) код |
Призначення основних компонентів транслятора:
1. Лексичний аналізатор.
Вхід: вхідний текст (послідовність літер) програми.
Вихід: послідовність лексем програми.
Лексема – це ланцюжок літер, що має певний зміст. Всі лексеми мови програмування (їх кількість, як правило, нескінчена) можна розбити на скінчену множину класів. Для більшості мов програмування актуальні наступні класи лексем:
- зарезервовані слова;
- ідентифікатори;
- числові константи (цілі та дійсні числа);
- літерні константи;
- рядкові константи;
- коди операцій;
- коментарі. Коментарі безпосередньо не несуть інформації щодо структури програми. В подальшому вони не використовуються, тобто не передаються синтаксичному аналізатору.
- дужки та інші елементи програми.
2. Синтаксичний аналізатор.
Вхід: послідовність лексем програми.
Вихід: - “Так” + синтаксична структура (синтаксичний терм) програми,
- “Ні” + синтаксичні помилки в програмі.
3. Семантичний аналізатор.
Вхід: Синтаксичний терм програми.
Вихід: - “Так” + семантична структура (семантичний терм) програми,
- “Ні” + семантичні помилки в програмі.
4. Оптимізація проміжного коду.
Вхід: семантичний терм програми.
Вихід: оптимізований семантичний терм програми.
Оптимізація – це еквівалентне перетворення програми на основі певних критеріїв. Серед критеріїв оптимізації можна виділити оптимізацію по пам’яті та оптимізацію по швидкості виконання результуючої програми. В залежності від підходів по оптимізації програми можна розглядати машиннозалежні та машиннонезалежні методи оптимізації. На відміну від машиннонезалежних методів машиннозалежні методи оптимізації враховують архітектурні особливості ЕОМ, наприклад, наявність апаратного стека, наявність вільних регістрів тощо.
5. Генерація об’єктного коду.
Вхід: семантичний терм програми.
Вихід: результуючий (об’єктний) код програми.
