Курсовая работа: Розробка компілятора з вхідної мови програмування

Курсовая работа: Розробка компілятора з вхідної мови програмування

Міністерство освіти і науки України

Національний університет “Львівська політехніка”

КУРСОВА РОБОТА

З дисципліни: «Системне програмування»

на тему:

“Розробка компілятора з вхідної мови програмування”

Виконав: студ. гр. КІМ-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 - років роботи). З тих пір розроблені різноманітні системні технології рішення багатьох задач, що виникають при компіляції. Крім того, розроблені хороші мови реалізації, програмні середовища і програмний інструментарій. Проблема компіляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови.. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою компілятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього компілятор має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати об'єктний код або виконавчий модуль. Сьогодні від компілятора вимагається також створення оптимізованого коду програми. Тому створення ефективного виконавчого коду є дуже проблемою в наш час, бо для створення цього необхідно враховувати всі можливі варіанти покращеної апаратної частини, розвиток якої досяг сьогодні теоретичної межі продуктивності.

Завдяки цьому "солідний компілятор" може бути реалізований навіть як курсова робота по проектуванню компіляторів.

1. Завдання на курсовий проект

Розробити компілятор з вхідної мови програмування короткий опис якої подано нижче (у відповідності з заданим варіантом) з виводом необхідної проміжної інформації на кожному кроці. Розробити інтерфейс користувача (інтегроване середовище програмування вхідною мовою).

Варіант № 13

В таблиці варіанта завдання використано наступні позначення:

A: Тип даних: byte(1).

B: Додаткова арифметична операція: ^ (піднесення до степеня).

C: Додаткова логічна операція: NOT.

D: Оператор циклу: do-while (2).

2. Формальний опис вхідної мови програмування

Розробити компілятор заданої вхідної мови програмування.

-  три типи даних: логічний тип даних (boolean), знаковий цілочисельний тип (1byte) та беззнаковий цілочисельний тип розміром 1 байт;

-  змінних з довільної довжини;

-  арифметичні операції над цілими: +, -, *, /, “-” (унарний мінус), ^ (операція піднесення до степеню);

-  символи групування арифметичних операцій “(” , “)”

-  логічні операції над цілими: <, >, ==, | = ;

-  логічну операцію над логічними даними NOT;

-  оператор присвоєння “=”;

-  оператори блоку “{“ , “}”;

-  оператор виводу (print);

-  оператор виконання дії за умовою (if-then-else);

-  оператор циклу (do-while);

Визначимо окремі термінальні символи та нерозривні набори термін.

Символів(ключові слова);

{( usigned

} ) char

; < if

= > then

+ = = else

- <> while

^ NOT do

* program true

/ bool false

print

До термінальних символів віднесемо також усі цифри (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_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), який реалізує функції операційних та управляючих компонентів. Разом з інтерфейсним обладнанням він реалізує комунікаційний компонент, який забезпечує зв’язок ВМ із зовнішнім світом.

Загальна схема компілятора

Можна виділити сім різних логічних задач:

а.  Інтерпретація – визначення точного змістового навантаження, створення матриці та таблиць з допомогою програм інтерпретації;

б.  Машинно-незалежна оптимізація – створення оптимальнішої матриці;

в.  Лексичний аналіз – розпізнавання базових елементів та створення стандартних символів;

г.  Синтаксичний аналіз – розпізнавання базових синтаксичних конструкцій з використанням редукцій;

д.  Розподіл пам’яті – модифікація таблиць ідентифікаторів та літералів. В матриці розміщується інформація, з допомогою якої генерується код, який розподіляє динамічну пам’ять;

е.  Генерація коду – використання макропроцесора для отримання більш оптимального вихідного коду;

Фази з першої по четверту машинно-незалежні і визначаються тільки мовою. Фази з п’ятої по сьому – машинно-залежні і не залежать від мови. З метою забезпечення вищої ефективності ці фази можуть не розділятись так чітко.

Компілятор необхідно оцінювати не тільки по об’єктному коду, що генерується, але також і по об’єму оперативної пам’яті, що він займає і по часу, що потрібен для трансляції. На жаль, ці критерії оптимальності часто досить суперечливі. Крім того, оптимальність коду обернено пропорційна складності, розміру та часу роботи самого компілятора. Насправді необхідні компроміси.

Компілятором використовуються бази даних, що забезпечують зв’язки між фазами: вхідний код, таблиця стандартних символів, таблиця термінальних символів, таблиця ідентифікаторів, таблиця літералів, редукції, матриця, кодові продукції, код компоновки, кінцевий об’єктний код.

3.1 Розробка лексичного аналізатора

Для обробки текстів вхідних програм існує кілька способів побудови мовних процесорів. Одним з варіантів є інтерпретатор.

Інтерпретатор – це програма, яка обробляє вхідну програму, написану на вхідній мові і проводить обчислення, задані цією мовою.

Транслятор – програма, що обробляє вхідну програму, написану на вхідній мові і генерує програму на об’єктній мові. Об’єктна мова як правило є мовою деякої ЕОМ і таку програму одразу можна виконувати. Транслятори можна поділити на асемблери і компілятори, які транслюють відповідно мови низького і високого рівня.

Перед написанням компілятора вхідну мову потрібно подати в термінах деякої граматики. Ця граматика визначає форму або синтаксис допустимих виразів мови. Проблема компіляції – проблема пошуку в тексті вхідної програми конструкцій, що визначені граматикою та генерації відповідного коду для кожного виразу вхідної мови. Конструкції вхідної мови зручно подавати у вигляді лексем. Лексеми – це неділимі фундаментальні одиниці мови. Перегляд вхідного тексту та розпізнавання лексем називається лексичним аналізом, а процедура, яка його виконує – сканером. Після розпізнавання лексем кожен вираз можна розпізнати як окрему конструкцію мови, що описані граматикою. Цей процес називається синтаксичним аналізом.

Процес розробки компілятора можна зобразити такою схемою:

Рисунок 1 - Процес розробки компілятора.

Сканер або лексичний блок – одна з найпростіших частин компілятора. Він переглядає символи вхідної програми зліва направо і групує певні термінальні символи в єдині синтаксичні об’єкти. Цілі числа, ідентифікатори, символьні константи є нетермінальними символами і також групуються в таблиці.

Процес роботи лексичного аналізатора є складнішим. Побудований при лексичному аналізі список лексем проглядається зліва направо і аналізується. Є два основні способи для аналізу списку лексем. Це спосіб операторного передування і рекурсивний спуск.

Для роботи компілятора різна допоміжна інформація знаходиться в таблицях, якими дані передаються від одного до іншого етапу. В деяких реалізаціях записи, що заносяться в таблицю можуть мати різну довжину. Таким чином компілятору потрібні методи організації інформації, здатні швидко запам’ятати і видати інформацію про велику частину програми. Основну проблему синтаксичного аналізу можна сформулювати так: є велика кількість об’єктів, що можуть зустрічатися в програмі. Об'єкти можуть зустрічатися в непередбачуваному порядку. Як тільки об’єкт зустрівся, потрібно перевірити, чи не був він раніше занесений в таблицю. Якщо в таблиці об’єкту немає, його необхідно туди записати. Одним із способів запам'ятовування об'єктів є таблиці з прямим доступом.

При рекурсивному спуску відповідність блоків лексем синтаксичним правилам перевіряється відповідно до дерева розбору деякої конструкції.

Покажемо на прикладі дерево конструкції while мови С.

While (f+a*d) a=a+5;

Рисунок 2 Конструкції while мови С

При знаходженні ключового слова while перевіряється наявність дужки і викликається процедура перевірки запису виразу.

При перегляді виразу методом операторного передування лексеми проглядаються в обох напрямках, якщо це потрібно і визначається, чи порядок їх співпадає з описаними конструкціями.

На етапі синтаксичного аналізу визначаються помилки. Після того, як синтаксис оператора визначено, іде інтерпретація його значення, тобто семантичний аналіз. Кожній синтаксичній одиниці відповідає певне значення, яке може бути виражене в формі реальних входів або в проміжній формі. Проміжною формою синтаксичної конструкції є дерево розбору.

Після синтаксичного і семантичного аналізу тексту програми відбувається трансляція тексту в проміжну мову, якою у більшості випадків є асемблер. Трансляція тексту може відбуватись як за один, так і за декілька проходів. Перевагою однопрохідних компіляторів є те, що не потрібно підтримувати зв’язок між проходами, але недоліком є те, що всі змінні, функції, мітки і константи мусять обов’язково бути описані перед їх використанням.

Процес компіляції вхідного файлу можна розділити умовно на кілька етапів. Основні етапи – це лексичний, синтаксичний та семантичний аналіз та трансляція. На кожному з цих етапів дані представляються у зручному для обробки вигляді.

Для лексичного аналізу вхідними даними є текстовий файл. Лексичний аналізатор формує динамічний список в основній пам'яті, в якому кожен вузол містить як інформацію про лексему, так і вказівник на наступну лексему. Останній вказівник має значення NULL. Структура вузла списку:

NODE

{ int line;– номер рядка лексеми

int idlexem;– код лексеми (номер у таблиці)

int type;– тип, якщо це ідентифікатор

int is_int;– чи це ідентифікатор, чи рядкова константа, чи число

int is_ar;– кількість індексів масиву (для простої змінної – 0)

NODE* next; }– вказівник на наступний елемент списку

Кожен ідентифікатор, не знайдений в таблиці лексем, записується в таблицю лексем, що є двовимірним символьним масивом. Паралельно існує масив вказівників на список параметрів, в якому всі елементи, що відповідають функції, мають вказівник на список параметрів функції. Структура вузла цього списку:

FPAR {

int type;– тип параметра (1..4)

FPAR* next; }– вказівник на наступний елемент списку

Список лексем є вхідним для синтаксичного аналізатора, який є суміщений з семантичним. На виході синтаксичного аналізатора є інформація про аналіз, що записується у файл. Це є повідомлення про першу знайдену помилку або ж повідомлення про те, що помилок немає.

Якщо помилки немає, запускається транслятор, який транслює список лексем у файл на проміжній мові С++ відповідно до таблиці С-лексем і правил побудови вхідної мови.

Порміжний файл з розширенням с транслюється у ехе-файл стандартним компілятором bсс.ехе.

3.1.1 Розробка блок-схеми програми

Для побудови компілятора необхідно спроектувати його будову на рівні функцій і їх взаємозв'язків, тобто правил виклику. Це потрібно для побудови узгодженої багатомодульної структури при програмуванні зверху вниз. Кожну задачу розділяємо на дрібніші підзадачі, які потім в свою чергу уконкретнюємо.

Загальну структуру програми можна подати в такому спрощеному вигляді:

Рисунок 3 Загальна структура програми у спрощеному вигляді

3.2 Розробка синтаксичного аналізатора

Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.

Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Крім того, важливою функцією є локалізація синтаксичних помилок. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але задача синтаксичного аналізу не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції інформацію про знайдені і розібрані синтаксичні конструкції, якщо відокремлюється фаза генерації об’єктного коду.

Кожна мова програмування має правила, які визначають синтаксичну структуру коректних програм. В Pascal, наприклад, програма створюється з блоків, блок – з інструкцій, інструкції – з виразів, вирази – з токенів і т.д. Синтаксис конструкцій мови програмування може бути описаний за допомогою контекстно-вільних граматик або нотації БНФ (Backus-Naur Form, форма Бекуса-Наура). Граматики забезпечують значні переваги розробникам мов програмування і авторам компіляторів.

Граматика дає точну і при цьому просту для розуміння синтаксичну специфікацію мови програмування.

Для деяких класів граматик можливо автоматично побудувати ефективний синтаксичний аналізатор, який визначає, чи коректна структура початкової програми. Додатковою перевагою автоматичного створення аналізатора є можливість виявлення синтаксичних неоднозначностей та інших складних для розпізнавання конструкцій мови, які інакше могли б залишитися непоміченими на початкових фазах створення мови і його компілятора.

Правильно побудована граматика додає мові програмування структуру, яка сприяє полегшенню трансляції початкової програми в об'єктний код і виявленню помилок. Для перетворення описів трансляції, заснованих на граматиці мови, в робочій програмі є відповідний програмний інструментарій.

З часом мови еволюціонують, збагатившись новими конструкціями і виконуючи нові задачі. Додавання конструкцій в мову виявиться більш простою задачею, якщо існуюча реалізація мови заснована на його граматичному описі.

Є три основні типи синтаксичних аналізаторів граматик. Універсальні методи розбору, такі як алгоритми Кока-Янгера-Касамі або Ерлі, можуть працювати з будь-якою граматикою. Проте ці методи дуже неефективні для використання в промислових компіляторах. Методи, які звичайно використовуються в компіляторах, класифікуються як низхідні (зверху вниз, top-down) або висхідні (з низу до верху, bottom-up). Як видно з назв, низхідні синтаксичні аналізатори будують дерево розбору зверху вниз (до листя), тоді як висхідні починають з листя і йдуть до кореня. В обох випадках вхідний потік синтаксичного аналізатора сканується посимвольно зліва направо. Найефективніші низхідні і висхідні методи працюють тільки з підкласами граматик, проте деякі з цих підкласів, такі як LL- і LR-граматики, достатньо виразні для опису більшості синтаксичних конструкцій мов програмування. Реалізовані вручну синтаксичні аналізатори частіше працюють з LL-граматиками. Синтаксичні аналізатори для дещо більшого класу LR-граматик звичайно створюються за допомогою автоматизованих інструментів. Будемо вважати, що вихід синтаксичного аналізатора є деяким представленням дерева розбору вхідного потоку токенів, виданого лексичним аналізатором. На практиці є безліч задач, які можуть супроводжувати процес розбору, - наприклад, збір інформації про різні токени в таблиці символів, виконання перевірки типів і інших видів семантичного аналізу, а також створення проміжного коду. Всі ці задачі представлені одним блоком "Інші задачі початкової фази компіляції" ( рисунок 4).

Страницы: 1, 2