Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
СИНТЕЗ КОМПІЛЯТОРА МОВИ ПРОГРАМУВАННЯ SPL ? Simple Programming Language.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2003
Тип роботи:
Курсова робота
Предмет:
Системне програмне забезпечення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти І науки України
національний університет “Львівська політехніка”
Курсова робота з дисципліни
“Системне програмне забезпечення”
Синтез компілятора мови програмуваннЯ
SPL Simple Programming Language
Львів – 2003
Анотація
Задачею системного програмування, яка вирішується в даному курсовому проекті є розробка компілятора мови програмування високого рівня. Процес проектування передбачає ретельне планування і ціленаправлену розробку, в результаті чого отримується програмний продукт, який супроводжується чіткою документацією і який пройшов усі необхідні випробування.
В пояснювальній записці крім загальнотеоретичних питань по основним методам та засобам конструювання компіляторів, описані мотивації вибору конкретного шляху реалізації та деталізовано сам процес проектування компілтора SPL (Simple Programming Language). Для перевірки на коректність комплекcу виконаних робіт наводяться тестові програми, які демонструють основні можливості мови програмування SPL.
Розроблений компілятор супроводжується інтегрованим середовищем розробника TurboSPL, яке дає можливість значно спростити процес розробки, тестування, відлагодження та редагування програми на мові SPL.
Технічне завдання
Розробляємий компілятор є спрощеним варіантом компілятора мови програмування високого рівня. Лексичні, синтаксичні та семантичні правила компілтора SPL є аналогічними до відповідних правил мов високого рівня, в межах які описуються нижче. Таким чином в курсовому проекті повинно бути реалізовано наступні вимоги строготипізованої мови програмуваня SPL:
Базові типи даних
Передбачається реалізація трьох стандартних типів даних:
boolean, змінні цього типу приймають одне з двох значень true або false;
integer, цілочисельний тип з діапазоном допустимих значень –32768..32767;
real, дійсний тип у відповідності до стандарту IEEE 754.
Вимоги до операцій та виразів
для змінних типу integer передбачено виконання наступних цілочисельних операцій : “+” – додавання; “–” – віднімання; “*” – множення; “/” – ділення, та піднесення до степеня “^”.
для типу real реалізовано арифметичні операції аналогічні до цілочисельного типу;
змінним логічного типу boolean дозволено використовувати операцію присвоєння іншої однотипної змінної або константи, та операції алгебри логіки: “–” - інверсія, “+” – логічне АБО, “*” – логічне І, “^” – виключне АБО.
Ввід-вивід
Засоби вводу-виводу забезпечуються наступними процедурами:
input <список ідентифікаторів> – дає можливість вводити значення змінним;
output <ідентифікаторів> – виводить на екран значення змінних та констант;
Реалізація циклічних та умовних конструкцій
Забезпечення підтримки стандартного циклу FOR з можливістю вкладених циклів.
умовні конструкції визначаються у формі IF … THEN GOTO <мітка>.
5. Безумовний перехід GOTO <мітка>.
Інші аспекти лексики, синтаксису та семантики мови програмування SPL уточнюються по ходу проектування.
Зміст
1. Вступ
Одними з ключових задач системного програмування являються задачі пов’язані з побудовою трансляторів.
Транслятор – це програма, яка переводить вхідну програму на вхідній мові програмування в еквівалентну їй вихідну програму на результуючій мові. Вихідними даними для для роботи транслятора являється текст вхідної порграми – деяка послідовність конструкцій вхідної мови програмування. Вихідними продуктом транслятора являється текст результуючої програми. Результуюча програма будується по синтаксичним правилам заданими у вхідній мові, а її зміст визначається семантикою вихідної мови. Важливою вимогою у визначенні транслятора являється еквівалентність вхідної і вихідної програм.
Крім поняття “транслятора” широко використовують близьке йому по змісту поняття “компілятора”.
Компілятор – це транслятор, який здійснює перевод вхідної програми в еквівалентну їй об’єктну на мові машинних команд або на мові асемблера. Результуюча програма компілятора називається “об’єктною програмою” або “об’єктним кодом”. Породжена компілятором програма не може безпосередньо виконуватись на комп’ютері, так як вона не прив’язана до конкретних областей пам’яті, де повинні розміщуватися код і дані. Компілятор є найбільш поширеним видом транслятора.
На сучасному рівні розвитку комп’ютерних технологій компілятори являються частиною будь-якої обчислювальної системи. Без їх існування програмування будь-якої прикладної програми було б значно ускладнено, а то і зовсім неможливо.
2. Теоретичні аспекти компіляції
2.1. Мови та способи задання мов
2.1.1. Поняття мови. Формальне визначення мови
В загальному випадку мова – це заданий набір символів і правил, які встановлюють способи комбінації цих символів між собою для записів осмислених текстів. Основою будь-якої природньої або штучної мови являється алфавіт, який визначає набор допустимих символів мови.
Алфавіт – це злічена множина допустимих символів мови. Будемо позначати цю множину символом V. Ланцюжок символів являється ланцюжком над алфавітом V:
(V), якщо в неї входять тільки символи, що належать множині символів V. Для будь-якого алфавіта V пустий ланцюжок може як являтися, так і не являтися ланцюжком (V). Ця умова оговорюється додатково.
Якщо V – деякий алфавіт, то:
V+ – множина всіх ланцюжків над алфавітом V без ;
V* – множина всіх ланцюжків над алфавітом V включаючи ;
Справедливою є рівність: V* = V+ {}.
Мовою L над алфавітом V: L(V) називається деяка злічена підмножина ланцюжків кінцевої довжини із множини всіх ланцюжків над алфавітом V. З цього означення слідує, два висновки: по-перше, множина ланцюжків мови не повинна бути кінцевою; по-друге, хоча кожний ланцюжок символів, що входить в мову, повинен мати кінцеву довжину, ця довжина може бути скільки треба великою і формально ні чим не обмежена.
Усі існуючі мови підпадають під це визначення. Більшість реальних і штучних мов містять безмежну множину ланцюжків. Також в більшості мов довжина ланцюжка ні чим не обмежена. Ланцюжок символів, що належить заданій мові, часто називають реченням мови, а множину ланцюжків символів деякої мови L(V) – множиною речень даної мови.
2.1.2. Cпособи задання мов
Отже, кожна мова – це множина ланцюжків символів над деяким алфавітом. Але крім алфавіта, мова передбачає і задання правил побудови допустимих ланцюжків, оскільки звичайно далеко не всі ланцюжки над заданим алфавітом належать мові. Символи можуть об’єднуватися в слова і лексеми – елементарні конструкції мови, на їх основі будуються речення – більш складні конструкції. І ті і інші в загальному виді являються ланцюжками символів, але передбачають деякі правила побудови. Таким чином, необхідно вказати ці правила, або строго кажучи, задати мову.
Мову можна задати трьома способами:
Перерахуванням всіх допустимих ланцюжків мови.
Вказанням способа породження ланцюжків мови (заданням граматики мови).
Визначення метода розпізнавання ланцюжків мови.
Перший із методів являється чисто формальним і на практиці не застосовується так як більшість мов містять безмежну кількість допустимих ланцюжків і перерахувати їх просто не можливо. Другий спосіб пеердбачає деяке описання правил, за допомогою яких будуються ланцюжки мови. Тоді будь-який ланцюжок побудований за допомогою цих правил із символів алфавіта мови, буде належати заданій мові. Третій спосіб передбачає побудову деякого логічного пристрою (розпізнавача) – автомата, який на вході отримує ланцюжок символів, а на виході видає відповідь – чи належить даний ланцюжок заданій мові чи ні.
2.1.3. Лексика, синтаксис та семантика мови
Говорячи про будь-яку мову, можна виділити його синтаксис та семантику. Крім того, транслятори мають справу також з лексичними конструкціями (лексемами), які задаються лексискою мови.
Синтаксис мови – це набір правил, що визначає допустимі конструкції мови. Синтаксис визначає “форму мови” – задає набір ланцюжків символів, які належать мові. Частіше за све синтаксис мови можна задати у вигляді сторгого набора правил, але повністю це твердження справедливе тільки для чисто формальних мов. Навіть для більшості мов програмування набор заданих синтаксичних конструкцій потребує додаткових пояснень, а синтаксис мов природнього спілкування цілком відповідає загальноприйнятому погляду, що “виключення тільки підтверджують правила”.
Семантика мови – це розділ мови, що визначає значення речень мови. Семантика визначає “зміст мови” – задає значення для всіх допустимих ланцюжків мови. Семантика для більшості мов визначається неформальними методами. Чисто формальні мови позбавлені будь-якого змісту.
Лексика – це сукупність слів (словарний запас) мови. Слово або лексична одиниця (лексема) мови – це конструкція, яка складається з елементів алфавіту мови і не містить в собі інших конструкцій. Інакше кажучи, лексична одиниця може містити тільки елементарні символи і не може містити інших лексичних одиниць.
2.1.4. Особливості мов програмування
Мови програмування займають деяку проміжну сходинку між формальними та природніми мовами. З формальними мовами їх об’єднують строгі синтаксичні правила, на основі яких будуються речення мови. Від мов природнього спілкування в мови програмування перейшли лексичні одиниці, які представляють основні ключові слова. Крім того, із алгебри мови програмування перейняли основні позначення математичних операцій, що також робить їх більш зрозумілими для людини.
Для задання мови програмування слід вирішити три питання:
Визначити множину допустимих слів мови.
Визначити множину правильних програм мови.
Задати зміт для кожної правидбної програми.
Тільки перші два питання повністю або частково вдається вирішити за допомогою теорії формальних мов.
Перше питання вирішується легко. Визначаючи алфавіт мови, ми автоматично визначаємо множину допустимих символів. Для мов програмування алфавіт – це частіше за все той набір символів, які можна ввести з клавіатури. Його основу складає молодша половина таблиці міжнародного кодування символів (таблиці ASCII), до якої добавляють символи національних алфавітів.
Друге питання вирішується в теорії формальних мов тільки частково. Для всіх мов програмування існують правила, що визначають синтаксисмови, але їх не є достатньо для того щоб строго визначити усі можливі конструкції мови. Додаткові обмеження накладаються семантикою мови. Ці обмеження оговорюються в неформальній формі для кожної окремої мови програмування. До таких обмежень можна віднести необхідність попереднього опису змінних і функцій, необхідність відповідності типів змінних і констант у виразах, формальних і фактичних параметрах у визовах функцій і інші.
Звідси слідує, що практично усі мови програмування строго кажучи не являються формальними мовами. І саме тому у всіх трансляторах, крім синтаксичного розбору і аналізу речень мови, додатково пеердбачено семантичний аналіз.
Третє питання в принципі не відноситься до теорії формальних мов, оскільки, так як вже було сказано, такі мови позбавлені будь-якого змісту. Для відповіді на нього необхідно використовувати інші підходи. В якості таких підходів можна вказати наступні:
викласти зміст програми, написаній на мові програмування, на іншій мові, більш зрозумілій тому, кому адресована ця програма;
використовувати для перевірки змісту деяку “ідеальну машину”, яка призначена для виконання програм, написаних на даній мові.
Коментарі в хоршій програмі – це і є викладення її змісту. Побудова блок-схем, а рівно і будь-який інший опис алгоритма програми – це також спосіб викладення змісту програми на іншій мові. Та і документація до програми – також спосіб викладення її змісту. Але усі ці способи орієнтовані на людину, якій вони, звичайно ж, більш зрозумілі. Однак, не існує поки універсального способа перевірки, наскільки опис відповідає програмі.
Машина розуміє тільки одну мову – мову машинних команд. Але викласти програму на мові машинних команд – задача занадто трудоємка для людини, так раз для її вирішення створюються транслятори.
Другий підхід використовується при відладці програми. Оцінку ж результатів виконання програми при відладці виконує людина. Будь-які намагання поручити це діло машині позбавлені змісту поза контекстом розв’язуємої задачі.
2.2. Визначення граматики та способи її задання
2.2.1. Поняття про граматику мови
Граматика – це опис способу побудови конструкцій деякої мови. Іншими словами, це математична система, що визначає мову.
Фактично, визначивши граматику мови, ми вказуємо правила породження ланцюжків символів, які належать даній мові. Таким чином граматика – це генератор ланцюжків мови. Вона відносяться до другого способу визначення мов – породженню ланцюжків символів.
Граматику мови можна описати різними способами. Для багатьох мов (і для синтаксичної частини мов програмування в тому числі) допустимо використання формального використання опису граматики, побудоване на основі системи правил.
Правило – це впорядкована пара ланцюжків символів (,). В правилах дуже важливий порядок ланцюжків, тому їх частіше записують у вигляді (або ::=). Такий запис читається як “ породжує ” або “ по визначенню є ”.
Граматика мови програмування містить правила двух типів: перші (визначають синтаксис конструкції мови) досить легко піддаються формальному опису; другі (визначають семантичні обмеження мови) звичайно викладаються в неформальній формі. Тому будь-який опис мови програмування звичайно складається з двох частин: спочатку викладаються правила побудови синтаксичних конструкцій, а потім на природній мові дається опис семантичних правил. Природна мова зрозуміла людині, користувачу, який буде писати програми на мові програмування; для компілятора семантичні обмеження необхідно викладати у вигляді алгоритмів перевірки правильності програми. Такою перевіркою в компіляторі займається семантичний аналізатор – спеціально розроблена для цього частина компілятора.
Мова задана граматикою G позначається як L(G).
2.2.2. Формальне визначення граматики мови. Форма Бекуса-Наура
Для повного формального визначення граматик, крім правил породження ланцюжків мови необхідно задати також алфавіт мови.
Формально граматика G, визначається як четвірка G(VT, VN, P, S), де
VT – множина термінальних символів;
VN – множина нетермінальних символів VT VN = ;
P – множина правил граматики виду , де V+; V*;
S – цільовий символ граматики S VN.
Множина V = VN VT називається повним алфавітом граматики G.
Розглянемо множину VN і VT. Множина термінальних символів VT містить символи, які входять в алфавіт мови, який породжується граматикою. Як правило, символи з множини VT зустрічаються тільки в ланцюжках правих частин правил, якщо ж вони зустрічаються в лівій частині правил, то повинні також бути і в правій його частині. Множина нетермінальних символів VN містить символи, які визначають слова, поняття, констркції мови. Кожний символ даної множини може зустрічатися в ланцюжках як лівої так і правої частин правил граматик, але він мусить хоча б один раз бути в лівій частині хоча б одного правила. Правила граматик будуються так, щоб в лівій частині кожного правила був хоча б один нетермінальний символ.
Ці дві множини не перетинаються: кожний символ може бути або термінальним або нетермінальним. Ні один символ в алфавіті граматики не може бути нетермінальним і термінальним одночасно. Цільовий символ граматики – це завжди нетермінальний символ.
У множині правил граматики може бути декілька правил, що мають однакові праві частини, виду: 1, 2, … , n. Тоді ці правила об’єднуються разом і записуються у виді: 12 … n. Одному рядку в такому записі відповідає відразу n правил.
Таку форму запису правил граматики називають формою Бекуса-Наура. Форма Бекуса-Наура передбачає, як правило, також, що нетермінальні символи беруться у кутові дужки < >. Іноді знак “” в правилах граматики заміняють на знак “::=” (що характерно для старих монографій), але це всього лиш незначна модифікація форми запису, що не впливає на її суть.
Нижче наводиться приклад граматики для цілих десяткових чисел зі знаком:
G( {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, –, +}, {<число>, <чс>, <цифра>}, Р, <число>)
P:
<число> <чс>+<чс>–<чс>
<чс> <цифра><чс><цифра>
<цифра> 0123456789
Розглянемо складові елементи граматики:
множина термінальних символів VT містить дванадцять елементів; десять десяткових цифр і два знака;
множина нетермінальних символів VN містить три елемента: символи <число>, <чс> і <цифра>;
множина правил містить 15 правил, котрі записані в три рядки (тобто мається тільки три різних правих частини правил);
цільовим символом граматики являється символ <число>.
2.2.3. Принцип рекурсії в правилах граматики
Особливість формальних граматик в тому, що вони дозволяють визначити безкінечну множину ланцюжків мови за допомогою кінцевого набору правил. Наведена вище в прикладі граматика для цілих десяткових чисел зі знаком визначає безкінечну множину цілих чисел за допомогою 15 правил.
Можливість користуватися кінцевим набором правил досягається в такій формі запису граматики за рахунок рекурсивних правил. Рекурсія в правилах граматики виражається в тому, що один із нетермінальних символів визначається сам через себе. Рекурсія може бути безпосередньою (явною) – тоді символ визначається сам через себе в одному правилі, або неявно – тоді те ж саме відбувається через ланцюжок правил.
В розглянутій вище граматиці G безпосередня рекурсія присутня в правилі: <чс><чс><цифра>.
Щоб рекурсія не була безкінечною, для нетермінального символа граматики повинні існувати також і інші правила, які визначають його, минаючи самого себе і позволяють уникниути безкінечного рекурсивного визначення. Такими правилами являються <чс><цифра> - в граматиці G.
Принцип рекурсії – важливе поняття в представленні про формальні граматики. Так або інакше, явно або неявно рекурсія завжди присутня в граматиках будь-яких реальних мов програмування. Саме вона дозволяє будувати безмежну кількість ланцюжків мови, і говорити про їх породження неможливо без розуміння принципа рекурсії. Як правило, в граматиці реальної мови програмування міститься не одне, а ціла множина правил, побудованих за допомогою рекурсії.
2.2.4. Інші способи задання граматик
Форма Бекуса-Наура зручна з формальної точки зору, але не завжди доступний для розуміння спосіб запису формальних граматик. Рекурсивні визначення є зручними для формального аналізу ланцюжків мови, але не зручні з точки зору людини.
Але при створенні мови програмування, важливо, щоб його граматику розуміли не тільки ті, кому належить складати компілятори для даної мови, але і користувачі мови – майбутні розробники програм. Тому існують і інші способи опису правил формальних граматик, які орієнтовані на більшу зрозумілість людині.
Далі розглянемо два найбільш поширених з цих двох способів: запис правил граматики з використанням метасимволів і запис правил граматики в графічному виді.
1. Запис правил граматик з використанням метасимволів
Запис правил граматики з використанням метасимволів передбачає, що в рядку правила граматики можуть зустрічатися спеціальні символи – метасимволи, - які мають особливий зміст і трактуються спеціальним чином. В якості таких мета символів часто виступають наступні символи ( ) (круглі дужки), [ ] (квадратні дужки), { } (фігурні дужки), “,” (кома) і “” (лапки).
Ці метасимволи мають наступний зміст:
круглі дужки означають, що із всіх перерахованих всередині них ланцюжків символів в даному місці правила граматики може стояти тільки один ланцюжок;
квадратні дужки означають, що вказаний в них ланцюжок може зустрічатися, а може і не зустрічатися в даному місці правил граматики;
фігурні дужки означають, що вказаний в середині них ланцюжок не зустрічається в даному місці правила граматики, зустрічається один раз, або скільки завгодно разів;
кома служить для того, щоб розділяти ланцюжки символів всередині круглих дужок;
лапки використовуються в тих випадках, коли один із метасимволів потрібно включити в ланцюжок звичайним чином – тобто коли одна із дужок або кома повинні бути присутніми в ланцюжку символів мови.
Ось як повинні виглядати правила розглянутої вище граматика G, якщо їх записати з використанням метасимволів:
<число> [ (+, –) ] <цифра> {<цифра>}
<цифра> 0123456789
Форма запису правил з використанням метасимволів – це зручний і зрозумілий спосіб представлення правил граматик. Вона в багатьох випадках дозволяє повністю уникнути рекурсії, замінивши її символом ітерайції {} (фігурні дужки).
2. Запис правил граматик в графічному виді
При записі правил в графічному виді вся граматика представляється в формі набора спеціальних чином побудованих діаграм. Ця форма була запропонована при описанні граматики мови Pascal.
В такій формі запису кожному нетермінальному символу відповідає діаграма, побудована у вигляді направленого графа. Граф має наступні типи вершин:
точка входа (на діаграмі ні як не позначено, з неї просто починається вхідна дуга графа);
нетермінальний символ (на діаграмі позначається прямокутником, в який вписано позначення символа);
ланцюжок термінальних символів (на діаграмі позначається овалом, кругом, або прямокутником з закругленими краями, всередину якого вписаний ланцюжок);
вузлова точа;
точка вихода (ні як не позначена, в неї просто входить вихідна дуга графа).
Кожна діаграма має має тільки одну точку входа і одну точку вихода, і скільки завгодно вершин інших трьох типів. Вершини з’єднуютсья між собою направленими дугами графа. Із вхідної точки дуги можуть тільки виходить, а у вхідну точку – тільки входить. В інші вершини дуги можуть як входити так і виходити.
Це зручний спосіб описання правил граматик, який оперує образами, а тому орієнтований виключно на людей. Опишемо граматику G за допомогою діаграм:
Число
Доданок
+
0
1
2
3
5
4
6
7
8
9
Цифра
2.3. Розпізнавачі. Задача розбору
Для кожної мови програмування є важливим не тільки вміти побудувати текст програми на цій мові, але і визначити приналежність тексту до даної мови. Саме цю задачу вирішують компілятори в числі інших задач (компілятор повинен не тільки розібрати вихідну програму, а і побудувати їй еквівалентну результуючу програму ) . По відношенню до вихідної програми компілятор виступає як розпізнавач, а людина, яка створила порграму на деякій мові виступає в ролі генератора ланцюжків даної мови.
Розпізнавач – це спеціальний алгоритм, який дозволяє визначити приналежність ланцюжку символів деякій мові. Задача розпізнавача полягає в тому, щоб на основі вихідного ланцюжку дати відповідь, чи належить вона заданій мові чи ні. Розпізнавачі, як було сказано вище представляють собою один із способів задання мови.
В загальному вигляді розпізнавач можно відобразити у вигляді умовної схеми:
a1
a2
an
ПК
Робоча (зовнішня)
пам’ять
Зчитуюча головка
пам’ять
Вхідний ланцюг символів
Слід зауважити, що представлений рисунок усього лиш умовна схема, яка відображає роботу алгоритму розпізнавача. Як видно із малюнка розпізнавач складається з наступних компонентів:
стрічки, яка містить вихідний ланцюжок символів і зчитуючої головки, яка вибирає черговий символ в цьому ланцюжку;
пристрою керування (ПК), який координує роботу розпізнавача, має деякий набор станів і кінцеву пам’ять (для збереження свого стану і деякої проміжної інформації);
зовнішньої (робочої) пам’яті, яка може зберігати деяку інформацію в процесі роботи розпізнавача і на відміну від пам’яті ПК може мати необмежений об’єм.
Розпізнавач працює з символами свого алфавіту – алфавіту розпізнавача. Алфавіт розпізнавача є скінченним. Він включає в себе усі допустимі символи вхідних ланцюжків, а також деякий додатковий алфавіт символів, які можуть оброблятися ПК і зберігатися в робочій памяті розпізнавача.
В процесі своєї роботи розпізнавач може виконувати деякі елементарні операції, такі як читання чергового символа із вхідного ланцюжка , зсув вхідного ланцюжка на задану кількість символів (вправо чи вліво), доступ до робочої пам’яті для читання або запису інформації, перетворення інформації в пам’яті, зміна стану ПК. Те, які конкретно операції повинні виконуватися в процесі роботи розпізнавача, визначається в ПК.
Розпізнавач працює по крокам чи тактам. На початку такта, як правило зчитується черговий символ з вхідного ланцюжка, і в залежності від цього символа ПК визначає, які дії необхідно виконувати. Вся робота розпізнавача складається з послідовності тактів. На початку кожного такту стан розпізнавача визначається його конфігурацією. В процесі роботи конфігурація розпізнавача міняється.
Конфігурація розпізнавача визначається наступними параметрами:
Вмістиме вхідного ланцюжку символів і положення зчитуючої головки на ньому.
Стан ПК.
Вміст зовнішньої пам’яті.
Для розпізнавача завжди задається визначена конфігурація, яка рахується початковою конфігурацією. В початковій конфігурації зчитуюча головка спостерігає перший символ вхідного ланцюжку, ПК знаходиться в заданому початковому стані, а зовнішня пам’ять або пуста, або містить строго визначену інформацію.
Крім початкового стану для розпізнавача задається одна або декілька кінцевих конфігурацій В кінцевій конфігурації зчитуюча головка, як правило знаходиться за кінцем вихідного ланцюжку (часто для розпізнавачів вводять спеціальний символ, який означає кінець вхідного ланцюжка).
Розпізнавач допускає вхідний ланцюжок символів , якщо, знаходячись в початковій конфігурації і отримавши на вхід цей ланцюжок, він може проробити послідовність кроків, яка закінчується одною із його кінцевих конфігурацій .
Мова, що визначається розпізнавачем, – це множина всіх ланцюжків, які допускає розпізнавач.
Граматики і розпізнавачі – два незалежних методи, які реально можуть бути використані для визначення певної мови. Однак при розробці компілятора для деякої мови програмування виникає задача, яка вимагає зв’язати між собою ці методи задання мов. Задача розробників полягає в тому, щоб побудувати розпізнавач для заданої мови, який потім буде основою синтаксичного аналізатора в компіляторі. Таким чином, задача розбору в загальному випадку заключається в наступному: на основі правил граматики деякої мови побудувати розпізнавач для цієї мови. Задана граматика і розпізнавач повинні бути еквівалентні, тобто визначати одну й ту ж мову.
Так як мови програмування не являються чисто формальними мовами і несуть в собі деякий смисл (семантику), то задача розбору для створення реальних компіляторів, розуміється дещо ширше, ніж вона формулюється для чисто формальних мов. Компілятор повинен не просто дати відповідь про приналежність вхідного ланцюжку символів заданій мові, але і визначити її смислове навантаження. Для цього необхідно виявити ті правила граматики, на основі яких ланцюжок був побудований. Фактично робота розпізнавачів у складі компіляторів зводиться до побудови в тому або іншому вигляді дерева розбору вхідного ланцюжку. Потім це дерево розбору використовується компілятором для синтезу результуючого коду.
Крім того, якщо вхідний ланцюжок символів не належить заданій мові – вихідна програма містить помилку, – розробнику програми не цікаво просто взнати сам факт наявності помилки. В даному випадку задача розбору також розширяється: розпізнавач у складі компілятора повинен не тільки встановити факт присутності помилки у вхідній програмі, але і по можливості визначити тип помилки і те місце у ланцюжку символів де вона зустрічається.
2.4. Етапи трансляції. Загальна схема роботи транслятора
На рис. Представлена загальна схема роботи компілятора. З неї видно, що в цілому процес компіляції складається з двох основних етапів – синтеза і аналіза.
Таблиця ідентифікаторів
Лексичний аналів
Синтаксичний розбір
Семантичний аналів
Внутрішнє представлення програми
Підготовка до генерації коду
Генерація коду
Вихідна програма
Аналіз і локалізація знайдених помилок
Повідомлення про помилку
Об’єктна програма
Аналіз
Синтез
На етапі аналізу виконується розпізнавання тексту вихідної програми, створення і заповнення таблиць ідентифікаторів. Результатом його роботи служить деяке внутрішнє представлення програми, зрозуміле компілятору.
На етапі синтезу на основі внутрішнього представлення програми і інформації, яка міститься в таблиці (таблицях) ідентифікаторів, породжується текст результуючої програми. Результатом цього етапа являється об’єктний код.
Крім того, в складі компілятора присутня частина, відповідна за аналіз і виправлення помилок, яка при наявності помилок в тексті вихідної програми повинна максимально повно інформувати користувача про тип помилки і місце її виникнення. В кращому випадку компілятор може запропонувати користувачу варіанти виправлення помилок.
Ці етапи в свою чергу складаються з більш менших етапів називаємих фазами компіляції. Склад фаз компіляції наведено в самому загальному випадку, їх конкретна реалізація і процес взаємодії можуть, звичайно, розрізнятися в залежності від версії компілятора.
Компілятор вцілому з точки зору теорії формальних мов виступає в “двох іпостасях”, виконує дві основні функції.
По-перше, він являється розпізнавачем для мови вихідної програми. Тобто він повинен отримати на вхід ланцюжок символів вхідної мови, перевірити її приналежність мові і, більш того, виявити правила, по яким цей ланцюжок було побудовано. Генератором ланцюжків вхідної мови виступає користувач – автор вхідної програми.
По-друге, компілятор являється генератором для мови результуючої програми. Він повинен побудувати на виході ланцюжок вихідної мови по визначеним правилам, на мові машинних команд або мові асемблера. Розпізнавачем в цьому випадку буде виступати вже обчислювальна система, під яку створюється результуюча програма.
Далі наводиться перелік основних фаз компіляції і короткий їх фунуцій.
Лексичний аналіз (сканер) – це частина компілятора, яка читає літери програми на вихідній мові і будує із них слова (лексеми) вихідної мови. На вхід лексичного аналізатора поступає текст вихідної програми, а вихідна інформація передається для подальшої обробки компілятором на етапі синтаксичного розбору. З теоретичної точки зору лесичний аналізатор не являється обов’язковою, необхідною частиною компілятора.
Синтаксичний розбір – це основна частина компілятора на етапі аналіза. Вона виконує виділення синтаксичних конструкцій в тексті вихідної прграми, обробленим лексичним аналізатором. На цій же фазі компіляції перевіряється синтаксична правильність програм. Синтаксичний розбір грає головну роль – роль розпізнавача текста вхідної мови програмування.
Семантичний аналіз – це частина компілятора, яка первіряє правильність текста вхідної програми з точки зору семантики вхідної мови. Крім безпосередньої перевірки, семантичний аналіз повинен виконувати перетворення тексту, які вимагаються семантикою мови(такі як добавлення функцій неявного перетворення типів). В різних реалізаціях компіляторів семантичний аналіз може частково входити в фазу синтаксичного розбору, частково – в фазу підготовки до генерації коду.
Підготовка до генерації коду – це фаза, на якій компілятором виконуються попередні дії, безпосередньо пов’язані з синтезом текста результуючої програми, але ще не ведуть до породження текста на вихідній мові. Звичайно в цю фазу входять дії, пов’язані з ідентифікацією елементів мови, розподілом пам’яті і т.д.
Генерація кода – ця фаза, безпосередньо пов’язана з породженням команд, які складають речення вихідної мови і вцілому текст результуючої програми. Це основна фаза на етапі синтезу результуючої програми.Крім безпосереднього породження тексту результуючої програми, генерація звичйано включає в себе також оптимізацію – процес, пов’язаний з обробкою вже породженого тексту. Іноді оптимізацію виділяють в окрему фазу компіляції, так як вона здійснює серйозний вплив на якість і ефективність результуючої програми.
Таблиці ідентифікаторів – це спеціальним чином організовані набори даних, які служать для зберігання інформації про елементи вихідної програми, які потім використовуються для породження текста результуючої програми. Таблиця ідентифікаторів в конкретній реалізації компілятора може бути одна, або декілька. Елементами вихідної програми, інформацію про які необхідно зберігати в процесі компіляції, являються змінні, константи, функції і т.д.
2.5. Таблиці ідентифікаторів
Перевірка правильності семантики і генерації кода потребує знання характеристик змінних, коснтант і функцій і інших елемнтів, які зустрічаються на вихідній мові. Всі ці елементи в вихідній програмі, як правило позначаються ідентифікаторами. Виділення ідентифікаторів і інших елементів вихідної програми відбувається на фазі лексичного аналіза. Їх характеристики визначаються на фазах синатксичного розбору, семантичного аналізу і підготовки до генерації коду.
В будь-якому випадку компілятор повинен мати можливість знати всі знайдені ідентифікатори і пов’язані з ними характеристики на протязі всього процесу компіляції, щоб мати можливість використовувати їх на різних фазах компіляції. Для цієї цілі, як було сказано вище, в компіляторах використовується спеціальне збереження даних, називаєме таблицями ідентифікаторів або таблицями символів.
Будь-яка таблиця ідентифікаторів складається з набора полів, кількість яких рівна кількості різних ідентифікаторів, знайдених в вихідній програмі. Кожне поле містить в собі повну інформацію про даний елемент таблиці.
Склад інформації, яка зберігається в таблиці ідентифікаторів для кожного елемента вихідної програми, залежить від семантики вихідної мови і типу елемента. Наприклад, в таблицях ідентифікаторів може зберігатися наступна інформація:
для змінних:
ім’я змінної;
тип даних змінної;
область памяті, пов’язана із змінною;
для констант:
назва константи;
значення константи;
тип даних констант;
для функцій:
ім’я функції;
кількість і тип формальних аргументів функції;
тип повертаємого результата;
адреса кода функції.
Наведений вище склад зберігаємої інформації, звичайно ж, являється тільки прикладним. Конкретне наповнення таблиць ідентифікаторів залежить від реалізації компілятора. Крім того, не вся інформація таблиць ідентифікаторів заповнюється компілятором відразу – він може декілька разів виконати зверенння до даних в таблиці ідентифікаторів на різних фазах компіляції. Наприклад, імена змінних можуть бути виділені на фазі лексичного аналізу, типи даних для змінних – на фазі синтаксичного розбору, а область пам’яті пов’язується із змінною тільки на фазі підготовки до генерації коду.
Незалежно від реалізації компілятора принцип його роботи з таблицею ідентифікаторів залишається одним і тим самим – на різних фазах компіляції компілятор вимушений багатократно звертатися до таблиці для пошуку інформації і запису нових даних. Як правило, кожний елемент у вихідній програмі, однозначно ідентифікується своїм іменем. Тому компілятору доводиться часто виконувати пошук необхідного елемента в таблиці ідентифікаторів по його імені, в той час як процес заповнення таблиці виконується нечасто – нові ідентифікатори в програмі описуються значно рідше, чим використовуться. Звідси можна зробити висновок , що таблиця ідентифікаторів повинна бути організована таким чином, щоб компілятор мав можливість максимально швидко шукати потрібні йому елементи.
Найпростіший способ оганізації таблиці полягає в тому, щоб добавляти елементи в порядку їх поступлення. Тоді таблиця буде представляти собою невпорядкований масив інформації, кожна комірка якого буде містити дані про відповідний елемент табл.
2.6. Лексичний аналізатор
Лексичний аналіз (сканер) – це частина компілятора, яка читає літери програми на вихідній мові і будує із них слова (лексеми) вихідної мови. На вхід лексичного аналізатора поступає текст вихідної програми, а вихідна інформація передається для подальшої обробки компілятором на етапі синтаксичного розбору.
З теоретичної точки зору лексичний аналізатор не являється обов’язковою, необхідною частиною компілятора. Всі його функції можуть виконуватися на етапі синтаксичного розбору, оскільки повністю регламентовані синтаксисом вхідної мови. Однак існує декілька причин, по яким в склад компілятора включають лексичний аналіз:
застосування лексичного аналізатора спрощує роботу з текстом вихідної програми на етапі синтаксичного розбору і скорочує об’єм обробляємої інформації, так як лексичний аналізатор структурує поступаємий на вхід вихідний текст прграми і викидає всю незначущу інформацію;
для виділення в тексті і розбору лексем можливо застосовувати просту, ефективну і теоретично добре пророблену техніку аналіза, в той час як на етапі синтаксичного аналіза конструкцій вихідної мови використовуються достатньо складні алгоритми розбору;
сканер відділяє складний по конструкції синтаксичний аналізатор від роботи безпосередньо з текстом вихідної програми, структура якого може варіюватися в залежності від версії вхідної мови – при такій конструкції компілятор для перехода від одної версії мови до іншої достатньо тільки перебудувати простий лексичний аналізатор.
Функції, які виконуються лексичним аналізатором, і склад лексем які він виділяє в тексті вихідної програми, можуть міняться в залежності від версії компілятора. Те, які функції повинен виконувати лексичний аналізатор і які типи лексем він повинен виділяти у вхідній програмі, а які залишати для етапа синтаксичного розбору, вирішують розробники компілятора. В основному лексичні аналізатори виконують виключення з тексту програми коментарів, незначащих пробілів, символів табуляції і переводу рядку, а також виділення лексем наступних типів: ідентифікаторів, рядкових, символьних і числових констант, ключевих (слів) вхідної мови, знаків операцій і розділювачів.
В найпростішому випадку фази лексичного і семантичного аналізу можуть виконуватися компілятором послідовно. Але для багатьох мов програмування на етапі лексичного аналізу може бути недостатньо інформації для однозначного визначення типу і границь чергової лексеми. Тому в більшості компіляторів лексичний і синтаксичний аналізатори – це взаємозв’язані частини. Можливі два принципово різних метода організації взаємозв’язку лексичного аналізу і синтаксичного розбору:
послідовний;
паралельний.
При послідовному варіанті лексичний аналізатор переглядає весь текст вихідної програми від початку до кінця і перетворює його в структурований набір даних. Цей набір даних також називається таблицею лексем. В таблиці лексем ключові слова мови, ідентифікатори і константи, як правило заміняються на спеціально оговорені коди. Для ідентифікаторів і констант, крім того, встановлюється зв’язок між таблицею лексем і таблицею ідентифікаторів, яка заповнюється паралельно.
В цьому варіанті лексичний аналізатор переглядає весь текст вихідної програми один раз від початку до кінця. Таблиця лексем будується повністю уся відразу і більше до неї компілятор не повертається. Всю подальшу обробку виконують наступні фази компіляції.
При паралельному варіанті лексичний аналіз вихідного тексту виконується поетапно так, що синтаксичний аналізатор, виконавши розбір чергової конструкції мови, звертається до сканера за наступною лексемою. При цьому він може повідомити інформацію про те, яку лексему слід очікувати. В процесі розбору при виникненні помилки може відбутися “відкат назад”, щоб спробувати виконати аналіз текста на іншій основі. І тільки після того як синтаксичний аналізатор успішно виконає розбір чергової констукції мови, лексичний аналізатор поміщає знайдені лексеми в таблицю лексем і таблицю ідентифікаторів і продовжує розбір далі в тому ж порядку. Робота синтаксичного і лексичного аналізаторів в варіанті їх паралельної взаємодії зображена у вигляді схеми:
Вихідна програма
Лексичний аналізатор (сканер)
Таблиця ідентифікаторів (таблиця імен)
Синтаксичний розбір (аналіз)
Ідентифікатори
Чергова лексема
Звернення за лексемою
Очевидно, що послідовний варіант організації взіємодії лексичного аналізу і синтаксичного розбору являється більш ефективним, так як він не вимагає організації складних механізмів обміну даними і не потребує повторного читання вже розібраних лексем. Цей метод являється і більш простим. Однак не для всіх мов пр...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора