Міністерство освіти і науки України
Національний університет “Львівська політехніка”
З дисципліни: «Системне програмування»
на тему:
“Розробка компілятора з вхідної мови програмування”
Виконав: студ. гр. КІМ-21з
Мевшук Г.Г.
Львів 2011
Згідно заданого завдання в даному курсовому проекті розроблено компілятор з вхідної мови програмування Pascal. Оболонка компілятора розроблена в середовищі програмування Borland C під операційну систему Windows і в опис проекту не входить. Сам компілятор написанний на мові Pascal, та поданий у пояснювальній записці, а також разом з оболонкою в електронному варіанті. В пояснювальній записці подано детальний опис мови, огляд існуючих методів розробки компіляторів, а також описано процес розробки програми компілятора на рівні блок-схем і тексту програми. До проекту додано результати тестування програми.
Зміст
Вступ
1. Завдання на курсовий проект
2. Формальний опис вхідної мови програмування
3. Розробка компілятора вхідної мови програмування
3.1 Розробка лексичного аналізатора
3.1.1 Розробка блок-схеми програми
3.2 Розробка синтаксичного аналізатора
3.2.1 Обробка синтаксичних помилок
3.3 Розробка семантичного аналізатора
3.4 Розробка оптимізатора коду
3.5 Розробка генератора коду
4. Відладка та тестування компілятора
4.6.1 Виявлення лексичних помилок
4.6.2 Виявлення синтаксичних помилок
4.6.3 Виявлення семантичних помилок
4.6.4 Загальна перевірка коректності роботи транслятора
Висновки
Література
Додатки
Вступ
Компілятор – це програма, яка читає текст програми, написаної на одній мові – початковій, і транслює (переводить) його в еквівалентний текст на іншій мові – цільовій. Одним з важливих моментів трансляції є повідомлення користувача про наявність помилок в початковій програмі.
Створення компіляторів є одною з невід‘ємних частин системного програмного забезпечення. Одним із завдань компілятора є переведення написаного тексту програми у машинний код, який повинен відповідати комп‘ютерній системі. Оскільки сьогоднішній час – час великого розвитку комп‘ютерної галузі, то створений машинний код з часом стає застарілим, тобто не відповідає принципу оптимального використання комп‘ютерних ресурсів. Тому для запобігання цього явища необхідно створювати нові компілятори, які б відповідали потребам теперішнього часу.
Проблема компіляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою компілятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього компілятор має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати об'єктний код або виконавчий модуль.
На перший погляд, різноманітність компіляторів приголомшує. Використовуються тисячі початкових мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, виникаючих у всіх областях комп'ютерних технологій. Цільові мови не менше різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп'ютерів. Іноді компілятори класифікують як однопрохідні, багатопрохідні, виконуючі, відлагоджуючі, оптимізуючі — залежно від призначення і принципів та технологій їх створення. Не дивлячись на уявну складність і різноманітність, основні задачі, виконувані різними компіляторами, по суті, одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних початкових мов і цільових машин з використанням одних і тих же базових технологій. Знання про організацію і написання компіляторів істотно зросли з часів перших компіляторів, що з'явилися на початку 1950-х рр. Сьогодні складно визначити, коли саме з'явився на світ перший компілятор, оскільки в ті роки проводилося багато експериментів і розробок різними незалежними групами. В основному метою цих розробок було перетворення в машинний код арифметичних формул. В 50-х роках про компілятори ходила слава як про програми, украй складні в написанні (наприклад, на написання першого компілятора Fortran було витрачено людиною 18 - років роботи). З тих пір розроблені різноманітні системні технології рішення багатьох задач, що виникають при компіляції. Крім того, розроблені хороші мови реалізації, програмні середовища і програмний інструментарій. Проблема компіляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови.. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою компілятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього компілятор має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати об'єктний код або виконавчий модуль. Сьогодні від компілятора вимагається також створення оптимізованого коду програми. Тому створення ефективного виконавчого коду є дуже проблемою в наш час, бо для створення цього необхідно враховувати всі можливі варіанти покращеної апаратної частини, розвиток якої досяг сьогодні теоретичної межі продуктивності.
Завдяки цьому "солідний компілятор" може бути реалізований навіть як курсова робота по проектуванню компіляторів.
Розробити компілятор з вхідної мови програмування короткий опис якої подано нижче (у відповідності з заданим варіантом) з виводом необхідної проміжної інформації на кожному кроці. Розробити інтерфейс користувача (інтегроване середовище програмування вхідною мовою).
Варіант № 13
В таблиці варіанта завдання використано наступні позначення:
A: Тип даних: byte(1).
B: Додаткова арифметична операція: ^ (піднесення до степеня).
C: Додаткова логічна операція: NOT.
D: Оператор циклу: do-while (2).
| № | A | B | C | D |
| 13 | 1 (byte) | ^ | NOT | do-while |
2. Формальний опис вхідної мови програмування
Розробити компілятор заданої вхідної мови програмування.
- три типи даних: логічний тип даних (boolean), знаковий цілочисельний тип (1byte) та беззнаковий цілочисельний тип розміром 1 байт;
- змінних з довільної довжини;
- арифметичні операції над цілими: +, -, *, /, “-” (унарний мінус), ^ (операція піднесення до степеню);
- символи групування арифметичних операцій “(” , “)”
- логічні операції над цілими: <, >, ==, | = ;
- логічну операцію над логічними даними NOT;
- оператор присвоєння “=”;
- оператори блоку “{“ , “}”;
- оператор виводу (print);
- оператор виконання дії за умовою (if-then-else);
- оператор циклу (do-while);
Визначимо окремі термінальні символи та нерозривні набори термін.
Символів(ключові слова);
{( usigned
} ) char
; < if
= > then
+ = = else
- <> while
^ NOT do
* program true
/ bool false
До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z) та символ пробілу (“ ”). Всього 28+10+52+1=91 термінальних виразів. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми.
- символ “ | ” розділяє альтернативи
- символи “ [ ”,“ ] ” означає необов’язковість
- символи “ { ”,“ } ” означає повтор
Формальний опис заданої мови BNF:
<program>::= prog <block>
<block>::= {<statement> | [{<statement >}]}
<statement>::= <declaration> | <operator>
<declaration>::=<type><ident>;
<operator>::=<bind> | <if-then-else> | <do-while > | <print>
<bind>::=<ident> = <expression>;
<if-then-else>::= if <bool expression> then <bloc> [else<bloc>]
<while-do>::= while <bool_ehpression> do <bloc>
<print>::= print <ident> | <int-const> | <log-const>;
<type>::= boolean | byte | ubyte
<ident>::=<letter> [{<letter>}]
<byte_corst>::= [] <number> [{<number>}]
<bool_const>::= true | false
<letter>::= a | …| z | A | … | Z
<number>::= 0 | 1 | … | 9
<logic.conct>::= true | fals
<expression>::=<num.expression>|<bool_expression>|<log.expression>
<num.expression>::=<num_operand>[{<num.operation><num.operand>}]
<bool_expression>::=<num.operand>[{<bool.operation><num_operand>}]
<logic_expression>::=<logic_operand>[{|<logic.operand>}]
<logic_operand>::= (<logic_expression>) | <ident>|<logic_const>
<num.operand>::=(<num.expression>) | <ident> | <byte_const>
<num.operation>::= * | / | + | - | ^
<bool_operation>::= < | > | = = | < >
<log_expression>::=<log_operand> [{NOT<log_operand>}]
<log_operand>:: (<log_expression>) | <cident> | <logic_const>
3. Розробка компілятора вхідної мови програмування
Процедурно-орієнтовані мови програмування, такі як FORTRAN, Pascal, C, C++ та ін. засновані на принципі послідовного виконання операторів, команд або директив. Їх базові оператори, операції, команди та директиви можна класифікувати по трьох основних групах:
а) Безумовні оператори (statements) обрахунків та перетворень;
б) Оператори обробки розгалужень та передачі управління;
в) Оператори організації циклічної обробки.
В загальному випадку віртуальна машина складається з інформаційного, операційного, управляючого та комунікаційного компонентів. Будь-яка віртуальна машина повинна мати:
а) Пам’ять різних видів та типів для збереження кодів програм і даних (інформаційний компонент) і механізми доступу до неї;
б) Вказівник поточної операції (основа управляючої компоненти), що змінюється при підрахунку номера оператора;
в) Блок виконання операцій (operators), який реалізує функції операційних та управляючих компонентів. Разом з інтерфейсним обладнанням він реалізує комунікаційний компонент, який забезпечує зв’язок ВМ із зовнішнім світом.