Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Курсова робота
Предмет:
Системне програмування та операційні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
КУРСОВА РОБОТА
з предмету
“Системне програмування”
на тему : “Розробка системних програмних модулів та компонент систем програмування.”
ВАРІАНТ N° 43
АНОТАЦІЯ
В даному курсовому проекті розроблено транслятор вхідної мови програмування згідно заданого варіанту. Оболонка транслятора розроблена в середовищі Visual Studio за допогою MFC. Сам транслятор написанний на мові C++, та поданий у пояснювальній записці, а також разом з оболонкою в електронному варіанті. В пояснювальній записці подано детальний опис мови, огляд існуючих методів розробки трансляторів, а також описано процес розробки програми транслятора на рівні блок-схем і тексту програми. До проекту додано результати тестування програми.
ЗМІСТ
АНОТАЦІЯ 2
ЗМІСТ 3
ЗАВДАННЯ НА КУРСОВУ РОБОТУ 5
ВСТУП 7
1.ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ 8
1.1. Опис мов програмування 8
1.2. Однопрохідна організація взаємодії блоків транслятора 12
1.3. Комбіновані взаємодії блоків транслятора 14
2.ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ 15
2.1. Деталізований опис вхідної мови в термінах розширеної нотації
Бекуса-Наура 15
2.2 Опис термінальних символів та ключових слів 15
3.РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ 17
3.1. Вибір технології програмування 17
3.2. ЛЕКСИЧНИЙ АНАЛІЗАТОР 18
3.2.1. Розробка лексичного аналізатора 18
3.2.2 Опис програми реалізації лексичного аналізатора 18
3.3. СИНТАКСИЧНИЙ АНАЛІЗАТОР 21
3.3.1. Розробка синтаксичного аналізатора 22
3.3.2 Розробка дерев граматичного розбору 22
3.3.3. Опис програми реалізації синтаксичного аналізатора 22
3.4. ГЕНЕРАТОР КОДУ 24
3.4.1. Розробка генератора коду 24
3.4.2. Опис програми реалізації генератора коду 24
ВИСНОВКИ 26
СПИСОК ЛІТЕРАТУРИ 27
ДОДАТКИ
А. Лістинг програм
А1. Файл «translator.h»
А2. Файл «main.cpp»
А3. Файл «lex_an.cpp»
А4. Файл «syn_an.cpp»
А5. Файл «gen_code.cpp»
А6. Файл « errors.cpp»
Б. Тестова програма
ЗАВДАННЯ НА КУРСОВУ РОБОТУ
1. Цільова мова транслятора асемблер (iх86).
2. Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами tasm32.exe і tlink32.exe.
3. Мова розробки транслятора: ANSI C або C++.
4. Реалізувати оболонку або інтерфейс з командного рядка.
5. На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
6. На виході розробленого транслятора мають створюватись чотири файли:
файл з повідомленнями про помилки (або про їх відсутність);
файл на мові асемблера;
об’єктний файл;
виконавчий файл.
7. Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування.
Таблиця 1. Опис вхідної мови програмування.
Опис
Синтаксис
Приклад
Блок тіла програми
NAME<name>;
DATA…; BODY-END
Name<name>
start
data
<опис змінних>;
<тіло програми>
Body-end
Оператори вводу-виводу
input
output
scan(Ytrg); /* змінна */
print (Ytrg +Jytf); /* вираз*/
print (“рядок”); /* рядок */
Оператор присвоєння
->
Ytrg << 1; Ytrg <<Ytrg +Jytf; Ytrg << Ytrg *( Ytrg +4);
Оператор
if [–else] (СІ)
if (Ytrg == Jytf)
start
_A >> 0;
_B >> 1;
end
else
start
_A >> 1;
_B >> 0;
end
Регістр ключових слів
Up
NAME<name>
Регістр ідентифікаторів
Low8 перший символ
Jytf
Арифметичні операції
+;
-;
*;
/;
%
Ytrg >>Ytrg +Jytf;
Ytrg >>Ytrg -Jytf;
Ytrg >>Ytrg *Jytf;
Ytrg >>Ytrg /Jytf;
Ytrg >>Ytrg %Jytf;
Операції порівняння
==
=!
Le
ge
if (Ytrg ==Jytf) ...
if (Ytrg=!Jytf) ...
Логічні операції
!;
&;
| ;
Ytrg >>Ytrg !;
Ytrg >>Ytrg &Jytf;
Ytrg >>Ytrg |Jytf;
Типи даних
Int_4
...
data
int_4 Ytrg, Ytrg >>18,
...
Коментар
/*….*/
!! Coment
ВСТУП
В даний час штучні мови, що використовують для опису предметної області текстове представлення, широко застосовуються не тільки в програмуванні, але і в інших областях. З їх допомогою описується структура всіляких документів, тривимірних віртуальних світів, графічних інтерфейсів користувача і багатьох інших об'єктів, використовуваних в моделях і в реальному світі. Для того, щоб ці текстові описи були коректно складені, а потім правильно розпізнані і інтерпретовані, використовуються спеціальні методи їх аналізу і перетворення. У основі методів лежить теорія мов і формальних граматик, а також теорія автоматів. Програмні системи, призначені для аналізу і інтерпретації текстів, називаються трансляторами.
Не дивлячись на те, що до теперішнього часу розроблені тисячі різних мов і їх трансляторів, процес створення нових програм в цій області не припиняється. Це зв'язно як з розвитком технології виробництва обчислювальних систем, так і з необхідністю вирішення все більш складних прикладних завдань. Крім того, елементи теорії мов і формальних граматик застосовні і в інших різноманітних областях, наприклад, при описі структур даних, файлів, зображень, представлених не в текстовому, а двійковому форматі. Ці методи корисні і при розробці своїх трансляторів навіть там, де вже є відповідні аналоги. Така розробка може бути обумовлена різними причинами, зокрема, функціональними обмеженнями, відсутністю локалізації, низькою ефективністю. Можна привести безліч прикладів, коли розробка свого транслятора може виявитися актуальною. Тому, основи теорії мов і формальних граматик, а також практичні методи розробки трансляторів лежать у фундаменті інженерної освіти по інформатиці і обчислювальній техніці.
1. ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ.
1.1. Опис мов програмування.
Мови програмування досить сильно відрізняються одна від одної за призначенням, структурою, семантичній складності, методами реалізації. Це накладає свої специфічні особливості на розробку конкретних трансляторів.
Разом з тим, всі мови програмування володіють рядом загальних характеристик і параметрів. Ця спільність визначає і схожі для всіх мов принципи організації трансляторів.
1. Мови програмування призначені для полегшення програмування. Тому їх оператори і структури даних потужніші, ніж в машинних мовах.
2. Для підвищення наочності програм замість машинних кодів використовуються символічні або графічні представлення конструкцій мови, зручніші для їх сприйняття людиною.
3. Для будь-якої мови визначається:
● Множина символів, які можна використовувати для запису правильних програм (алфавіт), основні елементи.
● Множина правильних програм (синтаксис).
● "Сенс" кожної правильної програми (семантика).
Незалежно від специфіки мови будь-який транслятор можна вважати функціональним перетворювачем F, що забезпечує однозначне відображення X в Y, де X - програма на початковій мові, Y - програма на вихідній мові. Тому сам процес трансляції формально можна представити досить просто і зрозуміло:
Y = F(X) (1)
Формально кожна правильна програма X - це ланцюжок символів з деякого алфавіту A, що перетворюється у відповідний їй ланцюжок Y, складений з символів алфавіту B.
Мова програмування, як і будь-яка складна система, визначається через ієрархію понять, задаючу взаємозв'язки між його елементами. Ці поняття зв'язані між собою відповідно до синтаксичних правил. Кожна з програм, побудована за цими правилами, має відповідну ієрархічну структуру.
У зв'язку з цим для всіх мов і їх програм можна додатково виділити наступні загальні риси: кожна мова повинна містити правила, що дозволяють породжувати програми, відповідні цій мові або розпізнавати відповідність між написаними програмами і заданою мовою.
Зв'язок структури програми з мовою програмування називається синтаксичним відображенням.
Як приклад розглянемо залежність між ієрархічною структурою і ланцюжком символів, що визначає наступний арифметичний вираз:
а + (b + с) * d
У більшості мов програмування даний вираз визначає ієрархію програмних об'єктів, яку можна відобразити у вигляді дерева (рис.1):
У кружках представлені символи, які використовуються як елементарні конструкції, а в прямокутниках задаються складені поняття, що мають ієрархічну і, можливо, рекурсивну структуру. Ця ієрархія визначається з допомога синтаксичних правил, записаних на спеціальній мові, яка називається метамовою:
<вираз> ::= <доданок> | <вираз> + <доданок>
<доданок> ::= <множник> | <доданок> * <множник>
<множник> ::= <буква> | ( <вираз> )
<буква> ::= а | b | з | d | i | f | g | h | i | j | до | l | m | n | о | p | q | r | s | t | u | v | w | x | у | z
Якщо правила будуть записані інакше, то зміниться і ієрархічна структура. Як приклад можна привести наступний спосіб запису правил:
<вираз> ::= <операнд> | <вираз> + < операнд > | <вираз> * < операнд >
<операнд> ::= <буква> | ( <вираз> )
<буква> ::= а | b | з | d | i | f | g | h | i | j | до | l | m | n | о | p | q | r | s | t | u | v | w | x | у | z
В результаті синтаксичного розбору того ж арифметичного виразу буде побудована ієрархічна структура, представлена на рис.2
Слід зазначити, що ієрархічна структура в загальному випадку може бути жодним чином не пов'язана з семантикою виразу. І в тому і іншому випадку пріоритет виконання операцій може бути реалізований відповідно до загальноприйнятих правил, коли множення передує додаванню (або навпаки, всі операції можуть мати однаковий пріоритет при будь-якому наборі правил). Проте перша структура явно підтримує подальшу реалізацію загальноприйнятого пріоритету, тоді як друга більше підходить для реалізації операцій з однаковим пріоритетом і їх виконанню справа наліво.
Процес знаходження синтаксичної структури заданої програми називається синтаксичним розбором.
Синтаксична структура, правильна для однієї мови, може бути помилковою для іншої. Наприклад, в мові Форт приведеною вираз не буде розпізнаний. Проте для цієї мови коректним буде постфіксний вираз:
а b з + d * +
Його синтаксична структура описується правилами:
<вираз> ::= <буква> | <операнд> <операнд> <операція>
< операнд > ::= < буква > | < вираз >
< операція > ::= + | *
<буква> ::= а | b | з | d | i | f | g | h | i | j | до | l | m | n | о | p | q | r | s | t | u | v | w | x | у | z
Ієрархічне дерево, що визначає синтаксичну структуру, представлене на рис.3
Іншою характерною особливістю всіх мов є їх семантика. Вона визначає сенс операцій мови, коректність операндів. Ланцюжки, що мають однакову синтаксичну структуру в різних мовах програмування, можуть розрізнятися по семантиці (що, наприклад, спостерігається в C++, Pascal, Basic для приведеного вище фрагмента арифметичного виразу).
Знання семантики мови дозволяє відокремити її від його синтаксису і використовувати для перетворення в іншу мову (здійснити генерацію коду).
Опис семантики і розпізнавання її коректності зазвичай є самою трудомісткою і об'ємною частиною транслятора, оскільки необхідно здійснити перебір і аналіз безлічі варіантів допустимих комбінацій операцій і операндів.
Організація процесів трансляції, що визначає реалізацію основних фаз, може здійснюватися різним чином. Це визначається різними варіантами взаємодії блоків транслятора: лексичного аналізатора, синтаксичного аналізатора і генератора коди. Не дивлячись на однаковий кінцевий результат, різні варіанти взаємодії блоків транслятора забезпечують різні варіанти зберігання проміжних даних. Можна виділити два основні варіанти взаємодії блоків транслятора:
● багатопрохідну організацію, при якій кожна з фаз є незалежним процесом, передавальним управління наступній фазі тільки після закінчення повної обробки своїх даних;
● однопрохідну організацію, при якій всі фази представляють єдиний процес і передають один одному дані невеликими фрагментами.
На основі двох основних варіантів можна також створювати їх різноманітні поєднання.
1.2. Однопрохідна організація взаємодії блоків транслятора.
Один з варіантів взаємодії блоків компілятора при однопрохідній організації представлено на рис.5
В цьому випадку процес трансляції протікає таким чином. Лексичний аналізатор читає фрагмент вхідного тексту, необхідний для отримання однієї лексеми. Після формування лексеми ним здійснюється виклик синтаксичного аналізатора і передача йому створеної лексеми як параметра. Якщо синтаксичний аналізатор може побудувати черговий елемент проміжного уявлення, то він робить це і передає побудований фрагмент генератору коду. Інакше синтаксичний аналізатор повертає управління сканеру, даючи, тим самим, зрозуміти, що чергова лексема оброблена і потрібні нові дані.
Генератор коду функціонує аналогічним чином. По отриманому фрагменту проміжного представлення він створює відповідний фрагмент об'єктного коду. Після цього управління повертається синтаксичному аналізатору.
Після закінчення вхідного тексту і завершенні обробки всіх проміжних даних кожним з блоків лексичний аналізатор ініціює процес завершення програми.
Найчастіше в однопрохідних трансляторах використовується інша схема управління, в якій роль основного блоку грає синтаксичний аналізатор (рис. 6).
Лексичний аналізатор і генератор коду виступають в ролі підпрограм, що викликаються ним. Як тільки синтаксичному аналізатору потрібна чергова лексема, він викликає сканер. При отриманні фрагмента проміжного уявлення здійснюється звернення до генератора коду. Завершення процесу трансляції відбувається після отримання і обробки останньої лексеми і ініціюється синтаксичним аналізатором.
До переваг однопрохідної схеми слід віднести відсутність великих об'ємів проміжних даних, високу швидкість обробки із-за поєднанні фаз в єдиному процесі і відсутність звернень до зовнішніх запам’ятовуючих пристоїв.
До недоліків можна віднести: неможливість реалізації такої схеми трансляції для складних по структурі мов і відсутність проміжних даних, які можна використовувати для комплексного аналізу і оптимізації.
Така схема часто застосовується для простих по семантичній і синтаксичній структурах мов програмування, як в компіляторах, так і в інтерпретаторах. Прикладами таких мов можуть служити Basic і Pascal.
1.3. Комбіновані взаємодії блоків транслятора.
Поєднання багатопрохідної і однопрохідної схем трансляції породжують різноманітні комбіновані варіанти, багато хто з яких успішно використовується. Як приклад можна розглянути деякі з них.
На рис.7 представлена схема взаємодії блоків транслятора, що розбиває весь процес на два проходи. На першому проході породжується повне проміжне представлення програми, а на другому здійснюється генерація коду. Використання такої схеми дозволяє легко переносити транслятор з однієї обчислювальної системи на іншу шляхом переписування генератора коду.
2.ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ.
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура.
<program> ::= NAME<name> data <data_blok> <code_blok> body-end .
<data_blok> ::=<type> [<declaration> {,<declaration>}] {,<type>[<declaration> {, <declaration>}] }; .<type> ::= int integer .
<declaration> ::= <ident> [ >> <const> ] .
<ident> ::= <h_letter>[<l _letter>][<l _letter>][<l _letter>].
<letter>::=<h_letter>|<l_letter>
<h_letter>::= A|B|C|D|E|F|G|H|I|J|K|L|N|M|O|P|Q|R|S|T|U|V|W|X|Y|Z
<l_letter>::= |a|b|c|d|e|f|g|h|i|j|k|l|n|m|o|p|q|r|s|t|u|v|w|x|y|z .
<number> ::= 0|1|2|3|4|5|6|7|8|9 .
<const> ::= [-]<number>{number}.
<code_blok> ::= <statement> {<statement>} .
<statement> ::= <equation>|<cycle>|<scan>|<print>.
<equation> ::= <ident> >> <expression>.
<expression> ::= <operand>|(<operand>)|(<operand><operation><operand>)|<operand><operation> <operand> .
<operand> ::= <ident>|<const> .
<operation> ::= +|-|*|/|%|==|!=|<|>|!!|&&||| .
<cycle> ::= <if> start <code_blok> end [else start <code_blok> end] .
<if> ::= if (<expression>) .
<scan> ::=scan(<ident>); .
<print> ::= print(<expression>|<string>); .
<string> ::= “{<letter>}” .
2.2. Опис термінальних символів та ключових слів.
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
Термінальні символи:
; – кінець блоку опису ідентифікаторів, або закінчення виразу.
, – роздільник між ідентифікаторами в блоці опису ідентифікаторів.
>> – оператор присвоєння.
+ – арифметична операція додавання.
- – арифметична операція відніманя.
* – арифметична операція множення.
/ – арифметична операція ділення.
% – арифметична операція остачі від ділення.
&& – логічна операція «і».
!! – логічна операція «не».
|| – логічна операція «або».
( – відкриваюча дужка.
) – закриваюча дужка.
== – операція порівняння «дорівнює».
!= – операція порівняння «не дорівнює».
< – операція порівняння «менше».
> – операція порівняння «більше».
Ключові слова:
integer – тип даних.
Program<mel> – початок програми.
variable – початок блоку опису ідентифікаторів.
start – початок блоку.
stop – кінець блоку.
scan – оператор вводу.
print – оператор виводу.
if – оператор умовного переходу.
else – оператор умовного переходу.
До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробілу, знаку «-», «_» та «”».
3. РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ.
3.1. Вибір технології програмування.
Для ефективної роботи створюваної програми важливу роль відіграє попереднє складення алгоритму роботи програми, алгоритму написання програми і вибір технології програмування, а саме використання яких структур, типів даних чи алгоритмів дасть нам виграш у кількості коду, його якості і ефективності чи в розумінні.
Тому робимо аналіз нашої програми. Для роботи з виразами (перетворення їх в постфіксну форму) нам знадобиться структура стек. Тому на основі знань, здобутих в курсі основ програмування реалізовуємо стек, а також необхідні функції для роботи з ним: Init (ініціалізація стеку), Push (закинути значення до стеку), Pop (витягнути значення зі стеку), IsEmpty (перевірка на стек порожній), IsFull (перевірка чи стек повний).
Для полегшення роботи з класами лексем використовуємо тип enum для перерахування всіх можливих типів і полегшення наступного опрацювання лексем.
Для полегшення обробки лексем також використовуємо структуру sLEX для зберігання номера рядка та номера позиції лексеми в рядку, імені лексеми, вказівника на номер ідентифікатора в таблиці ідентифікаторів (якщо лексема є ідентифікатором), та класу лексеми.
Для полегшення обробки ідентифікаторів використовуємо структуру sID для зберігання імені ідентифікатора, його типу та значення.
Для полегшення обробки помилок використовуємо структуру sERR для зберігання номера рядка та номера позиції початку помилки в рядку і також тексту самої помилки.
Також використовуємо структуру sTAB для зберігання робочих даних програми – таблиці лексем, таблиці ідентифікаторів, таблиці помилок, буфера для виразу в постфіксній формі, а також назв вхідного файлу, файлу з таблицею лексем, файлу з помилками та вихідного файлу.
Крім того, доцільним є розбиття вихідного коду на процедури, оскільки великі частини коду часто повторюються. Для цього, наприклад, створені асемблерні процедури INPUT (процедура вводу), OUTPUT (процедура виводу), MOD_ (процедура остачі від ділення), AND_ (процедура логічної операції «і»), OR_ (процедура логічної операції «або»), NOT_ (процедура логічної операції «не»), EQ_ (процедура операції порівняння «дорівнює»), GE_ (процедура операції порівняння «більше»), LE_ (процедура операції порівняння «менше»).
Використання даних структур повинно спростити написання коду програми і полегшити її розуміння і читабельність, тому, на мою думку, технологія програмування вибрана вірно.
3.2. ЛЕКСИЧНИЙ АНАЛІЗАТОР.
3.3.1. Розробка лексичного аналізатора.
Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. В цьому випадку використовуються звичайні засоби обробки рядків. Вхідна програма проглядається послідовно з початку до кінця. Базові елементи, або лексичнi одиницi, роздiляються пробілами, знаками операцiй i спецiальними символами (новий рядок, знак табуляції), i таким чином видiляються та розпізнаються iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова).
При виділенні лексеми вона розпізнається та записується у таблицю лексем, разом з цим в таблицю лексем записується номер рядка та номер позиції в рядку для цієї лексеми та її клас. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до класу лексеми, що має свій унікальний номер і це значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Зберігаючи в таблиці лексем номер рядка та номер позиції в рядку для лексеми забезпечується чітке розташування помилки у вхідній програмі, при виявленні такої.
При лексичному аналiзі виявляються i вiдзначаються лексичнi помилки (наприклад: недопустимi символи, неправильнi ідентифікатори, не задекларовані ідентифікатори в блоці опису даних, перевищення максимального та мінімального значення ідентифікаторами під час присвоєння.). Лексична фаза вiдкидає також i коментарi, оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
Під час лексичного аналізу, коли проглядається блок опису даних створюється таблиця ідентифікаторів, в якій записується ідентифікатор та його значення, якщо воно присвоюється в блоці опису даних. Проходячи далі блок коду програми, якщо лексичний аналізатор зустрічає ідентифікатор, якого немає в таблиці ідентифікаторів формується помилка.
3.2.2. Опис програми реалізації лексичного аналізатора.
Для лексичного аналізу я використав 3 функції, які реалізовані у файлі «lex_an.cpp» (Додаток A3.): LexicalAnalis, GetLex та PrintLexArray;
Функція LexicalAnalis виконує лексичний аналіз. На вхід функції потрібно подати файл для аналізу, а на виході отримуємо таблицю лексем, таблицю ідентифікаторів, та помилки програми, які можуть виникнути під час лексичного аналізу.
Функція LexicalAnalis працює за таким алгоритмом:
- спочатку за допомогою функції GetLex ми зчитуємо з вхідного файлу лексему;
- додаємо цю лексему в таблицю лексем, вказавши номер рядка та номер позиції цієї лексеми в рядку, клас лексеми та якщо лексема ідентифікатор, то вказівник на цей ідентифікатор в таблиці ідентифікаторів;
- якщо лексема ідентифікатор і лексичний аналізатор аналізує блок опису даних, то додаємо цей ідентифікатор в таблицю ідентифікаторів; інакше, якщо лексичний аналізатор вже проаналізував блок опису даних, то перевіряємо чи цей ідентифікатор є в таблиці ідентифікаторів, якщо немає, то формуємо помилку, що в програмі використовується неописаний ідентифікатор;
- далі беремо наступну лексему за допомогою функції GetLex, тобто проходим заново всі описані вище пункти, поки не зустрінемо кінець файлу.
Функція GetLex формує лексему з вхідного файлу програми та передаємо її лексичному аналізатору.
Ця функція працює за таким алгоритмом:
- якщо знайшли символ переходу на новий рядок або табуляцію або пробіл, то пропускаємо його і продовжуємо шукати лексему;
- якщо знайшли символ ‘ !!’, тоді перевіряємо чи наступний символ ‘ !!’, якщо так, то це означає що ми наткнулись на коментар. Пропускаємо коментар шукаючи символ ‘ !!’, після якого йде символ ‘ !!’. Якщо проглянувши файл до кінця ми не знаходимо символ ‘ !!’, після якого йде символ ‘ !!’, то формуємо помилку, що неможливо знайти кінець коментаря;
- якщо знайшли символ ‘;’ або ‘(’ або ‘)’ або ‘+’ або ‘*’ або ‘/’ або ‘%’, або ‘,’ тоді формуємо лексему та виходимо з функції;
- якщо знайшли символ ‘"’, то це означає що ми наткнулись на лексему класу «рядок». Зчитуємо цю лексему, поки не знайдемо символ ‘"’, тоді формуємо лексему та виходимо з функції. Якщо проглянувши файл до кінця ми не знаходимо символ ‘"’, то формуємо помилку, що неможливо знайти кінець рядка;
- якщо знайшли символ ‘&’, тоді перевіряємо чи наступний символ ‘&’, якщо так, тоді формуємо лексему та виходимо з функції, якщо наступний символ не ‘&’, то формуємо помилку про знаходження невідомого символу;
- якщо знайшли символ ‘!’, тоді перевіряємо чи наступний символ ‘!’, якщо так, тоді формуємо лексему та виходимо з функції, якщо наступний символ не ‘!’, то формуємо помилку про знаходження невідомого символу;
- якщо знайшли символ ‘|’, тоді перевіряємо чи наступний символ ‘|’, якщо так, тоді формуємо лексему та виходимо з функції, якщо наступний символ не ‘|’, то формуємо помилку про знаходження невідомого символу;
- якщо знайшли символ ‘>’, тоді перевіряємо чи наступний символ ‘>’, якщо так, тоді формуємо лексему та виходимо з функції, якщо наступний символ не ‘<’, то формуємо помилку про знаходження невідомого символу;
- якщо знайшли символ великої літери, тоді це означає що ми наткнулись на ідентифікатор, далі перевіряємо чи наступний символ буква, якщо так, тоді зчитуємо всі наступні букви та цифри, якщо назва ідентифікатора більша за 4 символів, то формуємо помилку та виходимо з функції. Якщо після того як ми знайшли символ ‘_’, наступний символ не є буквою, то формуємо помилку, що неправильний формат ідентифікатора;
- якщо знайшли символ ‘-’, тоді це означає що ми наткнулись на від’ємне число або арифметичну операцію мінус. Перевіряємо, чи наступний символ цифра, якщо так, зчитуємо всі наступні цифри і формуємо лексему та виходимо з функції. Якщо наступний символ не цифра, то це означає, що лексема є арифметичною операцією мінус, формуємо лексему та виходимо з функції;
- якщо знайшли символ цифра, то зчитуємо всі наступні цифри і формуємо лексему та виходимо з функції;
- якщо знайшли символ буква, то зчитуємо всі наступні букви і перевіряємо, чи сформоване слово є одним із зарезервованих слів (scan, print, if, else, program<name>, start, stop, data, integer), то формуємо лексему та виходимо з функції. Якщо сформоване слово не є зарезервованим словом, то формуємо помилку про знайдення невідомого слова.
- якщо знайшли символ кінця вхідного файлу програми, по закінчуємо лексичний аналіз;
- якщо якийсь інакший символ (не перелічений вище), то формуємо помилку, про знайдення невідомого символу та продовжуємо алгоритм з початку.
Функція PrintLexArray друкує сформовану таблицю лексем в файл.
3.3. СИНТАКСИЧНИЙ ТА СЕМАНТИЧНИЙ АНАЛІЗАТОР.
3.3.1. Розробка синтаксичного та семантичного аналізатора.
Синтаксичний аналіз – це процес, в якому досліджується послідовність лексем, яку повернув лексичний аналізатор, і визначається, чи відповідає вона структурним умовам, що сформульовані у визначені синтаксису мови.
Синтаксичний аналізатор – це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. В задачу синтаксичного аналізатора входить: знайти та виділити основні синтаксичні конструкції мови в послідовності лексем програми, встановити тип та правильність побудови кожної синтаксичної конструкції. Синтаксичний аналізатор дає нам відповідь на питання, належить чи ні, ланцюжок вхідних лексем заданій мові.
3.3.2. Розробка дерев граматичного розбору.
На основі нижче наведеного дерева граматичного розбору (Рис.3.4.) аналізується черговий набір послідовних лексем. Дерево не є універсальним.
Рис.3.4. Дерево граматичного розбору.
3.3.3. Опис програми реалізації синтаксичного аналізатора.
Для синтаксичного та я використав функцію CheckProgram реалізовану в файлі «syn_an.cpp» (Додаток A4.).
На вхід функції потрібно подати таблицю лексем, а на виході отримуємо сформовані аналізатором синтаксичні та семантичні помилки.
Функція CheckProgram працює за таким алгоритмом:
- перевіряємо, чи перша лексема – «mainprogram», якщо ні, то формуємо помилку, що очікувалось «mainprogram»;
- перевіряємо, чи наступна лексема – «start», якщо ні, то формуємо помилку, що очікувалось «start»;
- якщо наступна лексема «data», то перевіряємо блок опису даних, який закінчується лексемою ‘;’. В блоці опису даних перевіряємо, чи правильно розставлені лексеми – ‘,’ (чи стоять у відповідних місцях, чи не пропущені); чи правильно відбувається присвоєння в блоці опису даних; чи не присутні лишні лексеми в ньому і т.д. Якщо виявлені якісь негаразди, то формуємо відповідні помили;
- перевіряємо блок коду програми. Тут перевіряємо, чи не присутні лишні лексеми; перевіряємо вирази (баланс дужок, відповідність типів до операцій над ними і т.д.); перевіряємо правильність використання операторів: scan , print, if, else. Якщо виявлені якісь негаразди, то формуємо відповідні помили;
- перевіряємо, чи остання лексема – «end», якщо ні, то формуємо помилку, що очікувалось «end».
3.4. ГЕНЕРАТОР КОДУ.
3.4.1. Розробка генератора коду.
Генерація коду – це машинно-залежний етап компіляції, під час якого відбувається побудова машинного еквівалента вхідної програми. Зазвичай входом для генератора коду служить проміжна форма представлення програми, а на виході може з’являтися об’єктний код або модуль завантаження.
У компілятора, реалізованого в даній курсовій роботі, вихідна мова - програма на мові Assembler. Ця програма записується у файл, що має таку ж саму назву, як і файл з вхідним текстом, але з розширення “asm”. Генерація коду відбувається одразу ж після синтаксичного аналізу. Генератор коду запускається у випадку, коли після роботи лексичного та синтаксичного з семантичним аналізаторів не виявлено жодних помилок.
3.4.2. Опис програми реалізації генератора коду
Для генератора коду я використав 18 функції, які реалізовані у файлі «code_gen.cpp» (Додаток A5.): CodeGenerator, PrintTitle, PrintData, PrintInit,PrintEnding, PrintCode, ConvertToPostfixForm, Prioritet, GenASMCode, PrintInput, PrintOutput, PrintMOD, PrintAND, PrintOR, PrintNOT, PrintEQ, PrintGE, PrintLE.
Функція CodeGenerator виконує генерацію коду у вихідний асемблерний файл.
Функція CodeGenerator працює за таким алгоритмом:
- викликає функцію PrintTitle, для друку заголовку асемблерної програми (шапки) в асемблерний файл;
- викликає функцію PrintData, для друку сегменту даних в асемблерний файл;
- викликає функцію PrintInit, для друку ініціалізації співпроцесора в асемблерний файл;
- викликає функцію PrintCode, для друку сегменту коду в асемблерний файл;
- викликає функцію PrintEnding, для друку асемблерних процедур в кінець асемблерного файлу;
Функція PrintData друкує сегмент даних в асемблерний файл, якому описує всі ідентифікатори з таблиці ідентифікаторів; всі рядки використані в функціях виводу та додаткові змінні для логічних операцій та процедур вводу і виводу.
Функція PrintCode друкує сегменту коду в асемблерний файл. Вона спочатку шукає початок блоку коду в таблиці лексем, і переглядаючи далі таблицю лексем до кінця формує сегмент коду за таким алгоритмом:
- якщо знаходимо вивід рядка, то формуємо асемблерний код виводу рядка;
- якщо знаходимо вивід виразу, то за допомогою функції ConvertToPostfixForm конвертуємо цей вираз у постфіксну форму та за допомогою функції GenASMCode будуємо асемблерний код для цього виразу. Після цього формуємо асемблерний код виклику процедури для виводу;
- якщо знаходимо ввід, то формуємо асемблерний код виклику процедури для вводу;
- якщо знаходимо оператор умовного переходу, то за допомогою функції ConvertToPostfixForm конвертуємо умову в постфіксну форму та за допомогою функції GenASMCode будуємо асемблерний код для цієї умови. Після цього формуємо асемблерний код умовного переходу.
- якщо знаходимо вираз, то за допомогою функції ConvertToPostfixForm конвертуємо цей вираз у постфіксну форму та за допомогою функції GenASMCode будуємо асемблерний код для цього виразу.
Функція ConvertToPostfixForm конвертує вираз у постфіксну форму, формуючи в масиві послідовність номерів
14.04.2013 01:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора