Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмування.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
О
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2017
Тип роботи:
Інші
Предмет:
Системне програмування
Частина тексту файла (без зображень, графіків і формул):
ДЮЛЛЛМІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Пояснювальна записка
до курсової роботи з дисципліни: "Системне програмування"
На тему : «Розробка системних програмних модулів та компонент систем програмування.»
Індивідуальне завдання: “Розробка транслятора з вхідної мови програмування”
Львів – 2017
Анотація
Виконання курсової роботи полягає в розробці транслятора з вхідної мови програмування, яка задана варіантом, на мову асемблер, з подальшою компіляцією і створенням виконавчого файлу. Здійснюючи трансляцію, транслятор послідовно виконує такі фази роботи: лексичний аналіз, синтаксичний аналіз, генерація коду. Лексичний аналізатор створений на базі скінченного автомата, а синтаксичний аналізатор на основі висхідного методу з використанням з LR-граматики.
Qt (варіант вимови від розробників cute – к'ют) – крос-платформовий інструментарій розробки програмного забезпечення (ПЗ) мовою програмування C++, лістинг програми наведений у додатку А. Також у курсовій роботі наведено граф-схеми роботи лексичного і синтаксичного аналізаторів, генератора коду, детальний опис мови, описано процес розробки програми транслятора на рівні тексту програми.
До проекту додано результати тестування програми та текст програми транслятора.
Зміст
Анотація 2
Завдання на курсову роботу 4
Вступ 5
1.Огляд методів та способів проектування трансляторів 6
2.Формальний опис вхідної мови програмування 7
2.1.Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура 8
2.2. Термінальні символи та ключові слова 9
3.Розробка транслятора вхідної мови програмування 11
3.1.Вибір технології програмування 11
3.1.Проектування таблиць транслятора 11
3.3. Розробка лексичного аналізатора 14
3.3.1.Розробка граф-схеми алгоритму 15
3.3.2. Опис програми реалізації лексичного аналізатора 16
3.4.Розробка синтаксичного та семантичного аналізатора 17
3.4.1.Розробка дерева граматичного розбору 17
3.4.2.Розробка граф-схеми алгоритму 18
3.4.3. Опис програми реалізації синтаксичного та семантичного аналізатора 19
3.5.Розробка генератора коду 20
3.5.1. Розробка граф-схеми алгоритму 20
3.5.2. Опис програми реалізації генератора коду 20
4.Опис інтерфейсу та інструкції користувачеві 22
5. Відлагодження та тестування програми 23
5.1. Виявлення лексичних помилок 23
5.2. Виявлення синтаксичних помилок 24
5.3. Виявлення семантичних помилок 24
5.4. Загальна перевірка коректності роботи транслятора 25
Висновки 29
Список літератури 30
Додатки 31
Завдання на курсову роботу
1. Цільова мова транслятора асемблер (iх86).
2. Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами tasm.exe і tlink.exe або tasm32.exe і tlink32.exe.
3. Мова розробки транслятора: ANSI C або C++.
4. На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
5. На виході розробленого транслятора мають створюватись чотири файли:
файл з повідомленнями про помилки (або про їх відсутність);
файл на мові асемблера;
об’єктний файл;
виконавчий файл.
6. Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування.
Варіант 129:
Розробити транслятор вхідної мови програмування, короткий опис якої подано нижче:
блок тіла програми: Program <name>; Start Var…; Finish;
оператор вводу: Scan;
оператор виводу: Print;
оператор присвоєння: -> ;
оператор: If – go to – go to (Паскаль);
регістр ключових слів: Low ;
регістр індентифікаторів: Up-Low6 перший символ Up ;
арефметичні операції: +; -; Mul; Div; Mod;
операції порівняння: eq; noteq; less; gr ;
логічні операції: !!; &&; || ;
типи даних: int ;
Вступ
Компілятор (англ. Compiler від англ. to compile збирати в ціле) - комп'ютерна програма , що перетворює (компілює) програмний код, написаний певною мовою програмування, на семантично еквівалентний код в іншій мові програмування, який, як правило, необхідний для виконання програми машиною. Одна з важливих ролей компілятора є повідомленні про помилки у вихідній програмі, виявлених в процесі трансляції.
Транслятор – це той самий компілятор, з тією різницею, що генерує він не об’єктний код, а код на іншій мові програмування.
Якщо розглянути процес компіляції більш детально, можна побачити, що він являє собою послідовність фаз, кожна з яких перетворює одне з представлень вихідної програми в інше. На практиці деякі фази можуть об’єднуватися, а міжфазне представлення може не будуватися ясно.
Проблема трансляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою транслятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього він має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати код.
Метою даної курсової роботи є розробка компілятора мови програмування k129, створення прямого лексичного аналізатора, орієнтованого на розпізнавання лексем, що є визначені у формальному описі мови, синтаксичного аналізатора, генератора коду та складання деталізованого опису вхідної мови в термінах розширеної нотації Бекуса-Наура. Провести тестування компілятора на виявлення лексичних, синтаксичних і семантичних помилок, а також загальну перевірку коректності роботи.
1.Огляд методів та способів проектування трансляторів
Транслятором називається програма перекладу (трансляції) початкової програми, записаної вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна - вихідною, то такий транслятор називається компілятором.
Створення компіляторів відбувається в певних конкретних умовах: для різних мов, для різних цільових платформ, з різними вимогами для створення компіляторів. Є такі методи створення компіляторів:
прямий метод- цільовою мовою і мовою реалізації є асемблер;
метод розкрути;
використання крос-трансляторів;
з використанням віртуальних машин ;
компіляція на ходу.
Метод розкрутки – це метод створення транслятора для деякої мови програмування, при якому транслятор пишеться на тій же мові програмування, для трансляції якого він створюється. Суть цього методу полягає в наступному: Припустимо у нас є компілятор KA: P -> A, де P – деяка мова більш високого рівня, ніж мова асемблера. Тоді напишемо KP: L->A, а потім застосуємо компілятор КA до компілятора KP, тобто получимо KA= KA(KP): L ->A.
Крос-транслятор – компілятор, який працює на одній платформі і створює код для іншої платформи. Нехай у нас є два є два комп’ютера: комп’ютер М з мовою асемблера А і комп’ютер М1 з мовою асемблера А1. Крім того, припустимо, що наявний компілятор КА1 : L -> А, а сам комп’ютер М по якихось причинам не доступний або ще не існує компілятор КА : P -> A. Нас цікавить компілятор КА: L -> A. В такій ситуації ми можемо використовувати М1 в якості інструментальної машини і написати компілятор КР : L -> A, який прийнято називати крос-транслятором. Як тільки машина М стане доступною, ми зможемо перенести КР на М і “розкрутити” його за допомогою КА. Зрозуміло, що це рішення є достатньо трудоємнісне, оскільки можуть виникнути проблеми при переносі, наприклад, із-за відмінностей операційних систем.
Другий спосіб получення переносимої (portable) об’єктної програми пов'язаний з використанням віртуальних машин. При такому підході вихідна мова транслюється в код деякої спеціально розробленої машини, яку ніхто не збирається реалізовувати “в жалізо”. Потім для кожної цільової платформи пишеться інтерпретатор віртуальної машини.
Зрозуміло, що архітектура віртуальної машини повинна бути розроблена таким чином, щоб конструкції вихідної мови зручно відображалися в систему команд і сама система команд не була занадто складною. При виконанні цих умов можна досить швидко написати інтерпретатор віртуальної машини.
Основна неприємність, пов’язана з використанням віртуальних машин, полягає в тому, що звичайно час виконання інтерпретуючої програми значно більший, ніж час роботи програми відтрансльованої в “рідний” машинний код. Для того, щоб збільшити швидкість роботи програми, була розроблена технологія компіляції “на ходу”. Ідея полягає в тому, что JIT-компілятор генерує машинний код прямо в оперативній пам’яті, не зберігаючи його. Це призводить до значного збільшення швидкості виконання програми.
Методи граматичного розбору розбиваються на два великих класи: висхідні та низхідні. Висхідні (методи знизу-вверх) починають з елементів пропозиції (з “листя” ) і відшукують у граматиці якому поняттю вони відповідають, тобто визначають батьківську вершину для цих елементів, і т.д поки не приходять до кореня дерева (аксіоми граматики). У сучасних компіляторах застосовуються як низхідні, так і висхідні методи.
В даній курсовій роботі необхідно реалізувати висхідний метод граматичного розбору. Вагомою перевагою висхідного методу є його універсальність. Головним недоліком вважається складність реалізації.
2.Формальний опис вхідної мови програмування
Однією з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких я застосував розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).
Форма Бе́куса-Нау́ра (англ. Backus-Naur form, BNF) - це спосіб запису правил контекстно-вільної граматики, тобто це форма опису формальної мови. Саме її типово використовують для запису правил мов програмування та протоколів комунікації.
Формули БНФ складаються з наступних мета символів:
< – лівий обмежувач;
правий обмежувач;
-> – визначено як;
| – або;
“ ” — текстовий елемент (символ або група символів).
Розширені формули Бе́куса-Нау́ра використовують додаткові мета символи:
[] – елемент у дужках входить або не входить (є необов’язковим);
() – групування елементів у дужках;
{} – нуль або більше повторень елементів розташованих у дужках;
(* – початок блоку коментарів;
*) – кінець блоку коментарів.
Формули БНФ оперують термінальними і нетермінальними символами. Нетермінальні символи – це символи які введені для визначення “правил продукції”. Вони поміщаються в трикутні дужки: <цифра>. Натомість термінальні символи представляють лексеми або їх складові частини: 0,1,2,А,В,с,;,*,/,-,+.
2.1.Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
<програма>->Program<iм’я>Start Var<блок змінних><блок коду>Finish
< iм’я >-><велика буква>{<буква чи цифра>}
<буква чи цифра>-><мала буква>|<цифра>
<мала буква>->a|b|c|d|e|f|g|h|i|j|n|m|o|p|q|r|s|t|u|v|w|x|y|z
<велика буква>->A|B|C|D|E|F|G|H|I|J|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z
<цифра>->0|1|2|3|4|5|6|7|8|9
<блок змінних>-><пусто>|start variable<оголошення>{;<оголошення>};
<оголошення>-><тип><змінна>{,<змінна >}
<тип>->int
<змінна>-><назва змінної>
<назва змінної>-><велика буква>{<буква чи цифра>}6
<блок коду>->{<простий оператор>|<оператор вводу>|<оператор виводу>|<цикл>}
<цикл>->If(<змінна>|<цифра><порівняння><змінна>|<число>|<порожній оператор> go to
<порівняння>-> =|<>|!>|!<
<простий оператор>-><порожній оператор>|<оператор присвоєння>
<порожній оператор-> <пусто>
<оператор присвоєння>-><змінна>::=<вираз>
<вираз>-><операнд1><логічна операція><операнд1>|(<вираз>) <логічна операція><операнд1>|<операнд1><логічна операція>(<вираз>) | (<вираз>)
<логічна операція>(<вираз>)|<операнд1>
<логічна операція>->!! | && | ||
<операнд1>-><операнд2><адитивна операція><операнд2>|(<вираз>)
<адитивна операція><операнд2>|<операнд2>|<адитивна операція>
(<вираз>)|(<вираз>)<адитивна операція>(<вираз>)|<операнд2>
<адитивна операція> -> +|-
<операнд2> -> <операнд3><мультиплікативна операція><операнд4>|
(<вираз>) <мультиплікативна операція><операнд4>|<мультиплікативна операція>(<вираз>)|(<вираз>)< мультиплікативна операція >(<вираз>)|
<операнд3>
<мультиплікативна операція> -> Mul|Div|Mod
<оператор виводу> -> scan(<рядок>|<змінна>{,<рядок>|<змінна>});
<оператор вводу > -> print (<змінна>{,<змінна>});
<рядок > -> ”{<буква>|<цифра>}” .
2.2. Термінальні символи та ключові слова
Визначимо окремі термінальні символи та нерозривні набори нетермінальних символів (ключові слова):
Таб.2.1.Таблиця термінальних символів і ключових слів
Термінальний символ або ключове слово
Значення
Program
початок тексту програми
Start Var
блок опису змінних
Scan
оператор вводу
Print
оператор виводу
If
початок умовного оператора
Go to
кінець умовного оператора
->
оператор присвоєння
+
операція додавання
-
Операція віднімання
Mul
операція множення
Div
операція ділення
Mod
знаходження залишку від ділення
=
перевірка на рівність
<>
перевірка на нерівність
!>
перевірка чи менше
!>
перевірка чи більше-рівно
!!
операція логічного заперечення
&&
кон’юнкція
||
диз’юнкція
int
16-ох бітові знакові цілі
!!
рядковий коментар
;
ознака кінця оператора
( , )
відкриваюча і закриваюча дужка
Як термінальні символи використовуються також усі арабські цифри (0–9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл.
3.Розробка транслятора вхідної мови програмування
3.1.Вибір технології програмування
Для виконання курсової роботи була вибрана об’єктно-орієнтована технологія програмування. Обєктно орієнтоване програмування (надалі ООП) – парадигма програмування, в якій основними концепціями є поняття об'єктів і класів.
Тому при складанні транслятора треба брати до уваги швидкість компіляції, якість об’єктної програми. Проект повинен давати можливість просто вносити зміни.
Тому при складанні транслятора треба брати до уваги швидкість компіляції, якість об’єктної програми. Проект повинен давати можливість просто вносити зміни.
Клас – це тип, що описує будову об'єктів. Поняття "клас" має на увазі деяка поведінка і спосіб представлення. Поняття "об'єкт" має на увазі щось, що має певну поведінку і спосіб представлення. Говорять, що об'єкт – це екземпляр класу. Клас можна порівняти з кресленням, згідн о з яким створюються об'єкти. Зазвичай класи розробляють так, щоб їх об'єкти відповідали об'єктам предметної області.
Qt (варіант вимови від розробників cute – к'ют) – крос-платформовий інструментарій розробки програмного забезпечення (ПЗ) мовою програмування C++. Дозволяє запускати написане за його допомогою ПЗ на більшості сучасних операційних систем (ОС), просто компілюючи текст програми для кожної операційної системи без зміни серцевого коду. Містить всі основні класи, які можуть бути потрібні для розробки прикладного програмного забезпечення, починаючи з елементів графічного інтерфейсу й закінчуючи класами для роботи з мережею, базами даних, OpenGL, SVG і XML. Бібліотека дозволяє керувати нитями, працювати з мережею та забезпечує крос-платформовий доступ до файлів.
3.1.Проектування таблиць транслятора
Лексичний аналізатор буде працювати паралельно синтаксичному , тобто синтаксичний аналізатор буде звертатись до лексичного, щоб той повернув наступний токен. Для його реалізація мені потрібні таблиця ключовий, клас Token – об’єкт якого містить тип лексеми, клас Word – наслідує Token і доповнює полем ім’я лексеми ( це потрібно для створення таблиці ключовий слів та ідентифікаторів ), клас String - наслідує Token і доповнює полем для збереження константного рядка, клас Num - наслідує Token і доповнює полем для збереження числової константи.
class Token {
public :
Token(int t =0):tag(t){}
QString toString(){
return ""+ QString::number(tag);
}
Token& operator=(const Token& tok){
this->tag=tok.tag;
return *this ;
}
int tag ;
};
class Num : public Token{
public :
const int value ;
Num(int v ):Token(NUM),value(v){}
QString toString(){
return QString::number(value) ;
}
};
class String : public Token{
public :
QString text ;
String(QString t ):Token(STRING),text(t){}
QString toString(){
return ""+ text ;
}
};
Таблиця ключовий слів – це хеш таблиця (ім’я –ключ , значення – тип токену ) в якій вже збережені ключові слова. Формується вона за допомогою фукції reserve(). Наприклад:
reserve (new Word ("Program", PROGRAM));
reserve (new Word ("Startvar", STARTVAR));
reserve (new Word ("finish", FINISH));
reserve (new Word ("Scan", SCAN));
reserve (new Word ("Print", PRINT));
reserve (new Word ("int", INT));
reserve (new Word ("go to", GO TO));
reserve (new Word ("if", IF));
reserve (new Word ("<>", NOTEQ));
reserve (new Word ("=", EQ));
reserve (new Word ("!>", LESS));
reserve (new Word ("!<", GR));
Атрибути лексем використовуються при синтаксичному аналізі. Лексеми мають наступні коди:
Таб.3.1 Відповідність атрибутів з їхніми кодами
Клас лексеми
Атрибут
Код атрибута
Числова константа
num
256
Лексема оголошення
id
257
Оператор циклу
do
258
Лексема оголошення
int
259
Оператор порівняння
=
260
Оператор порівняння
<>
261
Оператор порівняння
!>
262
Оператор порівняння
!>
263
Оператор виводу
Print
264
Ключове слово
Startvar
265
Ключове слово
Program
266
Ключове слово
Finish
267
Оператор вводу
Scan
268
Рядкова константа
String
269
Неопізнана лексема
Unidentified
270
Коди всіх інший однобайтових символів відповідають таблиці ASCII.
3.3. Розробка лексичного аналізатора
Лексичний аналіз - це процес перетворення послідовності символів в послідовність токенів (груп символів що відповідають певним шаблонам), та визначення їх типів. Програма, чи функція що виконує лексичний аналіз, називається лексичним аналізатором, чи сканером. Часто сканер є звичайною функцію що використовується парсером (синтаксичним аналізатором), для отримання наступного токена з потоку вхідних символів в процесі компіляції.
З кожною лексемою зв’язано два поняття:
Клас лексеми, що визначає загальну назву для категорії елементів, що мають спільні властивості (наприклад, ідентифікатор, ціле число, рядок символів і т. д.).
Значення лексеми, що визначає підрядок символів вхідного ланцюга, що відповідають розпізнаному класу лексеми. В залежності від класу, значення лексеми може бути перетворено у внутрішнє представлення вже на етапі лексичного аналізу. Так, наприклад, роблять з числами, перетворюючи їх в машинне двійкове представлення, що забезпечує більш компактне зберігання і перевірку правильності діапазону на ранній стадії аналізу.
3.3.1.Розробка граф-схеми алгоритму
Лексичний аналізатор починає свою роботу з блоку 1. Далі відривається вхідний файл у блоці 2. Наступні блоки оформлені у вигляді циклу. Виконується перевірка на кінець файлу у блоці 3. Якщо файл закінчився або виникла помилка, то лексичний аналізатор закінчує свою роботу у блоці 14.
Блок 4 виділяє перший символ нової лексеми. У блоках 4,5,6,7 перевіряється відповідність лексеми до типу.
У блоках 9,10,11 та 12 відбувається обробка лексеми та перехід до перевірки наявності наступної.
У блоці 13 формується повідомлення про помилку та перехід до завершення роботи лексичного аналізатора.
Рис 3.1.Граф-схема роботи лексичного аналізатора
3.3.2. Опис програми реалізації лексичного аналізатора
Нижче будуть приведені фрагменти коду лексичного аналізатора та коментарі, для пояснення його роботи.
Таб.3.2.Опис програми роботи лексичного аналізатора
Фрагмент коду
Коментар
void Readch(){
if(column < text.length()){
peek = text.at(column);
++column;}
else peek='\0';
}
Це функція, яка зчитує наступний символ з вхідного текста, поки змінна column менша за довжину вхідного текста, і записує його в зміну peek.
Token* Scan(){
if(inMarks==1){
QString temp;
while (peek!='"') {
temp+=peek;
if(peek=='\n')++line;
readch(); }
peek=' ';
--column;
inMarks=2;
return new String(temp);
}
Це основна функція лексичного аналізатора, яка сканує текст, визначає лексеми і повертає їх.
Цей фрагмент коду опрацьовує випадок, коли лапки відкриті. Він працює наступним чином – поки наступним символом не будуть лапки символи будуть записуватись в змінну. Після цього буфер для символу очиститься і повернеться вказівник на об’єкт типу String, в якому буде знаходитись рядкова константа.
for(;;Readch()){
if(peek==' '||peek=='\t')continue;
else if (peek=='\n') ++line;
else break; }
Цей фрагмент коду пропускає пробіли, символи табуляції та інкрементує змінну line при переході на наступний рядок.
if(peek.isLetter()) {
QString s ;
bool check=true;
do {
s.append(peek);Readch();
}while (peek.isLetter() || peek.isNumber());
if(s=="Int"){
if (peek =='_' &&readch('4'))
return new Word("int",INT);
else {column-=2;s.chop(2);} }
const Word * w =&words.value(s); }
Функція зчитує літери в буфер, якщо буфер рівний «Int», то перевіряються наступні символи, чи дорівнюють вони «_4». Якщо так, то повертає Word("Int_2", INT_2), інакше перевіряє послідовність символів буфера, чи вони є ключовим словом та повертає об’єкт типу Word.
3.4.Розробка синтаксичного та семантичного аналізатора
Синтаксичний розбір (розпізнавання) є першим етапом синтаксичного аналізу. Саме при його виконанні здійснюється підтвердження того, що вхідний ланцюжок символів є програмою, а окремі підланцюжки складають синтаксично правильні програмні об'єкти. Вслід за розпізнаванням окремих підланцюжків здійснюється аналіз їх семантичної коректності на основі накопиченої інформації. Потім проводиться додавання нових об'єктів в об'єктну модель програми або в проміжне представлення.
Розбір призначений для доказу того, що аналізований вхідний ланцюжок, записаний на вхідній стрічці, належить або не належить безлічі ланцюжків породжуваних граматикою даної мови. Виконання синтаксичного розбору здійснюється розпізнавачами, тому даний процес також називається розпізнаванням вхідного ланцюжка. Мета доказу в тому, щоб відповісти на питання: чи належить аналізований ланцюжок безлічі правильних ланцюжків заданої мови. Відповідь «так» дається, якщо така приналежність встановлена. Інакше дається відповідь «ні». Отримання відповіді «ні» пов'язано з поняттям відмови. Єдина відмова на будь-якому рівні веде до загальної відмови.
Основною задачею семантичного аналізатора є ідентифікація імен. При розпізнавання конструкції декларуванні(оголошенні) імені, програма зберігає інформацію про об’єкт в таблиці ідентифікаторів.
3.4.1.Розробка дерева граматичного розбору
Нисхідний метод полягає в побудові дерева розбору, починаючи від кореневої вершини. Розбір полягає в заповненні проміжку між початковим нетерміналом і символами вхідного ланцюжка правилами, виведеними з початкового нетермінала. Підстановка ґрунтується на тім факторі, що коренева вершина є вузлом, що складається з листів, що є ланцюжком терміналів і нетерміналів одного з альтернативних правил, породжуваних початковим нетерміналом. Правило, що підставляється, у загальному випадку обирається довільно. Замість нових нетермінальних вершин здійснюється підстановка виведених з них правил. Процес протікає доти, поки не будуть установлені всі зв'язки дерева, що з'єднують кореневу вершину і символи вхідного ланцюжка, чи поки не будуть перебрані всі можливі комбінації правил. В останньому випадку вхідний ланцюжок відкидається. Побудова дерева розбору підтверджує приналежність вхідного ланцюжка даній мові.
Рис 3.2.Дерево граматичного розбору
3.4.2.Розробка граф-схеми алгоритму
Синтаксичний аналізатор починає роботу з блоку 1. Далі йду перевірка чи є наступна лексема. Якщо нема, або виникає помилка, то синтаксичний аналізатор завершує свою роботу у блоці 22. Якщо наступна лексема наявна, то він вибирає у блоці 3 та порівнює з ключовими словами блоків коду у блоках 4,6,8,9,10,11,13,15 та 17. У блоках 5,7,9,12,14,16,18 та 20 йде перевірка наступних лексем. Якщо не було жодного співпадіння, то генерується повідомлення про помилку в блоці 21.
Рис 3.3.Граф-схема роботи синтаксичного аналізатора
3.4.3. Опис програми реалізації синтаксичного та семантичного аналізатора
Синтаксичний і семантичний аналізатори поєднані і реалізовується класом Parser . При побудові використовується LR(3)-граматика і LR(3)-аналізатор який розпізнає цю граматику.
LR(3)-аналізатор С це висхідний алгоритм синтаксичного розбору (англ. Bottom-up parsing). Цифра 3 говорить, що для визначення шляху розбору потрібно не більше трьох лексем (англ. k-token lookahead).
В цьому класі присутні наступні властивості:
Таб.4.Опис програми роботи синтакчисного та семантичного аналізатора
Властивість
Коментар
QVector <short> codeIn;
Вектор (контейнер) для проміжного коду команди.
QVector <QString> paramIn;
Вектор (контейнер) для параметрів .
Token* look;
Змінна для зберігання токена повернутого лексичним аналізатора.
QVector <Token*> table;
Таблиця для зберігання токенів.
QStack <int> place;
Сюди буде збережена остання операція цикла, щоб виконати її після блоку цикла.
QStack <id> id_table;
Таблиця для зберігання ідентифікаторів, які ми вже перевірили в хеш-таблиці після декларації.
jmp_buf jumpBuffer;
Буфер для виконання далекого стрибка при знаходженні помилки.
QVector <int> line;
Вектор для зберігання змінної знайденної в блоці операторів.
QHash <QString,Id> name_table;
Таблиця для зберігання ідентифікаторів.
Якщо синтаксичний аналізатор виявить помилку, він відішле сигнал, що сталася помилка, а обробник сигналу виведе його на екран. Після того робота синтаксичного аналіза зупиниться.
3.5.Розробка генератора коду
Генерація коду – це машинно-залежний етап компіляції, під час якого відбувається побудова машинного еквівалента вхідної програми. Зазвичай входом для генератора коду служить проміжна форма представлення програми, а на виході може з’являтися об’єктний код або модуль завантаження.
3.5.1. Розробка граф-схеми алгоритму
Оскільки синтаксичний аналізатор працює паралельно з генератором коду то граф-схема генератора коду така ж як і синтаксичного аналізатора (рис.3.3).
3.5.2. Опис програми реалізації генератора коду
В даному трансляторі генератор коду послідовно викликає окремі функції, які записують у вихідний файл частини коду. Для кожного ланцюжка вхідної мови існує окрема функція, яка враховуючи послідовність лексем створює відповідний вихідний код.
Табл 3.5 . Пояснення коду
Фрагмент коду
Коментар
void Generator::generate()
Це функція, яка аналізує коди команд і викликає відповідні фукції.
void Generator::Scan(QString & variable , bool state )
{ variable.chop(1);
output.append("push offset "+variable+' \n');
if(state) output.append("push offset inp1 \n");
else output.append("push offset inp2 \n");
output.append("call scanf \n");}
Це функція, яка генерує код для виводу змінної. Аргументами є ім’я змінної та її тип (state = 0 – цілий тип, state = 1 – рядковий тип).
void Generator::Print(QString &variable, short state)
Ця функція формує асемблерний код для оператора print. Аргументами є ім’я змінної та її тип (state = 0 – цілий тип, state = 1 – рядковий тип).
void Generator::decl(QString &variable, bool state)
Ця функція формує асемблерний код для декларації змінних.
void Generator::for_gen(QString &expr)
Ця функція формує асемблерний код для оператора циклу.
4.Опис інтерфейсу та інструкції користувачеві
Створений компілятор є програмою з графічною оболонкою. Програма містить редактор тексту, а також транслятор. Він може запускатися таким способом:
За допомогою виконавчого файла test_kursova.exe. Після його запуску відкриється вікно програми і текстовий редактор готовий до вводу програми.
Інструкція для користувача:
1. Після введення потрібної програми у текстовий редактор, потрібно зберегти файл з розширенням *.k129 у папку з masm32. Це можна виконати за допомого кнопки Save As.
2. Наступним кроком потрібно перевірити задану програму на наявність помилок. Для цього потрібно нажати кнопку – Parsing.
3. Якщо немає жодних помилок, потрібно згенерувати асемблерний файл за допомогою кнопки – Generator.
4. Далі послідово асемблювати та лінкувати за допомою кнопок – Assembly і Link – відповідно.
5.Запуск – за допомогою комбінації клавіш Ctrl+R або в Run->run.
Також в редакторі присутні наступні функції:
Ведення і редагування тексту;
Відкриття нового файл(Ctrl+O);
Збереження файлу(Ctrl+S);
Закриття програми(Ctrl+Q);
5. Відлагодження та тестування програми
Відлагодження програми відбувається на основі спеціально створених тестів за допомогою автоматизованого відлагоджувача який присутній в середовищі Qt Creator, в покроковому режимі перевіряється значення потрібних змінних і вмістиме потрібних структур даних. За допомогою breakpoints відбувається зупинка виконання програми в тих місцях де відбулася логічна помилка або в місцях визначених студентом.
5.1. Виявлення лексичних помилок
До помилок виявлених на етапі лексичного аналізу відносить тільки одна помилка – виявлення нерозпізнаної лексеми. Якщо було виявлено нерозпізнану лексему – в таблицю лексем заноситься поле з коментарем «Нерозпізнана лексема», і їй присвоюється код -1, і на етапі синтаксичного аналізу буде згенерована помилка пов’язана з цією лексемою.
Приклад виявлення:
Текст програми з лексичними помилками:
#Proram <DSFG>;
Start Var
[
Int A,B;
];
[
Scan(A,B);
Print("test=",A);
] Finish
Текст повідомлення про лексичні помилки:
line:1:Program
Дійсно допущена помилка у строці 1 в ключовому слові Program.
5.2. Виявлення синтаксичних помилок
На етапі синтаксичного аналізу виявляється основна кількість помилок. Ці помилки пов’язані з невірними записами конструкцій вхідної мови. Всі помилки виявленні на етапі синтаксичного аналізу заносяться в таблицю помилок. Таблиця помилок містить лексему яка спричинила помилку, коментар і рядок в якому виникла помилка.
Приклад виявлення:
Текст програми з синтаксичними помилками:
#Program <DSFG>;
Start Var
[Int A,D;
;
[
Scan(A,D);
A -> A Mul D
Print("A=",A);
] Finish
Текст повідомлення про помилки:
line:4:forbiten symbol
Дійсно, допущена помилка у строкці 4, не закриті дужки.
5.3. Виявлення семантичних помилок
Суттю виявлення семантичних помилок є перевірка числових констант на відповідність типу int_2, тобто цілому числу з відповідним діапазоном значень і перевірку чи всі ідентифікатори, які користувач хоче використати оголошені в розділі start variable.
Приклад виявлення:
Текст програми з семантичними помилками:
#Program <DSFG>;
Start Var
[Int A,B;];
[
Scan(A,B);
A -> A Dibv B;
B->C Mod B;
B->A Mod B;
Print("A=",A);
] Finish
Текст повідомлення про помилки:
line:1:D - unclered variable line : 7
Дійсно, у 7 строці використана змінна, яка не була оголошена у блоці start variable.
5.4. Загальна перевірка коректності роботи транслятора
Загальна перевірка полягає в транслюванні завідомо коректної вхідної програми з використанням всіх можливостей мови в асемблерний код та перевірці на правильність виконання програми попередньо скомпільованої та злінкованої програми.
Код коректної програми:
#Program <
25.03.2019 18:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора