Автор: Пользователь скрыл имя, 25 Февраля 2012 в 16:19, курсовая работа
Незважаючи на більш ніж піввікову історію обчислювальної техніки, формально роком народження теорії трансляторів можна вважати 1957, коли з'явився перший транслятор мови Фортран, створений Бекасом. До цього часу створення трансляторів було досить "творчим" процесом. Лише поява теорії формальних мов і строгих математичних моделей дозволило перейти від "творчості" до "науки".
Вступ
1. Огляд методів та способів проектування трансляторів
1.1. Основні поняття і визначення
1.2. Узагальнена структура транслятора
1.4. Варіанти взаємодії блоків транслятора
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.5. Розробка генератора коду
3.5.1. Розробка граф-схеми алгоритму
3.5.2. Опис програмної реалізації генератора коду
4. Опис інтерфейсу та інструкції користувача
4.1. Опис інтерфейсу
4.1.1. Головне меню та панель інструментів.
4.2. Інструкція програміста
4.2.1. Алфавіт мови
4.2.2. Коментарі
4.2.3. Тип даних
4.2.4. Розділи, використовувані при написанні програм
4.2.5. Типи операцій
4.2.6. Типи операторів
5. Відлагодження та тестування програми
5.1. Виявлення лексичних помилок
5.2. Виявлення синтаксичних помилок
5.3. Виявлення семантичних помилок
5.4. Загальна перевірка коректності роботи транслятора
Висновки
Список літератури
Додатки
А. Лістинг програми
50
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
КУРСОВА РОБОТА
з предмету “Системне програмування”
на тему “Розробка системних програмних модулів та компонент систем програмування.”
Виконав:
студент групи КІ – 31
Критович Д.М.
Перевірив:
Мархівка В.С.
Львів – 2011
Анотація
Задача, яка вирішується в даному курсовому проекті є розробка транслятора вхідної мови програмування. Транслятор розроблений за допомогою мови програмування C#, на основі програмного продукту “Visual Studio 2010”, в якому використовується стандартний набір користувацького інтерфейсу на основі компонентів пакету “.Net Framework”, який значно спрощує процес тестування, відлагодження та редагування програми.
У пояснювальній записці подано опис кожного етапу написання транслятора, структурні схеми, які дають змогу краще зрозуміти призначення кожного етапу, та взаємозвязок між ними. Для перевірки на коректність комплекcу виконаних робіт наводяться тестові програми, які демонструють основні можливості даної мови програмування.
Зміст |
|
Завдання на курсову роботу | 5 |
Вступ | 7 |
1. Огляд методів та способів проектування трансляторів | 8 |
1.1. Основні поняття і визначення | 8 |
1.2. Узагальнена структура транслятора | 11 |
1.4. Варіанти взаємодії блоків транслятора | 15 |
2. Формальний опис вхідної мови програмування | 16 |
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура |
16 |
2.2. Опис термінальних символів та ключових слів | 17 |
3. Розробка транслятора вхідної мови програмування | 18 |
3.1. Вибір технології програмування | 18 |
3.2. Проектування таблиць транслятора та вибір структур даних | 19 |
3.3. Розробка лексичного аналізатора | 21 |
3.3.1. Розробка граф-схеми алгоритму | 22 |
3.3.2. Опис програмної реалізації лексичного аналізатора | 25 |
3.4. Розробка синтаксичного та семантичного аналізатора | 27 |
3.4.1. Розробка граф-схеми алгоритму | 28 |
3.4.2. Опис програмної реалізації синтаксичного та семантичного аналізатора |
31 |
3.5. Розробка генератора коду | 33 |
3.5.1. Розробка граф-схеми алгоритму | 34 |
3.5.2. Опис програмної реалізації генератора коду | 34 |
4. Опис інтерфейсу та інструкції користувача | 35 |
4.1. Опис інтерфейсу | 35 |
4.1.1. Головне меню та панель інструментів. | 36 |
4.2. Інструкція програміста | 37 |
4.2.1. Алфавіт мови | 38 |
4.2.2. Коментарі | 38 |
4.2.3. Тип даних | 38 |
4.2.4. Розділи, використовувані при написанні програм | 39 |
4.2.5. Типи операцій | 40 |
4.2.6. Типи операторів | 41 |
5. Відлагодження та тестування програми | 43 |
5.1. Виявлення лексичних помилок | 43 |
5.2. Виявлення синтаксичних помилок | 44 |
5.3. Виявлення семантичних помилок | 45 |
5.4. Загальна перевірка коректності роботи транслятора | 46 |
Висновки | 47 |
Список літератури | 48 |
Додатки | 49 |
А. Лістинг програми | 49 |
Завдання на курсову роботу
Розробити транслятор вхідної мови програмування, короткий опис якої подано нижче:
- типи даних:
Integer <змінна>;
- оператор вводу:
Input (<змінна>);
- оператор виводу:
Output (" < повідомлення > ");
Output (< змінна >);
- блок тіла програми:
Program <ім’я>
Var
<опис змінних>;
Start
<тіло програми>;
Finish
- оператор:
For – DownTo - Do (Паскаль);
For( <змінна> := <вираз>) DownTo(<вираз>)
Start
<тіло циклу>
Finish
- регістр ключових слів:
Up-Low перший символ Up;
- регістр ідентифікаторів:
Up-Low6 перший символ Up;
- операції арифметичні:
+; -; Mul; Div; Mod;
- операції порівняння:
==; != ; Le; Ge;
- операції логічні:
!!; &&; ||;
- коментар:
/* ... */;
- оператор присвоєння:
:=;
Вступ
Незважаючи на більш ніж піввікову історію обчислювальної техніки, формально роком народження теорії трансляторів можна вважати 1957, коли з'явився перший транслятор мови Фортран, створений Бекасом. До цього часу створення трансляторів було досить "творчим" процесом. Лише поява теорії формальних мов і строгих математичних моделей дозволило перейти від "творчості" до "науки". Саме завдяки цьому стала можливим поява сотень нових мов програмування. Більше того, формальна теорія трансляторів дала новий стимул розвитку математичної лінгвістики і методам штучного інтелекту, пов'язаних із природними і штучними мовами. Основу теорії трансляторів становить теорія формальних мов - досить складними, насиченими термінами, визначеннями, математичними моделями і іншими формалізмами розділ математики. Отже, транслятори є невід'ємною частиною будь-якої обчислювальної системи - без них нам довелося б усе програмувати на автокоді або навіть у машинних командах. Тому транслятори стали важливою практичною областю наукових досліджень, пов'язаних з обчислювальними машинами.
1. Огляд методів та способів проектування трансляторів
1.1. Основні поняття і визначення
Транслятор - обслуговуюча програма, що перетворює вхідну програму, надану вхідною мовою програмування, у робочу програму, представлену об'єктною мовою.
Наведене визначення відноситься до всіх різновидів транслюючих програм. Однак у кожної з таких програм можуть бути свої особливості по організації процесу трансляції. У цей час транслятори розділяються на три основні групи: асемблери, компілятори і інтерпретатори.
Асемблер - системна обслуговуюча програма, що перетворює символічні конструкції в команди машинної мови. Специфічною рисою асемблерів є те, що вони здійснюють дослівну трансляцію однієї символічної команди в одну машинну. Таким чином, мова асемблера (ще називається автокодом) призначена для полегшення сприйняття системи команд комп'ютера і прискорення програмування в цій системі команд. Програмістові набагато легше запам'ятати мнемонічне позначення машинних команд, чим їхній двійковий код. Тому, основний виграш досягається не за рахунок збільшення потужності окремих команд, а за рахунок підвищення ефективності їхнього сприйняття.
Разом з тим, мова асемблера, крім аналогів машинних команд, містить безліч додаткових директив, що полегшують, зокрема, керування ресурсами комп'ютера, написання повторюваних фрагментів, побудова багатомодульних програм. Тому виразність мови є набагато кращою, ніж просто мови символічного кодування, що значно підвищує ефективність програмування.
Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову програми, записаною вхідною мовою програмування. Також як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншу (найчастіше, у мову конкретного комп'ютера). Разом з тим, команди вхідної мови значно відрізняються по організації і потужності від команд машинної мови. Існують мови, у яких одна команда вхідної мови транслюється в 7-10 машинних команд. Однак є і такі мови, у яких кожній команді може відповідати 100 і більше машинних команд (наприклад, Пролог). Крім того, у вхідних мовах досить часто використовується строга типізація даних, здійснювана через їхній попередній опис. Програмування може опиратися не на кодуванні алгоритму, а на ретельне обмірковування структур даних або класів. Процес трансляції з таких мов звичайно називається компіляцією, а вихідні мови звичайно відносяться до мов програмування високого рівня. Абстрагування мови програмування від системи команд комп'ютера привело до незалежного створення найрізноманітніших мов, орієнтованих на рішення конкретних завдань. З'явилися мови для наукових, економічних розрахунків, доступу до баз даних і інші.
Інтерпретатор - програма або пристрій, що здійснює по-операторну трансляцію і виконання вхідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму машинною мовою. Розпізнавши команду вхідної мови, він відразу виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу вхідного тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і налагодження програм більш гнучким. Крім того, відсутність вихідного машинного коду дозволяє не "засмічувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна досить легко адаптувати до будь-яких машинних архітектур, розробивши його тільки один раз на широко розповсюдженій мові програмування. Тому, інтерпретуючі мови, типу Java Script, VB Script, одержали широке поширення. Недоліком інтерпретаторів є низька швидкість виконання програм. Звичайно інтерпретуючі програми виконуються в 50-100 разів повільніше програм, написаних у машинних кодах.
Загальні властивості і закономірності властиві як різним мовам програмування, так і трансляторам. У них протікають схожі процеси перетворення вхідного тексту. Незважаючи на те, що взаємодія цих процесів може бути організовано різним шляхом, можна виділити функції, виконання яких приводить до однакових результатів. Назвемо такі функції фазами процесу трансляції.
З огляду на схожість компілятора і інтерпретатора, розглянемо фази, що існують у компіляторі.
У ньому виділяються:
1. Фаза лексичного аналізу.
2. Фаза синтаксичного аналізу, що складає з:
розпізнавання синтаксичної структури;
семантичного розбору, у процесі якого здійснюється робота з таблицями, породження проміжного семантичного представлення або об'єктної моделі мови.
3. Фаза генерації коду, що здійснює:
семантичний аналіз компонентів проміжного представлення або об'єктної моделі мови;
переклад проміжного представлення або об'єктної моделі в об'єктний код.
Поряд з основними фазами процесу трансляції можливі також додаткові фази:
1. Фаза дослідження і оптимізації проміжного представлення, що складає з:
аналізу коректності проміжного представлення;
оптимізації проміжного представлення.
2. Фаза оптимізації об'єктного коду.
Інтерпретатор відрізняється тим, що фаза генерації коду звичайно заміняється фазою емуляції елементів проміжного представлення або об'єктної моделі мови. Крім того, в інтерпретаторі звичайно не проводиться оптимізація проміжного представлення, а відразу ж здійснюється його емуляція.
Крім цього можна виділити єдиний для всіх фаз процес аналізу й виправлення помилок, що існують в оброблюваному вхідному тексті програми.
Узагальнена структура компілятора, що враховує існуючі в ньому фази, представлена на рис. 1.1.
Рис. 1.1. Узагальнена структура компілятора.
Він складається з лексичного аналізатора, синтаксичного аналізатора, генератора коду, аналізатора помилок. В інтерпретаторі замість генератора коду використовується емулятор (рис. 1.2), у який, крім елементів проміжного преставлення, передаються вхідні дані. На вихід емулятора видається результат обчислень.
Лексичний аналізатор (відомий також як сканер) здійснює читання вхідного ланцюжка символів і їхнє угруповання в елементарні конструкції, названі лексемами. Кожна лексема має клас і значення. Звичайно претендентами на роль лексем виступають елементарні конструкції мови, наприклад, ідентифікатор, дійсне число, коментар. Отримані лексеми передаються синтаксичному аналізатору. Сканер не є обов'язковою частиною транслятора. Однак, він дозволяє підвищити ефективність процесу трансляції.
Рис. 1.2. Узагальнена структура інтерпретатора.
Синтаксичний аналізатор здійснює розбір вхідної програми, використовуючи надходженні лексеми, побудову синтаксичної структури програми і семантичний аналіз із формуванням об'єктної моделі мови. Об'єктна модель представляє синтаксичну структуру, доповнену семантичними зв'язками між існуючими поняттями.
Цими зв'язками можуть бути:
посилання на змінні, типи даних і імена процедур, розташовувані в таблицях імен;
зв'язки, що визначають послідовність виконання команд;
зв'язки, що визначають вкладеність елементів об'єктної моделі мови й інші.
Таким чином, синтаксичний аналізатор є досить складним блоком транслятора. Тому його можна розбити на наступні складові:
розпізнавання;
блок семантичного аналізу;
об'єктну модель, або проміжне представлення, що складається з таблиці імен і синтаксичної структури.
Узагальнена структура синтаксичного аналізатора наведена на рис. 1.3.
Рис. 1.3. Узагальнена схема синтаксичного аналізатора.
Розпізнавання одержує ланцюжок лексем і на її основі здійснює розбір відповідно до використовуваних правил. Лексеми, при успішному розборі правил, передаються семантичному аналізатору, що будує таблицю імен і фіксує фрагменти синтаксичної структури. Крім цього, між таблицею імен і синтаксичною структурою фіксуються додаткові семантичні зв'язки. У результаті формується об'єктна модель програми, звільнена від прив'язки до синтаксису мови програмування. Досить часто замість синтаксичної структури, що повністю копіює ієрархію об'єктів мови, створюється її спрощений аналог, що називається проміжним представленням.
Информация о работе Розробка системних програмних модулів та компонент систем програмування