скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыКурсовая работа: Розробка та реалізація компонентів системного програмного забезпечення

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

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

на тему:

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

Львів 2011


Анотація

В курсовому проекті розроблено компілятор з простої мови програмування з назвою М13.

Компілятор розроблений в середовищі програмування Borland C/C++ на мові С, та поданий у пояснювальній записці, а також в електронному варіанті. В пояснювальній записці подано огляд існуючих методів розробки компіляторів, детальний опис мови, а також описано процес розробки програми компілятора на рівні блок-схем і тексту програми. В додатку міститься текст компілятора, а також результати тестування програми.

компілятор програма схема тестування


Завдання

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

·  Кожна програма починається зі слова begіn і закінчується словом end. Все що до begіn і після end не аналізується.

·  Програма має надавати можливість працювати зі змінними k, l, m. Змінні перед використанням мають бути попередньо оголошені за наступним форматом: «тип даних» «змінна1», «змінна2».

·  Присвоєння до змінних виконується оператором присвоєння:=.

·  Програма має надавати можливість працювати з константами k1, k2, k3. Константи ініціюються наступним чином: «константа» = «число;».

·  Ввід даних зі стандартного вводу відбувається оператором scanf(), а вивід оператором prіntf().

·  Програма має працювати з типом даних float.

·  Програма має виконувати операції *,/,+, –.

Вихідною мовою трансляції є мова С.

Математичний вираз має бути розібраний в залежності від пріоритету виконання та розписаний викликом власних С функцій.

Цільова мова компілятора: ANSІ C. Для отримання виконавчого файлу на виході розробленого компілятора скористатися програмою bcc.exe. Мова розробки компілятора: ANSІ C. Реалізувати інтерфейс командного рядка. На вхід розробленого компілятора має подаватися текстовий файл, написаний на заданій мові програмування. На виході розробленого компілятора мають з’являтися чотири файли: файл з повідомленнями про помилки (або про їх відсутність), файл на мові СІ, об’єктний та виконавчий файли.

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


Вступ

На перший погляд, різноманітність компіляторів вражає. Використовуються тисячі вихідних мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, які виникають у всіх областях застосування комп’ютера. Цільові мови не менш різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп’ютерів. Деколи компілятори класифікують як однопрохідні, багато прохідні, виконуючі (load-and-go), відлагоджуючі, оптимізуючи – в залежності від призначення і принципів і технологій їх створення.

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

В 50-х роках про компілятори ходила слава, що це програми, дуже складні в написанні (наприклад, перший компілятор Fortran потребував 18 людино-років роботи). З того часу розроблені різноманітні систематичні технології вирішення багатьох задач, виникаючих при компіляції. Крім цього, розроблені хороші мови реалізації, програмні середовища та програмні інструменти. Завдяки цьому «солідний» компілятор може бути реалізований в якості курсової роботи з проектування компіляторів.


1.  Аналітичний розділ

1.1 Фази компілятора

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

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

Рис. 1. Фази компілятора


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

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

 

1.2 Лексичний аналіз

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

Рис. 2. Взаємодія лексичного і синтаксичного аналізаторів

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

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

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

Є ряд причин, по яких фаза аналізу компіляції розділяється на лексичний і синтаксичний аналізи:

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

1.3.1 Обробка синтаксичних помилок

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

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

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

• лексичними, такими як невірно записані ідентифікатори, ключові слова або оператори;

• синтаксичними, наприклад, арифметичні вирази з незбалансованими дужками;

• семантичними, такими як оператори, використані до несумісних операндів;

• логічними, наприклад нескінченна рекурсія.

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

Обробник помилок синтаксичного аналізатора має дуже просто формульовану мету:

• він повинен ясно і точно повідомляти про наявність помилок;

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

• він не повинен істотно уповільнювати обробку коректної програми.

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

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

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


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

© 2010.