Розробка та реалізація компонент системного програмного забезпечення.. Курсова робота з Системне програмне забезпечення. Робота № 202424

Розробка та реалізація компонент системного програмного забезпечення.

Інформація про навчальний заклад

ВУЗ:

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

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра електронних обчислювальних машин

Інформація про роботу

Рік:

2005

Тип роботи:

Курсова робота

Предмет:

Системне програмне забезпечення

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ національний університет “Львівська політехніКА” КАФЕДРА ЕЛЕКТРОННИХ ОБЧИСЛЮВАЛЬНИХ МАШИН КУРСОВИЙ ПРОЕКТ на тему: “Розробка та реалізація компонент системного програмного забезпечення” з курсу “Системне програмне забезпечення” Львів-2005 АНОТАЦІЯ В даному курсовому проекті розроблено компілятор з вхідної мови програмування Z1. Компілятор розроблений в середовищі програмування Borland C та поданий у пояснювальній записці, а також в електронному варіанті. В пояснювальній записці подано огляд існуючих методів розробки компіляторів, детальний опис мови, а також описано процес розробки програми компілятора на рівні блок-схем і тексту програми. До проекту додано результати тестування програми. ЗАВДАННЯ Розробити транслятор заданої вхідної мови програмування, до якої висуваються наступні базові вимоги: Кожна програма починається зі слова (1) і закінчується словом (2). Все що до (1) і після (2) не аналізується. Наприклад як у мові Паскаль begin end. Програма має надавати можливість працювати зі змінними (3). Змінні перед використанням мають бути попередньо оголошені за наступним форматом: “тип даних” “змінна1”, “змінна2”; Наприклад integer x,y; Присвоєння до змінних виконується оператором присвоєння :=. Наприклад x:=y+5; Програма має надавати можливість працювати з константами (4). Константи ініціюються наступним чином: “константа” = “число”. Наприклад а=3; Ввід даних зі стандартного вводу відбувається оператором (5), а вивід оператором (6). Наприклад input x; output (y). Програма має працювати з типом даних (7) Програма має виконувати операції (8). Вихідною мовою трансляції є мова С. Виконавши базові вимоги студент може отримати оцінку в межах 50 – 70 балів. На оцінку в межах 71 – 87 балів (табл. 1) додатково потрібно реалізувати дужки у математичних виразах, а також перелік змінних не вказаний (тобта поле 3 не враховувати). На оцінку в межах 88-100 балів (табл. 2) вихідною мовою трансляції є мова асемблера, а також в полі 9 вказаний оператор, який потрібно реалізувати . Математичний вираз має бути розібраний в залежності від пріоритету виконання та розписаний викликом власних С функцій. Цільова мова компілятора: ANSI C. Для отримання виконавчого файлу на виході розробленого компілятора скористатися програмою bcc.exe. Мова розробки компілятора: ANSI C. Реалізувати інтерфейс командного рядка. На вхід розробленого компілятора має подаватися текстовий файл, написаний на заданій мові програмування. На виході розробленого компілятора мають з’являтися чотири файли: файл з повідомленнями про помилки (або про їх відсутність), файл на мові СІ, об’єктний та виконавчий файли. Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та номеру його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування. табл. 2 P – оператор мови Паскаль, С- оператор мови С. ВСТУП Компілятор – це програма, яка читає текст програми, написаної на одній мові – початковій, і транслює (переводить) його в еквівалентний текст на іншій мові – цільовій. Одним з важливих моментів трансляції є повідомлення користувача про наявність помилок в початковій програмі. Створення компіляторів є одною з невід‘ємних частин системного програмного забезпечення. Одним із завдань компілятора є переведення написаного тексту програми у машинний код, який повинен відповідати комп‘ютерній системі. Оскільки сьогоднішній час – час великого розвитку комп‘ютерної галузі, то створений машинний код з часом стає застарілим, тобто не відповідає принципу оптимального використання комп‘ютерних ресурсів. Тому для запобігання цього явища необхідно створювати нові компілятори, які б відповідали потребам теперішнього часу. Проблема компіляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою компілятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього компілятор має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати об'єктний код або виконавчий модуль. На перший погляд, різноманітність компіляторів приголомшує. Використовуються тисячі початкових мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, виникаючих у всіх областях комп'ютерних технологій. Цільові мови не менше різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп'ютерів. Іноді компілятори класифікують як однопрохідні, багатопрохідні, виконуючі, відлагоджуючі, оптимізуючі — залежно від призначення і принципів та технологій їх створення. Не дивлячись на уявну складність і різноманітність, основні задачі, виконувані різними компіляторами, по суті, одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних початкових мов і цільових машин з використанням одних і тих же базових технологій. Знання про організацію і написання компіляторів істотно зросли з часів перших компіляторів, що з'явилися на початку 1950-х рр. Сьогодні складно визначити, коли саме з'явився на світ перший компілятор, оскільки в ті роки проводилося багато експериментів і розробок різними незалежними групами. В основному метою цих розробок було перетворення в машинний код арифметичних формул. В 50-х роках про компілятори ходила слава як про програми, украй складні в написанні (наприклад, на написання першого компілятора Fortran було витрачено 18 людино-років роботи). З тих пір розроблені різноманітні системні технології рішення багатьох задач, що виникають при компіляції. Крім того, розроблені хороші мови реалізації, програмні середовища і програмний інструментарій. Завдяки цьому "солідний компілятор" може бути реалізований навіть як курсова робота по проектуванню компіляторів. ЗМІСТ Анотація.........................................................................................................................2 Завдання.........................................................................................................................3 Вступ...............................................................................................................................5 1. Аналітичний розділ.................................................................................................7 1.1. Фази компілятора……………………….............................................................7 1.2. Лексичний аналіз…………………………………….........................................8 1.3. Синтаксичний анал..............................................................................................9 1.3.1. Обробка синтаксичних помилок….........................................................10 1.4. Семантичний аналіз…………………................................................................11 1.4.1. Таблиці ідентифікаторів і таблиці символів..........................................13 1.4.2. Таблиці ідентифікаторів...........................................................................13 1.5. Генератор коду....................................................................................................14 2. Розділ проектування.................................................................................................15 2.1. Формальний опис вхідної мови програмування...............................................15 2.1.1. Деталізований опис вхідної мови ……....................................................15 2.1.2. Перелік термінальних символів та ключових слів ................................15 2.1.3. Формальний опис вхідної мови в термінах BNF....................................15 2.1.4. Повне дерево граматичного розбор.........................................................17 2.2. Лексичний аналізатор…………………………..................................................18 2.2.1. Структури даних та змінні, що використовуються на данному етапі компіляції..........................................................................18 2.2.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції..................................................................................................19 2.3. Синтаксичний аналізатор…………………………...........................................22 2.3.1. Структури даних та змінні, що використовуються на данному етапі компіляції..........................................................................22 2.3.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції..................................................................................................23 2.4. Семантичний аналізатор………………...……..................................................25 2.4.1. Структури даних та змінні, що використовуються на данному етапі компіляції..........................................................................25 2.4.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції..................................................................................................25 2.5. Генератор коду…………………………..……..................................................27 2.5.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції..................................................................................................27 4. Тестування компілятора.........................................................................................27 4.1. Виявлення лексичних помилок ………...……..................................................28 4.2. Виявлення синтаксичних помилок ……….......................................................28 4.3. Виявлення семантичних помилок ………...……..............................................29 4.4. Загальна перевірка коректності роботи компілятора …..................................29 Висновки........................................................................................................................30 Список використаної літератури..............................................................................31 Додатки..........................................................................................................................32 1. АНАЛІТИЧНИЙ РОЗДІЛ 1.1. Фази компілятора Концептуально компілятор працює пофазно, причому в процесі кожної фази відбувається перетворення початкової програми з одного представлення в інше. Типове розбиття компілятора на фази показано на рис.1. Рис.1. Фази компілятора. На практиці деякі фази можуть бути згрупований разом і проміжні представлення програми усередині таких груп можуть явно не будуватися. Перші три фази формують аналізуючу частину компілятора. Управління таблицею символів і обробка помилок показані у взаємодії з шістьма фазами: лексичним аналізом, синтаксичним аналізом, семантичним аналізом, генерацією проміжного коду, оптимізацією коду і генерацією коду. Неформально диспетчер таблиці символів і обробник помилок також можуть вважатися "фазами" компілятора. Однією з важливих функцій компілятора є запис використовуваних в початковій програмі ідентифікаторів і збір інформації про різні атрибути кожного ідентифікатора. Ці атрибути надають відомості про відведену ідентифікатору пам'ять, його тип, області видимості (де в програмі він може застосовуватися). При використанні імен процедур атрибути говорять про кількість і тип їх аргументів, метод передачі кожного аргументу (наприклад, по посиланню) і тип значення, що повертається, якщо таке є. Таблиця символів є структурою даних, що містить записи про кожний ідентифікатор з полями для його атрибутів. Дана структура дозволяє швидко знайти інформацію про будь-який ідентифікатор і внести необхідні зміни. 1.2. Лексичний аналіз Лексичний аналізатор є першою фазою компілятора. Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів для передачі в синтаксичний аналізатор. На рис.2. схематично показано взаємодію лексичного і синтаксичного аналізаторів, яка звичайно реалізується шляхом створення лексичного аналізатора як підпрограма синтаксичного аналізатора (або підпрограми, що викликається ним). При отриманні запиту на наступний токен лексичний аналізатор зчитує вхідний потік символів до точної ідентифікації наступного токена. Рис.2. Взаємодія лексичного і синтаксичного аналізаторів. Всі символи вхідної послідовності розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. В цьому випадку використовуються звичайнi засоби обробки рядків. Вхiдна програма проглядається послiдовно з початку до кінця. Базовi елементи, або лексичнi одиницi, роздiляються пробiлами, знаками операцiй i спецiальними символами (новий рядок, знак табуляції), i таким чином видiляються та розпізнаються iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова). При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись до лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми (для локалізації місця помилки) та інша додаткова інформація. При лексичному аналiзі виявляються i вiдзначаються лексичнi помилки (наприклад, недопустимi символи i неправильнi iдентифiкатори). Лексична фаза вiдкидає також i коментарi, оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду. Лексичний аналізатор (сканер) не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора. Є ряд причин, по яких фаза аналізу компіляції розділяється на лексичний і синтаксичний аналізи: Мабуть, найважливішою причиною є спрощення розробки. Відділення лексичного аналізатора від синтаксичного часто дозволяє спростити одну з фаз аналізу. Наприклад, включення в синтаксичний аналізатор коментарів і пропусків істотно складніше, ніж видалення їх лексичним аналізатором. При створенні нової мови розділення лексичних і синтаксичних правил може привести до більш чіткої і ясної побудови мови. Збільшується ефективність компілятора. Окремий лексичний аналізатор дозволяє створити спеціалізований і потенційно більш ефективний процесор для вирішення поставленої задачі. Оскільки на читання початкової програми і розбір її на токени витрачається багато часу, спеціалізовані технології буферизації і обробки токенів можуть істотно підвищити продуктивність компілятора. Збільшується переносимість компілятора. Особливості вхідного алфавіту і інші специфічні характеристики пристроїв, що використовуються, можуть обмежувати можливості лексичного аналізатора. Наприклад, таким чином може бути вирішена проблема спеціальних нестандартних символів, таких як Т в Pascal. Існує ряд спеціалізованих інструментів, призначених для автоматизації побудови лексичних і синтаксичних аналізаторів (у тому випадку, коли вони розділені). 1.3. Синтаксичний аналіз Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови. Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції і представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми. Крім того, важливою функцією є локалізація синтаксичних помилок. Як правило, синтаксичні конструкції мови програмування можуть бути описані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але задача синтаксичного аналізу не обмежується тільки такою перевіркою. Синтаксичний аналізатор повинен мати деяку результуючу мову, за допомогою якої він передає наступним фазам компіляції інформацію про знайдені і розібрані синтаксичні конструкції, якщо відокремлюється фаза генерації об’єктного коду. Кожна мова програмування має правила, які визначають синтаксичну структуру коректних програм. В Pascal, наприклад, програма створюється з блоків, блок – з інструкцій, інструкції – з виразів, вирази – з токенів і т.д. Синтаксис конструкцій мови програмування може бути описаний за допомогою контекстно-вільних граматик або нотації БНФ (Backus-Naur Form, форма Бекуса-Наура). Граматики забезпечують значні переваги розробникам мов програмування і авторам компіляторів. Граматика дає точну і при цьому просту для розуміння синтаксичну специфікацію мови програмування. Для деяких класів граматик ми можемо автоматично побудувати ефективний синтаксичний аналізатор, який визначає, чи коректна структура початкової програми. Додатковою перевагою автоматичного створення аналізатора є можливість виявлення синтаксичних неоднозначностей та інших складних для розпізнавання конструкцій мови, які інакше могли б залишитися непоміченими на початкових фазах створення мови і його компілятора. Правильно побудована граматика додає мові програмування структуру, яка сприяє полегшенню трансляції початкової програми в об'єктний код і виявленню помилок. Для перетворення описів трансляції, заснованих на граматиці мови, в робочій програмі є відповідний програмний інструментарій. З часом мови еволюціонують, збагатившись новими конструкціями і виконуючи нові задачі. Додавання конструкцій в мову виявиться більш простою задачею, якщо існуюча реалізація мови заснована на його граматичному описі. Є три основні типи синтаксичних аналізаторів граматик. Універсальні методи розбору, такі як алгоритми Кока-Янгера-Касамі або Ерлі, можуть працювати з будь-якою граматикою. Проте ці методи дуже неефективні для використання в промислових компіляторах. Методи, які звичайно використовуються в компіляторах, класифікуються як низхідні (зверху вниз, top-down) або висхідні (з низу до верху, bottom-up). Як видно з назв, низхідні синтаксичні аналізатори будують дерево розбору зверху вниз (до листя), тоді як висхідні починають з листя і йдуть до кореня. В обох випадках вхідний потік синтаксичного аналізатора сканується посимвольний зліва направо. Найефективніші низхідні і висхідні методи працюють тільки з підкласами граматик, проте деякі з цих підкласів, такі як LL- і LR-граматики, достатньо виразні для опису більшості синтаксичних конструкцій мов програмування. Реалізовані вручну синтаксичні аналізатори частіше працюють з LL-граматиками. Синтаксичні аналізатори для дещо більшого класу LR-граматик звичайно створюються за допомогою автоматизованих інструментів. Будемо вважати, що вихід синтаксичного аналізатора є деяким представленням дерева розбору вхідного потоку токенів, виданого лексичним аналізатором. На практиці є безліч задач, які можуть супроводжувати процес розбору, - наприклад, збір інформації про різні токени в таблиці символів, виконання перевірки типів і інших видів семантичного аналізу, а також створення проміжного коду. Всі ці задачі представлені одним блоком "Інші задачі початкової фази компіляції" рис.3. Рис.3. Місце синтаксичного аналізатора в моделі компілятора 1.3.1. Обробка синтаксичних помилок. Якщо компілятор матиме справу виключно з коректними програмами, його розробка і реалізація істотно спрощуються. Проте дуже часто програмісти пишуть програми з помилками, і добрий компілятор повинен допомогти програмісту знайти їх і локалізувати. Примітно, що хоча помилки — явище надзвичайно поширене, лише в декількох мовах питання обробки помилок розглядалося ще на фазі створення мови. Наша цивілізація істотно відрізнялася б від свого нинішнього стану, якби в природних мовах були такі ж вимоги до синтаксичної точності, як і в мовах програмування. Більшість специфікацій мов програмування, проте, не визначає реакції компілятора на помилки — це питання віддається на відкуп розробникам компілятора. Проте планування системи обробки помилок з самого початку роботи над компілятором може як спростити його структуру, так і поліпшити його реакцію на помилки. Ми знаємо, що будь-яка програма потенційно містить безліч помилок самого різного рівня. Наприклад, помилки можуть бути • лексичними, такими як невірно записані ідентифікатори, ключові слова або оператори; • синтаксичними, наприклад, арифметичні вирази з незбалансованими дужками; • семантичними, такими як оператори, використані до несумісних операндів; • логічними, наприклад нескінченна рекурсія. Часто основні дії по виявленню помилок і відновленню після них концентруються у фазі синтаксичного аналізу. Одна з причин цього полягає в тому, що багато помилок за своєю природою є синтаксичними або виявляються, коли потік токенів, що йде від лексичного аналізатора, порушує визначаючі мова програмування граматичні правила. Друга причина полягає в точності сучасних методів розбору; вони дуже ефективно виявляють синтаксичні помилки в програмі. Визначення присутності в програмі семантичних або логічних помилок — задача набагато складніша. Обробник помилок синтаксичного аналізатора має дуже просто формульовану мету: • він повинен ясно і точно повідомляти про наявність помилок; • він повинен забезпечувати швидке відновлення після помилки, щоб продовжити пошук подальших помилок; • він не повинен істотно уповільнювати обробку коректної програми. Ефективна реалізація цієї мети є вельми складною задачею. На щастя, звичайні помилки достатньо прості, і для їх обробки часто достатньо простих механізмів обробки помилок. В деяких випадках, проте, помилка може відбутися задовго до моменту її виявлення (і за багато рядків коду до місця її виявлення), і визначити її природу вельми непросто. В складних ситуаціях обробник помилок, по суті, повинен просто здогадатися, що саме мав на увазі програміст, коли писав програму. Деякі методи розбору, такі як LL і LR, виявляють помилки, як тільки це стає можливим. Точніше кажучи, вони володіють властивістю перевірки коректності префіксів, тобто виявляють помилку, як тільки з'ясовується що префікс вхідної інформації не є префіксом жодного коректного рядка мови. 1.4. Семантичний аналіз В процесі роботи компілятор зберігає інформацію про об'єкти програми. Як правило, інформація про кожний об'єкт складається із двох основних елементів: імені об'єкта і його властивостей. Інформація про об'єкти програми повинна бути організована так, щоб пошук її був по можливості швидше, а необхідної пам'яті по можливості менше. Крім того, з боку мови програмування можуть бути додаткові вимоги. Імена можуть мати певну область видимості. Наприклад поле запису повинне бути унікально в межах структури (або рівня структури), але може співпадати з ім'ям об'єктів зовні запису (або іншого рівня запису). В той же час ім'я поля може відкриватися оператором приєднання, і тоді може виникнути конфлікт імен (або неоднозначність в трактуванні імені). Якщо мова має блокову структуру, то необхідно забезпечити такий спосіб зберігання інформації, щоб, по-перше підтримувати блоковий механізм видимості, а по-друге – ефективно звільняти пам'ять по виході з блоку. В деяких мовах (наприклад, Аді) одночасно (в одному блоці) можуть бути видимі декілька об'єктів з одним ім'ям, в інших така ситуація неприпустима. Є декілька основних способів організації інформації в компіляторах: таблиці ідентифікаторів; таблиці символів; способи реалізації блокової структури; Перевірка типів Компілятор повинен переконатися, що початкова програма слідує як синтаксичним, так і семантичним угодам початкової мови. Така перевірка, іменована статичній (static checking), — на відміну від динамічної, виконуваної в процесі роботи цільової програми, — гарантує, що будуть виявлені певні типи програмних помилок. Нижче представлені приклади статичних перевірок. 1. Перевірки типів. Компілятор повинен повідомляти про помилку, якщо оператор застосовується до несумісному з ним операнда, наприклад при складанні змінних, що є масивом і функцією. 2. Перевірки управління. Передача управління за межі мовних конструкцій повинна проводитися в певне місце. Наприклад, в мові програмування С оператор break передає управління за межі самої вкладеної інструкції while, for або switch; якщо ж такі відсутні, то виводиться повідомлення про помилку. 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). 2.1.1. Деталізований опис вхідної мови два типи даних: int, float; змінні довільної довжини; арифметичні операції над цілими: +, -, *, /; символи групування арифметичних операцій: “(”, “)”; логічні операції над цілими: >; оператор присвоєння: “:=” ; оператори блоку: “{”, “}”; оператор циклу (for-to-do). 2.1.2. Перелік термінальних символів та ключових слів Визначаємо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова): { } ; = + - * / ( ) > : , . main int float for to do put get const До термінальних символів треба віднести також усі цифри (0..9), латинські букви (a-z, A-Z), символ пробілу і табуляції. Всього: 23 + 10 + 52 + 1 + 1 = 87 термінальних виразів. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми. 2.1.3. Формальний опис вхідної мови в термінах BNF Правила написання правил у розширеній нотації Бекуса-Наура: Нетермінальні вирази записуються у кутових дужках: “<”, “>” ; Термінальні вирази записуються жирним шрифтом або у подвійних лапках; Усі нетермінальні вирази мають бути “розкриті” за допомогою термінальних; Сивол “::=” відділяє праву частину правила від лівої; символ “|” розділяє альтернативи; сиволи “[”, “]” означають необов’язковість (вираз в дужках може бути відсутнім); символи “{”, “}” означають повторення. Формальний опис заданої вхідної мови в термінах BNF Формальний опис складено за допомогою 23 нетермінальних виразів. 2.1.4. Повне дерево граматичного розбор Рис.5. Повне дерево граматичного розбору. 2.2. Лексичний аналізатор. Лексичний аналіз - це виділення з вхідного тексту програми, який складається з послідовності одиночних символів, послідовність слів або лексем. Лексеми – це неділимі фундаментальні одиниці мови. В даному курсовому проекті реалізовано прямий лексичний аналізатор. Він побудований на основі детермінованого автомата. На кожному кроці він зчитує один символ, і переходить в наступний стан, який приближує його до розпізнавання лексеми або помилки. На вихід подається розпізнана лексема, яка записується у таблицю лексем. Важливим етапом лексичного аналізу є визначення і локалізація помилок. Для цього використовується відповідна функція, яка визначає тип помилки і її місце у вхідній програмі. 2.2.1. Структури даних та змінні, що використовуються на данному етапі компіляції. Cтруктура, де міститься інформація про зчитаний токен. Містить поля lexem - імя лексеми, token - токен, number - порядковий номер, line - рядок. typedef struct { int number; char lexem[64]; char token[15]; int line; } token_tab; Cтруктура, де міститься інформація про зчитаний ідентифікатор. Містить поля name - імя ідентифікатора, type - тип, number - порядковий номер, line - рядок, is_init - ознака ініціалізації. typedef struct { int number; char name[64]; char type[10]; int line; int is_init; } iden_tab; Змінні: int iden_count; Лічильник ідентифікаторів int symbol_class; Визначає клас змінної int i; Допоміжна змінна для лічильника циклу у функції zero_string () int line=1; Визначає № стрічки у вхідному файлі int error_flag=0; Використовується для задання лексичної помилки int t_count=1; Визначає № токена у таблиці токенів char cur_lex[64]=""; Масив елементів для зберігання поточної лексеми char symbol=' '; Зберігає зчитаний символ char *token; Зберігає токен FILE *f_read, Вказівники на файл: f_read-вхідний, FILE *f_error; error_f - помилки, FILE *f_id; f_id - файл у якому міститься інформація про ідентифікатори FILE *f_lex; f_lex - файл з інформацією про лексеми token_tab *t_tab; Вказівник на таблицю токенів iden_tab id_tab[200]; Таблиця ідентифікаторів int id_count=0; Зберігає кількість ідентифікаторів int c_count=0; Лічильник циклів 2.2.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції void get_symbol(); Функція читає з вхідного файлу 1 символ, визначає клас символу, повертає зчитаний символ і його клас. Клас символу потрібен для того, щоб мати можливість перевірити можливі послідовності символів. Класи символів перелічені нижче. void zero_string(); Функція призначена для обнулення стрічки символів. Використовується при визначенні токену. (Виділивши в тексті програми токен, ми подаємо його на вихід, а масив, де зберігалась поточна лексема, обнулюємо.) void error (int line, int error_flag); Функція - обробник помилок. Її передаються в якості параметрів рядок, в якому знайдена помилка і тип помилки. Функція error створює файл error.txt, записує в нього повідомлення про помилку, а також виводить відповідне повідомлення на екран. void write_table (token_tab *); Ця функція записує в таблицю токенів інформацію про відповідний токен, а саме: порядковий номер, лексему, токен, рядок. В якості аргументу передаємо вказівни на таблицю токенів. void print_table (token_tab *); Ця функція виводить 1 елемент з таблиці токенів у файл. Виводяться: порядковий номер, лексема, токен, номер рядка. В якості аргументу передаємо вказівни на таблицю токенів. int check_main (); Ця функція призначена для видалення символів, які стоять до початку тіла програми. Якщо такі символи знайдено, то аналізатор їх відкидає і продовжує далі перевірку тексту вхідної програми. Повертає 0 - якщо зчитана лексема зустрічається перед main, і 1 - в протилежному випадку. void SCANNER(); Функція, яка зчитує символи, формує їх у лексеми, розпізнає лексеми і формує з них токени. Для своєї роботи використовує всі вище описані допоміжні функції. Також виділяє у вхідному тексті програми пробільні символи. Рис.6. Блок-схема роботи функції get_symbol () Рис.7. Блок-схема роботи функції SCANNER () 2.3. Синтаксичний аналiз Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови. В даному курсовому проекті реалізовано лексично-керований синтаксичний аналізатор, який працює методом рекурсивного спуску. Він отримує від лексичного аналізатора токен і перевіряє, чи може цей токен входити до поточног ланцюжка токенів. Також відбувається перевірка на наявність синтаксичних помилок. 2.3.1. Структури даних та змінні, що використовуються на данному етапі компіляції. Cтруктура, де міститься інформація про зчитаний токен. Містить поля lexem - імя лексеми, token - токен, number - порядковий номер, line - рядок. typedef struct { int number; char lexem[64]; char token[15]; int line; } token_tab; Cтруктура, де міститься інформація про зчитаний ідентифікатор. Містить поля name - імя ідентифікатора, type - тип, number - порядковий номер, line - рядок, is_init - ознака ініціалізації. typedef struct { int number; char name[64]; char type[10]; int line; int is_init; } iden_tab; Змінні: int line=1; Визначає № стрічки у вхідному файлі int error_flag=0; Використовується для задання синтаксичної помилки int t_count=1; Визначає № токена у таблиці токенів FILE *f_read, Вказівники на файл: f_read-вхідний, FILE *f_tree; f_tree - файл з деревом синтаксичного розбору FILE *f_error; error_f - помилки, FILE *f_id; f_id - файл у якому міститься інформація про ідентифікатори FILE *f_lex; f_lex - файл з інформацією про лексеми token_tab *t_tab; Вказівник на таблицю токенів iden_tab id_tab[200]; Таблиця ідентифікаторів int id_count=0; Зберігає кількість ідентифікаторів int is_minus=0; Ознака оголошення операції унарний мінус int is_op=0; Ознака оголошення арифметичної операції int c_count=0; Лічильник циклів 2.3.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції void Syntax(); Функція - синтаксичний аналізатор. В її тілі відбувається виклик інших допоміжних функцій для аналізу граматики тексту вхідної програми void Find_Main(); Функція перевіряє чи оголошений початок тіла програми у вигляді main {. В разі відсутності такого оголошення відбувається виклик функції error з відповідним кодом помилки. void Find_Const(); Функція перевіряє чи є в програмі оголошення констант виду const <type> <name>=<int_literal><float_literal>. В разі неправильного оголошення відбувається виклик функції error з відповідним кодом помилки. void Find_Var(); Функція перевіряє чи є в програмі оголошення змінних виду <type> <name>; В разі неправильного оголошення відбувається виклик функції error з відповідним кодом помилки. void Find_Block_Main(); Функція шукає в програмі блок виконання до якого входять присвоєння змінних, виконання арифметичних і логічних операційб оголошення циклу for, виклик функцій вводу/виводу. В її тілі відбувається виклик інших функцій, які шукають вищеперелічені блоки. void Find_Add_Sub(); Функція шукає в виразі підвираз виконання операцій додавання та віднімання. В її тілі відбувається виклик інших функцій (для операцій з вищим пріоритетом). void Find_Mult_Div(); Функція шукає в виразі підвираз виконання операцій множення та ділення. В її тілі відбувається виклик інших функцій (для операцій з вищим пріоритетом). void Find_Bilshe (); Функція шукає в виразі підвираз виконання операції порівняння. В її тілі відбувається виклик інших функцій (для операцій з вищим пріоритетом). void Find_Ident(); Функція шукає в виразі оголошення змінних, констант, числових літералів, дужок, операції унарного мінуса (операції з найвищим пріоритетом). В її тілі відбувається рекурсивний виклик попередніх функцій (для операцій з нижчим пріоритетом). void WriteTree (char *s); Функція, яка записує у файл дерево граматичного розбору. Виділивши під час синтаксичного аналізу блок, функція записує його у файл tree_.txt. 2.4. Семантичний аналізатор Семантичний аналіз – це перевірка вхідної програми на правильне використання ідентифікаторів. А саме: використання тільки задекларованих попередньо ідентифікаторів, їх ініціалізація перед використанням у виразах, сумісність між різними типами ідентифікаторів, а також перевірка цифрових констант на переповнення. В даній курсовій роботі семантичний аналізатор вбудований в синтаксичний. Розпізнавши використання константи, відбувається перевірка того, чи вона є оголошеною і чи вона є ініціалізованою. Крім того, відбувається перевірка спів падіння типів змінних в арифметичних операціях (наприклад, змінній типу int не можна присвоїти значення типу float). 2.4.1. Структури даних та змінні, що використовуються на данному етапі компіляції. int iden_count; Лічильник ідентифікаторів int line=1; Визначає № стрічки у вхідному файлі int error_flag=0; Використовується для задання семантичної помилки int t_count=1; Визначає № токена у таблиці токенів FILE *f_read, *f_error; Вказівники на файл (f_read-вхідний, error_f-помилки, FILE *f_id; f_id - файл з інформацією про ідентифікатори FILE *f_out; f_out - вихідний, FILE *f_lex; f_lex - файл з інформацією про лексеми FILE *f_tree; f_tree - файл з деревом синтаксичного розбору) token_tab *t_tab; Вказівник на таблицю токенів iden_tab id_tab[200]; Таблиця ідентифікаторів char tmp_type[10]; Тимчасова змінна для зберігання типу ідeнтифікатора (при операції ділення) char tmp_type1[10]; Тимчасова змінна для зберігання типу ідeнтифікатора int position=0; Вказує поточну позицію елемента в таблиці ідентифікаторів int id_count=0; Зберігає кількість ідентифікаторів int declared=0; Ознака того, що змінну оголошено int decl_number=0; Якщо змінну оголошено, то decl_number міститиме позицію в таблиці int c_count=0; Лічильник циклів int is_minus=0; Ознака оголошення операції унарний мінус int is_op=0; Ознака оголошення арифметичної операції char temp[64]; Зберігає лічильник циклів при оголошенні циклу 2.4.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції void write_iden(); Призначена для запису інформації про ідентифікатор в таблицю ідентифікаторів. Записуються: імя ідентифікатора, його порядковий номер, номер рядка, в якому він зустрічається. void scan_iden(); Виконує пошук ідентифікатора в таблиці ідентифікаторів. Пошук виконується по імені ідентифікатора. int is_declared (); Перевіряє чи знайдеий ідентифікатор був попередньо оголошений. В разі успішного завершення повертає порядковий номер ідентифікатора в таблиці. В разі помилки викликається функія error з відповідним кодом помилки. void write_type(); Функція виконує запис типу ідентифікатора в таблицю ідентифікаторів (в поле type поточного ідентифікатора). 2.5. Генератор коду Генерація коду – це машинно-залежний етап компіляції, під час якого відбувається побудова машинного еквівалента вхідної програми. Зазвичай входом для генератора коду служить проміжна форма представлення програми, а на виході може з’являтися об’єктний код або модуль завантаження. У компілятора, реалізованого в даній курсовій роботі, вихідна мова не об’єктний код, а програма на мові Borland C. Ця програма записується у файл, що має назву output_.txt. Після закриття файлу відбувається запуск програми bcc.exe – компілятор Borland C. Генерація коду відбувається одразу ж після семантичного аналізу 2.5.1. Структури даних та змінні, що використовуються на данному етапі компіляції. На даному етапі використовуються ті ж змінні і структури, що й на етапі синтаксичного аналізу, оскільки в даному курсовому проекті генерація коду є синтаксично керованою. 2.5.2. Функції та алгоритми їх роботи, які реалізують даний етап компіляції void Generate (char *); Функція - генератор вихідного коду. Під час її роботи відбувається запис вихідного тексту програми у файл. 4. Тестування компілятора Тестування компілятора проводилось на 4-ох програмах: - тестова програма, в якій навмисно зроблені лексичні помилки - тестова програма, в якій навмисно зроблені синтаксичні помилки - тестова програма, в якій навмисно зроблені семантичні помилки - робоча (правильна) тестова програма з використанням усіх мовних конструкцій, що є в завданні 4.1. Виявлення лексичних помилок Програма на вхідній мові, що містить навмисно допущені лексичні помилки міститься у файлі LexError.Z1 (див. Додатки). Запуск на компілювання відбувається наступним чином: compilerZ1.exe LexError.Z1 В результаті на екрані ми отримуєм наступні повідомлення: Starting analyse... Lex error: Unknown symbol in line 9 Error during analyse! See ERROR_.TXT file З повідомлення випливає, що в ході компіляції було виявлено невідому лексему ’#’ в 9 рядку. Під час роботи сканера може виникнути помилка вище наведеного типу (тобто виявлено невідому лексему), а також неправильне оголошення ім’я змінної (коли першою є цифра) і неправильно оголошена числова константа з плаваючою комою. На всі ці помилки передбачено відповідні повідомлення. 4.2. Виявлення синтаксичних помилок Програма на вхідній мові, що містить навмисно допущені синтаксичні помилки міститься у файлі SyntError.Z1 (див. Додатки). Запуск на компілювання відбувається наступним чином: compilerZ1.exe SyntError.Z1 В результаті на екрані ми отримуєм наступні повідомлення: Starting analyse... Syntax error: Missing ‘;’ in line 9 Error during analyse! See ERROR_.TXT file З повідомлення випливає, що в ході компіляції було виявлено синтаксичну помилку – пропущено роздільник ’;’. Після цьог компіляцію було перервано. Можливі наступні типи синтаксичних помилок, що реалізовані в компіляторі: Відсутній початок програми Відсутня ’{’ Відсутня ’}’ Непередбачена ’}’ або ’)’ Невірна комбінація дужок – коли при ’(’ наступною є не ’)’ Відсутній ідентифікатор після слова int I float Відсутня ’;’ Невірне подання ’for-to-do’ Неправильне оголошення функцій вводу або виводу put або get Недозволена операція. 4.3. Виявлення семантичних помилок Програма на вхідній мові, що містить навмисно допущені синтаксичні помилки міститься у файлі SemEror.Z1 (див. Додатки). Запуск на компілювання відбувається наступним чином: compilerZ1.exe SemError.Z1 В результаті на екрані ми отримуєм наступні повідомлення: Starting analyse... Semantic error: Undeclarated identifier 'w' in line 9 Error during analyse! See ERROR_.TXT file З повідомлення випливає, що в ході компіляції було виявлено семантичну помилку – було виявлено неоголошену змінну b. Після чого компіляцію було перервано. Можливі наступні типи семантичні помилок, що реалізовані в компіляторі: Багатократне оголошення Змінна не оголошена Змінна не ініціалізована Неспівпадіння типів змінних 4.4. Загальна перевірка коректності роботи компілятора Перевірка роботи компілятора на правильній тестовій програмі з використанням усіх мовних конструкцій. Програма знаходиться у файлі test.Z1 (див. Додатки) Запуск на компілювання відбувається наступним чином: compilerZ1.exe test.Z1 В результаті на екрані ми отримуєм наступні повідомлення: Starting analyse... Analyse finished successfully! Press ENTER to start code generation З повідомлення випливає, що процес компілювання пройшов успішно. В результаті було згенеровано файл з розширенням output_.txt, а також автоматично запущено bcc.exe, за допомогою яких було створено output_.exe файл. ВИСНОВКИ В процесі виконання курсової роботи було виконано наступне: Складено формальний опис мови програмування Z1, в термінах розширеної нотації Бекуса-Наура, виділено усі термінальні символи та ключові слова. Створено компілятор мови програмування Z1, а саме: Розроблено прямий лексичний аналізатор, орієнтований на розпізнавання лексем, що є заявлені в формальному описі мови програмування. Розроблено синтаксичний аналізатор, який працює методом рекурсивного спуску. Складено дерево граматичного розбору на осно

Курсова робота Системне програмне забезпечення

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись