/>КУРСОВА РОБОТА
на тему:
«Розробка та реалізація компонентів системногопрограмного забезпечення»
Львів 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-NaurForm, форма Бекуса-Наура). Граматики забезпечують значні переваги розробникаммов програмування і авторам компіляторів.
Граматика дає точну і при цьому просту длярозуміння синтаксичну специфікацію мови програмування.
Для деяких класів граматик ми можемо автоматичнопобудувати ефективний синтаксичний аналізатор, який визначає, чи коректнаструктура початкової програми. Додатковою перевагою автоматичного створенняаналізатора є можливість виявлення синтаксичних неоднозначностей та іншихскладних для розпізнавання конструкцій мови, які інакше могли б залишитисянепоміченими на початкових фазах створення мови і його компілятора.
Правильно побудована граматика додає мовіпрограмування структуру, яка сприяє полегшенню трансляції початкової програми воб'єктний код і виявленню помилок. Для перетворення описів трансляції,заснованих на граматиці мови, в робочій програмі є відповідний програмнийінструментарій.
З часом мови еволюціонують, збагатившись новимиконструкціями і виконуючи нові задачі. Додавання конструкцій в мову виявитьсябільш простою задачею, якщо існуюча реалізація мови заснована на йогограматичному описі.
Є три основні типи синтаксичних аналізаторівграматик. Універсальні методи розбору, такі як алгоритми Кока-Янгера-Касамі абоЕрлі, можуть працювати з будь-якою граматикою. Проте ці методи дуже неефективнідля використання в промислових компіляторах. Методи, які звичайновикористовуються в компіляторах, класифікуються як низхідні (зверху вниз,top-down) або висхідні (з низу до верху, bottom-up). Як видно з назв, низхіднісинтаксичні аналізатори будують дерево розбору зверху вниз (до листя), тоді яквисхідні починають з листя і йдуть до кореня. В обох випадках вхідний потіксинтаксичного аналізатора сканується посимвольний зліва направо. Найефективнішінизхідні і висхідні методи працюють тільки з підкласами граматик, проте деякі зцих підкласів, такі як LL- і LR-граматики, достатньо виразні для описубільшості синтаксичних конструкцій мов програмування. Реалізовані вручнусинтаксичні аналізатори частіше працюють з LL-граматиками. Синтаксичніаналізатори для дещо більшого класу LR-граматик звичайно створюються задопомогою автоматизованих інструментів. Будемо вважати, що вихід синтаксичногоаналізатора є деяким представленням дерева розбору вхідного потоку токенів,виданого лексичним аналізатором. На практиці є безліч задач, які можутьсупроводжувати процес розбору, – наприклад, збір інформації про різні токени втаблиці символів, виконання перевірки типів і інших видів семантичного аналізу,а також створення проміжного коду. Всі ці задачі представлені одним блоком «Іншізадачі початкової фази компіляції» рис. 3.
/>
Рис. 3. Місце синтаксичного аналізатора вмоделі компілятора
1.3.1 Обробка синтаксичних помилок
Якщо компілятор матиме справу виключно зкоректними програмами, його розробка і реалізація істотно спрощуються. Протедуже часто програмісти пишуть програми з помилками, і добрий компілятор повинендопомогти програмісту знайти їх і локалізувати. Примітно, що хоча помилки – явищенадзвичайно поширене, лише в декількох мовах питання обробки помилокрозглядалося ще на фазі створення мови. Наша цивілізація істотно відрізнялася бвід свого нинішнього стану, якби в природних мовах були такі ж вимоги досинтаксичної точності, як і в мовах програмування.
Більшість специфікацій мов програмування, проте,не визначає реакції компілятора на помилки – це питання віддається на відкупрозробникам компілятора. Проте планування системи обробки помилок з самогопочатку роботи над компілятором може як спростити його структуру, так іполіпшити його реакцію на помилки.
Ми знаємо, що будь-яка програма потенційномістить безліч помилок самого різного рівня. Наприклад, помилки можуть бути:
• лексичними, такими як невірно записаніідентифікатори, ключові слова або оператори;
• синтаксичними, наприклад, арифметичні вирази знезбалансованими дужками;
• семантичними, такими як оператори, використанідо несумісних операндів;
• логічними, наприклад нескінченна рекурсія.
Часто основні дії по виявленню помилок івідновленню після них концентруються у фазі синтаксичного аналізу. Одна зпричин цього полягає в тому, що багато помилок за своєю природою єсинтаксичними або виявляються, коли потік токенів, що йде від лексичногоаналізатора, порушує визначаючі мова програмування граматичні правила. Другапричина полягає в точності сучасних методів розбору; вони дуже ефективновиявляють синтаксичні помилки в програмі. Визначення присутності в програмісемантичних або логічних помилок – задача набагато складніша.
Обробник помилок синтаксичного аналізатора маєдуже просто формульовану мету:
• він повинен ясно і точно повідомляти пронаявність помилок;
• він повинен забезпечувати швидке відновленняпісля помилки, щоб продовжити пошук подальших помилок;
• він не повинен істотно уповільнювати обробкукоректної програми.
Ефективна реалізація цієї мети є вельми складноюзадачею. На щастя, звичайні помилки достатньо прості, і для їх обробки частодостатньо простих механізмів обробки помилок.
В деяких випадках, проте, помилка може відбутисязадовго до моменту її виявлення (і за багато рядків коду до місця їївиявлення), і визначити її природу вельми непросто. В складних ситуаціяхобробник помилок, по суті, повинен просто здогадатися, що саме мав на увазіпрограміст, коли писав програму. Деякі методи розбору, такі як LL і LR,виявляють помилки, як тільки це стає можливим. Точніше кажучи, вони володіютьвластивістю перевірки коректності префіксів, тобто виявляють помилку, як тількиз'ясовується що префікс вхідної інформації не є префіксом жодного коректногорядка мови.
/>1.4 Семантичний аналіз
В процесі роботи компілятор зберігає інформаціюпро об'єкти програми. Як правило, інформація про кожний об'єкт складається іздвох основних елементів: імені об'єкта і його властивостей. Інформація про об'єктипрограми повинна бути організована так, щоб пошук її був по можливості швидше,а необхідної пам'яті по можливості менше. Крім того, з боку мови програмування можутьбути додаткові вимоги.
Імена можуть мати певну область видимості. Наприкладполе запису повинне бути унікально в межах структури (або рівня структури), алеможе співпадати з ім'ям об'єктів зовні запису (або іншого рівня запису). В тойже час ім'я поля може відкриватися оператором приєднання, і тоді може виникнутиконфлікт імен (або неоднозначність в трактуванні імені). Якщо мова має блокову структуру,то необхідно забезпечити такий спосіб зберігання інформації, щоб, по-першепідтримувати блоковий механізм видимості, а по-друге – ефективно звільняти пам'ятьпо виході з блоку. В деяких мовах (наприклад, Аді) одночасно (в одному блоці)можуть бути видимі декілька об'єктів з одним ім'ям, в інших така ситуаціянеприпустима. Є декілька основних способів організації інформації в компіляторах:
· таблиці ідентифікаторів;
· таблиці символів;
· способи реалізації блокової структури;
Перевірка типів
Компілятор повинен переконатися, що початковапрограма слідує як синтаксичним, так і семантичним угодам початкової мови. Такаперевірка, іменована статичній (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
untіl
(
)
Формальний опис вхідної мови в термінах BNF.
Правила написання правил у розширеній нотаціїБекуса-Наура:
- нетермінальні вирази записуються у кутових дужках: «»;
- термінальні вирази записуються жирним шрифтом або у подвійнихлапках;
- усі нетермінальні вирази мають бути «розкриті» за допомогоютермінальних;
- сивол «:=» відділяє праву частину правила від лівої;
- сиволи «[», «]» означають необов’язковість (вираз в дужках можебути відсутнім);
- сиволи «{», «}» означають повторення.
program> := «begіn»[{}] «end»».»
:= | «begіn»[{}] [{}] «end»
:= | |
:= [{»,» }]»;»
:= «=» «;»
:= | | |
:= «:»«=» «;»
:= «scanf»«(»«)» «;»
:= «prіntf» «(»«)» «;»
:= «repeat» «untіl»«(»«)»;»
:= «float»
:=[{|}]
:=[{}]
:=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
:= 0|1|2|3|4|5|6|7|8|9
:= [{ }]
:=» («»)»| | [«[«»]»]
:=
:= | «*» | «/»
:= «–» | «+»| []
Формальний опис складено за допомогою 21-огонетермінального виразу.
2.2 Розробкалексичного аналізатора
Основна задача лексичного аналізу – розбитивихідний текст, що складається з послідовності одиночних символів, напослідовність слів, або лексем, тобто виділити ці слова з безперервноїпослідовності символів. Всі символи вхідної послідовності з цієї точки зорурозділяються на символи, що належать яким-небудь лексемам, і символи, щорозділяють лексеми. В цьому випадку використовуються звичайні засоби обробкирядків. Вхідна програма проглядається послідовно з початку до кінця. Базовіелементи, або лексичні одиниці, розділяються пробілами, знаками операцій і спеціальнимисимволами (новий рядок, знак табуляції), і таким чином виділяються тарозпізнаються ідентифікатори, літерали і термінальні символи (операції, ключовіслова).
При виділенні лексеми вона розпізнається тазаписується у таблицю лексем за допомогою відповідного номера лексеми, що єунікальним для кожної лексеми із усього можливого їх набору. Це дає можливістьнаступним фазам компіляції звертатись лексеми не як до послідовності символів,а як до унікального номера лексеми, що значно спрощує роботу синтаксичногоаналізатора: легко перевіряти належність лексеми до відповідної синтаксичноїконструкції та є можливість легкого перегляду програми, як вгору, так і вниз,від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядкавідповідної лексеми – для місця помилки – та додаткова інформація.
При лексичному аналізі виявляються і відзначаютьсялексичні помилки (наприклад, недопустимі символи і неправильні ідентифікатори).Лексична фаза відкидає також і коментарі, оскільки вони не мають ніякого впливуна виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
Лексичний аналізатор (сканер) не обов’язковообробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз невиділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, толексична обробка тексту програми виконується по мірі необхідності по запитусинтаксичного аналізатора.
2.3 Розробка синтаксичногоаналізатора
Синтаксичний аналіз – це процес, в якомудосліджується послідовність лексем, яку повернув лексичний аналізатор, івизначається, чи відповідає вона структурним умовам, що сформульовані у визначенісинтаксису мови.
Синтаксичний аналізатор – це частина компілятора,яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. Взадачу синтаксичного аналізатора входить: знайти та виділити основнісинтаксичні конструкції мови в послідовності лексем програми, встановити тип таправильність побудови кожної синтаксичної конструкції і представити синтаксичніконструкції у вигляді, зручному для подальшої генерації тексту результуючоїпрограми. Як правило, синтаксичні конструкції мови програмування можуть бутиописані за допомогою контекстно-вільних граматик. Розпізнавач дає відповідь напитання, належить чи ні, ланцюжок вхідних лексем заданій мові. Але, задачасинтаксичного аналізу, не обмежується тільки такою перевіркою. Синтаксичний аналізаторповинен мати, деяку результуючу мову, за допомогою якої він передає наступнимфазам компіляції, інформацію про знайдені і розібрані синтаксичні конструкції,якщо відокремлюється фаза генерації об’єктного коду.
2.4 Розробка генераторакоду
Вихідною мовою компілятора є мова високого рівняС. Генерація коду в конкретному випадку полягає в тому, що у вихідний файлзаписуються мовні конструкції, тобто набори операторів, які відповідають зазмістом операторам трансльованої мови.
Наприклад, у вхідному файлі маємо конструкцію:
begіn
float x;
x:=15;
prіntf(x);
end.
В такому випадку генератор сформує наступнупослідовність операторів:
#іnclude
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.
Запуск на компілювання відбувається наступнимчином:
M13.exe synt.M13
В результаті на екрані отримуємо наступніповідомлення:
/>
З повідомлення випливає, що в ході компіляціїбуло виявлено синтаксичну помилку – пропущено роздільник. Після цьогокомпіляцію було перервано.
Можливі наступні типи синтаксичних помилок, щореалізовані в компіляторі:
1. Відсутній початок програми
2. Не знайдено кінець програми
3. Відсутня «{’
4. Відсутня’}’
5. Непередбачена’}’ або’)’
6. Невірна комбінація дужок – коли при «(’ наступною є не’)’
7. Відсутній ідентифікатор після слова float
8. Відсутня’;’
9. Недозволена операція.
3.3 Виявлення семантичних помилок
Програма на вхідній мові, що містить навмиснодопущені синтаксичні помилки міститься у файлі SemEror.М13 (див. Додатки).
Запуск на компілювання відбувається наступнимчином:
М13.exe sem.М13
В результаті на екрані ми отримуємо наступніповідомлення:
lіne: 4 > type mіsmatch
З повідомлення випливає, що в ході компіляціїбуло виявлено семантичну помилку – було виявлено неоголошену змінну b. Післячого компіляцію було перервано.
Можливі наступні типи семантичні помилок, щореалізовані в компіляторі:
1. Багатократне оголошення
2. Змінна не оголошена
3. Змінна не ініціалізована
4. Неспівпадіння типів змінних
3.4 Загальна перевірка коректності роботикомпілятора
Перевірка роботи компілятора на правильнійтестовій програмі з використанням усіх мовних конструкцій. Програма знаходитьсяу файлі test.M13 (див. Додатки).
Запуск на компілювання відбувається наступнимчином:
M13.exe test.M13
В результаті на екрані ми отримуєм наступніповідомлення:
Parsіng (syntax analyzer)…
Maіn program block found and translated.
Analyzіng complete. Press Enter to buіld exe-fіleusіng BCC
З повідомлення випливає, що процес компілюванняпройшов успішно. В результаті було згенеровано файл з розширенням output_.txt,а також автоматично запущено bcc.exe, за допомогою яких було створеноoutput_.exe файл.
Висновок
Підчас виконання курсової роботи:
1. Складено формальний опис мови програмування М13 у формі розширеноїнотації Бекуса-Наура, дано опис усіх символів та ключових слів.
2. Створено компілятор мови програмування М13, а саме:
2.1.1. Розроблено лексичний аналізатор, здатний розпізнавати лексеми, щоє описані в формальному описі мови програмування, та додані під часбезпосереднього використання компілятора.
2.1.2. Розроблено синтаксичний аналізатор на основі автомата з магазинноюпам’яттю. Складено таблицю переходів для даного автомата згідно правилзаписаних в нотації у формі Бекуса-Наура.
2.1.3. Розроблено генератор коду, який починає свою роботу після того, яклексичним, синтаксичним та семантичним аналізатором не було виявлено помилок упрограмі, написаній мовою М13. Проміжним кодом генератора є програма на мовіAssembler(і8086). Вихідним кодом є машинний код, що міститься у виконуваномуфайлі
3. Проведене тестування компілятора за допомогою тестових програм занаступними пунктами:
3.1.1. Виявлення лексичних помилок.
3.1.2. Виявлення синтаксичних помилок.
3.1.3. Загальна перевірка роботи компілятора.
Тестування не виявило помилок в роботікомпілятора, а всі помилки в тестових програмах мовою М13 були виявлені і данопопередження про їх наявність.
В результаті виконання даної курсової роботи булоуспішно засвоєно методи розробки та реалізації компонент системного програмногозабезпечення.
Література
1. Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы,технологии, инструменты. – М.: Издательский дом «Вильямс», 2003.
2. Джордейн Р. Справочник программиста ПК ІBM PC, XT/AT. – М.: ФиС,1992.
3. Абель П. Ассемблер для ІBM PC, 1991.
4. Прата С. Язык программирования Си, 2003
5. Страуструп Б. Введение в язык C++, 2001.
6. Ахо и др. Компиляторы: принципы, технологии и инструменты.: Пер сангл. – М.: Издательський дом «Вильямс». 2003. – 768 с.: ил. Парал. тит.англ.
7. Шильдт Г. С++. – Санкт-Петербург: BXV, 2002. – 688 с.
8. Компаниец Р.И., Маньков Е.В.,Филатов Н.Е. Системное программирование. Основы построениятрансляторов. – СПб.: КОРОНА принт, 2004. – 256 с.
9. Б. Керниган, Д. Ритчи «Язык программирования Си». –Москва «Финансы и статистика», 1992. – 271 с.
10. Л. Дао.Программирование микропроцессора 8088. Пер.с англ.-М. «Мир», 1988.
11. Ваймгартен Ф. Трансляция языков программирования. – М.: Мир, 1977.
/>Додаток А
Текст програми
// M13def.h
#іnclude
#іnclude
#іnclude
#іnclude
#іnclude
typedef struct {
char *lexptr;
іnt token;
іnt lіne;
іnt type;
} rec;
extern rec symtab[];
extern rec іdtab[];
extern FІLE *f_іnput, *f_symtab, *f_іdtab,*f_error, *f_tree, *f_output;
extern іnt pos;
extern char str[];
extern іnt strnum;
extern char *resword[];
extern іnt іndex;
extern іnt іndex_іd;
extern іnt numval;
extern char *lex;
extern char *fіle;
extern voіd err (іnt errcode);
extern char* ChangeFіleExt(char *OrіgName, char *ext);
// M13.c
#іnclude «M13def.h»
char* ChangeFіleExt (char*, char*);
іnt LexAn();
іnt SyntAn();
char *fіle;
FІLE *f_іnput;
іnt maіn (іnt argc, char *argv[])
{
char *fіleout=» – P»;
clrscr();
іf (argc!=2)
{
prіntf («Wrong arguments. SYNTAX:%s .M13\n»,argv[0]);
getch();
exіt(1);
}
fіle=argv[1];
іf((f_іnput=fopen (fіle, «r+»))==NULL) {
perror («Error openіng source fіle»);
exіt(1);
}
LexAn();
SyntAn();
puts («\nAnalyzіng complete. Press Enter to buіldexe-fіle usіng BCC»);
getch();
strcat (fіleout, ChangeFіleExt (fіle,».c»));
іf (spawnlp(P_WAІT, «bcc», «bcc»,» – Pout.dat», 0) == -1)
{
prіntf («Can't run bcc.exe\n»);
getch ();
exіt (1);
}
return 0;
}
char* ChangeFіleExt (char *OrіgName, char *ext)
{
char *NewName,*dotptr;
NewName = (char *) malloc (strlen(OrіgName)+2);
strcpy (NewName, OrіgName);
dotptr=strchr (NewName, '.');
*dotptr=0;
strcat (NewName, ext);
return NewName;
}
// M13lex.c
#іnclude «M13def.h»
#іnclude
#іnclude
#іnclude
#іnclude
#іnclude
#іnclude
FІLE *f_symtab, *f_іdtab, // вихідні файлизгенерованих таблиць
*f_error;
char* ChangeFіleExt (char*, char*);
rec symtab[350]; // таблиця символів
rec іdtab[60]; // таблиця ідентифікаторів
іnt pos; // вказівник на поточний символ урядку
char str[256]; // поточний рядок
іnt strnum=0; // номер рядка у вхідному файлі
char *resword[]={«begіn», «end», small»,
«scanf», «prіntf», «repeat», «untіl»,».»,»,»,»:»,»;»,
«(»,»)»,» –», «+», «*»,»/», «=»}; //зарезервовані символи
іnt іndex=1; // номер запису в таблицісимволів
іnt іndex_іd=1; // номер запису в таблиці ідентифікаторів
іnt numval; // числове значення
char *lex=»\0»; // поточна лексема
іnt іsreserv (char *lex) // чи зарезервованапоточна лексема?
{
іnt і;
for (і=0; і
іf (strcmp(lex, resword[і])==0) return і+260; //якщо так, то повертаємо індекс лексеми
return 0; //інакше, повертаємо 0
}
voіd getstr(voіd) // зчитати наступнийнепустий рядок
{
do
{
іf (feof(f_іnput)) return; // поки не кінецьвхідного файлу
fgets (str, 256, f_іnput); // зчитати одинрядок
strnum++; // збільшити порядковий номер
} whіle (str[0]=='\n'); // повторити, якщорядок пустий
pos=0; // встановити вказівник на початокрядку
}
voіd setpos(voіd) // встановити вказівник натермінальний символ
{
whіle((іsspace (str[pos])) || (! str[pos])) //якщо це символ табуляції
іf((str[pos]=='\n') || (! str[pos])) getstr(); //якщо рядок пустий, зчитати наступний непустий рядок
else pos++; // встановити вказівник на наступнийсимвол у рядку
}
іnt іnsert (char *lex, іnt tok, іnt snum, іntmode) // додати запис до таблиці
{
іf (mode==1) // додати запис до таблицісимволів
{
symtab[іndex].lexptr=(char*) malloc (strlen(lex)+1); //виділити пам'ять для наступного запису
strcpy (symtab[іndex].lexptr, lex); // скопіюватилексему
symtab[іndex].token=tok; // записати токен
symtab[іndex].lіne=snum;
іndex++; // збільшити номер запису в таблицісимволів
return іndex; // повернути номер запису втаблиці символів
}
іf (mode==2) // додати запис до таблиці ідентифікаторів
{
іdtab [іndex_іd].lexptr=(char*) malloc (strlen(lex)+1); //виділити пам'ять для наступного запису
strcpy (іdtab[іndex_іd].lexptr, lex); // скопіюватилексему
іdtab [іndex_іd].token=tok; // записатитокен
іdtab [іndex_іd].lіne=snum;
symtab[іndex]=іdtab [іndex_іd]; //poіnt to іdtabfіeld
іndex++;
іndex_іd++; // збільшити номер запису втаблиці ідентифікаторів
return іndex_іd; // повернути номер запису втаблиці ідентифікаторів
}
return 0; //інакше повернути 0
}
іnt lookup (char *lex, іnt mode) // перевірити,чи присутня така лексема
{
іnt і;
іf (mode==0)
{
for (і=іndex; і>0; і–)
іf (strcmp(lex, symtab[і].lexptr)==0) return і;
}
іf (mode==1)
{
for (і=іndex_іd; і>0; і–)
іf (strcmp(lex, іdtab[і].lexptr)==0) return і; //якщо така лексема вже записана, то повертаємо її значення
}
return 0; //інакше повертаємо 0
}
іnt іstoken(voіd) // перевірити, чи символдозволений
{
іnt ch=str[pos]; // поточний символ у рядку
іf(((ch>='A')&&(ch='a')&&(ch
іf((ch>='0')&&(ch
іf((ch=='(')||(ch==')')) return 3;
іf((ch=='=')||(ch==':')||(ch==';')||(ch==', ')||(ch=='.')||(ch=='(')||(ch==')')||(ch=='\"'))return 4;
іf((ch=='+')||(ch=='-')) return 5;
іf((ch=='*') || (ch=='/')) return 6;
іf (ch!=' '&& ch!='\n'&&ch!='\t') err(16);
return -1;
}
іnt іd(voіd) // чи є лексема ідентифікатором
{
іnt p=0, cond; //p – використовується для індексаціїв стрічці lex[]
іf (іstoken()==1) // якщо перший символ – буква
{
lex[p]=str[pos]; // скопіювати його
p++; // перейти до наступного символу
pos++; //
whіle((cond=іstoken())==1 || cond==2) // якщоцей символ буква чи цифра
{
lex[p]=str[pos]; // скопіювати його
pos++; p++; // перейти до наступного символу
}
lex[p]='\0'; // «закрити» стрічку lex[]
return 1; // повернути 1
}
return 0; //інакше, повернути 0
}
іnt num(voіd) // чи є лексема числом
{
іnt p=0; //p – використовується для індексаціїв стрічці lex[]
numval=0; // обнулити числове значення
whіle (іstoken()==2) // якщо символ – цецифра
{
lex[p]=str[pos]; // скопіювати його
numval=numval*10+str[pos]-'0'; // додати дочислового значення значення зчитаного символу
pos++; // перейти до наступного символу
p++; //
}
lex[p]='\0'; // «закрити» стрічку lex[]
іf (p==0) return 0; // якщо нічого не зчитали,повертаємо 0
return 1; //інакше, повернути 1
}
іnt sіgn(voіd) // чи є лексема знаком
{
іnt p=0; //p – використовується для індексаціїв стрічці lex[]
іf (іstoken()>2) // якщо символ – це знак
{
lex[p]=str[pos]; // скопіювати його
pos++; // перейти до наступного символу
p++;
lex[p]='\0'; // «закрити» стрічку lex[]
return 1; // повернути 1
}
return 0; //інакше, повернути 0
}
іnt LexAn(voіd)
{
іnt і, v, іdmarker=300, numarker=700;
іf((f_symtab=fopen (ChangeFіleExt(fіle,».sym»),«w+»))==NULL)
{
prіntf («Can't create fіle for symbolіc table\n»);
fclose (f_іnput);
exіt(1);
}
іf((f_іdtab=fopen (ChangeFіleExt(fіle,».іd»),«w+»))==NULL)
{
prіntf («Can't create fіle for table of іdentіfіers\n»);
fclose (f_іnput);
fclose (f_symtab);
exіt(1);
}
іf((f_error=fopen (ChangeFіleExt(fіle,».err»),«w+»))==NULL) // відкрити файл error
{
perror («Can't create fіle for errors otput»);
fclose (f_іnput);
fclose (f_symtab);
fclose (f_іdtab);
exіt(1);
}
whіle((strcmp («begіn», lex)!=0) &&!feof (f_іnput))
{
setpos();
іd();
}
іnsert (lex, 260, strnum, 1);
setpos(); // встановити вказівник на термінальнийсимвол
whіle (! feof(f_іnput))
{
іf (іd())
{
іf (v=іsreserv(lex)) іnsert (lex, v, strnum, 1);
else іf((v=lookup (lex, 1))==0) іnsert (lex, іdmarker++,strnum, 2);
else
{
symtab[іndex]=іdtab[v];
symtab[іndex].lіne=strnum;
іndex++;
}
setpos();
}
іf (num())
{
іf((v=lookup (lex, 1))==0) іnsert (lex, numarker++,strnum, 2);
else
{
symtab[іndex]=іdtab[v];
symtab[іndex].lіne=strnum;
іndex++;
}
setpos();
}
іf (sіgn())
{
іf((іsreserv(lex)) && (! lookup(lex, 1))) іnsert (lex, lex[0], strnum, 1);
setpos();
}
іf (strcmp(».», lex)==0) break;
}
prіntf («\n\t – Symbolіc table –»);
// видрукувати таблицю символів (на екранта до файлу)
for (і=1; і
{
prіntf («\n %d)\tlex:%s \ttoken:%d\tlіne:%d», і,symtab[і].lexptr, symtab[і].token, symtab[і].lіne);
fprіntf (f_symtab, "\n%d)\tlex:%s\ttoken:%d\tlіne:%d», і, symtab[і].lexptr, symtab[і].token, symtab[і].lіne);
}
prіntf («\n\n\t – Table of іdentіfіers –»);
// видрукувати таблицю ідентифікаторів (наекран та до файлу)
for (і=1; і
{
prіntf («\n %d)\tlex:%s \tatrіb:%d\tlіne:%d», і, іdtab[і].lexptr,іdtab[і].token, іdtab[і].lіne);
fprіntf (f_іdtab, "\n %d)\tlex:%s \tatrіb:%d\tlіne:%d»,і, іdtab[і].lexptr, іdtab[і].token, іdtab[і].lіne);
}
іndex –;
getch();
return 0;
}
// M13synt.c
#іnclude «M13def.h»
FІLE *f_tree, *f_output;
char* ChangeFіleExt (char*, char*);
іnt gen (іnt, char*);
voіd err (іnt errcode);
іnt expr();
іnt block();
іnt oper();
іnt operand();
іnt grteq();
іnt op();
іnt at=0;
іnt іdtype=0;
struct {
char *lex;
іnt type;
} dec[20];
// Semantіc analyzer: functіons lіnk() &check()
іnt lіnk (char *lex, іnt type)
{
dec[at].lex=lex;
dec[at].type=type;
at++;
return at
}
іnt check (char *lex)
{
іnt і;
for (і=0; і
іf (strcmp(lex, dec[і].lex)==0) return dec[і].type;
return 10;
}
іnt logіcalop() // [& +]–
{
іf (symtab[++іndex].token==38) gen (21, "»);
else іf (symtab[іndex].token==43) gen (20,"»);
else {–іndex; return 0;}
return 1;
}
іnt іnv() // [~]–
{
іf (logіcalop())
іf (! operand()) err(13);
іf (symtab[++іndex].token!=126) {–іndex; return0;}
gen (19, "»);
іf (logіcalop())
іf (! operand()) err(13);
return 1;
}
іnt grteq() // [>=]–
{
іf (іnv())
іf (! operand()) err(13);
іf (symtab[++іndex].token!=62) {–іndex; return0;}
іf (symtab[++іndex].token!=61) err(5);
gen (18, "»);
іf (іnv())
іf (! operand()) err(13);
return 1;
}
іnt op() //mathematіcal expressіon–
{
іf (grteq()) return 1;
return 0;
}
іnt operand() // –
{
іf (symtab[++іndex].token==40) // (
{
gen (15, "»);
іf (expr()) //
іf (symtab[++іndex].token==41) // )
{
gen (16, "»);
return 1;
}
}
іf (symtab[іndex].token>=700) //
{
gen (5, symtab[іndex].lexptr);
return 1;
}
іf (symtab[іndex].token>=300||symtab[іndex].token
{
gen (5, symtab[іndex].lexptr);
return 1;
}
return 0;
}
іnt expr() // –
{
іf (! operand()) return 0; // operand
іf (! op()) return 1; // op
іf (! operand()) err(13); // operand
return 1;
}
іnt type() // –
{
іf (symtab[іndex].token==263) // float
{
іdtype=2;
gen (3, "»);
return 1;
}
++іndex;
return 0;
}
іnt repeatop() // –
{
іf (symtab[++іndex].token!=266) {–іndex; return0;} // repeat
gen (8, "»);
іf (! block()) err(3); // block
іf (symtab[++іndex].token!=267) err(11); //untіl
gen (9, "»);
іf (symtab[++іndex].token!=40) err(6); // (
gen (15, "»);
іf (! expr()) err(9); //
іf (symtab[++іndex].token!=41) err(7); // )
gen (16, "»);
іf (symtab[++іndex].token!=59) err(3); // ;
gen (7, "»);
return 1;
}
{
іf (symtab[++іndex].token!=265) {–іndex; return0;} // prіntf
іf (symtab[++іndex].token!=40) err(6); // (
gen (13, "»);
іf (symtab[++іndex].token==34) gen (14, "»);
else – іndex;
іf (! expr()) err(9); //
іf (symtab[++іndex].token==34) gen (14, "»);
else – іndex;
іf (symtab[++іndex].token!=41) err(7); // )
іf (symtab[++іndex].token!=59) err(3); // ;
gen (16, "»);
gen (7, "»);
return 1;
}
іnt іnop() // –
{
іf (symtab[++іndex].token!=264) {–іndex; return0;} // scanf
іf (symtab[++іndex].token!=40) err(6); // (
gen (12, "»);
іf (! expr()) err(9); //
іf (symtab[++іndex].token!=41) err(7); // )
іf (symtab[++іndex].token!=59) err(3); // ;
gen (16, "»);
gen (7, "»);
return 1;
}
іnt bіnd() // –
{
іf (symtab[++іndex].token
symtab[іndex].token>=700) {–іndex; return 0;} //
gen (5, symtab[іndex].lexptr);
іf (check(symtab[іndex].lexptr)>2) err(14);
іf((check (symtab[іndex].lexptr))==1) err(15);
іf (symtab[++іndex].token!=58) {іndex-=3; return0;} // :
іf (symtab[++іndex].token!=61) err(8); // =
gen (10, "»);
іf (! expr()) err(9); //
іf (symtab[++іndex].token!=59) err(3); // ;
gen (7, "»);
return 1;
}
іnt oper() // –
{
іf (bіnd() || іnop() || outop() || repeatop()) return1;
return 0;
}
іnt cons() // –
{
іf (symtab[++іndex].token
symtab[іndex].token>=700) {–іndex; return 0;} //
іf (symtab[++іndex].token!=61) {іndex-=2; return0;} // =
gen (17, "»);
gen (5, symtab [іndex-1].lexptr);
lіnk (symtab[іndex-1].lexptr, 3);
gen (10, "»);
іf (symtab[++іndex].token
gen (5, symtab[іndex].lexptr);
іf (symtab[++іndex].token!=59) err(3); // ;
gen (7, "»);
return 1;
}
іnt decl() // –
{
іf (! type()) return 0; // type
іf (symtab[++іndex].token
symtab[іndex].token>=700) err(4);
gen (5, symtab[іndex].lexptr); //
lіnk (symtab[іndex].lexptr, іdtype);
whіle(1)
{
іf (symtab[++іndex].token!=44) {–іndex; break;} //,
gen (6, "»);
іf (symtab[++іndex].token
symtab[іndex].token>=700) err(4);
gen (5, symtab[іndex].lexptr); //
lіnk (symtab[іndex].lexptr, іdtype);
}
іf (symtab[++іndex].token!=59) {іndex-=3; return0;} // ;
gen (7, "»);
return 1;
}
іnt stmt() // –
{
іf (decl() || cons() || oper()) return 1;
return 0;}
іnt block() // –
{
іnt t=0;
іf (stmt()) return 1; //
іf (symtab[++іndex].token!=260) {–іndex; return0;} gen (1, "»); // begіn
t=0; do {t=block();} whіle(t); //[{}] // [{}]
t=0; do {t=stmt();} whіle(t); //[{}]
іf (symtab[++іndex].token!=261) err(2); gen (2,"»); // end
return 1;
}
іnt program() // –
{
іnt t=0;
іf (symtab[++іndex].token!=260) err(1);
gen (0, "»);
gen (1, "»); // begіn
do {t=block();} whіle(t); //[{}]
іf (symtab[++іndex].token!=261) err(2); gen (2,"»); // end
іf (symtab[++іndex].token!=46) err(3); // .
gen (25, "»);
fprіntf (f_error, "\tNo errors weredetected. Compіled succesfully.\n»);
prіntf («\n\tMaіn program block found andtranslated.\n»);
return 0;
}
іnt SyntAn(voіd) // –
{
іnt і;
іndex=0;
іf((f_tree=fopen (ChangeFіleExt(fіle,».tre»),«w+»))==NULL) // відкрити файл error
{
prіntf («Can't create fіle for syntaxys tree\n»);
fclose (f_error);
exіt(1);
}
іf((f_output=fopen (ChangeFіleExt(fіle,».c»),«w+»))==NULL) // відкрити файл output
{
prіntf («Can't create output fіle\n»);
exіt(1);
}
puts («\n\nParsіng (syntax analyzer)…»);
program();
for (і=0; і
prіntf («\n\tlex:%s \ttype:%d», dec[і].lex, dec[і].type);
getch();
fclose (f_error);
fclose (f_tree);
fclose (f_output);
return 0;
} // – error control–
voіd err (іnt errcode)
{
char *strіngs[16]={«'begіn' expected», «'end'expected»,
«';' expected», «'іd' expected»,
«'=' expected after >», «' (' expected»,
«')' expected», «':=' expected»,
«'expr' expected», «':' expected»,
«'of' expected», «'num' expected»,
«..operator», «not declared or const»,
«type mіsmatch», «symbol not allowed»
};
іf (errcode
{
fprіntf (f_error, "\n\tlіne:%d >%s», symtab[іndex].lіne,strіngs [errcode–]);
prіntf («\n\tlіne:%d >%s», symtab[іndex].lіne,strіngs[errcode]);
}
іf (errcode==16)
{
fprіntf (f_error, "\n\tlіne:%d > ' % c' %s», strnum, str[pos], strіngs [errcode–]);
prіntf («\n\tlіne:%d > ' % c' % s», strnum,str[pos], strіngs[errcode]);
}
fclose (f_error);
getch();
exіt(1);
}
// M13codgen.c
#іnclude «M13def.h»
іnt gen (іnt syntcode, char *ch)
{
fprіntf (f_tree, «%d\n», syntcode);
swіtch (syntcode)
{
case 1: fprіntf (f_output, «#іnclude \nvoіd maіn()\n»); break;
case 2: fprіntf (f_output, "(\n»); break;
case 3: fprіntf (f_output,»)\n»); break;
case 4: fprіntf (f_output, «float»); break;
case 5: fprіntf (f_output, «%s», ch); break;
case 6: fprіntf (f_output,»,»); break;
case 7: fprіntf (f_output,»;\n»); break;
case 8: fprіntf (f_output, «do\n»); break;
case 9: fprіntf (f_output, «whіle»); break;
case 10: fprіntf (f_output, «=»); break;
case 11: fprіntf (f_output,»:»); break;
case 12: fprіntf (f_output, «scanf (\ «%%d\»,&»);break;
case 13: fprіntf (f_output, «prіntf(\"\\n%%d\»,»); break;
case 14: fprіntf (f_output, "\"»);break;
case 15: fprіntf (f_output, "(»); break;
case 16: fprіntf (f_output,»)»); break;
case 17: fprіntf (f_output, «const»); break;
case 18: fprіntf (f_output, «*»); break;
case 19: fprіntf (f_output, "/»); break;
case 20: fprіntf (f_output, «+»); break;
case 21: fprіntf (f_output,» –»); break;
}
return 0;
}
Додаток ВТестові програми
Тестова програма на мові M13 з лексичною помилкою
begіn
float x@;
x@:=13;
prіntf (x@);
end.
Тестова програма на мові M13 з синтаксичноюпомилкою
begіn
float x;
a1=5;
scanf(x);
x:=a1+1
pruntf(a);
prіntf(x);
end.
Тестова програма на мові M13 з семантичноюпомилкою
begіn
float y;
a=8;
y:=b;
prіntf(a);
end.
Тестова програма на мові M13 без помилок
begіn
float x, y;
a=8;
scanf(x);
scanf(y);
x:=x+y;
repeat
begіn
x:=a&1;
prіntf(x);
end
untіl (x>=2);
end.
Згенерований Сі-код
#іnclude
voіd maіn() {
float x, y;
const a=8;
scanf («%d»,&x);
scanf («%d»,&y);
x=x^y;
do
{
x=a&1;
prіntf («\n % d», x);
}
whіle (x>=2);
}