Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Компілятор
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Курсова робота
Предмет:
Системне програмування та операційні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЕОМ
Курсова робота
з предмету “Системне програмування”
на тему: Розробка транслятора з вхідної мови програмування.
Варіант № 67
Львів – 2014
Анотація
В даній курсовій роботі я розробив транслятор з вхідної мови програмування. Розробка програмних модулів і компонент системного програмування є дуже актуальним завданням в наш час. Транслятор до даної курсової роботи я розробив в середовищі програмування Microsoft Visual Studio 2010. Для побудови транслятора я використав низхідний метод граматичного розбору. В пояснювальній записці подав огляд існуючих методів розробки трансляторів, детальний опис мови, а також опис процесу розробки програми транслятора. В проекті містяться результати тестування програми та вихідний текст програми транслятора. Також показано і детально описано розробку і виконання наступних фаз компіляції:лексичний аналіз;синтаксичний аналіз;генерація коду.
Результатом виконання курсової роботи є повноцінна функціональна програма на мові Assembler, яка є інтерпретованою програмою реалізованої на заданій вхідній мові програмування.
Зміст
Завдання на курсову роботу…………………………………………… ……4
Вступ …….…. 5
1. Огляд методів та способів проектування трансляторів ... 6
1.1. Введення в компіляцію…………………………………..…. …..…6
1.2 Лексичний аналіз………………………………………...….…..….….8
1.3.Синтаксичний аналіз………………………………………..………....9
1.4. Опис розпізнавача…………………………………………………...10
2. Формальний опис вхідної мови програмування …12
2.1 Деталізований опис вхідної мови в термінах EBNF 12
2.2 Опис термінальних символів та ключових слів 14
3. Розробка транслятора вхідної мови програмування 17
3.1 Вибір технології програмування 17
3.2 Проектування таблиць транслятора та вибір структур даних 18
3.3 Розробка лексичного аналізатора 19
3.3.1 Опис лексичного аналізатора………………………..………....…19
3.3.2 Опис граф-схеми лексичного аналізатора 22
3.3.3 Опис програми реалізації лексичного аналізатора 23
3.4 Розробка синтаксичного аналізатора 24
3.4.1 Опис програми реалізації синтаксичного аналізатора 24
3.4.2 Опис граф-схеми синтаксичного аналізатора …………..………..27
3.4.3 Опис програми реалізації синт.та сим.аналіз 28
3.4.4.Розробка дерев граматичного розбору………………….………29
3.5 Розробка генератора коду 30
3.5.1 Розробка алгоритму 30
3.5.2 Опис блок-схеми реалізації генератора коду 32
3.5.3 Опис програми реалізації генератора коду 32
4. Опис інтерфейсу та інструкції користувача 33
5. Відлагодження та тестування програми 34
5.1 Виявлення лексичних помилок 34
5.2 Виявлення синтаксичних помилок 34
5.3 Виявлення семантичних помилок 35
5.4 Загальна перевірка коректності роботи транслятора 36
Висновки 38
Список літератури 38
Додаток A загальний алгоритм роботи транслятора 39
Додаток Б лістинг програми заготовки початкового коду 41
Завдання на курсову роботу
1. Цільова мова транслятора асемблер (iх86).
2. Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами ml.exe (MASM32)
3. Мова розробки транслятора: С++.
4. Реалізувати оболонку або інтерфейс з командного рядка.
5. На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
6. На виході розробленого транслятора мають створюватись чотири файли:
1)файл з повідомленнями про помилки ; 2)файл на мові асемблера; 3)об’єктний файл;4)виконавчий файл.
7. Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування.
Деталізований опис вхідної мови
- типи даних:Long int ;
- оператор вводу: input;
- оператор виводу: output;
- блок тіла програми: program <name>; begin var …; end
- оператор: do-while
- регістр ключових слів: Low ;
- регістр ідентифікаторів:Up-Low4
- операції арифметичні: +,-,*,/,%
- операції порівняння: =; <>; >; <
- операції логічні: !, and, or;
- коментар: /*…
- ідентифікатори змінних, числові константи;
- оператор присвоєння: := ;
Вступ
Відповідно до варіанту завдання на курсову роботу необхідно спроектувати транслятор для деякої власної мови програмування. Основна увага відводиться вивченню методів розбору, організації таблиць, розміщенню елементів в пам'яті, представленню типів даних.
Результатом трансляції є файл-програма асемблера, по діях аналогічна програмі на «нашій» мові.В даній курсовій роботі я реалізував транслятор на мові програмування С++ .
На сьогоднішній день існує досить багато мов програмування:низькорівневі та високорівневі.
Транслятори становлять істотну частину програмного забезпечення ЕОМ. На сьогодні існує досить багато мов програмування. Нарівні з традиційними мовами, такими, як Fortran, широке поширення отримали так звані «універсальні мови» (Паскаль, Сі, Модула-2, Ада та інші), а також деякі спеціалізовані (наприклад, мова обробки облікових структур Лісп). В даний час штучні мови, що використовують для опису предметної області текстове представлення, широко застосовуються не тільки в програмуванні, але і в інших областях. З їх допомогою описується структура всіляких документів, тривимірних віртуальних світів, графічних інтерфейсів користувача і багатьох інших об'єктів, використовуваних в моделях і в реальному світі. Для того, щоб ці текстові описи були коректно складені, а потім правильно розпізнані і інтерпретовані, використовуються спеціальні методи їх аналізу і перетворення. У основі методів лежить теорія мов і формальних граматик, а також теорія автоматів. Програмні системи, призначені для аналізу і інтерпретації текстів, називаються трансляторами.
Постійно зростає потреба в нових трансляторах це пов’язано з бурхливим розвитком архітектури ЕОМ. Цей розвиток йде у різних напрямах. Удосконалюється стара архітектура, як в концептуальному відношенні, так і по окремих, конкретних лініях. Внаслідок розвитку різноманітних архітектур створюються нові машини, які вимагають
Компілятор - комп'ютерна програма , що перетворює (компілює) програмний код, написаний певною мовою програмування, на семантично еквівалентний код в іншій мові програмування, який необхідний для виконання програми машиною.
Створення трансляторів є одною з невід’ємних частин системного програмного забезпечення. Одним із завдань транслятора є переведення написаного тексту програми у машинний код, який повинен відповідати комп’ютерній системі.
Огляд методів та способів проектування трансляторів
1.1. Введення в компіляцію
Створення компіляторів відбувається в певних конкретних умовах: для різних мов, для різних цільових платформ, з різними вимогами для створення компіляторів. Є такі методи створення компіляторів:
1. Прямий метод- цільовою мовою і мовою реалізації є асемблер.
2. Метод розкрути- саме цей метод і використовується у даній курсовій роботі, тобто вибирається інструмент (в даній курсовій це мова асемблер), для якого вже існує компілятор.
3.Використання крос-трансляторів.
4. З використанням віртуальних машин – дає спосіб отримати переносимо програму.
5. Компіляція на ходу.
Не дивлячись на те, що основні задачі, що виконуються компіляторами видаються складними і різноманітними, по суті вони одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних вихідних мов і цільових машин з використанням одних і тих же базових технологій.
Компіляція складається з двох частин: аналізу і синтезу. Аналіз – це розбиття початкової програми на складові частини і створення її проміжного представлення. Синтез – конструювання необхідної цільової програми з проміжного представлення.
В процесі аналізу визначаються і записуються в ієрархічну деревовидну структуру операції, задані початковою програмою. Часто використовується спеціальний вид дерева, що називається синтаксичним (або деревом синтаксичного розбору), в якому кожен вузол представляє операцію, а його дочірні вузли – аргументи операції.
Багато програмних інструментів, працюючи з початковими програмами, спочатку виконують певний вид аналізу. Розглянемо приклади таких інструментів.
Фази лексичного (ЛА) та синтаксичного (СА) аналізів розкладають початкову програму на частини. Генерація проміжного коду (ГПК), оптимізація (ОК) та генерація коду (ГК) машини синтезують об`єктну програму. Керування таблицями (КТ) та обробка помилками (ОП) використовуються на всіх фазах компіляції (див. рис.1).
Структурні редактори. Ці програми одержують як вхід послідовність команд для побудови початкової програми. Такий редактор не тільки виконує звичні для текстового редактора функції зі створення і модифікації тексту, але і аналізує текст програми, поміщаючи в початкову програму відповідну ієрархічну структуру. Тим самим він виконує додаткові задачі, що полегшують підготовку програми. Наприклад, редактор може перевіряти коректність введеного тексту, автоматично додавати структурні елементи (так, якщо користувач введе while, редактор додасть відповідне йому ключове слово do і запропонує ввести умовний вираз між ними) або переходить від ключового слова begin або лівої дужки до відповідного end або правої дужки. Більше того, результат на виході такого редактора часто подібний результату після фази аналізу компіляції.
Програми форматованого виводу для друку. За допомогою цих інструментів програма аналізується і роздруковується так, щоб її структура була максимально ясною. Наприклад, коментарі можуть бути виділені спеціальним шрифтом, а оператори – виведені з відступами, що вказують рівень вкладеності в ієрархічній структурі операторів.
Статичні перевіряючі програми. Дані інструменти зчитують програми, аналізують їх і намагаються знайти потенційні помилки без запуску програми. Такий аналіз часто дуже схожий на аналіз в оптимізуючих компіляторах. Наприклад, статична перевіряюча програма може визначити невиконання якоїсь частини початкової програми або використання деякої змінної до її оголошення. Так само можуть бути знайдені логічні помилки, наприклад спроби використання дійсної змінної як покажчик (із застосуванням технології перевірки типів).
При створенні цільової програми, окрім компілятора, може бути потрібним і ряд інших програм. Початкова програма може бути розділена на модулі, що зберігаються в окремих файлах. Задача збору початкової програми іноді доручається окремій програмі – препроцесору, який може також розкривати в тексті початкової програми скорочення, так звані макроси.
Цільова програма, створювана компілятором, може зажадати додаткову обробку перед запуском. Компілятор, створює асемблерний код, який переводиться асемблером в машинний код, а потім зв'язується («лінкуєтся») спільно з деякими бібліотечними програмами в код, що реально запускається на машині.
1.2. Лексичний аналіз
Основна задача лексичного аналізу – розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
Звичайно всі лексеми діляться на класи. Прикладами таких класів є числа, ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяка кінцева підмножина ідентифікаторів. З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох типів: для синтаксичного аналізатора, працюючого услід за лексичним, істотна інформація про послідовності класів лексем, обмежувачів та ключових слів, а для семантичного аналізу, працюючого услід за синтаксичним, важлива інформація про конкретні значення окремих лексем (ідентифікаторів, чисел і т.д.). Тому загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема. Якщо виділена лексема – обмежувач, то він (точніше, деяка його ознака) видається як результат лексичного аналізу. Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його до ключових слів. Якщо так, то видається ознака відповідного ключового слова, якщо немає – видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Якщо виділена лексема належить якому-небудь з інших класів лексем (число, рядок і т.д.), то видається ознака класу лексеми, а значення лексеми зберігається.
Лексичний аналізатор може працювати або як самостійна фаза трансляції, або як підпрограма, працююча за принципом «дай лексему». У першому випадку виходом лексичного аналізатора є файл лексем, у другому лексема видається при кожному зверненні до лексичного аналізатора (при цьому, як правило, тип лексеми повертається як значення функції, а значення передається через глобальну змінну). З точки зору формування значень лексем, належних класам лексем, лексичний аналізатор може або просто видавати значення кожної лексеми і в цьому випадку побудова таблиць переноситься на більш пізні фази, або він може самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.). У цьому випадку, як значення лексеми видається покажчик на вхід у відповідну таблицю.
1.3. Синтаксичний аналіз
Синтаксичний аналіз – це процес, в якому досліджується таблиця лексем, або кожна окрема лексема, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що явно сформульовані у визначені синтаксису мови. Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його у відповідності до граматики вихідної мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вихідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в тексті програми, встановити тип та правильність кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми.Узагальнена структурна схема аналізатора зображена на рис.2.
Рис. 2 - Узагальнена структура аналізатора
Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних символів заданій мові.
1.4. Опис розпізнавача.
В даній курсовій роботі згідно із завданням для непарних варіантів необхідно реалізувати висхідний метод граматичного розбору. Детермiнованi висхiднi розпiзнавачi, так само як i спаднi, можуть бути побудованi не для всякої КВ-граматики, а тiльки для визначених пiдкласiв таких граматик. Найбiльш широким пiдкласом КВ-граматик є LR(k)–граматики. Цi граматики забезпечують розпiзнавання ланцюжка при переглядi злiва направо, про що свiдчить буква L (/I>Left) у назвi граматики, i дозволяють виконати правобiчне згортання, про що свiдчить буква R (Right) у назвi.
У загальному випадку алгоритми побудови розпiзнавачiв для LR(k)–граматик виявляються досить складними i трудомiсткими, тому на практицi найчастiше використовують пiдкласи LR(k)–граматик: LR(0) або SLR(1) – простi (Simple), LR(1)–граматики, що дозволяють вiдносно просто виконувати побудову висхiдних розпiзнавачiв. При цьому для кожного пiдкласу LR(k)–граматик використовується свiй алгоритм побудови.
У загальному випадку процедуру побудови висхiдного розпiзнавача за заданою граматикоюможна описати в такий спосiб:
Визначити для даної граматики функції.
Побудувати детермiновану таблицю переходiв, що має по одному стовпцю для кожного граматичного символу i по одному рядку для кожного граматичного входження i маркера дна.
Якщо таблиця, побудована на кроцi 2, виходить недетермiнованою (має бiльше одного стану), то потрiбно перетворити цю таблицю в детермiновану, розглядаючи її як недетермiновану таблицю переходiв кiнцевого автомата з початковим станом h0.
Стани, отриманi на кроцi 3 (крiм стану, що вiдповiдає порожнiй множинi), варто використовувати як магазиннi символи. Отримана таблиця переходiв може мiстити переходи в порожню множину.
Керуючу таблицю заповнюють рядок за рядком вiдповiдно до множини граматичних входжень, що позначають рядки.
ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
Форма Бе́куса—Нау́ра — це спосіб запису правил контекстно-вільної граматики, тобто форма опису формальної мови.
Форма Бе́куса—Нау́ра є набором «продукцій», кожна з яких відповідає зразку:
<символ> ::= <вираз, що містить символи>,
де “вираз, що містить символи” це послідовність символів або послідовності символів, розділених вертикальною рискою | , що повністю перелічують можливий вибір символів з лівої частини формули.
< — лівий обмежувач виразу
> — правий обмежувач виразу
::= — визначене як
| — визначене або
Ці чотири символи є символами мета-мови, вони не визначені у мові, котру описують. Решта описаних символів належать до «абетки» описуваної мови.
Розши́рена фо́рма Бе́куса — На́ура (EBNF) є розширеною формою нотації Бекуса-Наура (BNF) — метасинтаксичної нотації.
Вихідні коди комп'ютерних програм складаються із термінальних символів. До термінальних символів належать видимі літери, цифри, знаки пунктуації, прогалини тощо.
EBNF визначає продукції, що співставляють послідовності із нетермінальними символами.
цифра без нуля = “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”;
цифра = ”0” | цифра без нуля;
Це правило продукції визначає нетермінальний символ «цифра», що знаходиться в лівій частині. Вертикальна риска позначає альтернативу, а термінальні символи знаходяться в лапках. Таким чином, цифра це або 0, або цифра без нуля, котра може бути 1 або 2 або 3 і так далі до 9.Продукція також може включати як термінальні так і не термінальні символи, розділені комами.
Вирази, що можна пропускати або можуть повторятись слід записувати у фігурних дужках { … }:
натуральне число = цифра без нуля , { цифра} ;
В цьому випадку, рядки 1, 2, …,10,…,12345,… є правильними виразами. Для того, аби відобразити це, все, що взято у фігурні дужки може повторюватись необмежену кількість раз, або не з'являтись взагалі.
Можлива поява може відображатися застосуванням квадратних дужок [ … ]:
ціле = “0” | [ “-” ], натуральне число;
Тобто, ціле це або нуль (0), або натуральне число, перед яким може знаходитись знак мінус.
Також, EBNF має синтаксичні засоби для описання певної кількості повторень, для вилучення деякої частини продукції або для запису коментарів в EBNF-граматику.
Однією з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких я застосував розширену нотацію Бекуса-Наура. Розширена форма Бекуса-Наура (скор. РБНФ) - формальна система визначення синтаксису, в якій одні синтаксичні категорії послідовно визначаються через інші. Використовується для опису контекстно-вільних формальних граматик. Запропоновано Никлаусом Віртом. Є розширеною переробкою форм Бекуса-Наура, відрізняється від БНФ більш «вмістимими» конструкціями, що дозволяють при тій же виразності дозволяє спростити і скоротити в обсязі опис.
2.2Реалізація нотації Бекуса-Наура
Розширена форма Бекуса — Наура є розширеною формою нотації Бекуса-Наура (BNF) —метасинтаксичної нотації. Cьогодні вона існує в багатьох варіантах..
Нотація Бекуса—Наура є спосіб запису правил контекстно-вільної граматики, себто формою опису формальної мови.
<program>::=program<name>var<var_blok>begin<code_blok>end.
<var_blok> ::=<declarations> [{;<declarations>} ];.
<name>::<letter>[<l_or_n>].
<declarations>::=Longint<declaration_i> [{,<declaration_i>}] | boolean <declaration_b> [{,<declaration_b>}] .
.<declaration_i> ::= <ident> [ ::= <const_i>] .
<declaration_b> ::= <ident> [ ::= <const_b>] .
<ident> ::= <letter>[<l _or_n>].
<l_or_n> ::= <letter>|<number> .
<letter>::=a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z .
<number> ::= 0|1|2|3|4|5|6|7|8|9 .
<const_i> ::= [-]<number>[{number}] .
<const_b> ::=true|false
<code_blok> ::= <statement> [{<statement>}] .
<statement> ::= <equation>|<cycle>|<input>|<output> .
<equation> ::= <ident> [::= <expression_i>|<expression_b>]; .
<expression_i>::= <term> [{+ <term> | - <term>}].
<term>::=<ident>|<const_i>|<factor>.
<factor>::=[{* <term> | / <term>| % <term> | <brackets>}].
<brackets>::=(<expression_i>).
<expression_b>::= <term_b> [{= <term_b> | <> <term_b> | ><term_b>| < <term_b>}].
<term_b>::=<ident>|<cmp_b>|<factor_b>.
<factor_b>::=<term_b> [{ or<term_b> | <and> |<not>|<brackets_b>}].
<and>::= [{ and<term_b>}]
<not>::=!<factor_b>
<brackets_b>::=(<expression_b>).
<cycle> ::= do (<expression_b>|<ident>) while <label1> <code_blok> <code_blok>
<input> ::= input(<ident>); .
<output> ::= output(<expression_i>|<string>|<expression_b>); .
<string> ::= “<l_or_n>[{<l_or_n>}]” .
2.3. Поняття формальної граматики та термінальних символів
Формальна граматика або просто граматика в теорії формальних мов — спосіб опису формальної мови, тобто виділення деякої підмножини з множини всіх слів деякого скінченного алфавіту.
Розрізняють породжувальні і аналітичні граматики — перші ставлять правила, за допомогою яких можна побудувати будь-яке слово мови, а другі дозволяють по даному слову визначити, входить воно в мову чи ні.
Термінал (термінальний символ) - об'єкт, безпосередньо присутній у словах мови, відповідного граматиці, і має конкретне, незмінне значення (узагальнення поняття «букви»). У формальних мовах, використовуваних на комп'ютері, в якості терміналів зазвичай беруть всі або частину стандартних символів ASCII - латинські букви, цифри та спец. символи.
Нетермінал (нетермінальний символ) - об'єкт, що позначає яку-небудь сутність мови (наприклад: формула, арифметичний вираз, команда) і не має конкретного символьного значення.
2.4 Опис термінальних символів та ключових слів .
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
Термінальні символи та ключові слова.
program – Початок програми
var – блок опису змінних
begin – початок тіла програми
end – кінець тіла програми
input – оператор вводу
output – оператор виводу
do-while – оператор циклу
+ – операція додавання
- — операція віднімання
* – операція множення
/ – операція ділення
%– остача від ділення
= – рівно
<> – не рівно
Long int – цілий тип даних
boolean – дійсний тип
:= - присвоєння
< - менше
> - більше
! - інверсія
and - кон`юнкція
or - диз`юнкція
/*… – блочний коментар
До термінальних символів віднесемо також усі цифри (0-9), латинські букви ( A-Z), символи табуляції, символ переходу на нову стрічку, пробілу, знаку «-», «_» та «”».
3. Розробка транслятора вхідної мови
Створення трансляторів є одною з невід’ємних частин системного програмного забезпечення. Транслятор розроблений в даній курсовій роботі працює за схемою поданою в додатку Б. Він включає в себе три головні фази:
лексичний аналіз
синтаксичний аналіз
генерація коду
Також тут реалізоване збереження проміжних результатів роботи: списку лексем, ідентифікаторів, міток, проміжного представлення мови. При виявлені помилок вони також додатково зберігаються в файл
3.1 Вибір технології програмування
Технологією програмування було обране об’єктно-орієнтоване програмування.Транслятор реалізовано мовою С++. На відміну від традиційних поглядів, коли програму розглядали як набір підпрограм, або як перелік інструкцій комп'ютеру, ООП програми можна вважати сукупністю об'єктів. Відповідно до парадигми об'єктно-орієнтованого програмування, кожний об'єкт здатний отримувати повідомлення, обробляти дані, та надсилати повідомлення іншим об'єктам.
Клас - це тип, що описує будову об'єктів. Поняття "клас" має на увазі деяка поведінка і спосіб представлення. Поняття "об'єкт" має на увазі щось, що має певну поведінку і спосіб представлення.
Структура даних "клас" є об'єктним типом даних. При цьому елементи такої структури (члени класу) можуть самі бути не лише даними, але і методами (тобто процедурами або функціями).
Поліморфізмом називають явище, при якому функції (методу) з одним і тим же ім'ям відповідає різний програмний код (поліморфний код) залежно від того, об'єкт якого класу використовується при виклику цього методу. Поліморфізм забезпечується тим, що в класі-нащадку змінюють реалізацію методу класу-предка з обов'язковим збереженням сигнатури методу.
3.2 Проектування таблиць транслятора та вибір структур даних
Використання таблиць значно полегшує створення трансляторів, тому у даному випадку використовуються кілька таблиць:
1)Таблиця лексем з елементами, які мають таку структуру:
enum LexemType
{ mainprogram_,
data_,
int_,
begin_,
end_,
input_,
output_,
do_,
while_,
newval_, // ->
add_, // +
sub_, // -
mul_, // *
div_, // /
mod_, // %
equ_, // ==
notequ_, // !=
le_, // le
ge_, // ge
not_, // !!
and_, // &&
or_, // ||
eof_, //
EndGroup_, // ;
komma_, // ,
ident_,
number_,
LeftBraket_, // (
RightBraket_, // )
unknown_
};
typedef struct Lexem
{
char name[50];
int value;
LexemType type;
int line;
}Lexema;
2) Таблиця ідентифікаторів з елементами типу Identificator та додатковою цілочисельною змінною в якій зберігається кількість визначених змінних. Структура елементів така:
typedef struct Ident
{
char name[50];
int value;
}Identifier;
3.3 Розробка лексичного аналізатора
3.3.1 Опис лексичного аналізатора.
Лексичний аналізатор є першою фазою компілятора. Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів для передачі в синтаксичний аналізатор. Всі символи вхідної послідовності розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. Вхiдна програма проглядається послідовно з початку до кінця. Базовi елементи, або лексичнi одиницi, роздiляються пробілами, знаками операцiй i спецiальними символами (новий рядок, знак табуляції), i таким чином видiляються та розпізнаються iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми – для місця помилки – та додаткова інформація.
При лексичному аналiзі виявляються i вiдзначаються лексичнi помилки (наприклад, недопустимi символи i неправильнi iдентифiкатори). Лексична фаза вiдкидає також i коментарi, оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
В даному курсовому проекті реалізовано прямий лексичний аналізатор, який виділяє з вхідного тексту програми окремі лексеми і на основі цього формує таблицю.
3.3.2Опис граф-схеми лексичного аналізатора
Робота лексичного аналізатора зображена на (Рис.3) і починається з відкриття і читання вхідного файлу з текстом програми (Блок №2). Далі перевіряється чи не був досягнутий кінець файлу (Блок №3). Якщо кінець файлу досягнутий то робота алгоритму завершується (Блок №21), якщо ні,то виділяється перший символ нової ликсеми (Блок №4) і перевіряється чи перший символ є ключовим словом(Блок №5).
Якщо перший символ ключове слово то виконується його збереження (Блок №6), і далі відбувається перевірка на функції розбору ідентифікаторів (Блок № 7), якщо ні то відбувається перевірка наступного символу (Блок №8). Потім відбувається перевірка чи перший символ 0 – 9 (Блок №9), якщо так, то відбуваеться виконання функції розбору числових констант(Блок №10), перевірка чи перший символ “ (Блок №11), якщо так то виконується функція розбору рядкових констант (Блок №12).
Потім перевіряється чи символ є оператором(Блок №13), якщо так то вібувається збереження до таблиці лексем(Блок №14). Після чого перевіряється чи є перший символ { (Блок №15), якщо так то виконується функція розбору коментарів (Блок №16). Далі перевіряється чи символ є розділювачем(Блок №17), якщо так то виконується зберігання до таблиці лексем (Блок №18).
Останній блок перевірки перевіряє чи перший символ не є жодним з вище перерахованих(Блок №19), якщо так то відповідно виконується функція виділення нерозпізнаних лексем(Блок №20). При досягненні кінця файлу (Блок №21), тобто якщо весь файл прочитано то лексичний аналізатор завершує свою роботу.
Рис .3-Граф-схема роботи лексичного аналізатора
3.3.3 Опис програми реалізації лексичного аналізатора
Програма по рядках читає вхідний файл. Прочитаний рядок передає як параметр функції Parser класу Parser.
Функція Parse() аналізує перший символ нової лексеми:
символ A-Z - то запускається функція ParseKeyWords()
символ a-z - то запускається функція ParseIdent()
cимвол 0-9 або -, - запускається функція ParseNum()
символ =,<,>,!,&,|,;, , ,(,) - відбувається збереження лексеми
символ \ - запускається функція ParseKoments()
символ “,то запускається функція ParseString()
символ не є жодним з вищезгаданих - запуск процедури ParseNoLeks()
Всі функції які використовує лексичний аналізатор зображені на ( рис.4) .
Рис.4- Функції лексичного аналізатора
В лексичному аналізаторі для розпізнання використовуються наступні функції:
Функція ParseKeyWords() виділяє послідовність символів, які можуть містити ключові слова і перевіряє чи ця послідовність символів є ключовим словом і якщо це ключове слово зберігає його, як лексему
Функція ParseIdent()виділяє послідовність символів, які можуть містити ідентифікатори і зберігає ідентифікатор
Функція ParseComments() перевіряє чи 2 символ теж */, то всі символи до кінця рядка вважає коментарем
Функція ParseNum()виділяє послідовність символів, які можуть містити числові константи і зберігає лексему
Функція ParseNoLex()шукає розділювач і вважає що всі символи, які вона виділила є нерозпізнаною лексемою
Функція ParseString() шукає символ завершення рядка і всі символи між початком і кінцем рядка вважає рядковою константою.
3.4 Розробка синтаксичного аналізатора
3.4. 1Опис програми реалізації синтаксичного аналізатора
Для виділення лексем використовуються правила задані регулярними виразами. Вхідна програма проглядається послідовно з початку. Початок тексту аналізується на відповідність певному регулярному виразові (блоки 5, 6, 7, 8, 9). При співпадінні виділена лексема записується при необхідності в таблицю лексем, змінних, стрічок чи генерується помилка і видаляється з початку тексту (блоки 10-18). Так повторюється доки вхідний текст не стане порожнім (блок 3).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись до лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо місця розташування відповідної лексеми у вхідному тексті (для локалізації місця помилки) та інша додаткова інформація.
При лексичному аналізі виявляються i відзначаються лексичні помилки (наприклад, недопустимі символи i неправильні iдентифiкатори). Лексична фаза відкидає також i коментарі, пробільні символи оскільки вони не мають ніякого впливу
19.05.2014 23:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора