Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки молоді та спорту України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
КУРСОВА РОБОТА
з предмету:
“Системне програмування”
на тему:
“ Розробка системних програмних модулів та компонент систем програмування.
Розробка транслятора з вхідної мови програмування”
Завдання на курсову роботу
ВАРІАНТ 41.
Розробити транслятор заданої вхідної мови програмування, до якої висуваються наступні вимоги. Реалізувати тип даних: знаковий цілочисельний тип розміром 4 байти. Реалізувати можливість використання змінних з іменами довжиною 9 символів (Up8 перший символ _ ), ключові слова нижнього регістру. Реалізувати арифметичні операції: додавання, віднімання, множення, ділення, взяття остачі від ділення. Реалізувати логічні операції: НЕ, І, АБО та операції порівняння: більше, менше, рівне, не рівне. Реалізувати наступні структури управління: оператор присвоєння, оператори блоку, оператор виводу, оператор вводу умовою, оператор розгалуження if-then [-else], реалізувати оператор присвоєння, оператори блоку (Body-End), та розділ оголошення змінних.
Цільова мова транслятора: асемблер (i86). Для отримання виконавчого файлу користувачеві скористатися програмами tasm.exe (компілятор мови асемблера) і tlink.exe (редактор зв’язків). Мова розробки компілятора: ANSI C або C++ (платформа win32). Реалізувати інтерфейс командного рядка. На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування. На виході розробленого транслятора мають з’являтися наступні файли: файл з повідомленнями про помилки (або про їх відсутність), файл на мові асемблера.
Анотація
В даному курсовому проекті розроблено транслятор з вхідної мови програмування B41. Транслятор розроблений в середовищі програмування Visual Studio 10.0, код якого подано в цій записці. Також тут подано огляд існуючих методів розробки трансляторів, детальний опис мови, описано процес розробки програми транслятора на рівні тексту програми.
До проекту додано результати тестування програми та текст програми транслятора.
Зміст
Вступ 5
1.Аналітичний розділ……………………………………………………………..7
2. Формальний опис вхідної мови програмування 17
2.1 Правила написання правил у розширеній нотації Бекуса-Наура: 18
2.2 Формальний опис заданої вхідної мови в термінах BNF: 18
2.3 Повний граф граматичного розбору ………………… …………………...20
3. Розробка транслятора вхідної мови програмування 21
3.1 Розробка лексичного аналізатора 21
3.2 Граф (спрощений) роботи лексичного аналізатора……………………….23
3.3 Розробка синтаксично-семантичного аналізатора та генератора коду….24
3.3.1 Розробка синтаксичного аналізатора 24
3.3.2 Розробка семантичного аналізатора 26
3.3.3 Розбір математичних виразів 26
3.3.4 Таблиця пріоритетів операцій 27
3.3.5 Оптимізатор коду 28
3.3.6 Розробка генератора коду 29
3.3.7 Блок-схема Синтаксично-семантичного аналізатора (фактично
спрощена схема роботи транслятора)………………………………….30
4. Опис інтерфейсу та інструкція користувачеві 32
5. Тестування та відлагодження програми 33
Висновок 34
Список використаної літератури 35
Додатки 36
Додаток 1 Лістинг програми 36
Додаток 2: Результат тестування програми 66
Вступ
Транслятори та компілятори є одною з невід’ємних частин системного програмного забезпечення. Одним із їх завдань є переведення написаного тексту програми у машинний код чи код іншої мови програмування, який повинен відповідати комп‘ютерній системі. Оскільки теперішній час – час стрімкого розвитку комп‘ютерної техніки, то створений машинний код з часом стає застарілим, тобто не відповідає принципу оптимального використання апаратних ресурсів. І одним із способів запобігання цієї проблеми стало створення нових трансляторів, які б відповідали потребам теперішнього часу.
Проблема трансляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою транслятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього він має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати код.
Транслятором називається програма перекладу (трансляції) початкової програми, записаною вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна – вихідною, то такий транслятор називається компілятором.
Транслятори дозволяють створювати об`єктні модулі, які пізніше, після етапу зв`язування відлагоджувачем, перетворюються у виконавчі файли.
Потреба різноманіття трансляторів дуже важлива, це прямо залежить від вхідної мови, яку він перекладає. Кожна з них реалізує клас задач, необхідних для користувача.
В даній курсовій роботі реалізується програма, яка транслює файл з деякої віртуальної мови, заданої завданням, в файл Асемблера з подальшою його компіляцією і створенням виконавчого файлу. Крім того, дана програма перевіряє на помилки (синтаксичні, семантичні, лексичні) вхідний файл і при їх присутності видає у файл повідомлення про помилки і зупиняє свою роботу до їх виправлення.
На прикладі даної програми нами вивчалася можливість створення достатньо потужних трансляторів в мову низького рівня (наприклад, Асемблер), - завдання, реалізація якого є достатньо потрібною на сучасному етапі розвитку програмування.
Метою виконання даної курсової роботиє освоєння структури трансляторів та основних засад їх створення. Виконуючи цю курсову роботу я закріплю теоретичні знаня та практичні навички із системного програмування.
Аналітичний розділ
Введення в компіляцію
Транслятором називається програма перекладу (трансляції) початкової програми, записаної вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна – вихідною, то такий транслятор називається компілятором. Програма, записана мовою високого рівня, найчастіше має два етапи – компіляції та виконання. На першому початкова програма перекладається машиною А в об`єктну програму мовою машини, на другому вона заноситься в пам`ять машини В. При її виконанні, за необхідності вводяться початкові дані та виводяться результати. Якщо А і В –різні машини, то говорять, що на ЕОМ А виконується крос-компіляція, і такий транслятор називається крос-компілятором.
Інтерпретатором є різновид транслятора для перекладу початкової програми в програму, записану простою проміжною алгоритмічною мовою, та для її виконання. Деякі програми в проміжну форму не перекладається, а відразу виконуються. Інтерпретатор простіший від компілятора, але працює повільніше.
Транслятор з різними вхідною та об`єктною мовами високого рівня називається препроцесором. Як частина компілятора, він при бажанні може використовуватися самостійно для розширення можливостей конкретної мови програмування (наприклад мови Сі).
Структура компілятора
Компілятор – це велика за розмірами програма. Складання компілятора ділять на фази, на яких перетворюють одне зображення програми в інше.
Фази лексичного (ЛА) та синтаксичного (СА) аналізів розкладають початкову програ-му на частини. Генерація проміжного коду (ГПК), оптимізація (ОК) та генерація коду (ГК) машини синтезують об`єктну програму. Керування таблицями (КТ) та обробка помилками (ОП) використовуються на всіх фазах компіляції (див. рис.1).
Лексичний аналіз об`єднує літери в лексеми – службові слова, ідентифікатори, знаки операцій та пунктуації. Лексеми можна кодувати цілими числами, наприклад, do-одиницею, “+” – двійкою, ідентифікатор – трійкою, константу – четвіркою тощо. До коду лексем ідентифікаторів і констант додається ще одна величина – вид чи значення лексеми.
Синтаксичний аналіз групує лексеми в синтаксичні структури, які можуть бути складовими інших синтаксичних структур; наприклад, А+В може входити в оператор чи вираз. Як рекурсивні структури даних, вони зображуються (явно чи неявно) у формі дерева з лексемами в вузлах і з позначенням синтаксичних конструкцій у внутрішніх вузлах. Крони піддерев відтворюють частини програми відповідної синтаксичної конструкції. Генерація проміжного коду створює послідовності найпростіших інструкцій (команд), складених з коду операцій та кількох операндів. Ці інструкції відрізняються від команд асемблера тим, що в них не вказуються конкретні регістри ЕОМ, необхідні для використання. Необов`язкова оптимізація коду має призначенням створення проміжного коду, за якого об`єктна програма буде ефективніша щодо часу виконання та обсягу потрібної пам`яті. У фазу ГК складається об`єктний код. Для цього розв`язуються такі задачі: розміщення даних у пам`яті, вибір коду доступу до них та вибір регістрів для обчислень.
Керування таблицями розв`язує задачу зберігання імен, використаних у програмі, інформації про них (наприклад, типу даних) та доступу до цієї інформації. Переважно використовується таблиця символів як структура даних. Обробка помилок відбувається кожного разу, коли помічені дефекти у програмі. Вона полягає у формуванні повідомлення про помилку та її нейтралізації, тобто виправленні інформації для передачі наступній фазі, щоб остання могла виконуватися. Основна мета – за одну обробку програми компілятором виявити максимум помилок.
Проходи компілятора
При реалізації компілятора одна чи декілька фаз (можлива частина фази) об’єднуються в програмні модулі, названі проходами. За кожного проходу прочитується з файла початкова програма чи результат попереднього проходу; здійснюється перетворення, задане його фазами; записується результат у проміжний або в результатний файл. Число проходів та методика об`єднання фаз у прохід визначаються особливостями вхідної мови та ЕОМ. Так, у мові ПЛ-1 описи даних можуть з`явитися після їхнього використання, як наприклад у групі операторів goto M; . . . ; M: a:=b+c;, де до ідентифікатора М звертаються раніше, ніж до опису. За такої ситуації скласти повністю код для оператора goto M; не можна до обробки опису М (оператора М: а:=b+c). Реалізація таких мов потребує щонайменше двох проходів. Багатопрохідний компілятор займає менше оперативної пам`яті ЕОМ від однопрохідного, але працює повільніше через необхідність багаторазового читання та записування файлів.
Модульна організація компілятора відтворена у трипрохідному неоптимізуючому компіляторі (рис.2.), що працює з чотирма поданнями (4 файла): початковою програмою – ланцюжком символів; послідовністю лексем; проміжним кодом і результатним списком машинних команд. Тут синтаксичний аналіз та генерація проміжного коду об`єднані в один прохід.
Кілька проходів можна скомбінувати в один, виконуючи їх паралельно із взаємною синхронізацією – таким чином створюється однопрохідний компілятор (рис.3.) Результат одного проходу, потрібний іншому, завдяки синхронізації та буферам дозволяє побудувати необхідний інтерфейс між фазами. Як правило, в однопрохідному компіляторі ведучою є фаза синтаксичного аналізу, яка кожного разу, коли потрібна їй лексема, запрошує фазу лексичного аналізу, керує генерацією проміжного коду, передає команди цього коду генера-тору коду для створення об`єктної програми. Проблеми, що виникають при використанні елемента даних раніше його означення за єдиного проходу, можна розв`язати методом оберненого заповнення: при генерації коду для команди goto M; за невизначеного М формується неповна команда і запам`ятовується її місце, а в момент визначення мітки М заповнюються всі порожні місця. Проте цей метод працює тоді, коли віддаль між точками використання та означення імені невелика.
Засоби побудови компіляторів
Існують спеціальні засоби (компілятори компіляторів, генератори компіляторів тощо) для полегшення конструювання компіляторів. Ідеальною вважається ситуація, коли є програма (або система програм), яка автоматично будує компілятор, маючи на вході описи лексики, синтаксису вхідної мови, результатів перетворень синтаксичних конструкцій та опис цільової машини.
Для полегшення побудови компіляторів розроблені такі основні інструментальні засоби: генератор лексичних аналізаторів, в якому інформація про лексеми задається регулярними виразами, а можливі дії обробки – операторами мови Сі; генератор, який за граматикою початкової мови створює СА з діями обробки; засоби генерації коду – спеціальні мови, зручні для опису процесу генерації машинного коду.
Основна проблема при реалізації мови програмування полягає в урахуванні суперечливих умов. Тому при складанні компілятора доводиться йти на компроміси, беручи до уваги, як буде використовуватися компілятор; що важливіше – швидкість компіляції чи якість об’єктної програми; створюється компілятор для нової ЕОМ чи ні; які інструментальні засоби можна залучати. Проект повинен давати можливість просто вносити зміни.
В реалізації мов високого рівня часто використовується специфічний тільки для компіляції засіб “розкрутки”. З кожним компілятором завжди зв`язані три мови програмування: Х – початкова, Y – об`єктна та Z – інструментальна. Компілятор перекладає програми мовою Х в програми, складені мовою Y, при цьому сам компілятор є програмою написаною мовою Z (позначатимемо компілятор як ).
Припустимо, що треба реалізувати нову мову високого рівня L для двох ЕОМ подібної організації А та В, і обидві ЕОМ не мають якихось інструментальних засобів для прискорення процесу створення компілятора. Покажемо, що треба зробити, щоб побудувати . Для цього виділимо в мові L підмножину S, достатню, щоб створити компілятор для перекладу з мови L на мову А, і побудуємо та відтестуємо . Потім напишемо на підмножині S компілятор для перекладу з мови L на мову А. Пропустивши програму через компілятор одержимо необхідний компілятор : ((
Реалізація після цього мови L для ЕОМ В значно простіша – треба переписати компілятор в компілятор ; транслювати програму в програму компіля-тором : ((
повторно транслювати програму компілятором і одержати потрібний компілятор : ((
Спрощена модель компілятора
Перевід програм, написаних на мовах програмування високого рівня на мову машинних кодів, виконуваних комп’ютером, здійснюється спеціальними програмами, які називаються трансляторами. За способом роботи транслятори поділяються на компілятори та інтерпретатори. Компілятор повинен виконати наступні кроки:
1. Розпiзнавати визначені рядки та окремі символи як базовi елементи мови.
2. Розпізнавати визначені комбiнацiї елементiв як синтаксичнi одиницi i iнтерпретувати їх значення.
3. Згенерувати вiдповiднi об’єктнi коди.
Компіляція може проводитись в декілька переглядів вихідного файла.
На першому перегляді відбувається лексичний аналіз. Компілятор виділяє окремі слова і символи, пропускаючи роздільники і коментарі, створює таблицю лексем. Другий перегляд відповідає синтаксичній фазі. Переглядається таблиця лексем, виділяються ідентифікатори і заносяться в таблицю змінних разом з їх типами, генерується об’єктна програма. Перший і другий перегляд можна об’єднати в один.
Починаючи з третього перегляду, відбуваються фази оптимізації, генерації асемблер-ного коду та інші.
На фазі лексичного аналізу вихідна програма, що являє собою потік символів, розбивається на лексеми – слова відповідно до визначення мови. Основним формалізмом, що лежить в основі реалізації лексичних аналізаторів, є кінцеві автомати і регулярні вирази. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, що викликається синтаксичним аналізатором, або як повний прохід, результатом якого є файл лексем. У процесі виділення лексем, лексичний аналізатор може, як самостійно будувати таблиці імен і констант, так і видавати значення для кожної лексеми при черговому зверненні до нього. У цьому випадку таблиця імен будується в подальших фазах (наприклад, в процесі синтаксичного аналізу). На етапі лексичного аналізу виявляються деякі (найпростіші) помилки (недопустимі символи, невірний запис чисел, ідентифікаторів та інше).
Основна задача синтаксичного аналізу – розбір структури програми. Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблицю імен. У процесі синтаксичного аналізу також виявляються помилки, пов’язані зі структурою програми. До синтаксичного аналізу входить і семантичний, на етапі якого перевіряється правильність тексту вихідної програми з точки зору семантики вихідної мови. Окрім перевірки, семантичний аналіз повинен виконувати перетворення тексту, що потребує семантика вихідної мови (наприклад, добавлення функцій неявного перетворення типів).
Після успішного завершення синтаксичного аналізу програма може бути переведена у внутрішнє представлення. Це робиться для цілей оптимізації і/або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати незалежний, від конкретної архітектури, компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. Для внутрішнього представлення, може використовуватися префіксна або постфіксна форма запису, орієнтований граф, трійки, четвірки і інші.
Підготовка до генерації коду – це фаза, на якій компілятором виконуються попередні дії, які безпосередньо пов’язані з синтезом тексту результуючої програми, але ще не ведуть до отримання тексту на результуючій мові. Як правило в цю фазу входять дії, що пов’язані з ідентифікацією елементів мови, розподіленням пам’яті та інше.
Генерація коду – це фаза, яка безпосередньо зв’язана з породженням команд, що складають конструкції результуючої мови і в цілому текст результуючої програми. Окрім цього, фаза генерації коду включає в себе оптимізацію – процес, що пов’язаний з опрацюванням вже існуючого результуючого коду. Інколи оптимізацію виділяють в окрему фазу компіляції. Фаз оптимізації може бути декілька. Оптимізацію звичайно ділять на машинно-залежну і машинно-незалежну, локальну і глобальну. Частина машинно-залежної оптимізації виконується на фазі генерації коду. Глобальна оптимізація намагається брати до уваги структуру всієї програми, локальна – тільки невеликих її фрагментів. Глобальна оптимізація засновується на глобальному потоковому аналізі, який виконується на графі програми і представляє по суті перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як міжпроцедурний аналіз, міжмодульний аналіз, аналіз областей життя змінних і т.д.
Лексичний аналіз
Основна задача лексичного аналізу – розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
Звичайно всі лексеми діляться на класи. Прикладами таких класів є числа, ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяка кінцева підмножина ідентифікаторів. З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох типів: для синтаксичного аналізатора, працюючого услід за лексичним, істотна інформація про послідовності класів лексем, обмежувачів та ключових слів, а для семантичного аналізу, працюючого услід за синтаксичним, важлива інформація про конкретні значення окремих лексем (ідентифікаторів, чисел і т.д.). Тому загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема. Якщо виділена лексема – обмежувач, то він (точніше, деяка його ознака) видається як результат лексичного аналізу. Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його до ключових слів. Якщо так, то видається ознака відповідного ключового слова, якщо немає – видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Якщо виділена лексема належить якому-небудь з інших класів лексем (число, рядок і т.д.), то видається ознака класу лексеми, а значення лексеми зберігається.
Лексичний аналізатор може працювати або як самостійна фаза трансляції, або як підпрограма, працююча за принципом «дай лексему». У першому випадку виходом лексичного аналізатора є файл лексем, у другому лексема видається при кожному зверненні до лексичного аналізатора (при цьому, як правило, тип лексеми повертається як значення функції, а значення передається через глобальну змінну). З точки зору формування значень лексем, належних класам лексем, лексичний аналізатор може або просто видавати значення кожної лексеми і в цьому випадку побудова таблиць переноситься на більш пізні фази, або він може самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.). У цьому випадку, як значення лексеми видається покажчик на вхід у відповідну таблицю.
Робота лексичного аналізатора описується формалізмом кінцевих автоматів. Однак безпосередній опис кінцевого автомата незручний практично. Тому для опису лексичних аналізаторів, як правило, використовують або формалізм регулярних виразів, або формалізм контекстно вільних граматик. По опису лексичного аналізатора у вигляді регулярних виразів або автоматної граматики будується кінцевий автомат, що розпізнає відповідну мову.
Синтаксичний аналіз
Синтаксичний аналіз – це процес, в якому досліджується таблиця лексем, або кожна окрема лексема, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що явно сформульовані у визначені синтаксису мови. Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його у відповідності до граматики вихідної мови. Але, в граматиці вихідної мови, як правило не вказується, які конструкції слід вважати лексемами. Прикладами конструкцій, які як правило розпізнаються на фазі лексичного аналізу, можуть бути ключові слова, константи та ідентифікатори. Але ці ж самі конструкції можуть розпізнаватися і синтаксичним аналізатором. На практиці не існує конкретного правила, що визначає, які конструкції повинні розпізнаватися на фазі лексичного аналізу, а які на фазі синтаксичного. Як правило, це визначає розробник компілятора, виходячи з технологічних аспектів програмування, а також синтаксису та семантики вхідної мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вихідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в тексті програми, встановити тип та правильність кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних символів заданій мові. Але, задача синтаксичного аналізу, не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати, деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції, інформацію про знайдені і розібрані синтаксичні конструкції.
2. Формальний опис вхідної мови програмування
Одною з перших задач, що виникають при побудові транслятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису. В курсовій роботі використано розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).
Далі приведено опис вхідної мови програмування згідно варіанту. А саме: лексеми, оператори, арифметичні знаки і логічні оператори, тип змінних і їх довжина:
- тип даних: знаковий цілий 4 байти; - змінні довжиною максимум 9 символів; - арифметичні операції над цілими: “+”; “-“; “mul”; “div”; “mod”; - символи групування арифметичних операцій: “(”, “)”; - операції порівняння над числами: “eg”; “ne”; “<=”; “>=”; - логічні операції над числами: “not”; “and”; “or”; - оператор присвоєння: “::=” ; - оператори блоку: “Body”, “End”;
- оператор виводу “streamout”;
- оператор вводу “streamin”; - оператор розгалуження: “if-then [-else]”.
Body
End
;
::=
+
-
*
/
%
(
)
<=
>=
eg
ne
,
integer16
not
and
or
if
Data
streamout
streamin
Name
then
else
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z) символ пробілу (“ ”) та символ табуляції. Всього: 26 + 10 + 52 + 2 = 91 термінальних виразів. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми.
2.1 Правила написання правил у розширеній нотації Бекуса-Наура
Для опису заданої вхідної мови використаємо розширену нотацію Бекуса-Наура, з наступними правилами написання правил:
- нетермінальні вирази записуються у кутових дужках: “<”, “>” ; - термінальні вирази записуються жирним шрифтом або у подвійних лапках; - усі нетермінальні вирази мають бути “розкриті” за допомогою термінальних; - сивол “::=” відділяє праву частину правила від лівої; - символ “|” розділяє альтернативи; - сиволи “[”, “]” означають необов’язковість (вираз в дужках може бути відсутнім); - сиволи “{”, “}” означають повторення.
2.2 Формальний опис заданої вхідної мови в термінах BNF
Формальний опис заданої вхідної мови подано в таблиці 1.
Таблиця 1. Опис вхідної мови в термінах розширеної нотації Бекуса-Наура
<program>
::= <statement>
<statement>
::= {[<variable>]}“Body“{[ <operator>]}”End”
<variable>
::= <type> <ident>{“,”[<ident>]};
<operator>
::= <bind> | <condition>|<streamin>|<streamout>
<block>
::=”Body“{[{[<operator>]}|{[<bind>]}]}”End”|<operator>”;”|<bind>”;”
<condition>
::= “if” ”(“ <expression>”)” ”then”<block>”else” <block>
<bind>
::= <ident> = <expression>;
<type>
::=integer16
<ident>
::= <letter> [{<letter>}]|[{number}]
<int_const>
::= [“-“]< number > [{<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|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
<expression>
::= <num_expression> | <bool_expression>
<num_expression>
::= [un_m]<operand> [{<num_operation> <operand>}]
<bool_expression>
::= ( <operand> <bool_operation> <operand> ) | <ident>
<operand>
::= ( <num_expression> ) | <ident> | <int_const>.
<num_operation>
::= mul | div | + | - | mod
<bool_operation>
::= <= | >= | eg | ne | not | and | or
<un_m>
::= -
Формальний опис складено за допомогою 19 нетермінальних виразів.
2.3Повний граф граматичного розбору
На рис.4 подано повний граф граматичного розбору, на якому вершиною виступає не термінальний символ <program>, його синами є не термінальні символи <data>, <data_blok>, <code_blok> і термінальні: Name, Body, End. За аналогічним принципом можна розібрати усі вузли графа, окрім листків. Усі вузли графа є термінальними символами.
Рис.4. Повний граф граматичного розбору
3. Розробка транслятора вхідної мови програмування
3.1 Розробка лексичного аналізатора
Основна задача лексичного аналізу – розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
Звичайно всі лексеми діляться на класи. Прикладами таких класів є числа, ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяка кінцева підмножина ідентифікаторів. З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох типів: для синтаксичного аналізатора, працюючого услід за лексичним, істотна інформація про послідовності класів лексем, обмежувачів та ключових слів, а для семантичного аналізу, працюючого услід за синтаксичним, важлива інформація про конкретні значення окремих лексем (ідентифікаторів, чисел і т.д.). Тому загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема. Якщо виділена лексема – обмежувач, то він (точніше, деяка його ознака) видається як результат лексичного аналізу. Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його до ключових слів. Якщо так, то видається ознака відповідного ключового слова, якщо немає – видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Якщо виділена лексема належить якому-небудь з інших класів лексем (число, рядок і т.д.), то видається ознака класу лексеми, а значення лексеми зберігається.
Лексичний аналізатор може працювати або як самостійна фаза трансляції, або як підпрограма, працююча за принципом «дай лексему». У першому випадку виходом лексичного аналізатора є файл лексем, у другому лексема видається при кожному зверненні до лексичного аналізатора (при цьому, як правило, тип лексеми повертається як значення функції, а значення передається через глобальну змінну). З точки зору формування значень лексем, належних класам лексем, лексичний аналізатор може або просто видавати значення кожної лексеми і в цьому випадку побудова таблиць переноситься на більш пізні фази, або він може самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.). У цьому випадку, як значення лексеми видається покажчик на вхід у відповідну таблицю.
Робота лексичного аналізатора описується формалізмом кінцевих автоматів. Однак безпосередній опис кінцевого автомата незручний практично. Тому для опису лексичних аналізаторів, як правило, використовують або формалізм регулярних виразів, або формалізм контекстно вільних граматик. По опису лексичного аналізатора у вигляді регулярних виразів або автоматної граматики будується кінцевий автомат, що роз
Сканер, або лексичний аналізатор – по суті набір підпрограм, які дозволяють працювати з вхідним текстом на рівні лексем, і не звертатись на вищих стадіях компіляції до таких деталей, як зчитування тексту програми з файлу, чи, грубо кажучи, вирішувати, що робити, якщо закінчилась зчитана стрічка. Також сканер повинен мати в своєму складі засоби, які виконують різні допоміжні функції, на зразок лексикологічного порівняння стрічок тексту і т. ін. Ці задачі можна вирішувати або самостійно, або покласти їх виконання на стандартні бібліотеки мови “C”. Весь комплекс засобів, що необхідні для лексичного аналізу вхідних текстів на заданій мові програмування, повністю представлений в складі транслятора розробленого в даній роботі.
Текст програми зчитується в глобальний символьний масив line, вказівник всередині її на поточний сивол також глобальна змінна lptr. Нижче наведений список функцій, які можна віднести до лексичного аналізатора та коротке пояснення її роботи.
void readString(void) - зчитує стрічки з вхідного потоку, поки не зчитає непусту стрічку;
void setlptr(void) - встановлює lptr на перший непустий символ в потоці;
int isToken(char *token) - перевіряє, чи лексема token є наступною у вхідному потоці;
void nextChar(void) - встановлює lptr на наступний непустий символ у вхідному потоці;
void nextToken(void) - встановлює lptr на наступну лексему у вхідному потоці;
char getChar(void) - отримує ненульовий символ з вхідного потоку;
char *getIdent(void) - отримує ідентифікатор з вхідного потоку;
char *getNumb(void) - отримує ціле число з вхідного потоку.
3.2 Граф роботи лексичного аналізатора.
Тепер можна розглянути сааме ядро, тобто суть роботи розроблюваного транслятора. Принципи роботи лексичного аналізатора подано у вигляді спрощеного графа (Рис.5)
Рис.5. Спрощений граф роботи лексичного аналізатора
Вузли:
1 – Файл з вхідними кодами програми розбивається на стрічки. Читання даних з нього іде стрічками.
2 – Коли в стрічці знаходиться перша лексемо то на неї ставиться вказівник.
3 – Лексема зчитується, перевіряється на помилки, а далі обробляється згідно змісту.
4 – Генерація файлу помилок. Запис помилок. Вихід з програми.
5 – Обробляються всі вирази та математичні оператори. Генерується їх асемблерний код.
6 – відбувається встановлення вказівника на наступну стрічку.
3.3 Розробка синтаксично-семантичного аналізатора та генератора коду.
Оскільки транслятор, реалізований мною у даній курсовій роботі є однопрохідним, то синтаксичний і семантичний аналізатори та генератор коду є тісно пов’язані один з одним.
3.3.1 Розробка синтаксичного аналізатора
Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.
Синтаксичний аналізатор – це частина транслятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Крім того, важливою функцією є локалізація синтаксичних помилок. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але задача синтаксичного аналізу не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції інформацію про знайдені і розібрані синтаксичні конструкції, якщо відокремлюється фаза генерації об’єктного коду.
Кожна мова програмування має правила, які визначають синтаксичну структуру коректних програм. В Pascal, наприклад, програма створюється з блоків, блок – з інструкцій, інструкції – з виразів, вирази – з токенів і т.д. Синтаксис конструкцій мови програмування може бути описаний за допомогою контекстно-вільних граматик або нотації БНФ (Backus-Naur Form, форма Бекуса-Наура).
Граматика дає точну і при цьому просту для розуміння синтаксичну специфікацію мови програмування.
Правильно побудована граматика додає мові програмування структуру, яка сприяє полегшенню трансляції початкової програми в об'єктний код і виявленню помилок. Для перетворення описів трансляції, заснованих на граматиці мови, в робочій програмі є відповідний програмний інструментарій.
З часом мови еволюціонують, збагатившись новими конструкціями і виконуючи нові задачі. Додавання конструкцій в мову виявиться більш простою задачею, якщо існуюча реалізація мови заснована на його граматичному описі.
Є три основні типи синтаксичних аналізаторів граматик. Універсальні методи розбору, такі як алгоритми Кока-Янгера-Касамі або Ерлі, можуть працювати з будь-якою граматикою. Проте ці методи дуже неефективні для використання в промислових компіляторах. Методи, які звичайно використовуються в компіляторах, класифікуються як низхідні (зверху вниз, top-down) або висхідні (з низу до верху, bottom-up). Як видно з назв, низхідні синтаксичні аналізатори будують дерево розбору зверху вниз (до листя), тоді як висхідні починають з листя і йдуть до кореня. В обох випадках вхідний потік синтаксичного аналізатора сканується посимвольний зліва направо. Найефективніші низхідні і висхідні методи працюють тільки з підкласами граматик, проте деякі з цих підкласів, такі як LL- і LR-граматики, достатньо виразні для опису більшості синтаксичних конструкцій мов програмування. Реалізовані вручну синтаксичні аналізатори частіше працюють з LL-граматиками. Синтаксичні аналізатори для дещо більшого класу LR-граматик звичайно створюються за допомогою автоматизованих інструментів. Будемо вважати, що вихід синтаксичного аналізатора є деяким представленням дерева розбору вхідного потоку токенів, виданого лексичним аналізатором. На практиці є безліч задач, які можуть супроводжувати процес розбору, - наприклад, збір інформації про різні
19.11.2013 19:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора