Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка компілятора з вхідної мови програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
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).
№
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
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_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).
/
Рисунок 4 Місце синтаксичного аналізатора в моделі компілятора
3.2.1 Обробка синтаксичних помилок
Якщо компілятор матиме справу виключно з коректними програмами, його розробка і реалізація істотно спрощуються. Проте дуже часто програмісти пишуть програми з помилками, і добрий компілятор повинен допомогти програмісту знайти їх і локалізувати. Примітно, що хоча помилки — явище надзвичайно поширене, лише в декількох мовах питання обробки помилок розглядалося ще на фазі створення мови. Наша цивілізація істотно відрізнялася б від свого нинішнього стану, якби в природних мовах були такі ж вимоги до синтаксичної точності, як і в мовах програмування.
Більшість специфікацій мов програмування, проте, не визначає реакції компілятора на помилки — це питання віддається на відкуп розробникам компілятора. Проте планування системи обробки помилок з самого початку роботи над компілятором може як спростити його структуру, так і поліпшити його реакцію на помилки.
Будь-яка програма потенційно містить безліч помилок самого різного рівня. Наприклад, помилки можуть бути
• лексичними, такими як невірно записані ідентифікатори, ключові слова або оператори;
• синтаксичними, наприклад, арифметичні вирази з незбалансованими дужками;
• семантичними, такими як оператори, використані до несумісних операндів;
• логічними, наприклад нескінченна рекурсія.
Часто основні дії по виявленню помилок і відновленню після них концентруються у фазі синтаксичного аналізу. Одна з причин цього полягає в тому, що багато помилок за своєю природою є синтаксичними або виявляються, коли потік токенів, що йде від лексичного аналізатора, порушує визначаючі мова програмування граматичні правила. Друга причина полягає в точності сучасних методів розбору; вони дуже ефективно виявляють синтаксичні помилки в програмі. Визначення присутності в програмі семантичних або логічних помилок — задача набагато складніша.
Обробник помилок синтаксичного аналізатора має просту формульовану мету:
• він повинен ясно і точно повідомляти про наявність помилок;
• він повинен забезпечувати швидке відновлення після помилки, щоб продовжити пошук подальших помилок;
• він не повинен істотно уповільнювати обробку коректної програми.
Ефективна реалізація цієї мети є вельми складною задачею. На щастя, звичайні помилки достатньо прості, і для їх обробки часто достатньо простих механізмів обробки помилок.
В деяких випадках, проте, помилка може відбутися задовго до моменту її виявлення (і за багато рядків коду до місця її виявлення), і визначити її природу вельми непросто. В складних ситуаціях обробник помилок, по суті, повинен просто здогадатися, що саме мав на увазі програміст, коли писав програму. Деякі методи розбору, такі як LL і LR, виявляють помилки, як тільки це стає можливим. Точніше кажучи, вони володіють властивістю перевірки коректності префіксів, тобто виявляють помилку, як тільки з'ясовується що префікс вхідної інформації не є префіксом жодного коректного рядка мови.
3.3 Розробка семантичного аналізатора
В процесі роботи компілятор зберігає інформацію про об'єкти програми. Як правило, інформація про кожний об'єкт складається із двох основних елементів: імені об'єкта і його властивостей. Інформація про об'єкти програми повинна бути організована так, щоб пошук її був по можливості швидше, а необхідної пам'яті по можливості менше. Крім того, з боку мови програмування можуть бути додаткові вимоги.
Імена можуть мати певну область видимості. Наприклад поле запису повинне бути унікально в межах структури (або рівня структури), але може співпадати з ім'ям об'єктів зовні запису (або іншого рівня запису). В той же час ім'я поля може відкриватися оператором приєднання, і тоді може виникнути конфлікт імен (або неоднозначність в трактуванні імені). Якщо мова має блокову структуру, то необхідно забезпечити такий спосіб зберігання інформації, щоб, по-перше підтримувати блоковий механізм видимості, а по-друге – ефективно звільняти пам'ять по виході з блоку. В деяких мовах (наприклад, Аді) одночасно (в одному блоці) можуть бути видимі декілька об'єктів з одним ім'ям, в інших така ситуація неприпустима. Є декілька основних способів організації інформації в компіляторах:
таблиці ідентифікаторів;
таблиці символів;
способи реалізації блокової структури;
Перевірка типів
Компілятор повинен переконатися, що початкова програма слідує як синтаксичним, так і семантичним угодам початкової мови. Така перевірка, іменована статичній (static checking), — на відміну від динамічної, виконуваної в процесі роботи цільової програми, — гарантує, що будуть виявлені певні типи програмних помилок.
Нижче представлені приклади статичних перевірок.
1. Перевірки типів. Компілятор повинен повідомляти про помилку, якщо оператор застосовується до несумісному з ним операнда, наприклад при складанні змінних, що є масивом і функцією.
2. Перевірки управління. Передача управління за межі мовних конструкцій повинна проводитися в певне місце. Наприклад, в мові програмування С оператор break передає управління за межі самої вкладеної інструкції while, for або switch; якщо ж такі відсутні, то виводиться повідомлення про помилку.
3. Перевірки єдиності. Існують ситуації, коли об'єкт може бути визначений тільки один раз. Наприклад, в мові програмування Pascal ідентифікатор повинен оголошуватися тільки один раз, всі мітки в конструкції case повинні бути різний, а елементи в скалярному типі не повинні повторюватися.
4. Перевірки, пов'язані з іменами. Іноді одне і те ж ім'я повинне використовуватися двічі (або більше число раз). Наприклад, в мові програмування Ada цикл або блок може мати ім'я, яке повинне знаходитися як на початку, так і в кінці конструкції.
Компілятор повинен перевірити, що в обох місцях використовується одне і те ж ім'я. В цьому розділі нас, в першу чергу, цікавить перевірка типів. Як видно з наведених приклади, більшість інших статичних перевірок є рутинною і може бути реалізований з використанням технологій, описаних в попередньому розділі. Деякі з них можуть використовуватися і для виконання інших дій. Наприклад, при внесенні інформації про ім'я в таблицю символів ми можемо переконатися в єдиності оголошення даного імені. Багато компіляторів Pascal об'єднують статичні перевірки і генерацію проміжного коду з синтаксичним аналізом. За наявності складніших конструкцій, на зразок тих, що використовуються в мові програмування Ada, може виявитися більш зручним виконати окремий прохід для проведення перевірок типів між синтаксичним аналізом і генерацією проміжного коду, як показано на рисунку 5.
/
Рисунок 5 Місце семантичного аналізатора в моделі компілятора.
Програма перевірки типів перевіряє, щоб тип конструкції відповідав очікуваному в даному контексті. Наприклад, вбудований арифметичний оператор mod в Pascal вимагає цілих операндів, тому програма перевірки типів повинна перевірити, щоб операнди mod в початковій програмі — цілого типу. Так само програма перевірки типів повинна переконатися, що операція розіменування застосовується до покажчика, індексація виконується з масивом, що визначена користувачем функція.
3.4 Розробка оптимізатора коду
компілятор програмування оболонка операційна
Оптимізація програмного коду - це модифікація програм, виконувана оптимізуючим компілятором або інтерпретатором з метою поліпшення їхніх характеристик, таких як продуктивності або компактності, - без зміни функціональності.
Оптимізація - не обов'язковий, але важливий етап компіляції. У принципі, вона може відбуватися під час трансляції програми, але, як правило, оптимізацію програми виділяють як окремий етап функціонування компіляторів. Компонувальники також можуть виконувати частина оптимізацій, таких як видалення невикористовуваних підпрограм або перевпорядкування підпрограм.
Розрізняють низько- і високорівневу оптимізацію. Низкорівнева оптимізація перетворює програму на рівні елементарних команд, наприклад, інструкцій процесорів архітектури x86. Високорівнева оптимізація здійснюється на рівні структурних елементів програми, таких як розгалуження й цикли.
3.5 Розробка генератора коду
Останньою стадією розробки компілятора є генератор коду, який дістає на вхід проміжне представлення вихідної програми і виводить еквівалентну цільову програму.
Традиційно, до генератора коду висуваються жорсткі вимоги. Вихідний код повинен бути коректним і високоякісним, що означає ефективне використання ресурсів цільової машини. Крім того, ефективно повинен бути розроблений і сам генератор коду.
Математично, проблема генерації оптимального коду є нерозв’язною. На практиці ми вимушені користуватись евристичними технологіями, які дають хороший, але не обов’язково оптимальний код. Вибір евристики дуже важливий, оскільки детально розроблений алгоритм розробки генератора коду може давати код, що працю в декілька раз швидше, ніж код отриманий недостатньо продуманим алгоритмом.
Хоча дрібні деталі генератора колу залежать від цільової машини і операційної системи, такі питання, як керування пам’яттю, вибір інструкцій, розподіл регістрів і порядок обчислень, властиві усім задачам, зв’язаним з генерацією коду.
Вхідний потік генератора коду являє собою проміжне представлення вихідної програми, отримане на початковій стадії компіляції, разом із таблицею символів, яка використовується для обчислення адрес часу виконання об’єктів даних, зазначених в проміжному представленні іменами.
Результатом генератора коду являється цільова програма. Подібно до проміжного коду, результат генератора коду може приймати різні види: абсолютний машинний код, переміщуваний машинний код, або асемблерна мова. Перевагою генерації абсолютної програми в машинному коді є те, що такий код поміщається у фіксоване місце пам’яті і негайно виконується. Невеликі програми при цьому швидко компілюються і виконуються.
Генерація переміщуваної програми у машинному коді (об’єктного модуля) забезпечує можливість роздільної компіляції підпрограм. Багато переміщуваних модулів можуть бути після цього зв’язані в одне ціле і завантажені на виконання спеціальною програмою – завантажувачем. Додаткові затрати на зв’язування і завантаження компенсуються можливістю роздільної компіляції підпрограм і викликом інших, раніше скомпільованих підпрограм із об’єктних модулів. Якщо цільова машина не обробляє переміщення автоматично, компілятор має надати завантажувачеві явну інформацю про переміщення для зв’язування сегментів роздільно скомпільованиз підпрограм.
Отримання на виході генератора коду програми на мові асемблера трохи полегшує процес генерації коду; в результаті ми можемо створювати символьні інструкції і використовувати можливості макросів асемблера. Плата за цю простоту – додатковий крок в обробці мови програмування асемблер після генерації коду.
4 Відладка та тестування компілятора
4.6.1 Виявлення лексичних помилок
Повідомлення про лексичну помилку виводиться, коли лексичний аналізатор знаходить лексему, що не відповідає лексиці мови програмування та ні одному з імен описаних користувачем змінних. Для перевірки розробленого компілятора на виявлення лексичних помилок внесемо в текст програми помилку – лексему BegAn.
'Error 13: Невідомий символ: BegAn '
З повідомлення стає зрозуміло, що в ході компіляції було виявлено невідомий символ ’ BegAn’ в 2-ому рядку.
Під час роботи сканера може виникнути помилка вище наведеного типу (тобто виявлено невідому лексему), а також неправильне оголошення ім’я змінної (коли першою є цифра).
Результат тестування в додатку Б.
4.6.2 Виявлення синтаксичних помилок
Повідомлення про синтаксичну помилку виводиться, коли синтаксичний аналізатор знаходить ланцюжок лексем, що не відповідає граматиці заданої мови. Для перевірки компілятора на виявлення синтаксичних помилок пропустимо в тексті програми роздільник «;».
В результаті на екрані отримуємо наступні повідомлення:
Error15: Пропущено ; пiсля операцii writeln'
З повідомлення випливає, що в ході компіляції було виявлено синтаксичну помилку – пропущено роздільник ’;’. Після цього компіляцію було перервано.
Результат тестування в додатку Б.
4.6.3 Виявлення семантичних помилок
Повідомлення про семантичну помилку виводиться семантичним аналізатором, коли у виразі не співпадають типи використовуваних змінних. Для перевірки компілятора на виявлення семантичних помилок внесемо в текст програми вираз з використанням змінних різних типів. Результат тестування в додатку Б.
'Error 18: Пропущено змінну: b'
З повідомлення випливає, що в ході компіляції було виявлено семантичну помилку – було виявлено неоголошену змінну b. Після чого компіляцію було перервано.
Можливі наступні типи семантичні помилок, що реалізовані в компіляторі:
Багатократне оголошення;
Змінна не оголошена;
Змінна не ініціалізована;
Не співпадіння типів змінних.
4.6.4 Загальна перевірка коректності роботи транслятора
Загальна перевірка полягає у здатності розробленого компілятора виконувати свої функції. Компілятор повинен транслювати програму у проміжне представлення на мові асемблер та створювати об’єктний і виконуваний файли за допомогою файлів tasm.exe та tlink.exe. Результат тестування в додатку Б.
Висновок
Під час виконання курсової роботи:
Складено формальний опис мови програмування М13 у формі розширеної нотації Бекуса-Наура, дано опис усіх символів та ключових слів.
Створено компілятор мови програмування М13, а саме:
Розроблено лексичний аналізатор, здатний розпізнавати лексеми, що є описані в формальному описі мови програмування, та додані під час безпосереднього використання компілятора.
Розроблено синтаксичний аналізатор на основі автомата з магазинною пам’яттю. Складено таблицю переходів для даного автомата згідно правил записаних в нотації у формі Бекуса-Наура.
Розроблено генератор коду, який починає свою роботу після того, як лексичним, синтаксичним та семантичним аналізатором не було виявлено помилок у програмі, написаній мовою М13. Проміжним кодом генератора є програма на мові Assembler(i8086). Вихідним кодом є машинний код, що міститься у виконуваному файлі
Проведене тестування компілятора за допомогою тестових програм за наступними пунктами:
Виявлення лексичних помилок.
Виявлення синтаксичних помилок.
Загальна перевірка роботи компілятора.
Тестування не виявило помилок в роботі компілятора, а всі помилки в тестових програмах мовою М13 були виявлені і дано попередження про їх наявність.
В результаті виконання даної курсової роботи було успішно засвоєно методи розробки та реалізації компонент системного програмного забезпечення.
Список використаної літератури
Бек Л.С. Введение в системное програмирование. – М.:Мир, 1988.
Касаткин М.В. Касаткина Т.Я. Професиональное програмирование на языке С.В 3т. – М. Мир, 1989.//т.3. Системное програмирование.
Кузьмин А.Я. Лексический анализ. – М.:ВШ.,1985.
Фролов А.
12.12.2012 20:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора