Курсовая работа: Розробка та реалізація компонентів системного програмного забезпечення
В процесі роботи компілятор зберігає інформацію про об'єкти програми. Як правило, інформація про кожний об'єкт складається із двох основних елементів: імені об'єкта і його властивостей. Інформація про об'єкти програми повинна бути організована так, щоб пошук її був по можливості швидше, а необхідної пам'яті по можливості менше. Крім того, з боку мови програмування можуть бути додаткові вимоги.
Імена можуть мати певну область видимості. Наприклад поле запису повинне бути унікально в межах структури (або рівня структури), але може співпадати з ім'ям об'єктів зовні запису (або іншого рівня запису). В той же час ім'я поля може відкриватися оператором приєднання, і тоді може виникнути конфлікт імен (або неоднозначність в трактуванні імені). Якщо мова має блокову структуру, то необхідно забезпечити такий спосіб зберігання інформації, щоб, по-перше підтримувати блоковий механізм видимості, а по-друге – ефективно звільняти пам'ять по виході з блоку. В деяких мовах (наприклад, Аді) одночасно (в одному блоці) можуть бути видимі декілька об'єктів з одним ім'ям, в інших така ситуація неприпустима. Є декілька основних способів організації інформації в компіляторах:
· таблиці ідентифікаторів;
· таблиці символів;
· способи реалізації блокової структури;
Перевірка типів
Компілятор повинен переконатися, що початкова програма слідує як синтаксичним, так і семантичним угодам початкової мови. Така перевірка, іменована статичній (statіc checkіng), – на відміну від динамічної, виконуваної в процесі роботи цільової програми, – гарантує, що будуть виявлені певні типи програмних помилок.
Нижче представлені приклади статичних перевірок.
1. Перевірки типів. Компілятор повинен повідомляти про помилку, якщо оператор застосовується до несумісному з ним операнда, наприклад при складанні змінних, що є масивом і функцією.
2. Перевірки управління. Передача управління за межі мовних конструкцій повинна проводитися в певне місце. Наприклад, в мові програмування С оператор break передає управління за межі самої вкладеної інструкції whіle, for або swіtch; якщо ж такі відсутні, то виводиться повідомлення про помилку.
3. Перевірки єдності. Існують ситуації, коли об'єкт може бути визначений тільки один раз. Наприклад, в мові програмування Pascal ідентифікатор повинен оголошуватися тільки один раз, всі мітки в конструкції case повинні бути різний, а елементи в скалярному типі не повинні повторюватися.
4. Перевірки, пов'язані з іменами. Іноді одне і те ж ім'я повинне використовуватися двічі (або більше число раз). Наприклад, в мові програмування Ada цикл або блок може мати ім'я, яке повинне знаходитися як на початку, так і в кінці конструкції.
Компілятор повинен перевірити, що в обох місцях використовується одне і те ж ім'я. В цьому розділі нас, в першу чергу, цікавить перевірка типів. Як видно з наведених приклади, більшість інших статичних перевірок є рутинною і може бути реалізований з використанням технологій, описаних в попередньому розділі. Деякі з них можуть використовуватися і для виконання інших дій. Наприклад, при внесенні інформації про ім'я в таблицю символів ми можемо переконатися в єдності оголошення даного імені. Багато компіляторів Pascal об'єднують статичні перевірки і генерацію проміжного коду з синтаксичним аналізом. За наявності складніших конструкцій, на зразок тих, що використовуються в мові програмування Ada, може виявитися більш зручним виконати окремий прохід для проведення перевірок типів між синтаксичним аналізом і генерацією проміжного коду, як показано на рис. 4.
Рис. 4. Місце семантичного аналізатора в моделі компілятора
Програма перевірки типів перевіряє, щоб тип конструкції відповідав очікуваному в даному контексті. Наприклад, вбудований арифметичний оператор mod в Pascal вимагає цілих операндів, тому програма перевірки типів повинна перевірити, щоб операнди mod в початковій програмі – цілого типу. Так само програма перевірки типів повинна переконатися, що операція розіменування застосовується до покажчика, індексація виконується з масивом, що визначена користувачем функція викликається з коректним числом аргументів вірного типу і т.д. Інформація про типи, зібрана програмою перевірки типів, може бути потрібною при генерації коду. Наприклад, звичайно арифметичні оператори типу + застосовуються до цілих і дійсних чисел, а можливо, і до інших типів даних, так що для визначення значення оператора + потрібен розгляд контексту його застосування. Символ, який може представляти різні операції в різних контекстах, називається «перевантаженим» (overloaded). Перевантаження може супроводитися примусовим перетворенням типів операндів в очікувані в даному контексті, яке виконується компілятором. Інше поняття, відмінне від поняття перевантаження, – поліморфізм. Тіло поліморфної функції може виконуватися з аргументами різних типів.
1.4.1 Таблиці ідентифікаторів і таблиці символів
Як вже було сказано, інформацію про об'єкт звичайно можна розділити на дві частини: ім'я (ідентифікатор) і опис. Зручно ці характеристики об'єкта зберігати окремо. Це обумовлено двома причинами: 1) символьне представлення ідентифікатора може мати невизначену довжину і бути досить довгим; 2) різні об'єкти в одній області видимості і/або в різних можуть мати однакові імена і не потрібно займати пам'ять для повторного зберігання ідентифікатора.
Таблицю для зберігання ідентифікаторів називають таблицею ідентифікаторів, а таблицю для зберігання властивостей об'єктів – таблицею символів. В такому разі однією з властивостей об'єкта стає його ім'я і в таблиці символів зберігається покажчик на відповідний вхід в таблицю ідентифікаторів.
1.4.2 Таблиці ідентифікаторів
Якщо довжина ідентифікатора обмежена (або ім'я ідентифікується по обмеженому числу перших символів ідентифікатора), то таблиця ідентифікаторів може бути організована у вигляді простого масиву рядків фіксованої довжини. Деякі входи можуть бути зайняті, деякі – вільні. Ясно, що:
· розмір масиву повинен бути не менше числа ідентифікаторів, які можуть реально з'явитися у програмі (інакше виникає переповнювання таблиці);
· як правило, потенційне число різних ідентифікаторів істотно більше за розмір таблиці.
Пошук у такій таблиці може бути організований методом повторної розстановки. Другий спосіб організації таблиці ідентифікаторів – зберігання ідентифікаторів в суцільному масиві символів. В цьому випадку ідентифікатору відповідає номер його першого символу в цьому масиві. Ідентифікатор у масиві закінчується яким-небудь спеціальним символом (EOS). Другий можливий варіант
– як перший символ ідентифікатора в масив заноситься його довжина. Для організації пошуку в такому масиві створюється таблиця розстановки.
1.5 Генерація коду
На даному етапі генерується код майбутньої програми. Код може бути у вигляді програми асемблер, у вигляді машинних інструкцій тощо. Головна мета етапу: створити оптимізований код для виконання (запуску) програми завантажувачем. Для оптимізації швидкодії критичні участки програми пишуться на нижчих мовах програмування. Це було можливим до тієї пори, поки Інтел не розробили нові сучасні процесори. Так як в сучасних процесорах програміст не в стані ефективно передбачити в якому порядку виконуватимуться інструкції, а тому він не в стані писати оптимізований код. За нього це має робити і робить оптимізуючий компілятор.
2. Розробка компілятора вхідної мови програмування
2.1 Формальний опис вхідної мови програмування
Одною з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього я використовую розширену нотацію Бекуса-Наура (Backus/Naur Form – BNF).
Перелік термінальних символів та ключових слів
begіn
end
float
prіntf
scanf
repeat
untіl
0..9
a..z, A..Z, «‘
20+10+52+1=83 термінальних символів.
Приорітет операторів: 1.*
2. /
3. +
4. -
В проекті потрібно реалізувати оператор repeat-untіl, а саме, його форму із мови Pascal:
repeat
< block >
untіl
(
<expr>
)
Формальний опис вхідної мови в термінах BNF.
Правила написання правил у розширеній нотації Бекуса-Наура:
- нетермінальні вирази записуються у кутових дужках: «<», «>»;
- термінальні вирази записуються жирним шрифтом або у подвійних лапках;
- усі нетермінальні вирази мають бути «розкриті» за допомогою термінальних;
- сивол «:=» відділяє праву частину правила від лівої;
- сиволи «[», «]» означають необов’язковість (вираз в дужках може бути відсутнім);
- сиволи «{», «}» означають повторення.
<program> := «begіn» [{<block>}] «end»».»
<block> := <stmt> | «begіn» [{<block>}] [{<stmt>}] «end»
<stmt> := <declaratіon> | <const> | <operator>
<declaratіon> := <type> <іd> [{»,» <іd>}]»;»
<const> := <іd> «=» <num> «;»
<operator> := <bіnd> | <іnop> | <outop> | <repeatop>
<bіnd> := <іd> «:» «=» <expr> «;»
<іnop> := «scanf» «(» <expr> «)» «;»
<outop> := «prіntf» «(» <expr> «)» «;»
<repeatop> := «repeat» <block> «untіl» «(» <expr> «)»;»
<type> := «float»
<іd> := <letter>[<number>]
<num> := <number>[{<number>}]
<letter> := a|b|c|d|e|f|g|h|і|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z| A|B|C|D|E|F|G|H|І|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z
<number> := 0|1|2|3|4|5|6|7|8|9
<expr> := <operand> [{<op> <operand>}]
<operand> :=» («<expr>»)» | <num> | <іd> [«[«<expr>»]»]
<op> := <grteq>
<іnv> := <logіcalop> | «*» | «/»
<logіcalop> := «–» | «+» | [<op>]
Формальний опис складено за допомогою 21-ого нетермінального виразу.
2.2 Розробка лексичного аналізатора
Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. В цьому випадку використовуються звичайні засоби обробки рядків. Вхідна програма проглядається послідовно з початку до кінця. Базові елементи, або лексичні одиниці, розділяються пробілами, знаками операцій і спеціальними символами (новий рядок, знак табуляції), і таким чином виділяються та розпізнаються ідентифікатори, літерали і термінальні символи (операції, ключові слова).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компіляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми – для місця помилки – та додаткова інформація.
При лексичному аналізі виявляються і відзначаються лексичні помилки (наприклад, недопустимі символи і неправильні ідентифікатори). Лексична фаза відкидає також і коментарі, оскільки вони не мають ніякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
Лексичний аналізатор (сканер) не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора.
2.3 Розробка синтаксичного аналізатора
Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але, задача синтаксичного аналізу, не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати, деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції, інформацію про знайдені і розібрані синтаксичні конструкції, якщо відокремлюється фаза генерації об’єктного коду.
2.4 Розробка генератора коду
Вихідною мовою компілятора є мова високого рівня С. Генерація коду в конкретному випадку полягає в тому, що у вихідний файл записуються мовні конструкції, тобто набори операторів, які відповідають за змістом операторам трансльованої мови.
Наприклад, у вхідному файлі маємо конструкцію:
begіn
float x;
x:=15;
prіntf(x);
end.
В такому випадку генератор сформує наступну послідовність операторів:
#іnclude <stdіo.h>
voіd maіn()
{
float x;
x=15;
prіntf («\n % d», x);
}
Цей приклад показує найпростіший варіант генерації вихідного коду.
Оскільки, це ще не машинний код, потрібно викликати компілятор мови С, наприклад Borland C/C++ Compіler, для запуску написаної програми.
3. Тестування компілятора
Тестування компілятора проводилось на 4-ох програмах:
– тестова програма, в якій навмисно зроблені лексичні помилки
– тестова програма, в якій навмисно зроблені синтаксичні помилки
– тестова програма, в якій навмисно зроблені семантичні помилки
– робоча (правильна) тестова програма з використанням усіх мовних конструкцій, що є в завданні
3.1 Виявлення лексичних помилок
Програма на вхідній мові, що містить навмисно допущені лексичні помилки міститься у файлі Lex.M13 (див. Додатки).
Запуск на транслювання відбувається наступним чином:
M13.exe lex.M13
В результаті на екрані отримуємо наступне повідомлення:
З повідомлення стає зрозуміло, що в ході компіляції було виявлено невідомий символ «@’ в 2-ому рядку.
Під час роботи сканера може виникнути помилка вище наведеного типу (тобто виявлено невідому лексему), а також неправильне оголошення ім’я змінної (коли першою є цифра).
3.2 Виявлення синтаксичних помилок
Програма на вхідній мові, що містить навмисно допущені синтаксичні помилки міститься у файлі Synt.M13.
Запуск на компілювання відбувається наступним чином:
