Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмування.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2018
Тип роботи:
Курсова робота
Предмет:
Системне програмування та операційні системи
Варіант:
142
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
КУРСОВА РОБОТА
з предмету “Системне програмування”
на тему “Розробка системних програмних модулів та компонент систем програмування.”
Варіант 142
АНОТАЦІЯ
В даній курсовій роботі розроблено транслятор вхідної мови програмування згідно заданого варіанту. Транслятор написанний на мові C#, та поданий у пояснювальній записці. В пояснювальній записці подано детальний опис мови, огляд існуючих методів розробки трансляторів, а також описано процес розробки програми транслятора на рівні блок-схем і тексту програми. До проекту додано результати тестування програми.
ЗМІСТ
АНОТАЦІЯ
ЗМІСТ
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
ВСТУП
1.ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ
1.1. Введення в компіляцію
1.2. Структура компілятора
1.3. Проходи компілятора
1.4. Засоби побудови компіляторів
1.5. Спрощена модель компілятора
1.6. Лексичний аналіз
1.7. Синтаксичний аналіз
2.ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
2.1. Деталізований опис вхідної мови в термінах розширеної нотації
Бекуса-Наура
2.2 Опис термінальних символів та ключових слів
3.РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
3.1. Вибір технології програмування
3.2. Проектування таблиць транслятора та вибір структур даних
3.3. ЛЕКСИЧНИЙ АНАЛІЗАТОР
3.3.1. Розробка лексичного аналізатора
3.3.2. Розробка граф-схеми алгоритму
3.4. СИНТАКСИЧНИЙ ТА СЕМАНТИЧНИЙ АНАЛІЗАТОР
3.4.1. Розробка синтаксичного та семантичного аналізатора
3.4.2 Розробка дерев граматичного розбору
3.4.3. Розробка граф-схеми алгоритму
3.5. ГЕНЕРАТОР КОДУ
3.5.1. Розробка генератора коду
3.5.2. Опис програми реалізації генератора коду
4.ОПИС ІНТЕРФЕЙСУ ТА ІНСТРУКЦІЇ КОРИСТУВАЧА
4.1. Транслятор
5.ВІДЛАГОДЖЕННЯ ТА ТЕСТУВАННЯ ПРОГРАМИ
5.1. Виявлення лексичних помилок
5.2. Виявлення синтаксичних помилок
5.3. Загальна перевірка коректності роботи транслятора
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТКИ
А. Лістинг програм
А1. Файл «Parser.cs»
А2. Файл «Syntactic.cs»
А3. Файл «Generation.cs»
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
1. Цільова мова транслятора асемблер (iх86).
2. Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами ml.exe (MASM32)
3. Мова розробки транслятора: С#
4. Реалізувати оболонку або інтерфейс з командного рядка.
5. На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
6. На виході розробленого транслятора мають створюватись чотири файли:
файл з повідомленнями про помилки (або про їх відсутність);
файл на мові асемблера;
об’єктний файл;
виконавчий файл.
7. Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування.
Зауваження:
1) В кожному завданні передбачається блок оголошення змінних;
2) В кожному завданні обов’язковим є оператор присвоєння та оператор типу – блок;
3) Оператори можуть бути довільної вкладеності і в любій послідовності.
Таблиця 1. Опис вхідної мови програмування.
Опис
Синтаксис
Приклад
Блок тіла програми
Startprogram
Variable…;Startblok - Endblok
Startprogram
Variable<опис змінних>;
Startblok<тіло програми>
Endblok
Оператори вводу-виводу
Get
Put
Get(_A); { змінна }
Put(_A+_B);
Put(“рядок”);
Оператор присвоєння
::
_A::1; _Aa::_A+3;
Оператор
If (Бесик)
If(_A>0)
Startblok
Put(“cycle while”);
Endblok
Регістр ключових слів
Up-Low перший символ Up
Startprogram
Регістр ідентифікаторів
Up-Low2 перший символ _
_A, _Aa
Арифметичні операції
++;
--;
**;
Div;
Mod
_C<- _A ++ _B;
_C<- _A -- _B;
_C<- _A ** _B;
_C<- _A Div _B;
_C<- _A Mod _B;
Операції порівняння
=;
<>;
>;
<
If (_A = _b)
Логічні операції
Not;
And;
Or
_C <-_A Not _B;
_C <-_A And _B;
_C >>_A Or _B;
Типи даних
Longint
Boolean
...
Variable Longint _A, _AB<-2,
...
Коментар
{ }
{ Coment }
ВСТУП
В даний час штучні мови, що використовують для опису предметної області текстове представлення, широко застосовуються не тільки в програмуванні, але і в інших областях. З їх допомогою описується структура всіляких документів, тривимірних віртуальних світів, графічних інтерфейсів користувача і багатьох інших об'єктів, використовуваних в моделях і в реальному світі. Для того, щоб ці текстові описи були коректно складені, а потім правильно розпізнані і інтерпретовані, використовуються спеціальні методи їх аналізу і перетворення. У основі методів лежить теорія мов і формальних граматик, а також теорія автоматів. Програмні системи, призначені для аналізу і інтерпретації текстів, називаються трансляторами.
Даний документ є запискою пояснення до курсового проекту по курсу «Системне програмування», яка виконується з метою закріплення теоретичних знань і придбання практичних навиків проектування окремих компонентів системного програмного забезпечення ЕОМ.
Відповідно до варіанту завдання необхідно спроектувати трансляор для деякої власної мови програмування. Основна увага при цьому приділяється вивченню методів розбору, організації таблиць, розміщенню елементів в пам'яті, представленню типів даних.
Програма на «нашій» мові, підтримувана транслятором, відповідно до завдання може містити:
- опис змінних цілого типу “Longint” і арифметичні вирази з ними
- оператори “If”
- безформатні оператори введення-виведення “Get”, “Put”
Результатом трансляції є файл-програма асемблера, по діях аналогічна програмі на «нашій» мові. Транслятор написаний на мові програмування С# .
На сьогоднішній день існує досить багато мов програмування. Наприклад:
- традиційні Fortran,
- «універсальні мови» (Паскаль, Сі, Модула-2, Ада та інші),
- спеціалізовані (наприклад, мова обробки облікових структур Лісп).
Транслятори становлять істотну частину програмного забезпечення ЕОМ. На сьогодні існує досить багато мов програмування. Нарівні з традиційними мовами, такими, як Fortran, широке поширення отримали так звані «універсальні мови» (Паскаль, Сі, Модула-2, Ада та інші), а також деякі спеціалізовані (наприклад, мова обробки облікових структур Лісп).
Постійно зростає потреба в нових трансляторах це пов’язано з бурхливим розвитком архітектури ЕОМ. Цей розвиток йде у різних напрямах. Удосконалюється стара архітектура, як в концептуальному відношенні, так і по окремих, конкретних лініях. Внаслідок розвитку різноманітних архітектур створюються нові машини, які вимагають створення трансляторів з використанням абсолютно нових ідей.
1. ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ
1.1. Введення в компіляцію
Транслятором називається програма перекладу (трансляції) початкової програми, записаної вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна – вихідною, то такий транслятор називається компілятором. Програма, записана мовою високого рівня, найчастіше має два етапи – компіляції та виконання. На першому початкова програма перекладається машиною А в об`єктну програму мовою машини, на другому вона заноситься в пам`ять машини В. При її виконанні, за необхідності вводяться початкові дані та виводяться результати. Якщо А і В –різні машини, то говорять, що на ЕОМ А виконується крос-компіляція, і такий транслятор називається крос-компілятором.
Інтерпретатором є різновид транслятора для перекладу початкової програми в програму, записану простою проміжною алгоритмічною мовою, та для її виконання. Деякі програми в проміжну форму не перекладається, а відразу виконуються. Інтерпретатор простіший від компілятора, але працює повільніше.
Транслятор з різними вхідною та об`єктною мовами високого рівня називається препроцесором. Як частина компілятора, він при бажанні може використовуватися самостійно для розширення можливостей конкретної мови програмування (наприклад мови Сі).
1.2. Структура компілятора
Компілятор – це велика за розмірами програма. Складання компілятора ділять на фази, на яких перетворюють одне зображення програми в інше.
Фази лексичного (ЛА) та синтаксичного (СА) аналізів розкладають початкову програму на частини. Генерація проміжного коду (ГПК), оптимізація (ОК) та генерація коду (ГК) машини синтезують об`єктну програму. Керування таблицями (КТ) та обробка помилками (ОП) використовуються на всіх фазах компіляції (див. рис.1).
Лексичний аналіз об`єднує літери в лексеми – службові слова, ідентифікатори, знаки операцій та пунктуації. Лексеми можна кодувати цілими числами, наприклад, do-одиницею, “+” – двійкою, ідентифікатор – трійкою, константу – четвіркою тощо. До коду лексем ідентифікаторів і констант додається ще одна величина – вид чи значення лексеми.
Синтаксичний аналіз групує лексеми в синтаксичні структури, які можуть бути складовими інших синтаксичних структур; наприклад, А+В може входити в оператор чи вираз. Як рекурсивні структури даних, вони зображуються (явно чи неявно) у формі дерева з лексемами в вузлах і з позначенням синтаксичних конструкцій у внутрішніх вузлах. Крони піддерев відтворюють частини програми відповідної синтаксичної конструкції. Генерація проміжного коду створює послідовності найпростіших інструкцій (команд), складених з коду операцій та кількох операндів. Ці інструкції відрізняються від команд асемблера тим, що в них не вказуються конкретні регістри ЕОМ, необхідні для використання. Необов`язкова оптимізація коду має призначенням створення проміжного коду, за якого об`єктна програма буде ефективніша щодо часу виконання та обсягу потрібної пам`яті. У фазу ГК складається об`єктний код. Для цього розв`язуються такі задачі: розміщення даних у пам`яті, вибір коду доступу до них та вибір регістрів для обчислень.
Керування таблицями розв`язує задачу зберігання імен, використаних у програмі, інформації про них (наприклад, типу даних) та доступу до цієї інформації. Переважно використовується таблиця символів як структура даних. Обробка помилок відбувається кожного разу, коли помічені дефекти у програмі. Вона полягає у формуванні повідомлення про помилку та її нейтралізації, тобто виправленні інформації для передачі наступній фазі, щоб остання могла виконуватися. Основна мета – за одну обробку програми компілятором виявити максимум помилок.
1.3. Проходи компілятора
При реалізації компілятора одна чи декілька фаз (можлива частина фази) об’єднуються в програмні модулі, названі проходами. За кожного проходу прочитується з файлу початкова програма чи результат попереднього проходу; здійснюється перетворення, задане його фазами; записується результат у проміжний або в результатний файл. Число проходів та методика об`єднання фаз у прохід визначаються особливостями вхідної мови та ЕОМ. Так, у мові ПЛ-1 описи даних можуть з`явитися після їхнього використання, як наприклад у групі операторів goto M; . . . ; M: a:=b+c;, де до ідентифікатора М звертаються раніше, ніж до опису. За такої ситуації скласти повністю код для оператора goto M; не можна до обробки опису М (оператора М: а:=b+c). Реалізація таких мов потребує щонайменше двох проходів. Багатопрохідний компілятор займає менше оперативної пам`яті ЕОМ від однопрохідного, але працює повільніше через необхідність багаторазового читання та записування файлів.
Модульна організація компілятора відтворена у трипрохідному неоптимізуючому компіляторі, що працює з чотирма поданнями (4 файла): початковою програмою –ланцюжком символів; послідовністю лексем; проміжним кодом і результатним списком машинних команд. Тут синтаксичний аналіз та генерація проміжного коду об`єднані в один прохід.
Кілька проходів можна скомбінувати в один, виконуючи їх паралельно із взаємною синхронізацією – таким чином створюється однопрохідний компілятор. Результат одного проходу, потрібний іншому, завдяки синхронізації та буферам дозволяє побудувати необхідний інтерфейс між фазами. Як правило, в однопрохідному компіляторі ведучою є фаза синтаксичного аналізу, яка кожного разу, коли потрібна їй лексема, запрошує фазу лексичного аналізу, керує генерацією проміжного коду, передає команди цього коду генератору коду для створення об`єктної програми. Проблеми, що виникають при використанні елемента даних раніше його означення за єдиного проходу, можна розв`язати методом оберненого заповнення: при генерації коду для команди goto M; за невизначеного М формується неповна команда і запам`ятовується її місце, а в момент визначення мітки М заповнюються всі порожні місця. Проте цей метод працює тоді, коли віддаль між точками використання та означення імені невелика.
1.4. Засоби побудови компіляторів
Існують спеціальні засоби (компілятори компіляторів, генератори компіляторів тощо) для полегшення конструювання компіляторів. Ідеальною вважається ситуація, коли є програма (або система програм), яка автоматично будує компілятор, маючи на вході описи лексики, синтаксису вхідної мови, результатів перетворень синтаксичних конструкцій та опис цільової машини.
Для полегшення побудови компіляторів розроблені такі основні інструментальні засоби: генератор лексичних аналізаторів, в якому інформація про лексеми задається регулярними виразами, а можливі дії обробки – операторами мови Сі; генератор, який за граматикою початкової мови створює СА з діями обробки; засоби генерації коду – спеціальні мови, зручні для опису процесу генерації машинного коду.
Основна проблема при реалізації мови програмування полягає в урахуванні суперечливих умов. Тому при складанні компілятора доводиться йти на компроміси, беручи до уваги, як буде використовуватися компілятор; що важливіше – швидкість компіляції чи якість об’єктної програми; створюється компілятор для нової ЕОМ чи ні; які інструментальні засоби можна залучати. Проект повинен давати можливість просто вносити зміни.
В реалізації мов високого рівня часто використовується специфічний тільки для компіляції засіб “розкрутки”. З кожним компілятором завжди зв`язані три мови програмування: Х – початкова, Y – об`єктна та Z – інструментальна. Компілятор перекладає програми мовою Х в програми, складені мовою Y, при цьому сам компілятор є програмою написаною мовою Z (позначатимемо компілятор як ).
Припустимо, що треба реалізувати нову мову високого рівня L для двох ЕОМ подібної організації А та В, і обидві ЕОМ не мають якихось інструментальних засобів для прискорення процесу створення компілятора. Покажемо, що треба зробити, щоб побудувати . Для цього виділимо в мові L підмножину S, достатню, щоб створити компілятор для перекладу з мови L на мову А, і побудуємо та протестуємо . Потім напишемо на підмножині S компілятор для перекладу з мови L на мову А. Пропустивши програму через компілятор одержимо необхідний компілятор : ((.
Реалізація після цього мови L для ЕОМ В значно простіша – треба переписати компілятор в компілятор ; транслювати програму в програму компілятором : ((, повторно транслювати програму компілятором і одержати потрібний компілятор : ((.
1.5. Спрощена модель компілятора
Перевід програм, написаних на мовах програмування високого рівня на мову машинних кодів, виконуваних комп’ютером, здійснюється спеціальними програмами, які називаються трансляторами. За способом роботи транслятори поділяються на компілятори та інтерпретатори. Компілятор повинен виконати наступні кроки:
Розпізнавати визначені рядки та окремі символи як базові елементи мови
Розпізнавати визначені комбінації елементів як синтаксичні одиниці i інтерпретувати їх значення
Генерувати вiдповiднi об’єктні коди
Компіляція може проводитись в декілька переглядів вихідного файла.
На першому перегляді відбувається лексичний аналіз. Компілятор виділяє окремі слова і символи, пропускаючи роздільники і коментарі, створює таблицю лексем. Другий перегляд відповідає синтаксичній фазі. Переглядається таблиця лексем, виділяються ідентифікатори і заносяться в таблицю змінних разом з їх типами, генерується об’єктна програма. Перший і другий перегляд можна об’єднати в один.
Починаючи з третього перегляду, відбуваються фази оптимізації, генерації асемблерного коду та інші.
На фазі лексичного аналізу вихідна програма, що являє собою потік символів, розбивається на лексеми – слова відповідно до визначення мови. Основним формалізмом, що лежить в основі реалізації лексичних аналізаторів, є кінцеві автомати і регулярні вирази. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, що викликається синтаксичним аналізатором, або як повний прохід, результатом якого є файл лексем. У процесі виділення лексем, лексичний аналізатор може, як самостійно будувати таблиці імен і констант, так і видавати значення для кожної лексеми при черговому зверненні до нього. У цьому випадку таблиця імен будується в подальших фазах (наприклад, в процесі синтаксичного аналізу). На етапі лексичного аналізу виявляються деякі (найпростіші) помилки (недопустимі символи, невірний запис чисел, ідентифікаторів та інше).
Основна задача синтаксичного аналізу – розбір структури програми. Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблицю імен. У процесі синтаксичного аналізу також виявляються помилки, пов’язані зі структурою програми. До синтаксичного аналізу входить і семантичний, на етапі якого перевіряється правильність тексту вихідної програми з точки зору семантики вихідної мови. Окрім перевірки, семантичний аналіз повинен виконувати перетворення тексту, що потребує семантика вихідної мови (наприклад, добавлення функцій неявного перетворення типів).
Після успішного завершення синтаксичного аналізу програма може бути переведена у внутрішнє представлення. Це робиться для цілей оптимізації і/або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати незалежний, від конкретної архітектури, компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. Для внутрішнього представлення, може використовуватися префіксна або постфіксна форма запису, орієнтований граф, трійки, четвірки і інші.
Підготовка до генерації коду – це фаза, на якій компілятором виконуються попередні дії, які безпосередньо пов’язані з синтезом тексту результуючої програми, але ще не ведуть до отримання тексту на результуючій мові. Як правило в цю фазу входять дії, що пов’язані з ідентифікацією елементів мови, розподіленням пам’яті та інше.
Генерація коду – це фаза, яка безпосередньо зв’язана з породженням команд, що складають конструкції результуючої мови і в цілому текст результуючої програми. Окрім цього, фаза генерації коду включає в себе оптимізацію – процес, що пов’язаний з опрацюванням вже існуючого результуючого коду. Інколи оптимізацію виділяють в окрему фазу компіляції. Фаз оптимізації може бути декілька. Оптимізацію звичайно ділять на машинно-залежну і машинно-незалежну, локальну і глобальну. Частина машинно-залежної оптимізації виконується на фазі генерації коду. Глобальна оптимізація намагається брати до уваги структуру всієї програми, локальна – тільки невеликих її фрагментів. Глобальна оптимізація засновується на глобальному потоковому аналізі, який виконується на графі програми і представляє по суті перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як міжпроцедурний аналіз, міжмодульний аналіз, аналіз областей життя змінних тощо.
1.6. Лексичний аналіз
Основна задача лексичного аналізу – розбити вхідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
Звичайно всі лексеми діляться на класи. Прикладами таких класів є числа,
ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова – це деяка кінцева підмножина ідентифікаторів. З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох типів: для синтаксичного аналізатора, працюючого услід за лексичним, істотна інформація про послідовності класів лексем, обмежувачів та ключових слів, а для семантичного аналізу, працюючого услід за синтаксичним, важлива інформація про конкретні значення окремих лексем (ідентифікаторів, чисел і т.д.). Тому загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема. Якщо виділена лексема – обмежувач, то він (точніше, деяка його ознака) видається як результат лексичного аналізу. Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його до ключових слів. Якщо так, то видається ознака відповідного ключового слова, якщо немає – видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Якщо виділена лексема належить якому-небудь з інших класів лексем (число, рядок і т.д.), то видається ознака класу лексеми, а значення лексеми зберігається.
Лексичний аналізатор може працювати або як самостійна фаза трансляції, або як підпрограма, працююча за принципом «дай лексему». У першому випадку виходом лексичного аналізатора є файл лексем, у другому лексема видається при кожному зверненні до лексичного аналізатора (при цьому, як правило, тип лексеми повертається як значення функції, а значення передається через глобальну змінну). З точки зору формування значень лексем, належних класам лексем, лексичний аналізатор може або просто видавати значення кожної лексеми і в цьому випадку побудова таблиць переноситься на більш пізні фази, або він може самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.). У цьому випадку, як значення лексеми видається покажчик на вхід у відповідну таблицю.
Робота лексичного аналізатора описується формалізмом кінцевих автоматів. Однак безпосередній опис кінцевого автомата незручний практично. Тому для опису лексичних аналізаторів, як правило, використовують або формалізм регулярних виразів, або формалізм контекстно вільних граматик. По опису лексичного аналізатора у вигляді регулярних виразів або автоматної граматики будується кінцевий автомат, що розпізнає відповідну мову.
1.7. Синтаксичний аналіз
Синтаксичний аналіз – це процес, в якому досліджується таблиця лексем, або кожна окрема лексема, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що явно сформульовані у визначені синтаксису мови. Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його у відповідності до граматики вихідної мови. Але, в граматиці вихідної мови, як правило не вказується, які конструкції слід вважати лексемами. Прикладами конструкцій, які як правило розпізнаються на фазі лексичного аналізу, можуть бути ключові слова, константи та ідентифікатори. Але ці ж самі конструкції можуть розпізнаватися і синтаксичним аналізатором. На практиці не існує конкретного правила, що визначає, які конструкції повинні розпізнаватися на фазі лексичного аналізу, а які на фазі синтаксичного. Як правило, це визначає розробник компілятора, виходячи з технологічних аспектів програмування, а також синтаксису та семантики вхідної мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вихідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в тексті програми, встановити тип та правильність кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних символів заданій мові. Але, задача синтаксичного аналізу, не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати, деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції, інформацію про знайдені і розібрані синтаксичні конструкції.
2.ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
Розширена форма Бекуса — Наура (англ. extended Backus–Naur form, EBNF) є розширеною формою нотації Бекуса-Наура (BNF) —метасинтаксичної нотації. Cьогодні вона існує в багатьох варіантах, перед усім — ISO-14977.
Нотація Бекуса—Наура (англ. Backus-Naur form, BNF) є спосіб запису правил контекстно-вільної граматики, себто формою опису формальної мови.
Нотація БНФ є набором «продукцій»(правил), де вираз, що містить символи -це послідовність символів або послідовності символів, розділених вертикальною рискою |, що повністю перелічують можливий вибір символ з лівої частини формули.
Формули БНФ складаються з наступних мета символів:
( < – лівий обмежувач;
( > – правий обмежувач;
( ::= – визначено як;
( | – або;
( “” — текстовий елемент (символ або група символів).
Розширені формули Бекуса-Наура використовують додаткові мета символи:
( [] – елемент у дужках входить або не входить (є необов’язковим);
( () – групування елементів у дужках; 19
( {} – нуль або більше повторень елементів розташованих у дужках;
( (* – початок блоку коментарів;
( *) – кінець блоку коментарів.
Нижче наведено опис вхідної мови згідно розширеної нотації Бекуса-Наура.
<program> ::= Startprogram Variable <VAR_blok>Startblok<code_blok> Endblok.
<VAR_blok> ::=<declarations> [{;<declarations>} ];.
<declarations>::=<type_i><declaration_i> [{,<declaration_i>}] | <type_b> <declaration_b> [{,<declaration_b>}] .
<type_i> ::=Longint.
<type_b> ::=Boolean.
<declaration_i> ::= <ident> [ ::<const_i>] .
<declaration_b> ::= <ident> [ :: <const_b>] .
<ident> ::= <letter>[<l _or_n>] .
<l_or_n> ::= <letter>|<number> .
<letter>::=<l_letter>|<h_letter>.
<h_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|.
<l_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>|<read>|<write> .
<equation> ::= <ident> :: <expression_i>|<expression_b>; .
<expression_i>::= <term> [{++ <term> | -- <term>}].
<term>::=<ident>|<const_i>|<factor>.
<factor>::= [{** <term> | Div <term>| Mod <term> | <brackets>}].
<brackets>::=(<expression_i>).
<expression_b>::= <term_b> [{= <term_b> | <> <term_b> | < <term_b>| > <term_b>}].
<term_b>::=<ident>|<const_b>|<factor_b>.
<factor_b>::=<term_b> [{Or|<term_b> | <and> |<not>|<brackets_b>}].
<and>::= [{ And<term_b>}]
<not>::=Not<factor_b>
<brackets_b>::=(<expression_b>).
<cycle> ::= If (<expression_b>|<ident>) [goto <label1>] <code_blok> Else
[goto <label2>][<label1><code_blok><label2>] End If
<read> ::= Get(<ident>); .
<write> ::= Put(<expression_і>|<string>); .
<string> ::= “[{<l_or_n>}]” .
2.2. Опис термінальних символів та ключових слів
Термінал (термінальний символ) - об'єкт, безпосередньо присутній в словах мови, відповідного граматиці, і має конкретне, незмінне значення (узагальнення поняття «букви»). У формальних мовах, що використовуються на комп'ютері, в якості терміналів зазвичай беруть всі або частину стандартних символів ASCII - латинські букви, цифри і спец. символи.
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
Ключові слова - це зарезервовані ідентифікатори, які можна використовувати тільки в тому сенсі, в якому вони визначені.
Нижче наведено опис вхідної мови, згідно з завданням.
Термінальні символи:
; – кінець блоку опису ідентифікаторів, або закінчення виразу.
, – роздільник між ідентифікаторами в блоці опису ідентифікаторів.
:: – оператор присвоєння.
Not – логічна операція «не».
And – логічна операція «і».
Or – логічна операція «або».
= – операція порівняння «дорівнює».
<> – операція порівняння «не дорівнює».
< – операція порівняння «менше».
> – операція порівняння «більше».
( – відкриваюча дужка.
) – закриваюча дужка.
Ключові слова:
++ – арифметична операція додавання.
-- – арифметична операція відніманя.
** – арифметична операція множення.
Div – арифметична операція ділення.
Mod – арифметична операція остачі від ділення.
Longint – тип даних.
Startprogram – початок програми.
Variable – початок блоку опису ідентифікаторів.
Startblock – початок блоку.
Endblock – кінець блоку.
Get – оператор вводу.
Put – оператор виводу.
If – оператор розгалуження.
Else – якщо умова не вірна.
Goto – безпосередній перехід
Boolean – бульовий тип даних
True – істина
False - хиба
До термінальних символів віднесемо також усі цифри (0-9), латинські букви ( A-Z), символи табуляції, символ переходу на нову стрічку, пробілу, знаку «-», «_» та «”».
3. РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
3.1. Вибір технології програмування
Для виконання курсової роботи було вибрано технологію об’єктно-орієнтованого програмування. Обєктно орієнтоване програмування (надалі ООП) - це парадигма програмування, в якій основними концепціями є поняття об'єктів і класів.
Клас - це тип, що описує будову об'єктів. Поняття "клас" має на увазі деяка поведінка і спосіб представлення. Поняття "об'єкт" має на увазі щось, що має певну поведінку і спосіб представлення. Говорять, що об'єкт - це екземпляр класу. Клас можна порівняти з кресленням, згідно з яким створюються об'єкти. Зазвичай класи розробляють так, щоб їх об'єкти відповідали об'єктам предметної області.
Структура даних "клас" є об'єктним типом даних. При цьому елементи такої структури (члени класу) можуть самі бути не лише даними, але і методами (тобто процедурами або функціями). Таке об'єднання називається інкапсуляцією.
Наявність інкапсуляції достатня для объектности мови програмування, але ще не означає його об'єктної орієнтованості - для цього потрібно наявність наслідування.
Але навіть наявність інкапсуляції і наслідування не робить мову програмування повною мірою об'єктною з точки зору ООП. Основні переваги ООП проявляються тільки у тому випадку, коли в мові програмування реалізований поліморфізм.
Абстракція - це надання об'єкту характеристик, які відрізняють його від усіх інших об'єктів, чітко визначаючи його концептуальні межі. Основна ідея полягає в тому, щоб відокремити спосіб використання складених об'єктів даних від деталей їх реалізації у вигляді простіших об'єктів, подібно до того, як функціональна абстракція розділяє спосіб використання функції і деталей її реалізації в термінах примітивніших функцій, таким чином, дані обробляються функцією високого рівня за допомогою виклику функцій низького рівня.
Такий підхід є основою об'єктно-орієнтованого програмування. Це дозволяє працювати з об'єктами, не вдаючись особливо їх реалізації. У кожному конкретному випадку застосовується той або інший підхід: інкапсуляція, поліморфізм або наслідування. Наприклад, при необхідності звернутися до прихованих даних об'єкту, слід скористатися інкапсуляцією, створивши, так звану, функцію доступу або властивість.
Інкапсуляція - це принцип, згідно з яким будь-який клас повинен розглядатися як чорний ящик, - користувач класу повинен бачити і використовувати тільки інтерфейсну частину класу (т. е. список декларованих властивостей і методів класу) і не вникати в його внутрішню реалізацію. Тому дані прийнято інкапсулювати в класі так, щоб доступ до них по читанню або запису здійснювався не безпосередньо, а за допомогою методів. Принцип інкапсуляції (теоретично) дозволяє мінімізувати число зв'язків між класами і, відповідно, спростити незалежну реалізацію і модифікацію класів.
Приховання даних - невід'ємна частина ООП, що управляє зонами видимості. Є логічним продовженням інкапсуляції. Метою приховання є неможливість для користувача дізнатися або зіпсувати внутрішній стан об'єкту.
Наслідуванням називається можливість породжувати один клас від іншого із збереженням усіх властивостей і методів класу-предка (прародителя, іноді його називають суперкласом) і додаючи, при необхідності, нові властивості і методи. Набір класів, пов'язаних відношенням спадкоємства, називають ієрархією. Спадкоємство покликане відобразити таку властивість реального світу, як ієрархічність.
Поліморфізмом називають явище, при якому функції (методу) з одним і тим же ім'ям відповідає різний програмний код (поліморфний код) залежно від того, об'єкт якого класу використовується при виклику цього методу. Поліморфізм забезпечується тим, що в класі-нащадку змінюють реалізацію методу класу-предка з обов'язковим збереженням сигнатури методу. Це забезпечує збереження незмінним інтерфейсу класу-предка і дозволяє здійснити зв'язування імені методу в коді з різними класами - з об'єкту
23.10.2019 21:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора