Розробка та вивчення компілятора

Размещено на http://www.allbest.ru/

Зміст

Вступ

1. Завдання на курсову роботу

2. Аналіз вихідного кодута його компіляція

2.1 Синтаксис вхідної програми

2.2 Початок роботи програми. Опрацювання вихідного тексту програми лексичним аналізатором

2.3 Синтаксичний аналіз

2.4 Генерація та оптимізація об'єктного коду

3. Графічний інтерфейс програми

Висновок

Список використаних джерел

Вступ

компілятор програма лексичний аналізатор

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

З розмежуванням задач, які повинна виконувати обчислювальна машина, почалось і розмежування програмного забезпечення, не тільки в плані функціоналу виконуваної роботи, а й в плані взаємодії з операційною системою, апаратним забезпеченням, користувачем. А з поділом програм виникла потреба в поділі мов програмування, на яких ці програми можна інтерпретувати - одні середовища розробки зробили ставку на пряму взаємодію з системою, інші - на простоту роботи для звичайного користувача. Зв'язок між мовою, на якій ми думаємо/програмуємо і завданнями та рішеннями, які ми можемо представляти в своїй уяві, дуже близька. З цієї причини обмежувати властивості мови тільки цілями виключення помилок програміста в кращому випадку небезпечно. Як і у випадку з природними мовами, є величезна користь бути, принаймі, двомовним. Мова надає програмісту набір концептуальних інструментів, якщо вони не відповідають завданню, то їх просто ігнорують. Гарне проектування і відсутність момилок може гарантуватися чисто за рахунок мовних засобів.

Компілятор (англ. tocompile- збирати в ціле), комп'ютерна програма (або набір програм) що перетворює програмний код, написаний певною мовою програмування, на семантично еквівалентний код в іншій мові програмування, який, як правило, необхідний для виконання програми

машиною, наприклад, комп'ютером. Завданням компілятора є повний переклад програми, написаний на одній з мов програмування (вихідній мові) в програму іншої мови програмування, до початку її виконання. Він оцінює її відповідно до синтаксичної конструкції мови та перекладає на машинну мову. Іншими словами, компілятор не виконує програми, він їх будує.

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

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

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

Для програмної реалізації завдання курсової роботи використовувалось середовище розробкиBorlandCodeGearRADStudioDelphi 2009.

1. Завдання на курсову роботу

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

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

Компілятор рекомендується побудувати з наступних складових частин:

лексичний аналізатор;

синтаксичний аналізатор;

оптимізатор;

генератор результуючого коду.

Для побудови компілятора рекомендується використовувати методи, освоєні в ході виконання лабораторних робіт по курсу «Системне програмне забезпечення». Вхідна мова компілятора повинна задовольняти наступним вимогам:

вхідна програма зачинається ключовим словом prog і закінчується ключовим словом end\

вхідна програма може бути розбита на рядки довільним чином, всі пропуски і переходи рядка повинні ігноруватися компілятором;

текст вхідної програми може містити коментарі будь-якої довжини, які повинні ігноруватися компілятором (вид коментаря заданий у варіанті завдання) ;

вхідна програма має бути єдиним модулем, що містить лінійну послідовність операторів, виклики процедур і функцій не передбачаються;

мають бути передбачені наступні варіанти операторів вхідної

програми:

оператор привласнення виду <змінна>: =^<вираз>;

умовний оператор вигляду if<умова>then<оператор>, або

і/<умова>then<оператор>else<оператор>

складений оператор виду begin. end;

оператор циклу, передбачений варіантом завдання;

вирази в операторах можуть містити наступні операції (мінімум) :

арифметичні операції складання (+) і віднімання (-) ;

операції порівняння менше (<), більше (>), рівно (=) ;

логічні операції «і» (and), «або» (or), «ні» (not) ;

додаткові арифметичні операції, передбачені варіантом завдання;

операндами у виразах можуть виступати ідентифікатори (змінні) іконстанти (тип допустимих констант вказаний у варіанті завдання) ;

всі ідентифікатори, що зустрічаються в вихіднійпрограмі, повинні сприйматися як змінні, що мають тип, заданого у варіанті завдання (попередній опис ідентифікаторів в вихідній програмі не потрібний) ;

повинні враховуватися два зумовлені ідентифікатори InpVar і CompileTest. сенс яких буде ясний з опису вихідної мови, щоприводиться нижче.

Пріоритет операцій виконавець роботи повинен вибрати самостійно (пріоритет операцій враховується в граматиці вхідної мови). Для зміни пріоритету операцій повинні використовуватися круглі дужки.

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

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

Компілятор повинен перевіряти наступні семантичні обмеження вхідної мови:

- не допускається присвоєння значень константам;

- не допускається привласнення значення ідентифікатору InpVar;

- не допускається використовувати ідентифікатор CompileTest інакше, як для привласнення йому значень.

Як вихідна (результуюча) мова повинна використовуватися мова асемблера, процесорів типу Intel 80x86 в модифікації вбудованої мови

асемблера компілятора Pascal виробництва фірми Borland.

Повинна використовуватись додаткова арифметична операція декрементування, тип циклу: цикл з передумовою, шістнадпяткові константи типу Word, та коментарі типу {. }

2. Аналіз вихідного коду та його компіляція

2.1 Синтаксис вхідної програми

Синтаксис - сторона мови програмування, яка описує структуру програм як наборів символів (зазвичай кажуть - безвідносно до змісту). Синтаксису мови протиставляється його семантика. Синтаксис мови описує «чисту» мову, в той же час семантика приписує значення (дії) різним синтаксичним конструкціям.

Кожна мова програмування має синтаксичний опис. Зазвичай синтаксис мови визначають за допомогою правил Бекуса-Наура.

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

Синтаксис вхідної програми дуже схожий на синтаксис мови Pascal, хоча і має деякі відмінності, а саме: для присвоєння значення змінній використовується знак рівності, для логічних операцій AND, OR, XOR і NOT використовуються спеціальні символи - «&», «|», «-» і «!» відповідно, для операції декрементування вирішено використати символ «-».

Константи оголошуються, як звичайні десяткові числа в діапазоні від 0 до 65 535, а в таблиці ідентифікаторів представляються у вигляді числа, що складається з чотирьох шістнадцяткових цифр.

Кількість змінних і констант може бути обмежена тільки об'ємом оперативної пам'яті комп'ютера.

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

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

В середині блоку можуть знаходитись вирази які містять арифметичні оператори: +, -, оператор декрементування; логічні оператори &, j,!, які означають операції and, or, хог і not відповідно; і на кінець оператори відношення >, <, =.

Умовою курсової роботи передбачена підтримка управляючих структурthen або if-then і оператор циклу, з перерахуванням по заданій змінній.

Синтаксис оператора умови наступний:

if (<condition>) then<block>;

де <condition> - булевий вираз, який в разі істинності призводить до виконання блоку <Ь1оск>. Конструкція if-then повинна закінчуватись крапкою з комою.

Цикл з передумовою описується наступним чином: while (<condition> ісс begin<block>end;

де <condition>- булевий вираз який є умовою виконання циклу, <block> блок операторів або один вираз, який є тілом циклу. Наприклад:

whileі<5 dobeginа=а»і; і=і+1; end;

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

2.2 Початок роботи програми. Опрацювання вихідного тексту програми лексичним аналізатором

При запуску програми на компіляцію основний модуль програми вивантажує вихідний код програми в об'єкт ТМето, після чого викликає модуль лексичного аналізатора (LexAuto).

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

AP_START - стан початку виразу;

АР _IF1, AP_IF2 - стани посимвольного аналізу ключового слова if;

AP_NOT 1, AP_NOT2, AP_NOT3 - стани посимвольного аналізу ключового слова not;

AP_ELSE1, AP_ELSE2, AP_ELSE3, AP_ELSE4 - стани посимвольного аналізу ключового слова else;

AP_END2, AP_END3 - стани посимвольного аналізу ключового слова end; AP_PROGl, AP_PROG2, AP_PROG3, AP_PROG4 - стани посимвольного аналізу ключового слова prog;

AP_ORl, AP_OR2 - стани посимвольного аналізу ключового слова or; AP_BEGIN1, AP_BEGIN2, AP_BEGIN3, AP_BEGIN4, AP_BEGIN5 - стани посимвольного аналізу ключового слова begin;

AP_XORl, AP_XOR2, AP_XOR3 - стани посимвольного аналізу ключового слова хог;

AP_AND1, AP_AND2, AP_AND3 - стани посимвольного аналізу ключового слова and;

AP_WHILE1, AP_WHILE2, AP_WHILE3, AP_WHILE4, AP_WHILE5 - стани посимвольного аналізу ключового слова while;

AP_COMM, AP_COMMSG - стани розпізнавання початку і кінця коментарів; AP_ASSIGN -стан розпізнавання оператора присвоєння;

АР_VAR - стан розпізнавання змінної;

AP_CONST - стан розпізнавання константи;

AP_D01, AP_D02 - стани посимвольного аналізу ключового слова do;

AP_SIGN - стан, що передбачає можливість вживання оператора інкрементування;

AP_LT - стан, що передбачає можливість вживання оператора «не дорівнює»;

AP_FIN - стан кінця виразу;

AP_ERR - стан помилки.

У разі задоволення умов певного порядку слідування символів, автомат переходить в чітко визначені стани, що дозволяють нам розпізнати лексему (оголошені в модулі LexType).

Приведемо список даних станів:

LEX_PROG - ключове слово prog;

LEX_FIN - ключове слово end. ;

LEX_SEMI - символ «; «;

LEX_IF - ключове слово if;

LEX_OPEN - відкрита дужка;

LEX_CLOSE - закрита дужка;

LEX_ELSE - ключове слово else;

LEX_BEGIN - ключове слово begin;

LEX_END - ключове слово end;

LEX_WHILE - ключове слово while;

LEX_DO - ключове слово do;

LEX_VAR - змінна;

LEX_CONST - константа;

LEX_ASSIGN - присвоєння;

LEX_OR ключове слово or;

LEX_XOR - ключове слово хог;

LEX_AND - ключовеслово and;

LEX_LT - «менше»;

LEX_GT - «більше»;

LEX_EQ - «рівне»;

LEX_NEQ - «нерівне»;

LEX_NOT - ключовеслово not;

LEX_SUB - віднімання;

LEX_ADD - додавання;

LEX_UMIN - інкрементування;

LEX_START - початоквиразу.

На основі даних станів головна програма починає побудову таблиці ідентифікаторів. Модуль LexElem визначає тип елементів таблиці та робить вивід, що відображається у вигляді простого списку в другій закладці форми основної програми (перед цим попередньо в основному модулі програми всі константипереводяться в формат, визначений варіантом завдання). Після цього на основ хеш-функції, яка визначається результатом додавання ASCII-коду першого середнього символів лексеми, поміщається в таблицю ідентифікаторів те виконує підключений модуль FncTree).

2.3 Синтаксичний аналіз

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

Приведемо дані правила нижче:

S> progLend.

L>О|L; О|L;

О>if (B) О else О| if (B) О| begin L end| while (B) do О| a: =E

B>B or C|B xor C| C

C>C and D|D

D>E<E|E>E|E=E|EoE| (B) |not (B)

E>E-T|E+T|T

T> incT|F

F> (E) |a|c

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

По заданій матриці модуль SyntSymb проводить синтаксичний розбір з допомогою алгоритму «зсув-згортка». Результат цього розбору формується в бінарне дерево модулем TblElem, що ми можемо бачити на закладці «Синтаксис» основної програми.

2.4 Генерація та оптимізанія об'єктного коду

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

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

Останнім етапом є представлення асемблерного коду програми. Виходячи з результатів виконання побудови списку тріад та оптимізації коду, модульTrdAsm формує код програми, який представляється в закладці основної форми програми «Команди».

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

генерації та оптимізації коду, і, при коректному виконанні завдання всіма модулями програми, виводить повідомлення «Компіляція виконана успішно».

Код всіх модулів та основного інтерфейсу програми представлено в додатку Б даної пояснювальної записки.

3. Графічний інтерфейс програми

Рис. 3. 1. Графічний інтерфейс програми

Висновки

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

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

Список використаних джерел

Молчанов А. Ю. Системное программное обеспечение: Учебник для вузов [Текст] /А. Ю. Молчанов. - СПб. : Питер, 2003

Компилятор - Википедия [електронний pecypc]/http://ru.wikipedia.org/wiki/

Конспект лекцій з дисципліни «Системне програмне забезпечення».

Гордеев А. В. Системное программное обеспечение [Текст] /А. В. Гордеев, А. Ю. Молчанов. - СПб. : Питер, 2002

Зубков С. В. Ассемблер для DOS, Windowsи Unix. - М. : ДМК Пресс, 2000.

Размещено на Allbest.ru