Курсова робота
З дисципліни: «Системне програмування»
На тему: «Розробка системних програмних модулів та компонент систем програмування»
На перший погляд, різноманітність компіляторів вражає. Використовуються тисячі вихідних мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, які виникають у всіх областях застосування комп’ютера. Цільові мови не менш різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп’ютерів. Деколи компілятори класифікують як однопрохідні, багато прохідні, виконуючі (load-and-go), відлагоджуючі, оптимізуючи – в залежності від призначення і принципів і технологій їх створення.
Не дивлячись на те, що основні задачі, що виконуються компіляторами видаються складними і різноманітними, по суті вони одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних вихідних мов і цільових машин з використанням одних і тих же базових технологій.
В 50‑х роках про компілятори ходила слава, що це програми, дуже складні в написанні (наприклад, перший компілятор Fortran потребував 18 людино-років роботи). З того часу розроблені різноманітні систематичні технології вирішення багатьох задач, виникаючих при компіляції. Крім цього, розроблені хороші мови реалізації, програмні середовища та програмні інструменти. Завдяки цьому «солідний» компілятор може бути реалізований в якості курсової роботи з проектування компіляторів [1].
1. Огляд способів та методів проектування трансляторів
Компіляція складається з двох частин: аналізу і синтезу. Аналіз – це розбиття початкової програми на складові частини і створення її проміжного представлення. Синтез – конструювання необхідної цільової програми з проміжного представлення.
В процесі аналізу визначаються і записуються в ієрархічну деревовидну структуру операції, задані початковою програмою. Часто використовується спеціальний вид дерева, що називається синтаксичним (або деревом синтаксичного розбору), в якому кожен вузол представляє операцію, а його дочірні вузли – аргументи операції.
Багато програмних інструментів, працюючи з початковими програмами, спочатку виконують певний вид аналізу. Розглянемо приклади таких інструментів.
Структурні редактори. Ці програми одержують як вхід послідовність команд для побудови початкової програми. Такий редактор не тільки виконує звичні для текстового редактора функції зі створення і модифікації тексту, але і аналізує текст програми, поміщаючи в початкову програму відповідну ієрархічну структуру. Тим самим він виконує додаткові задачі, що полегшують підготовку програми. Наприклад, редактор може перевіряти коректність введеного тексту, автоматично додавати структурні елементи (так, якщо користувач введе while, редактор додасть відповідне йому ключове слово do і запропонує ввести умовний вираз між ними) або переходить від ключового слова begin або лівої дужки до відповідного end або правої дужки. Більше того, результат на виході такого редактора часто подібний результату після фази аналізу компіляції.
Програми форматованого виводу для друку. За допомогою цих інструментів програма аналізується і роздруковується так, щоб її структура була максимально ясною. Наприклад, коментарі можуть бути виділені спеціальним шрифтом, а оператори – виведені з відступами, що вказують рівень вкладеності в ієрархічній структурі операторів.
Статичні перевіряючі програми. Дані інструменти зчитують програми, аналізують їх і намагаються знайти потенційні помилки без запуску програми. Такий аналіз часто дуже схожий на аналіз в оптимізуючих компіляторах. Наприклад, статична перевіряюча програма може визначити невиконання якоїсь частини початкової програми або використання деякої змінної до її оголошення. Так само можуть бути знайдені логічні помилки, наприклад спроби використання дійсної змінної як покажчик (із застосуванням технології перевірки типів).
Інтерпретатори. Замість створення цільової програми в результаті трансляції інтерпретатор виконує операції, вказані в початковій програмі. Наприклад, для оператора присвоєння він може побудувати дерево розбору, а потім виконати операції, проходячи по його вузлах, Корінь дерева вказує на виконання присвоєння, так що інтерпретатор викличе підпрограму для обчислення виразу, що визначається одним із піддерев, а потім збереже його значення у виділеній змінній. Таке піддерево вказує підпрограмі, що вона повинна обчислити суму двох виразів. Рекурсивний виклик підпрограми приводить до обчислення значення, яке потім підсумовується і зберігається. Інтерпретатори часто використовуються для командних мов, оскільки кожен їх оператор є викликом складної програми, такої як редактор або компілятор. Так само і деякі мови «дуже високого рівня», типу APL, переважно інтерпретуються, оскільки є безліч атрибутів даних, таких як розмір або тип масиву, які не можуть бути визначені в процесі компіляції.
Традиційно ми говоримо про компілятор як про програму, яка транслює початкову мову типу Fortran в асемблер або машинну мову. Проте є і інші застосування технології компіляції. Так, аналізуюча частина в кожному з приведених нижче прикладів подібна аналізатору звичайного компілятора.
Форматування тексту. Програма форматування тексту одержує на вхід потік символів, більшість з яких представляє текст, що виводиться, але багато символів означає абзаци, малюнки або математичні структури, наприклад верхні або нижні індекси.
«Кремнієві» компілятори (Silicon compilers). Такий компілятор має початкову мову, схожу із звичною мовою програмування. Проте змінні мови представляють не місце в пам'яті, а логічні сигнали (0 або 1) або групи сигналів в комутованих лініях. На виході такого компілятора виходить схема пристрою на відповідній мові.
Інтерпретатори запитів. Дані інтерпретатори транслюють предикати, що містять оператори відношення і логічні оператори, в командах пошуку в базі даних записів, що задовольняють даному предикату[1].
При створенні цільової програми, окрім компілятора, може бути потрібним і ряд інших програм. Початкова програма може бути розділена на модулі, що зберігаються в окремих файлах. Задача збору початкової програми іноді доручається окремій програмі – препроцесору, який може також розкривати в тексті початкової програми скорочення, так звані макроси.
Цільова програма, створювана компілятором, може зажадати додаткову обробку перед запуском. Компілятор, створює асемблерний код, який переводиться асемблером в машинний код, а потім зв'язується («лінкуєтся») спільно з деякими бібліотечними програмами в код, що реально запускається на машині.
<Number>:= 0|1|2|3|4|5|6|7|8|9
<Big_letter>:= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
<Small_letter>:= a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
<Constant>:= [–]<number>[{<number>}]
<Ident>:= <Big_letter>[{<Small_letter>|<Big_letter>|<Number>}]
<Type>:= Integer|Bool
<Operation_а>:= +|–
<Operation_m>:= Mul|Div|Mod
<Operation_l>:=!!|&&| ||
<Compare>:= ==|!=|Le|Ge
<Cycle>:= For <Ident>|<Constant> DownTo <Ident>|Constant> <Blok>
<Input>:= Input
<Output>:= Output
<Statement>:= <Input>|<Output>|<Equation>
<Equation>:= <Ident>:= {[(]<Ident>|<Const> <Operation_a>|<Operation_m>|<Operation_l> <Ident>|<Const>[)]}|< Ident>|<Const> <Compare> < Ident>|<Const>
<Blok>:= Start [<Statement>|<Cycle>] Finish
<Declaration>:= Var <Type>[<Ident>]
<Program>:= Program<Ident><Declaration><Blok>
Program – означає початок тексту програми, наступним описується ім’я програми;
Var – блок опису змінних;
Start – початок тіла програми (циклу);
Finish – кінець тіла програми (циклу);
Input – оператор вводу змінних;
Output – оператор виводу (змінних і рядкових констант).
:= – оператор присвоєння;
For – початок циклу, наступним описується початкове значення відліку;
DownTo – опис кінцевого значення відліку (крок циклу – 1);
+ – операція додавання;
– – операція віднімання;
Mul – операція множення;
Div – операція ділення;
Mod – операція знаходження залишку від ділення;
== – операція перевірки на рівність;
!= – перевірка на нерівність;
Le – перевірка чи менше/рівно;
Ge – перевірка чи більше/рівно;
!! – операція логічного заперечення;
&& – кон’юнкція;
|| – диз’юнкція;
Integer – 32‑ох розрядні знакові цілі;
Bool – однобайтні логічні змінні;
/* – початок коментарів;
*/ – кінець коментарів;
<< – початок рядкової константи при операції виводу;
>> – кінець рядкової константи при операції виводу;
– розділювач між аргументами;
; – ознака кінця оператора;
(– відкриваюча дужка;
) – закриваюча дужка;
Як термінальні символи використовуються також усі індійські цифри (0–9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл та синтаксичні знаки (!,?,\,/, %,$,@,^,_).
3. Розробка транслятора вхідної мови програмування
Необхідно вибрати ефективні методи розв’язку загальних задач, таких як розпізнавання лексем, синтаксичний розбір, семантичний аналіз та організація вводу / виводу, обчислення арифметичних виразів та організація вкладених операторів. Для реалізації лексичного аналізу в курсовій роботі використано метод перебору, тобто до чергової лексеми додається наступна буква, а тоді здійснюється пошук лексеми в таблицях ключових слів, та ідентифікаторів, якщо лексема не знайдена, тоді видається повідомлення про помилку. Під час аналізу поточних лексем здійснюється перевірка на наявність коментарів та рядкових констант при виводі. Окремим проходом формується таблиця лексем, в яку коментарі не вносяться. Таблиця лексем містить рядок, в якому була знайдена лексема, саму лексему, клас лексеми та її код. Синтаксичний аналіз базується на перевірці послідовності класів лексем, наприклад, якщо після оператора присвоєння слідує синтаксична лексема, чи після математичного оператора слідує лексема з класу порівнянь, то буде сформовано повідомлення по помилку. Для розробки синтаксичного аналізатора використано модель автомата з магазинною пам’яттю. На фазі семантичного аналізу здійснюється перевірка на відповідність типів. На цьому етапі перевіряється, чи не використовуються в одному виразі змінні одного типу, та чи не застосовано до них недопустимих операцій. Генератор коду починає свою роботу, якщо на попередніх фазах не було виявлено помилок. В залежності від коду лексеми в асемблерний файл вставляється конкретний набір процедур. Для реалізації обчислень арифметичних виразів використовується переведення їх у постфіксну форму, після чого такий вираз обчислюється з використанням математичного співпроцесора. Для переведення виразу у постфіксну форму використовується структура даних стек. Стек реалізований на масиві. В даному випадку використано стандартний набір функцій: Init (створення нового стеку), Empty (перевірка чи стек порожній), Full (перевірка чи стек повний), Push (заштовхування елементу у вершину стеку), Pop (вилучення елементу із вершини стеку). Ввід та вивід реалізовано за допомогою 21‑го переривання, функції 02h для посимвольного виводу тa 0Аh для вводу в буфер з подальшим розпізнаванням. Цикл реалізовано за допомогою команди далекого переходу (far ptr). Логічні операції виконуються над аргументами побітово, з використанням асемблерних команд AND, OR, NOT.