Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Транслятор вхідної мови програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Курсова робота
Предмет:
Системне програмування та операційні системи
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Інститут комп’ютерної техніки, автоматики та метрології
Кафедра “Електронні обчислювальні машини”
Курсова робота
з предмету “Системне програмування”
на тему: Розробка транслятора з вхідної мови програмування.
Варіант № 36
Анотація
В даній курсовій роботі розроблено транслятор з вхідної мови програмування s36. Дана робота носить навчальний характер, але є важливою, оскільки розробка програмних модулів і компонент системного програмування є актуальним завданням на сьогоднішній час. Транслятор розроблений в середовищі програмування Microsoft Visual Studio 2010 та поданий у пояснювальній записці, а також в електронному варіанті. Для побудови транслятора використано низхідний метод граматичного розбору. В пояснювальній записці подано огляд існуючих методів розробки трансляторів, детальний опис мови, а також описано процес розробки програми транслятора на рівні тексту програми. До проекту додано результати тестування програми та вихідний текст програми транслятора.
Зміст
Вступ 4
1. Огляд методів та способів проектування трансляторів 5
2. Формальний опис вхідної мови програмування 7
2.1 Деталізований опис вхідної мови в термінах EBNF 7
2.2 Опис термінальних символів та ключових слів 8
3. Розробка транслятора вхідної мови програмування 9
3.1 Вибір технології програмування 9
3.2 Проектування таблиць транслятора та вибір структур даних 9
3.3 Розробка лексичного аналізатора 12
3.3.1 Розробка граф-схеми алгоритму 12
3.3.2 Опис програми реалізації лексичного аналізатора 13
3.4 Опис синтаксичного та семантичного аналізатора 14
3.4.1 Розробка граф-схеми алгоритму 14
3.4.2 Опис програми реалізації синтаксичного та семантичного аналізатора 16
3.5 Розробка генератора коду 16
3.5.1 Розробка граф-схеми алгоритму 16
3.5.2 Опис програми реалізації генератора коду 17
4. Опис інтерфейсу та інструкції користувача 19
5. Відлагодження та тестування програми 20
5.1 Виявлення лексичних помилок 20
5.2 Виявлення синтаксичних помилок 21
5.3 Виявлення семантичних помилок 21
5.4 Загальна перевірка коректності роботи транслятора 22
Висновки 23
Список літератури 24
Додаток А завдання на курсову роботу 25
Додаток Б лістинг програми транслятора 26
Додаток В лістинг програми заготовки початкового коду 47
Вступ
Створення трансляторів є одною з невід’ємних частин системного програмного забезпечення. Одним із завдань транслятора є переведення написаного тексту програми у машинний код, який повинен відповідати комп’ютерній системі. Оскільки комп’ютерна галузь на сьогоднішній день розвивається дуже швидко, то створений машинний код з часом стає застарілим, тобто не відповідає принципу оптимального використання комп’ютерних ресурсів. Тому для запобігання цього явища необхідно створювати нові компілятори, які б відповідали потребам ринку.
Проблема трансляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою транслятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього транслятор має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати об'єктний код або виконавчий модуль.
В даній курсовій роботі розроблятиметься транслятор з вхідної мови програмування (див. додаток А). Програма-транслятор повинна буде з заданого на вході коду програми на вхідній мові сформувати код на мові асемблера. Компіляція асемблерного коду здіснуватиметься компілятором MASM 32. Також буде створено середовище розробки, що дозволяє створювати та підлагоджувати програму. Середовище розробки представлятиме з себе текстовий редактор з інтерфейсом SDI, де крім стандартних командних меню будуть командні меню для виконання всіх фаз трансляції. Також з метою поліпшення від лагодження буде додана можливість підсвічення і виділення помилок. Всі проміжні результати розробки програми будуть зберігатися в відповідниx файлах в каталозі з вхідною програмою.
1. Огляд методів та способів проектування трансляторів
На перший погляд, різноманітність компіляторів вражає. Використовуються тисячі вихідних мов, від традиційних, таких як Fortran і Pascal, до спеціалізованих, які виникають у всіх областях застосування комп’ютера. Цільові мови не менш різноманітні – це можуть бути інші мови програмування, різні машинні мови – від мов мікропроцесорів до суперкомп’ютерів. Компілятори класифікують як однопрохідні, багато прохідні, виконуючі (load-and-go), відлагоджуючі, оптимізуючи – в залежності від призначення і принципів і технологій їх створення.
Не дивлячись на те, що основні задачі, що виконуються компіляторами видаються складними і різноманітними, по суті вони одні і ті ж. Розуміючи ці задачі, ми можемо створювати компілятори для різних вихідних мов і цільових машин з використанням одних і тих же базових технологій.
В 50 х роках про компілятори ходила слава, що це програми, дуже складні в написанні (наприклад, перший компілятор Fortran потребував 18 людино-років роботи). З того часу розроблені різноманітні систематичні технології вирішення багатьох задач, виникаючих при компіляції. Крім цього, розроблені хороші мови реалізації, програмні середовища та програмні інструменти. Завдяки цьому «солідний» компілятор може бути реалізований в якості курсової роботи з проектування компіляторів.
Компіляція складається з двох частин: аналізу і синтезу. Аналіз – це розбиття початкової програми на складові частини і створення її проміжного представлення. Синтез – конструювання необхідної цільової програми з проміжного представлення.
В процесі аналізу визначаються і записуються в ієрархічну деревовидну структуру операції, задані початковою програмою. Часто використовується спеціальний вид дерева, що називається синтаксичним (або деревом синтаксичного розбору), в якому кожен вузол представляє операцію, а його дочірні вузли – аргументи операції.
Багато програмних інструментів, працюючи з початковими програмами, спочатку виконують певний вид аналізу. Розглянемо приклади таких інструментів.
Структурні редактори. Ці програми одержують як вхід послідовність команд для побудови початкової програми. Такий редактор не тільки виконує звичні для текстового редактора функції зі створення і модифікації тексту, але і аналізує текст програми, поміщаючи в початкову програму відповідну ієрархічну структуру. Тим самим він виконує додаткові задачі, що полегшують підготовку програми. Наприклад, редактор може перевіряти коректність введеного тексту, автоматично додавати структурні елементи (так, якщо користувач введе while, редактор додасть відповідне йому ключове слово do і запропонує ввести умовний вираз між ними) або переходить від ключового слова begin або лівої дужки до відповідного end або правої дужки. Більше того, результат на виході такого редактора часто подібний результату після фази аналізу компіляції.
Програми форматованого виводу для друку. За допомогою цих інструментів програма аналізується і роздруковується так, щоб її структура була максимально ясною. Наприклад, коментарі можуть бути виділені спеціальним шрифтом, а оператори – виведені з відступами, що вказують рівень вкладеності в ієрархічній структурі операторів.
Статичні перевіряючі програми. Дані інструменти зчитують програми, аналізують їх і намагаються знайти потенційні помилки без запуску програми. Такий аналіз часто дуже схожий на аналіз в оптимізуючих компіляторах. Наприклад, статична перевіряюча програма може визначити невиконання якоїсь частини початкової програми або використання деякої змінної до її оголошення. Так само можуть бути знайдені логічні помилки, наприклад спроби використання дійсної змінної як покажчик (із застосуванням технології перевірки типів).
При створенні цільової програми, окрім компілятора, може бути потрібним і ряд інших програм. Початкова програма може бути розділена на модулі, що зберігаються в окремих файлах. Задача збору початкової програми іноді доручається окремій програмі – препроцесору, який може також розкривати в тексті початкової програми скорочення, так звані макроси.
Цільова програма, створювана компілятором, може зажадати додаткову обробку перед запуском. Компілятор, створює асемблерний код, який переводиться асемблером в машинний код, а потім зв'язується («лінкуєтся») спільно з деякими бібліотечними програмами в код, що реально запускається на машині.
2. Формальний опис вхідної мови програмування
Одною з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких я використаю розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).
2.1 Деталізований опис вхідної мови в термінах EBNF
Нетермінальні вирази записуються у кутових дужках: “<”, “>” ;
Термінальні вирази записуються жирним шрифтом або у подвійних лапках;
Усі нетермінальні вирази мають бути “розкриті” за допомогою термінальних;
Символ “::=” відділяє праву частину правила від лівої;
символ “|” розділяє альтернативи;
символи “[”, “]” означають необов’язковість (вираз в дужках може бути відсутнім);
символи “{”, “}” означають повторення.
Таблиця 2.1 Деталізований опис вхідної мови
<program>
::= mainprogram start <declaration> {<statement >} end
<statement>
::= <label>: | <label>: <operator> {<label>: | <label>: <operator>}
<declaration>
::= data <var> <- <number>] {,<var> [<- <number>] } int_2;
<operator>
::= <assign> | <command>
<assign>
::= <var> <- <expression>;
<var>
::= _<letter_down> | {<letter_up> | <letter_down> | <digit>}
<label>
::= <letter_down> | {<letter_up> |<letter_down> | <digit>}
<letter_up>
::= A..Z
<letter_down>
::= a..z
<digit>
::= 0..9
<command>
::= <condition> | <input> | <output>;
<condition>
::= if <expression> goto <label>;
<number>
::= <digit> {<digit>}
<string>
::= “{<letter_up>|<letter_down>|<digit>}”
<input>
::= input <var>;
<output>
::= output <var> | <string> | <num> {,<var> | <string> | <num>};
<equality>
::= ne | eq
<comparison>
::= > | <
<addition>
::= add | sub
<multiplication>
::= * | / | %
<expression>
::= <atom> [{ or <atom> }]
<atom>
::= <eq> [{ and <eq> }]
<eq>
::= <comp> [{ <equality> <comp> }]
<comp>
::= <term> [{ <comparison> <term> }]
<term>
::= <mult> [{ <addition> <mult> }]
<mult>
::= <operand> [{ <multiplication> <operand> }]
<operand>
::= <var> | <number> | (<expression>) | !<var> | !<number> | !(<expression>)
2.2 Опис термінальних символів та ключових слів
Визначаємо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
mainprogram start end data ; add sub * / % : <- ne eq > < ! and or if goto ( ) , input output
До термінальних символів треба віднести також усі цифри (0..9), символ пробілу і табуляції. Це “цеглинки”, з яких має будуватися текст будь-якої вхідної програми.
Типи даних int_2;
Арифметичні операції над числами add, sub, /, *, %;
Логічні операції ne, eq, >, <,!, and, or;
Оператор присвоєння значень змінним <- ;
Круглі дужки ( );
Оператори вводу-виводу output, input;
Оператор оголошення змінних data;
Початок програми mainprogram;
Позначення початку і кінця блоку start та stop;
Умовний оператор if - goto;
3. Розробка транслятора вхідної мови
3.1 Вибір технології програмування
Технологією програмування було обране об’єктно-орієнтоване програмування На відміну від традиційних поглядів, коли програму розглядали як набір підпрограм, або як перелік інструкцій комп'ютеру, ООП програми можна вважати сукупністю об'єктів. Відповідно до парадигми об'єктно-орієнтованого програмування, кожний об'єкт здатний отримувати повідомлення, обробляти дані, та надсилати повідомлення іншим об'єктам. Кожен об'єкт – своєрідний незалежний автомат з окремим призначенням та відповідальністю.
Цільовою мовою програмування було обрано Microsoft C#. Дана мова програмування широко використовується для розв’язання задач різного рівня складності. Перевагами даної мови порівняно з іншими є широкий набір бібліотек класів для роботи з стрічками, регулярними виразами, файлами, різноманітними структурами даних: список, словник, стек, черга. Також дана мова забезпечує високу гнучкість і відносну простоту побудови користувацького інтерфейсу, взаємодії з файловою системою комп’ютера.
3.2 Проектування таблиць транслятора та вибір структур даних
Транслятор в даній роботі представлено класом Translator, який інкапсулює в собі дані та методи потрібні для роботи програми. До методів відноситься лексичний, синтаксичний аналізатор, генератор коду, методи для збереження проміжних даних у файл, процедури для перевірки операторів мови. До даних відносяться регулярні вирази для лексичного аналізу, таблиця змінних, таблиця міток, таблиця стрічок, таблиця помилок, таблиця лексем, таблиця результатів синтаксичного аналізу. Для зберігання таблиць обрано стандартну структуру даних список, так як вона дозволяє легко працювати з даними різного типу, підтримує індексацію (можна працювати так як з масивом), містить багато готових методів для пошуку вставки, заміни. Окремі складові елементи таблиці представлені кожна своїм класом.
Клас Token відповідає певній лексемі, містить інформацію про її місце розташування в тексті, унікальний номер лексеми, адресу в таблицях стрічок, змінних чи міток. Детальний опис полів і методів подано в таблиці 3.1.
Таблиця 3.1. Опис методів і полів класу Token
Клас містить наступні поля:
Lexem
поле задане перечисленням enum однзначно ідентифікує кожну лексему.
(див. таблицю 3.6)
Value
поле задає стрічку яка представляє лексему в тексті програми
Address
поле задає посилання та таблицю міток, ідентифікаторів, стрічок, якщо лексема має відповідний тип
Pos
поле задає положення лексеми в тексті програми
Клас містить наступні методи:
Token
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів
ToString
Метод для представлення лексеми в текстовому вигляді
Equals
Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.
Клас Identifier представляє кожну конкретну змінну в програмі. Містить методи для генерації асемблерного коду оголошення змінних, отримання унікального імені змінної для генератора коду. Детальний опис полів і методів подано в таблиці 3.2.
Таблиця 3.2. Опис методів і полів класу Identifier
Клас містить наступні поля:
Number
поле задає число яке початково записується в змінну при ініціалізації
Value
поле задає стрічку яка представляє ім’я змінної в тексті програми
IsInitialized
Поле містить істину якщо змінна ініціалізована початковим значенням і хибу якщо початкової ініціалізації немає
IsDeclared
Поле містить істину якщо змінна оголошена і хибу якщо не оголошена
Клас містить наступні методи:
Identifier
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів
ToString
Метод для представлення лексеми в текстовому вигляді
Equals
Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.
GetAsmName
Метод повертає стрічку яка представляє унікальне ім’я змінної для генератора коду. Базується на використанні хеш-функції.
GetAsmDef
Метод повертає стрічку яка представляє спеціальне оголошення змінної для побудови сегменту коду.
Клас TextLiteral представляє кожний конкретний текстовий літерал в програмі. Містить методи для генерації асемблерного коду оголошення літералу, отримання унікального імені літералу для генератора коду. Детальний опис полів і методів подано в таблиці 3.3.
Таблиця 3.3. Опис методів і полів класу TextLiteral
Клас містить наступні поля:
Value
поле задає стрічку яка представляє текст стрічки в програмі.
Клас містить наступні методи:
TextLiteral
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів.
Equals
Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.
GetAsmName
Метод повертає стрічку яка представляє унікальне ім’я літералу для генератора коду. Базується на використанні хеш-функції.
GetAsmDef
Метод повертає стрічку яка представляє спеціальне оголошення літералу для побудови сегменту коду.
Клас Label представляє кожну конкретну мітку. Містить методи для отримання унікального імені мітки для генератора коду. Детальний опис полів і методів подано в таблиці 3.4.
Таблиця 3.4. Опис методів і полів класу Label
Клас містить наступні поля:
Value
поле задає стрічку яка представляє ім’я мітки в програмі.
IsDeclared
Поле містить істину якщо мітка існує в коді і хибу якщо навпаки.
IsUsed
Поле містить істину якщо існує посилання на мітку в тексті вхідного коду і хибу якщо навпаки.
Клас містить наступні методи:
Label
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів.
Equals
Метод для порівняння двох міток за значеннями. Використовується для пошуку в стандартних структурах даних.
GetAsmName
Метод повертає стрічку яка представляє унікальне ім’я літералу для генератора коду. Базується на використанні хеш-функції.
ToString
Метод повертає стрічкове представлення об’єкту
Клас Error представляє кожну конкретну помилку. Містить методи для видачі текстових повідомлень про помилки. Детальний опис полів і методів подано в таблиці 3.5.
Таблиця 3.5. Опис методів і полів класу Error
Клас містить наступні поля:
Code
Поле представлене перечисленням для представлення коду помилки.
Pos1
Початкове положення помилки в тексті програми.
Pos2
Кінцеве положення помилки в тексті програми.
Клас містить наступні методи:
Error
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів.
Equals
Метод для порівняння двох міток за значеннями. Використовується для пошуку в стандартних структурах даних.
ToString
Метод повертає стрічкове представлення помилки в залежності від коду.
Перечислення Lexems представляє кожнен тип лексеми унікальним номером. В таблиці 3.6 подані усі існуючі типи лексем і означення до кожного типу.
Таблиця 3.6. Список усіх можливих лексем
Лексема
Означення
Лексема
Означення
Startblock
Початок блоку
Bigger
Більше ніж
Startprogram
Почакток програим
Fewer
Менше ніж
Var
Оголошення змінних
Not
Логічне Не
Endblock
Кінець блоку
And
Логічне І
Read
Оператор вводу
Or
Логічне АБО
Write
Оператор виводу
Assign
Оператор присвоювання
If
Оператор умови
Comma
Кома
Goto
Безумовний перехід
LBracket
Відкриваюча дужка
Error
Лексема помилкова
Equal
Ріно
Mod
Остача від ділення
Label
Мітка
NEqual
Не рівно
Whitespace
Пробільні символи
VarType
Тип даних
Variable
Змінна
Add
Додавання
Literal
Числовий літерал
Sub
Віднімання
String
Стрічковий літерал
Mul
Множення
Comment
Коментар
Semicolon
Крапка з комою
Colon
Двокрапка
RBracket
Закриваюча дужка
3.3 Розробка лексичного аналізатора
Лексичний аналізатор є першою фазою компілятора. Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів для передачі в синтаксичний аналізатор. Всі символи вхідної послідовності розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
3.3.1 Розробка граф-схеми алгоритму
Алгоритм лексичного аналізу базується на використанні засобів регулярних виразів. При цьому за допомогою регулярних виразів задаються правила виділення лексем, ідентифікаторів, міток з подальшим утворенням таблиці лексем і ідентифікаторів. Процес задання правил виділення лексем є достатньо простим і надзвичайно гнучким. Розбір виконується взалежності від правила виділення лексеми, заданого регулярним виразом, при чому ними можна виділити не лише базові одиниці мови, але й коментарі, пробільні символи і навіть лексичні помилки.
Рис. 1. Алгоритм лексичного аналізу.
3.3.2 Опис програми реалізації лексичного аналізатора
Для виділення лексем використовуються правила задані регулярними виразами. Вхідна програма проглядається послідовно з початку. Початок тексту аналізується на відповідність певному регулярному виразові (блоки 5, 6, 7, 8, 9). При співпадінні виділена лексема записується при необхідності в таблицю лексем, змінних, міток, стрічок чи генерується помилка і видаляється з початку тексту (блоки 10-20). Так повторюється доки вхідний текст не стане порожнім (блок 3).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись до лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо місця розташування відповідної лексеми у вхідному тексті (для локалізації місця помилки) та інша додаткова інформація.
При лексичному аналізі виявляються i відзначаються лексичні помилки (наприклад, недопустимі символи i неправильні iдентифiкатори). Лексична фаза відкидає також i коментарі, пробільні символи оскільки вони не мають ніякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
3.4 Розробка синтаксичного та семантичного аналізатора
Першим етапом синтаксичного аналізу є синтаксичний розбір. На етапі його виконання підтверджується то, що вхідний ланцюжок лексем є програмою, а окремі лексеми складають синтаксично правильні програмні об'єкти. Розбір призначений для перевірки того, чи ланцюжок відповідає певному правилу з сукупності правил визначеної граматикою. Синтаксичний розбір виконується методом рекурсивного спуску. Якщо на будь-якому рівні ланцюжок не відповідає ніякому правилу,то ми дістанемо помилку.
Основним завданням семантичного аналізатора є перевірка типів, ініціалізації змінних. Сама програма перевірки типів базується на інформації про синтаксичні конструкції мови, представлення типів і правилах присвоєння типів конструкціям мови.
3.4.1 Розробка граф-схеми алгоритму
Алгоритм синтаксичного аналізу використовує низхідний метод розбору. Для кожної конструкції мови розроблена певна процедура, яка і робить перевірку чи відповідає ланцюжок лексем певному правилу граматики. Також дані процедури формують проміжне представлення мовних конструкції для генератора коду. Спочатку перевіряється заголовок програми і розділ оголошення змінних, далі йде перевірка головного блоку і вкладених блоків. При неможливості спів ставити ланцюжок лексем певному правилу граматики генерується помилка.
Рис. 2. Алгоритм синтаксичного аналізу.
3.4.2 Опис програми реалізації синтаксичного та семантичного аналізатора
Для аналізу синтаксичний аналізатор отримує на вхід послідовність лексем сформовану лексичним аналізатором. Спочатку перевіряється заголовок програми (блок 2): початок головного блоку, розділ оголошення змінних, після цього відбувається перевірка коректності команд розміщених в головному блоці і вкладених блоках. Для кожної команди передбачена окрема процедура. Команди розпізнаються по черговій лексемі, відбувається зчитування ланцюжка лексем до крапки з комою. Прочитаний ланцюжок (блоки 3 - 18) передається на перевірку певній процедурі аналізу (блоки 7, 10, 14), яка проводить аналіз і при успішному завершенні формує проміжне представлення команди для генератора коду(блоки 15, 16, 17).
Проміжним представленням програми є списки лексем які представляють конкретні вирази, оператори, мітки. Вирази представлені зворотнім польським записом.
При знаходженні помилки в список помилок додається відповідний запис з інформацією про тип помилки і місце її локалізації в коді програми (блоки 11, 12, 13, 16). Список помилок є глобальним і доступним в будь-якому місці програми.
3.5 Розробка генератора коду
Генерація коду – це перетворення вхідної програми на деякій мові в еквівалентну програму на мові асемблер або у машинні коди. Проте, зважаючи на неможливість здійснити оцінку смислу вхідної програми загалом та існуючі обмеження мов програмування на етапі генерації коду ми ніколи не отримаємо на 100% еквівалентну програму мовою асемблер.
Генерація і оптимізація коду є завершальним етапом роботи компілятора чи транслятора. Вона виконується після виконання операцій лексичного, синтаксичного і семантичного аналізу, ідентифікації імен змінних і функцій, розподілу адресного простору для функцій і змінних.
3.5.1 Розробка граф-схеми алгоритму
Генерація коду є поетапним процесом, який відбувається на основі закінчених мовних конструкцій вхідної програми. Генератор вибирає закінчену синтаксичну конструкцію з тексту вхідної програми породжує для неї фрагмент результуючого коду і розміщує його в тексті результуючої програми. Далі береться наступна конструкція. Так відбуваться доти, доки не буде розібрана вся програма.
Рис. 3. Алгоритм генератора коду.
3.5.2 Опис програми реалізації генератора коду
Генерація коду відбувається поетапно. Генератор коду аналізує проміжне представлення (списки лексем) сформовані синтаксичним аналізом і генерує для них відповідний асемблерний код.
Спочатку генератор коду аналізує список ідентифікаторів і формує їхнє оголошення в сегменті даних (блоки 4, 6, 8). Далі відбувається подібна генерація машинного коду для списку стрічок (блоки 3, 5, 7). Після цього генератор формує заголовок машинного коду (блок 9). Далі зчитуються списки з проміжним представленням команд і формуються еквівалентні машинні інструкції (блоки 11, 13, 15). Далі в готовий асемблерний текст додаються сформовані машинні команди і код необхідних процедур (блоки 10, 12). Результати зберігаються у вихідний файл (блок 14).
Вихідна програма на машинній мові організована у вигляді готових процедур, кожна з яких відповідає за ввід/вивід результатів роботи, конкретну обчислювальну арифметичну чи логічну операцію, вивід повідомлення про помилки. Для обчислень використовується програмний стек, який представлений ділянкою пам’яті і зміщенням (вершина стеку). Даний метод має наступні переваги:
розмір стеку достатньо великий щоб уникнути помилок переповнення, як у випадку зі стеком математичного співпроцесора;
проста реалізація обчислень за допомогою готових процедур;
можливість виявлення помилок на етапі виконання:
ділення на нуль;
помилка ініціалізації змінної;
помилка переповнення;
помилка введення.
4. Опис інтерфейсу та інструкції користувача
Програма транслятор має простий інтерфейс SDI. Стандартне меню з командами збереження (Ctrl+S), відкриття (Ctrl+O), створення нового файлу (Ctrl+N). Також тут є меню з командами виконання всіх фаз трансляції і компіляції(F5). Меню довідки містить команду показу вікна з інформацією про програму. Головна робоча область складається з поля введення тексту і поля зі списком помилок.
Рис. 4. Середовище розробки мови s16.
Рис. 5. Користувацькі меню середовища розробки.
5. Відлагодження та тестування програми
Відлагодження програми відбувається в покроковому режимі в середовищі Microsoft Visual Studio 2010 з використанням точок зупинки, що дає можливість знайти місце логічної помилки. В покроковому режимі у нас є можливість прослідкувати за значеннями змінних.
Тестування програми буде відбуватися з допомогою готових прикладів на вхідній мові в яких можуть використовуватися різноманітні оператори вхідної мови, можуть бути допущені різноманітні лексичні, граматичні та синтаксичні помилки.
5.1 Виявлення лексичних помилок
На етапі лексичного аналізу виникають наступні помилки: Нерозпізнана лексема – це помилка яка може виникнути на етапі лексичного аналізу, коли лексема відповідає регулярному виразу лексичної помилки. Завеликий числовий літерал – це помилка яка може виникнути на етапі лексичного аналізу, коли числовий літерал є завеликим для типу INTEGR32. Знаходження повторної ініціалізації міток – це помилка яка може виникнути на етапі лексичного аналізу, коли однакова мітка є в різних місцях програми. Коли виникає будь-яка помилка, то вона записується в глобальний список помилок. Виявлені лексичні помилки виводяться в список помилок внизу робочої області (рис. 6).
#* dfg fdgdfg *#
mainprogram
start
data _I <- 0 int_2;
_I <- 999999999999;
Begin:
output "i = ",_I;
_I <- _I add 1;
if _I < 10 goto Begin;
end
Рис. 6 Виявлення лексичних помилок.
5.2 Виявлення синтаксичних помилок
На етапі синтаксичного аналізу виявляється основна кількість помилок. Ці помилки пов’язані з невірними записами конструкцій вхідної мови, незавершеність програми, неправильним форматом виразів. Всі помилки виявленні на етапі синтаксичного аналізу заносяться в таблицю помилок.
Для початку протестуємо наступний код в якому навмисно допущено різноманітні помилки. Як видно з (рис. 7) транслятор коректно виявляє різноманітні синтаксичні помилки.
#* dfg fdgdfg *#
mainprogram
start
data _I <- 0,_I int_2;
_II <-0;
Begin:
Begin:
output "i = ",_I;
_I <- _I add 1;
if _I < 10 goto Begin;
end
Рис. 7. Програма з багатьма помилками
5.3 Виявлення семантичних помилок
Основною метою семантичного аналізу є перевірка типів операндів. Оскільки згідно варіанту присутній тільки один тип longint, то така перевірка не буде проводитися. Виявлення семантичних помилок зводиться до перевірки того, чи змінні ініціалізовані початковими значеннями. Ця перевірка виконується на етапі виконання. Це досягається наявність додаткової інформації про ініціалізацію в сегменті коду. При виникненні такої помилки видасться повідомлення про помилку, виконання програми завершиться і вона поверне одиницю.
Синтаксично слідуючий код правильний, проте в ньму допущена семантична помилка: змінній і присвоюється неініціалізована змінна tmp, тому на етапі виконання згенерується помилка (рис. 8).
#* dfg fdgdfg *#
mainprogram
start
data _I <- 0, _II int_2;
_I <- _II;
end
Рис. 8. Виявлення помилок ініціалізації.
Схожим чином відбувається перевірка на деякі інші типи помилок. Наприклад помилка ділення на нуль. В наступному прикладі змінна tmp ділиться на нуль, тому генерується помилка.
#* dfg fdgdfg *#
mainprogram
start
data _I <- 0 int_2;
_I <- 999 / 0;
end
Рис. 9. Виявлення помилок виконання.
5.4. Загальна перевірка коректності роботи транслятора
Загальна перевірка коректності роботи транслятора полягає в транслюванні коректної вхідної програми з використанням всіх можливостей мови в асемблерний код та перевірці на правильність виконання програми, яку потрібно попередньо скомпілювати і транслювати за допомогою ml.exe
Висновки
В процесі виконання курсової роботи було виконано наступне: Складено формальний опис мови програмування s36, в термінах розширеної нотації Бекуса-Наура, виділено усі термінальні символи та ключові слова. Створено транслятор мови програмування s36, а саме:
Розроблено лексичний аналізатор, який виявляє лексичні помилки , та на виході дає таблицю лексем таблицю ідентифікаторів, з якими потім працює синтаксично-семантичний аналізатор. Розроблено синтаксичний та семантичний аналізатор, який виявляє синтаксичні та семантичні помилки на етапі аналізу та виконання, та на виході будує проміжне представлення, яке потім використовує генератор коду. Розроблено генератор коду, який генерує код, записаної нами програми на заданій мові програмування , у програму на мові асемблера . На виході ми отримуємо файл на мові асемблера , з якого ми отримаємо виконавчий файл, за допомогою ml i link.
Проведене тестування транслятора на тестових програмах за наступними пунктами:
На виявлення лексичних помилок.
На виявлення синтаксичних помилок.
Загальна перевірка роботи компілятора.
Тестування виявило деякі помилки в роботі транслятора , які були успішно усунуті. В результаті виконання даної курсової роботи було успішно засвоєно методи розробки та реалізації компонент системного програмування.
Список літератури
Хантер Р. Проектирование и конструирование компиляторов. – М.: Финансы и статистика, 1984. – 232 с.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. – М.: Мир, 1978. – т.1, 612 с.
Серебряков В.А. Лекции по конструированию компиляторов. – М.: МГУ, 1993.
Н.Г.Голубь “Исскуство программирования на ассемблере. Лекции и упражнения”. –Киев “DiaSoft”, 2002 – 642с.
Л.Бэк “Введение в системное програмирование”. – М.: Мир, 1999
Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир. 1975. - 554 с.
Шильдт Г. С#. – Санкт-Петербург: BXV, 2007. – 688 с.
Додаток А: Завдання на курсову роботу
Розробити транслятор заданої вхідної мови програмування, до якої висуваються наступні вимоги:
Кожна програма починається зі слова mainprogram і закінчується словом stop. Після mainprogram йде оператор головного блоку start і розділ оголошення змінних, кожен блок завершується ключовим словом stop. Наприклад як у мові Паскаль begin end. Програма має надавати можливість працювати зі змінними таких типів: int_2 – цілі числа. Змінні перед використанням мають бути попередньо оголошені та ініціалізовані, в іншому випадку генерується помилка на етапі трансляції чи на етапі виконаня. Регістр ключових слів і ідентифікаторів нижній. Довжина ідентифікаторів не повинна бути більшою за вісім символів.
Присвоєння змінних виконується оператором присвоєння <-.
Над змінними виконуються наступні операції.
Арифметичні: add, sub, *, /, % додавання, віднімання, ділення, множення, остача від ділення;
Логічні: !, and or логічні операції NOT, AND, OR.
Порівняння: ==, !=, >, < рівність, нерівність, більше, менше;
Ввід даних зі стандартного вводу відбувається оператором input, а вивід
13.05.2013 21:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора