Курсовая работа: Розробка системних програмних модулів та компонент систем програмування
Курсовая работа: Розробка системних програмних модулів та компонент систем програмування
Курсова робота
З дисципліни: «Системне програмування»
На тему: «Розробка системних програмних модулів та компонент систем програмування»
На перший погляд, різноманітність компіляторів вражає. Використовуються тисяч вихідних мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, які виникають у всіх областях застосування комп’ютера. Цільові мови не менш різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп’ютерів. Деколи компілятори класифікують як однопрохідні, багато прохідні, виконуючі (load-and-go), відлагоджуючі, оптимізуючи – в залежності від призначення і принципів і технологій їх створення.
Не дивлячись на те, що основні задачі, що виконуються компіляторами видаються складними і різноманітними, по суті вони одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних вихідних мов і цільових машин з використанням одних і тих же базових технологій.
В 50‑х роках про компілятори ходила слава, що це програми, дуже складні в написанн (наприклад, перший компілятор Fortran потребував 18 людино-років роботи). З того часу розроблені різноманітні систематичні технології вирішення багатьох задач, виникаючих при компіляції. Крім цього, розроблені хороші мови реалізації, програмні середовища та програмні інструменти. Завдяки цьому «солідний» компілятор може бути реалізований в якості курсової роботи з проектування компіляторів [1].
1. Огляд способів та методів проектування трансляторів
1.1 Модель аналізу-синтезу компіляції
Компіляція складається з двох частин: аналізу і синтезу. Аналіз – це розбиття початково програми на складові частини і створення її проміжного представлення. Синтез конструювання необхідної цільової програми з проміжного представлення.
В процесі аналізу визначаються і записуються в ієрархічну деревовидну структуру операції, задані початковою програмою. Часто використовується спеціальний вид дерева, що називається синтаксичним (або деревом синтаксичного розбору), в якому кожен вузол представляє операцію, а його дочірні вузли – аргументи операції.
Багато програмних інструментів, працюючи з початковими програмами, спочатку виконують певний вид аналізу. Розглянемо приклади таких інструментів.
Структурн редактори. Ці програми одержують як вхід послідовність команд для побудови початкової програми. Такий редактор не тільки виконує звичні для текстового редактора функції зі створення і модифікації тексту, але і аналізу текст програми, поміщаючи в початкову програму відповідну ієрархічну структуру. Тим самим він виконує додаткові задачі, що полегшують підготовку програми. Наприклад, редактор може перевіряти коректність введеного тексту, автоматично додавати структурні елементи (так, якщо користувач введе while, редактор додасть відповідне йому ключове слово do і запропонує ввести умовний вираз між ними) або переходить від ключового слова begin або лівої дужки до відповідного end або правої дужки. Більше того, результат на виході такого редактора часто подібний результату після фази аналізу компіляції.
Програми форматованого виводу для друку. За допомогою цих інструментів програма аналізується і роздруковується так, щоб її структура була максимально ясною. Наприклад, коментарі можуть бути виділені спеціальним шрифтом, а оператори виведені з відступами, що вказують рівень вкладеності в ієрархічній структур операторів.
1.2 Компілятори
Статичн перевіряючі програми. Дані інструменти зчитують програми, аналізують х і намагаються знайти потенційні помилки без запуску програми. Такий аналіз часто дуже схожий на аналіз в оптимізуючих компіляторах. Наприклад, статична перевіряюча програма може визначити невиконання якоїсь частини початково програми або використання деякої змінної до її оголошення. Так само можуть бути знайдені логічні помилки, наприклад спроби використання дійсної змінної як покажчик (із застосуванням технології перевірки типів).
Інтерпретатори. Замість створення цільової програми в результаті трансляції інтерпретатор викону операції, вказані в початковій програмі. Наприклад, для оператора присвоєння він може побудувати дерево розбору, а потім виконати операції, проходячи по його вузлах, Корінь дерева вказує на виконання присвоєння, так що інтерпретатор викличе підпрограму для обчислення виразу, що визначається одним із піддерев, а потім збереже його значення у виділеній змінній. Таке піддерево вказу підпрограмі, що вона повинна обчислити суму двох виразів. Рекурсивний виклик підпрограми приводить до обчислення значення, яке потім підсумовується зберігається. Інтерпретатори часто використовуються для командних мов, оскільки кожен їх оператор є викликом складної програми, такої як редактор або компілятор. Так само і деякі мови «дуже високого рівня», типу APL, переважно нтерпретуються, оскільки є безліч атрибутів даних, таких як розмір або тип масиву, які не можуть бути визначені в процесі компіляції.
Традиційно ми говоримо про компілятор як про програму, яка транслює початкову мову типу Fortran в асемблер або машинну мову. Проте є і інші застосування технолог компіляції. Так, аналізуюча частина в кожному з приведених нижче прикладів подібна аналізатору звичайного компілятора.
Форматування тексту. Програма форматування тексту одержує на вхід потік символів, більшість з яких представляє текст, що виводиться, але багато символів означа абзаци, малюнки або математичні структури, наприклад верхні або нижні індекси.
«Кремнієві» компілятори (Silicon compilers). Такий компілятор має початкову мову, схожу із звичною мовою програмування. Проте змінні мови представляють не місце в пам'яті, а логічні сигнали (0 або 1) або групи сигналів в комутованих лініях. На виході такого компілятора виходить схема пристрою на відповідній мові.
Інтерпретатори запитів. Дані інтерпретатори транслюють предикати, що містять оператори відношення і логічні оператори, в командах пошуку в базі даних записів, що задовольняють даному предикату[1].
1.3 Контекст компілятора
При створенні цільової програми, окрім компілятора, може бути потрібним і ряд інших програм. Початкова програма може бути розділена на модулі, що зберігаються в окремих файлах. Задача збору початкової програми іноді доручається окремій програмі – препроцесору, який може також розкривати в тексті початково програми скорочення, так звані макроси.
Цільова програма, створювана компілятором, може зажадати додаткову обробку перед запуском. Компілятор, створює асемблерний код, який переводиться асемблером в машинний код, а потім зв'язується («лінкуєтся») спільно з деякими бібліотечними програмами в код, що реально запускається на машині.
2. Формальний опис вхідної мови програмування
2.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>]
<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>:= <Const>[)]|< Ident>|<Const> <Compare> < Ident>|<Const>
<Blok>:= Start [<Statement>|<Cycle>] Finish
<Declaration>:= Var <Type>[<Ident>]
<Program>:= Program<Ident><Declaration><Blok>
2.2 Опис термінальних символів та ключових слів
Program – означає початок тексту програми, наступним описується ім’я програми;
Var – блок опису змінних;
Start – початок тіла програми (циклу);
Finish – кінець тіла програми (циклу);
Input – оператор вводу змінних;
Output – оператор виводу (змінних і рядкових констант).
:= – оператор присвоєння;
For – початок циклу, наступним описується початкове значення відліку;
DownTo – опис кінцевого значення відліку (крок циклу – 1);
+ операція додавання;
– – операція віднімання;
Mul операція множення;
Div операція ділення;
Mod операція знаходження залишку від ділення;
== операція перевірки на рівність;
!= перевірка на нерівність;
Le – перевірка чи менше/рівно;
Ge – перевірка чи більше/рівно;
!! операція логічного заперечення;
&& кон’юнкція;
|| диз’юнкція;
Integer – 32‑ох розрядні знакові цілі;
Bool – однобайтн логічні змінні;
/* початок коментарів;
*/ кінець коментарів;
<< – початок рядкової константи при операції виводу;
>> – кінець рядкової константи при операції виводу;
розділювач між аргументами;
; ознака кінця оператора;
(– відкриваюча дужка;
) закриваюча дужка;
Як термінальні символи використовуються також усі індійські цифри (0–9), латинськ букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл та синтаксичні знаки (!,?,\,/, %,$,@,^,_).
3. Розробка транслятора вхідної мови програмування
3.1 Вибір технолог програмування
Необхідно вибрати ефективні методи розв’язку загальних задач, таких як розпізнавання лексем, синтаксичний розбір, семантичний аналіз та організація вводу / виводу, обчислення арифметичних виразів та організація вкладених операторів. Для реалізації лексичного аналізу в курсовій роботі використано метод перебору, тобто до чергової лексеми додається наступна буква, а тоді здійснюється пошук лексеми в таблицях ключових слів, та ідентифікаторів, якщо лексема не знайдена, тоді видається повідомлення про помилку. Під час аналізу поточних лексем здійснюється перевірка на наявність коментарів та рядкових констант при виводі. Окремим проходом формується таблиця лексем, в яку коментарі не вносяться. Таблиця лексем містить рядок, в якому була знайдена лексема, саму лексему, клас лексеми та її код. Синтаксичний аналіз базується на перевірці послідовност класів лексем, наприклад, якщо після оператора присвоєння слідує синтаксична лексема, чи після математичного оператора слідує лексема з класу порівнянь, то буде сформовано повідомлення по помилку. Для розробки синтаксичного аналізатора використано модель автомата з магазинною пам’яттю. На фазі семантичного аналізу здійснюється перевірка на відповідність типів. На цьому етапі перевіряється, чи не використовуються в одному виразі змінні одного типу, та чи не застосовано до них недопустимих операцій. Генератор коду починає свою роботу, якщо на попередніх фазах не було виявлено помилок. В залежності від коду лексеми в асемблерний файл вставляється конкретний набір процедур. Для реалізац обчислень арифметичних виразів використовується переведення їх у постфіксну форму, після чого такий вираз обчислюється з використанням математичного співпроцесора. Для переведення виразу у постфіксну форму використовується структура даних стек. Стек реалізований на масиві. В даному випадку використано стандартний набір функцій: Init (створення нового стеку), Empty (перевірка чи стек порожній), Full (перевірка чи стек повний), Push (заштовхування елементу у вершину стеку), Pop (вилучення елементу із вершини стеку). Ввід та вивід реалізовано за допомогою 21‑го переривання, функції 02h для посимвольного виводу тa 0Аh для вводу в буфер з подальшим розпізнаванням. Цикл реалізовано за допомогою команди далекого переходу (far ptr). Логічн операції виконуються над аргументами побітово, з використанням асемблерних команд AND, OR, NOT.
3.2 Проектування таблиць транслятора та вибір структур даних
Для реалізації лексичного аналізу створюємо таблицю, в яку поміщаємо вс зарезервовані слова (char table[31] [10]), в курсовій роботі їх використовується 31‑е, і таблицю (char name[20] [7]) для ідентифікаторів, які будуть введені користувачем. Ім’я програми в цю таблицю не заноситься. Для реалізац таблиці лексем описана така структура:
struct Ltable
{
int num;
char slovo[30];
int klas;
char atribute;
int code;
};
Поле num призначене для зберігання рядка, в якому знаходиться лексема;
Поле slovo призначене для зберігання самої лексеми;
Поле klas призначене для зберігання класу до якого належить лексема;
Поле atribute призначене для зберігання атрибуту лексеми – «і» для ідентифікаторів цілого типу, «b» для логічних дентифікаторів та «0» для всіх решта;
Поле code призначене для зберігання коду лексеми.
Сама таблиця лексем є масивом таких структур.
Лексеми мають такі класи:
Клас лексем блоку 1
клас операторів вводу виводу 2
клас операторів присвоєння 3
клас математичних операторів 4
клас операторів порівняння 5
клас логічних операторів 6
клас дентифікаторів 7
клас операторів циклу 8
клас лексем оголошення 9
клас лексем опису і аргументів виводу 10
клас синтаксичних лексем 11
клас констант 12
Відомост про класи з таблиці лексем використовуються при синтаксичному аналізі. Інформація з поля atribute використовується при семантичному аналізі.
Ключов слова мають такі коди:
Program 0
Var 1
Start 2
Finish 3
Input 4
Output 5
For 6
DownTo 7
+ 8
– 9
Mul 10
Div 11
Mod 12
:= 13
== 14
!= 15
Le 16
Ge 17
!! 18
&& 19
|| 20
(21
) 22
; 23
24
<< 25
>> 26
Integer 27
Bool 28
Ус дентифікатори та цифрові константи отримують код 30. Коди використовуються генератором коду для формування відповідних процедур мовою асемблер.
Для реалізації стеку використано таку структуру:
struct stacktype
{char data[20] [10];
int prior[20];
int kod[20];
int top;
};
Поле data використовується для зберігання символу операції;
Поле prior використовується для зберігання пріоритету операції;
Страницы: 1, 2
