Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмуванн
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Системне програмування та операційні системи
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІКТА
/
Пояснювальна записка
до курсової роботи
з дисципліни:
"Системне програмування" (III курс, 5-й семестр)
На тему : «Розробка системних програмних модулів та компонент систем програмування.»
АНОТАЦІЯ
В курсовій роботі був розроблений транслятор з вхідної мови програмування, заданої завданням, на мову асемблер, з подальшою компіляцією отриманого коду і створення виконавчого файлу. Даний транслятор виконує лексичний аналіз, синтаксичний і семантичний, при наявності помилок у вхідному тексті програми створює список помилок і попереджень. У курсовій роботі створений лексичний аналізатор на базі скінченного автомата, а синтаксичний аналізатор на основі низхідного методу.
Зміст
Завдання на курсову роботу 4
Вступ 5
1. Огляд методів та способів проектування трансляторів 6
2. Формальний опис вхідної мови програмування 9
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура 10
2.2. Опис термінальних символів та ключових слів 11
3. Розробка транслятора вхідної мови програмування 13
3.1. Вибір технології програмування 13
3.2. Проектування таблиць транслятора та вибір структур даних 13
3.3. Розробка лексичного аналізатора 15
3.3.1. Розробка граф-схеми алгоритму 16
3.3.2. Опис програми реалізації лексичного аналізатора 18
3.4. Розробка синтаксичного та семантичного аналізатора 19
3.4.1. Розробка дерев граматичного розбору 20
3.4.2. Розробка граф-схеми алгоритму 21
3.4.3. Опис програми реалізації синтаксичного та семантичного аналізатора 23
3.5. Розробка генератора коду 24
3.5.1. Розробка граф-схеми алгоритму 25
3.5.2. Опис програми реалізації генератора коду 26
4. Опис інтерфейсу та інструкцій користувача 27
5. Відлагодження та тестування програми 27
5.1. Виявлення лексичних помилок. 31
5.2. Виявлення синтаксичних помилок. 28
5.3. Загальна перевірка коректності роботи транслятора. 28
Висновок 30
Список літератури 31
Додаток А. Текст програми-транслятора на мові С++ 32
Завдання на курсову роботу
Тема: Розробка транслятора з вхідної мови програмування.
Типи даних: INT16;
Оператор вводу: SCAN;
Оператор виводу: PRINT;
Блок тіла програми: PROGRAM<name>;
BEGIN VAR…; BEGIN - END
Оператор: WHILE – DO(Паскаль) ;
Регістр ключових слів: Up;
Регістр ідентифікаторів: Low-Up4 перший символ Up;
Операції арифметичні: ADD; SUB; MUL; DIV; MOD;
Операції порівняння: =; <>; >=; <=;
Операції логічні: !; &; |;
Коментар: #*...*#
Оператор присвоєння: ::=;
Вступ
Транслятор – програма або технічний засіб, що виконує трансляцію програми. Транслятор зазвичай виконує також діагностику помилок, формує словники ідентифікаторів, видає для друку тексти програми і т. д.
Трансляція програми – перетворення програми, представленої на одній з мов програмування, в програму на іншій мові, в певному сенсі, рівносильну з першою. Мова, на якій представлена вхідна програма, називається вхідною мовою, а сама програма – вихідним кодом. Вихідна мова називається цільовою мовою або об'єктним кодом.
Поняття трансляції відноситься не тільки до мов програмування, але і до інших комп'ютерних мов, на зразок мов розмітки, аналогічних HTML, і до природних мов, на зразок англійської або російської
Транслятори поділяються на:
Адресний.
Діалоговий.
Багатопрохідної.
Зворотний. (детранслятор).
Однопрохідної.
Оптимізуючий.
Синтаксично-орієнтований (синтаксично-керований).
Тестовий.
Мова процесорів (машинний код) зазвичай є низькорівневою. Існують платформи, які використовують в якості машинної мову високого рівня (наприклад, iAPX-432), але вони є винятком із правила через складність і високу вартість. Транслятор, який перетворює програми в машинну мову, який приймає і виконуваний безпосередньо процесором, називається компілятором.
Процес компіляції як правило складається з декількох етапів: лексичного, синтаксичного та семантичного аналізів (англ. Semantic analysis), генерації проміжного коду, оптимізації та генерації результуючого машинного коду. Крім цього, програма як правило залежить від сервісів, наданих операційною системою і сторонніми бібліотеками (наприклад, файловий ввід-висновок або графічний інтерфейс), і машинний код програми необхідно пов'язати з цими сервісами. Для зв'язування зі статичними бібліотеками виконується редактор зв'язків або компонувальник (який може представляти із себе окрему програму або бути частиною компілятора), а з операційною системою і динамічними бібліотеками зв'язування виконується на початку виконання програми завантажувача.
ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ
Є такі методи створення компіляторів:
1. Прямий метод- цільовою мовою і мовою реалізації є асемблер.
2. Метод розкрути- саме цей метод і використовується у даній курсовій роботі, тобто вибирається інструмент (в даній курсовій це мова асемблер), для якого вже існує компілятор.
3.Використання крос-трансляторів.
4.З використанням віртуальних машин–дає спосіб отримати переносимо програму.
5. Компіляція на ходу.
В даній курсовій роботі згідно із завданням для парних варіантів необхідно реалізувати низхідний метод граматичного розбору. Низхідний розбір — один з методів визначення приналежності вхідного рядка деякій формальній мові, описаній LL(k)-граматикою.
Для кожного нетермінального символу K будується функція, яка для будь-якого вхідного слова x робить дві речі:
Знаходить найбільший початок z слова x, здатний бути початком виводжуваного з K слова
Визначає, чи є початок z виводжуваним з K
Така функція має задовольняти наступні критерії:
Зчитувати із ще необробленого вхідного потоку максимальний початок A, який є початком деякого слова, виводжуваного з K
Визначати чи є A вивідним з K або просто невивідним початком виводжуваного з K слова
У випадку, якщо такий початок зчитати не вдається (і коректність функції для нетермінала K доведена), тоді вхідні дані не відповідають мові, і потрібно зупинити розбір.Розбір містить у собі виклики описаних вище функцій. Якщо для зчитаного нетермінала є складене правило, тоді при його розборі будуть викликані інші функції для розбору терміналів, що входять в нього. Дерево викликів, починаючи із самої«верхньої» функції еквівалентно дереву розбору.
Низхідний метод аналізу реалізується на основі контекстно-вільних граматик.
Контекстно-вільна граматика G це четвірка (N,T,P,S):
/
N та T скінченні множини, що не перетинаються
P скінченна підмножина /
При цьому, використовують наступні назви: N — множина нетермінальних символів, T — множина термінальних символів, P — множина правил виводу S початковий символ. Правила (α,β)єP записують як α→β.
В лівій частині правила виводу має знаходитись одна змінна (нетермінальний символ). Формально, має виконуватись /, wobei /.
LL аналізатор це алгоритм синтаксичного аналізу методом рекурсивного спуску для підмножини контекстно-вільних граматик. Він обробляє вхід зліва направо (тому перша буква означає Left), та будує ліворекурсивне виведення рядка (тому його порівнюють з LR аналізатором ). Клас граматик, що розпізнаються цим аналізатором називається LL граматиками.
Далі описується табличний аналізатор — альтернатива алгоритму рекурсивного спуску, який зазвичай кодується вручну (хоча не завжди, дивіться наприклад ANTLR для генератора аналізаторів LL(*) граматик методом рекурсивного спуску).
LL аналізатори називаються LL(k) аналізаторами, якщо вони дивляться на k токенів вперед протягом аналізу виразу. Якщо такий аналізатор існує та може розпізнавати вирази граматики без бектрекінгу, тоді граматика називається LL(k) граматикою. З цих граматик найпопулярнішою граматикою є граматика LL(1), бо незважаючи на її обмеженість, вона має дуже простий аналізатор. Мови, що відповідають LL(k) граматикам з великим k вважаються такими, що важко аналізуються, хоча сьогодні це не зовсім вірно через доступність та поширеність генераторів синтаксичних аналізаторів, що підтримують LL(k) граматики.
LL аналізатор називається LL(*) аналізатором, якщо він не обмежений скінченним числом токенів для попереднього перегляду, а може приймати рішення визначаючи чи належать вхідні токени регулярній мові (наприклад використовуючи ДСкА).
Існує конкуренція між «європейською школою» проектування мов, яка віддає перевагу LL граматикам, та «американською», яка частіше використовує LR-граматики. Це багато в чому завдяки традиціям викладання та детальному опису методів та інструментів в літературі. Інший вплив іде від досліджень Ніклауса Вірта в вищій технічній школі Цюріха, які описували багато способів оптимізації LL(1) мов, та компіляторів.
Аналізатор працює на рядках з певної контекстно вільної граматики.
Аналізатор складається з
вхідного буфера, в якому зберігається вхідний рядок
стека в якому зберігають термінальні та нетермінальні символи з граматики, що аналізується.
таблицю аналізу яка каже яке ( якщо існує ) правило граматики застосувати залежно від символів на вершині стеку, та наступного вхідного токена.
Аналізатор застосовує правило з таблиці, яке відповідає символу на вершині стеку (рядок таблиці) та символу з вхідного потоку (стовпець).
Формальний опис вхідної мови програмування
Форма Бе́куса—Нау́ра — це спосіб запису правил контекстно-вільної граматики, тобто форма опису формальної мови.
Форма Бе́куса—Нау́ра є набором «продукцій», кожна з яких відповідає зразку:
<символ> ::= <вираз, що містить символи>,
де “вираз, що містить символи” це послідовність символів або послідовності символів, розділених вертикальною рискою | , що повністю перелічують можливий вибір символів з лівої частини формули.
< — лівий обмежувач виразу
> — правий обмежувач виразу
::= — визначене як
| — визначене або
Ці чотири символи є символами мета-мови, вони не визначені у мові, котру описують. Решта описаних символів належать до «абетки» описуваної мови.
Розши́рена фо́рма Бе́куса — На́ура (EBNF) є розширеною формою нотації Бекуса-Наура (BNF) — метасинтаксичної нотації.
Вихідні коди комп'ютерних програм складаються із термінальних символів. До термінальних символів належать видимі літери, цифри, знаки пунктуації, прогалини тощо.
EBNF визначає продукції, що співставляють послідовності із нетермінальними символами.
цифра без нуля = “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”;
цифра = ”0” | цифра без нуля;
Це правило продукції визначає нетермінальний символ «цифра», що знаходиться в лівій частині. Вертикальна риска позначає альтернативу, а термінальні символи знаходяться в лапках. Таким чином, цифра це або 0, або цифра без нуля, котра може бути 1 або 2 або 3 і так далі до 9.
Продукція також може включати як термінальні так і не термінальні символи, розділені комами:
дванадцять = “1” , ”2”;
двісті один = “2” , ”0” , ”1”;
дванадцять тисяч двісті один = дванадцять , двісті один;
Вирази, що можна пропускати або можуть повторятись слід записувати у фігурних дужках { … }:
натуральне число = цифра без нуля , { цифра} ;
В цьому випадку, рядки 1, 2, …,10,…,12345,… є правильними виразами. Для того, аби відобразити це, все, що взято у фігурні дужки може повторюватись необмежену кількість раз, або не з'являтись взагалі.
Можлива поява може відображатися застосуванням квадратних дужок [ … ]:
ціле = “0” | [ “-” ], натуральне число;
Тобто, ціле це або нуль (0), або натуральне число, перед яким може знаходитись знак мінус.
Також, EBNF має синтаксичні засоби для описання певної кількості повторень, для вилучення деякої частини продукції або для запису коментарів в EBNF-граматику.
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
<program>::=PROGRAM<name>VAR…;BEGIN - END.
<code_block> ::=<declarations> [{;<declarations>} ];.
<declarations>::=Int_2<declaration_i> [{,<declaration_i>}].
<declaration_i> ::= <ident> [ :: <const_i>] .
<ident> ::= _<letter_l>[{<letter_h>}].
<letter>::=<letter_h>|<letter_l>|
<letter_l>::=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
<letter_h>::=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_varieble> ::= <statement> [{<statement>}] .
<statement> ::= <equation>|<For>|<read>|<write> .
<equation> ::= <ident> [<< <expression_i>|<expression_b>]; .
<expression_i>::= <term> [{++ <term> | -- <term>}].
<term>::=<ident>|<const>|<factor>.
<factor>::=[{** <term> | Div <term>| Mod <term> | <brackets>}].
<brackets>::=(<expression_i>).
<expression_b>::= <term_b> [{= <term_b> | <> <term_b> | Le<term_b>| Ge <term_b>}].
<term_b>::=<ident>|<const>|<factor_b>.
<factor_b>::=<term_b> [{ <or> <term_b> | <and> |<not>|<brackets_b>}].
<or> ::= [{ | <term_b>}]
<and>::= [{ &<term_b>}]
<not>::=!<factor_b>
<brackets_b>::=(<expression_b>).
<cycle> ::= For(<expression_b>|<ident>)To (<ident> | <const>) <code_blok> Next.
<read> ::= Scan(<ident>) .
<write> ::= Print (<ident>) .
2.2 Термінальні символи та ключові слова
Program – початок тексту програми;
Data - блок опису змінних;
Start – початок тіла програми;
End – кінець тіла програми;
Print – оператор виводу;
Scan– оператор вводу змінних;
::= - оператор присвоєння;
While – початок умовного блоку;
Do – початок умовного блоку виконання;
Next – кінець тіла циклу;
Div – операція ділення
Mod – операція знаходження залишку від ділення;
Add – операція додавання;
Sub – операція віднімання;
Mul – операція ділення;
= – операція перевірки на рівність;
<> – перевірка на нерівність;
>= – операція порівняння більше або рівно;
<= – операція порівняння менше або рівно;
! – операція логічного заперечення;
& – кон’юнкція;
| – диз’юнкція;
Int16 – 16 ти розрядні знакові цілі;
#* *# – коментар
,– розділювач між деклараціями змінних;
; – ознака кінця оператора;
(– відкриваюча дужка;
) – закриваюча дужка;
Як термінальні символи використовуються також усі арабські цифри (0–9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл.
3.РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ
3.1. Вибір технології програмування.
Для ефективної роботи створюваної програми важливу роль відіграє попереднє складення алгоритму роботи програми, алгоритму написання програми і вибір технології програмування.
Тому, при складанні транслятора треба брати до уваги швидкість компіляції, якість об’єктної програми. Проект повинен давати можливість просто вносити зміни.
Для реалізації лексичного аналізу в курсовій роботі використано метод перебору, тобто до чергового символу додається наступний символ і порівнюється з уже заготовленими ключовими словами. Якщо вхідне слово співпадає з одним із ключових, то дана лексема заноситься в таблицю лексем. В таблицю лексем заноситься назва лексеми, тип.
Синтаксичний аналіз базується на перевірці послідовності класів лексем, наприклад, якщо після оператора присвоєння слідує синтаксична лексема, чи після математичного оператора слідує лексема з класу порівнянь, то буде сформовано повідомлення по помилку.
Генератор коду починає свою роботу, якщо на попередніх фазах не було виявлено помилок. В залежності від коду лексеми в асемблерний файл вставляється конкретний набір процедур. Для реалізації обчислень арифметичних виразів використовується переведення їх у постфіксну форму, після чого, такий вираз обчислюється з використанням математичного співпроцесора. Для переведення виразу у постфіксну форму використовується структура даних – стек.
3.2. Проектування таблиць транслятора
Для реалізації лексичного аналізу створюємо таблицю лексем, в яку поміщаємо всі лексеми які будуть введені користувачем, і таблицю ідентифікаторів.
Для створення таблиці лексем, створюємо структуру з наступними полями: Таблиця 1
line
ID
name
Attribute
Поле для зберігання номера рядка з лексемою
Поле для зберігання коду лексеми
Поле для зберігання назви лексеми
Поле для зберігання адреси лексеми в таблиці ідентифікаторів.
struct Lexem_table
{
string name;
Lexem_Type type;
int line;
_Identifier_table_ *attribute;
};
Для створення таблиці ідентифікаторів, створюємо структуру з наступними полями:
Таблиця 2
name
value
type
поле для зберігання назви ідентифікатора
поле для зберігання значення ідентифікатора
Поле для зберігання типу ідентифікатора
typedef enum _Identifier_Type_
{
int16
} Identifier_Type;
typedef struct _Identifier_table_
{
int value;
Identifier_Type identifier_type;
string name;
public:
bool operator==(const _Identifier_table_ &idt) const
{
if (this->value == idt.value && this->identifier_type == idt.identifier_type && this->name == idt.name)
return true;
return false;
}
bool operator>(const _Identifier_table_ &idt) const
{
if (this->name > idt.name)
return true;
return false;
}
bool operator<(const _Identifier_table_ &idt) const
{
if (this->name < idt.name)
return true;
return false;
}
} Identifier_table;
Для зручнішого використання таблиць, створюємо загальну структуру реєстр:
typedef struct L //структура для зберігання данних
{
Lexema LexArray[1000]; //таблиця лексем
int length; //змінна під кількість лексем
Identifier IdTable[50]; //таблиця ідентифікаторів
int idnum; //номер
int PFExpr[200]; //буфер для виразу в постфіксній формі
Для зберігання типів лексем, використовуємо перелік:
enum LexemType //Перелік Типів лексем
{
startprogram_, //початок програми
variable_, //блок даних
int_, //тип даних integer32_t
startblok_, //початок тіла програми
endblok_, //кінець тіла програми
scan_, //Оператор вводу
print_, //Оператор виводу
while_, //оператор циклу
do_,
begin_,
end_,
is_, // >> - оператор присвоєння
add_, //операція додавання
sub_, //операція віднімання
mul_, //операція множення
div_, //операція ділення
mod_, //операція остача від ділення
equ_, // == - операція порівнянн
notequ_, // != - операція порівнянн
not_, // ! - логічне НЕ
and_, // & - логічне І
or_, // | - логічне АБО
eof_, //кінець файлу
EndGroup_, // ;
komma_, // ,
ident_, //ідентифікатор
number_, //число
LeftBraket_, // (
RightBraket_, // )
unknown_ //невідома лексема
};
3.3. Розробка лексичного аналізатора
Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Всі символи вхідної послідовності з цієї точки зору розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми. В цьому випадку використовуються звичайні засоби обробки рядків. Вх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катори). Лексична фаза вiдкидає також i коментарi, оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
Лексичний аналізатор (сканер) не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора.
В даному курсовому проекті реалізовано прямий лексичний аналізатор, який виділяє з вхідного тексту програми окремі лексеми і на основі цього формує таблицю.
3.3.1. Розробка граф-схеми алгоритму
При розробці алгоритму роботи лексичного аналізатора використовується скінченний автомат.
Особливостями цього алгоритму є те, що з потоку зчитується символ, і одразу ж перевіряється на приналежність до одного з типів. Якщо лексема двосимвольна, то перевіряється і наступний символ. Якщо символи відповідають всім вимогам, то заносяться в таблицю з приналежністю до типу, якщо ж ні, то тип заноситься як невідомий – лексема не опізнана.
Рис 1.Граф-схема роботи лексичного аналізатора
Блок 1 – Даний блок починає роботу лексичного аналізатора.
Блок 2 – Відкриває вхідний файл і посимвольно читає його з текстом програми.
Блок 3 – Перевіряє чи не досягнутий кінець файлу,якщо досягнутий то переходим на блок 21(Кінець) в інашому випадку переходимо на блок 4.
Блок 4 – Цей блок видалає і опрацьовує символ з потоку.
Блок 5 – Перевірка чи перший символ підкреслення,якщо так то переходимо на блок 6 в іншому випадку на блок 7.
Блок 6 – Цей блок розпізнає ідентифікатори.
Блок 7 – Перевірка чи перший символ літера,якщо так то переходим на блок 8, в іншому випадку на блок 9.
Блок 8 – Даний блок розпізнає ключові слова.
Блок 9 – Цей блок перевірки,перевіряє чи перший символ 0-9,якщо так то переходим на блок 10,якщо ні то на блок 11.
Блок 10 – Виконує розпізнавання числових констант.
Блок 11 – Відбувається перевірка чи символ є оператором,якщо так то переходим на блок 12,якщо ні то на блок 13.
Блок 12 – Виконується зберігання до таблиці лексем.
Блок 13 – Перевіряє чи перший символ є #,якщо так то переходим на блок 14,в іншому випадку перехід відбувається на блок 15.
Блок 14 – Виконується розпізнавання коментарів.
Блок 15 – Перевіряє чи символ є розділювач,якщо так то переходим на блок 16,в іншому пипадку переходим на блок 17.
Блок 16 – Виконується зберігання до таблиці лексем.
Блок 17 – Перевірка чи є ще інший символ,якщо так то переходим на блок 18,в іншому випадку завершуємо роботу лексичного аналізу.
Блок 18 – Виявлення нерозпізнаних лексем
Блок 19 – Якщо файл прочитано, завершення роботи лексичного аналізатора
3.3.2 Опис програми реалізації лексичного аналізатора
Програма по символу читає вхідний файл. Зчитаний символ одразу перевіряється на приналежність до певного типу лексем. Якщо, символ співпадає з зарезервованою лексемою, то він заноситься в таблицю лексем. Якщо ж зчитаний символ являється літерою, то зчитуються наступні символи, і перевіряються на спів падіння з ключовими словами. Якщо тип лексеми з’ясувати не вдалося, то вона заноситься в таблицю як невідома.
В лексичному аналізаторі використовуються наступні функції:
GetLexema() розпізнає слова з вхідного файлу, і формує таблицю лексем.
LexicalAnalyze() повертає значення, яке рівне кількості лексем у таблиці.
MakeLexOutFile() створює текстовий файл з таблицею лесем.
3.4.Розробка синтаксичного аналізатора
Синтаксичний розбір (розпізнавання) є першим етапом синтаксичного аналізу.Саме при його виконанні здійснюється підтвердження того, що вхідний ланцюжок символів є програмою, а окремі підланцюжки складають синтаксично правильні програмні об'єкти. Вслід за розпізнаванням окремих підланцюжків здійснюється аналіз їх семантичної коректності на основі накопиченої інформації. Потім проводиться додавання нових об'єктів в об'єктну модель програми або в проміжне представлення.
Розбір призначений для доказу того, що аналізований вхідний ланцюжок, записаний на вхідній стрічці, належить або не належить безлічі ланцюжків породжуваних граматикою даної мови. Виконання синтаксичного розбору здійснюється розпізнавачами, тому даний процес також називається розпізнаванням вхідного ланцюжка. Мета доказу в тому, щоб відповісти на питання: чи належить аналізований ланцюжок безлічі правильних ланцюжків заданої мови. Відповідь «так» дається, якщо така приналежність встановлена. Інакше дається відповідь «ні». Отримання відповіді «ні» пов'язано з поняттям відмови. Єдина відмова на будь-якому рівні веде до загальної відмови.
Щоб одержати відповідь «так» щодо всього ланцюжка, треба його одержати для кожного правила, що забезпечує розбір окремого підланцюжка. Аналізатор вибирає перший символ з сукупності лексем аналізуючи його визначає, яку функцію треба запустити щоб виконати перевірку заданого підланцюжка. Цей метод називається методом рекурсивного спуску, аналіз проводиться від кореня до листків.
Основним завданням семантичного аналізатора є перевірка типів. Також семантичний аналізатор повинен знаходити вирази, що використовуються без присвоєння та видавати попередження.
Сама програма перевірки типів базується на інформації про синтаксичні конструкції мови, представлення типів і правилах присвоєння типів конструкціям мови.
3.4.1. Розробка дерева граматичного розбору
Рис 2.Граф-схема дерева граматичного розбору
Дерево граматичного розбору розроблено згідно правил, даних у формі розширеної нотації Бекуса-Наура, та оформлено згідно правил ЄСКД.
3.4.2 Розробка граф-схеми алгоритму
Рис 3.Граф-схема роботи синтаксичного аналізатора
Блок 1 – Даний блок починає роботу синтаксичного аналізатора.
Блок 2 – Відбувається виявлення рутового терміналу PROGRAM.
Блок 3 – Перевіряє чи наступний символ VARIABLE,якщо так то переходим на блок 4,в іншому випадку переходим на блок 27.
Блок 4 – Відбувається розпізнавання блоку оголошенних змінних.
Блок 5 – Даних блок відподіжає на переходів до наступної лексеми.
Блок 6 – Перевіряє,чи наступний символ START-block,якщо так то переходим на блок 7,в іншому випадку на блок 27.
Блок 7 – Даний блок розбирає конструкцію START-block-END-block.
Блок 8 – Відбувається перевірка на помилку,якщо так то переходим на блок 27,в іншому випадку на блок 9.
Блок 9 – Цей блок робить перехід до наступної лексеми.
Блок 10 – Відбувається перевіка чи наступний символ буде PRINT,якщо так то переходим на блок 11,в іншому випадку на блок 14.
Блок 11 – Цей блок виконує розпізання розпізнання блоку виводу.
Блок 12 – Перевірка на помилку тобто якщо є помилка то переходим на блок 27 в іншому випадку на блок 11.
Блок 13 – Даний блок робить перехід до наступної лексеми.
Блок 14 – Перевіряє, чи наступний символ SCAN,якщо так то переходимо на блок 15,якщо ні то на блок 18
Блок 15 – В цьому блоці відбувається розпізання блоку виводу.
Блок 16 – Відбувається перевірка на помилку,якщо є помилка то переходим на блок 27 в іншому випадку на блок 17.
Блок 17 – В даному блоці відбувається перехід до наступної лексеми.
Блок 18 – Відбувається перевірка , чи наступний символ ідентифікатор,якщо так то переходим на блок 19 в іншому випадку переходим на блок 22.
Блок 19 – В цьому блоці відбувається розбір конструкції виразу.
Блок 20 – Відбувається перевірка на помилку,якщо є помилка то переходим на блок 27 в іншому випадку на блок 21.
Блок 21 – В даному блоці відбувається перехід до наступної лексеми.
Блок 22 – Перевіряє, чи наступний символ WHILE,якщо так то переходимо на блок 26,якщо ні то на блок 23
Блок 23 – В даному блоці відбувається розбір конструкції умовного оператора.
Блок 24 – Відбувається перевірка на помилку,якщо є помилка то переходим на блок 27 в іншому випадку на блок 25.
Блок 25 – В даному блоці відбувається перехід до наступної лексеми.
Блок 26 – Перевірка, чи це інша лексема,якщо це інша лексема то переходим на блок 27 в іншому випадку на блок 28.
Блок 27 – Видача помилки.
Блок 28 – Відбувається перевірка чи кінець файлу,якщо це кінець то переходим на блок 29 в іншому випадку на блок 10.
Блок 29 – Завершення синтаксичного аналізу.
3.4.3 Опис програми реалізації синтаксичного та семантичного аналізатора
На вхід синтаксичного аналізатора подається таблиця лексем, створена на етапі лексичного аналізу.
В синтаксичному аналізі використовуються функції для розбору всіх конструкції вхідної мови. Вхідна конструкція перевіряється по всіх правилах, згідно дерева граматичного розбору. Додатково була описана функція IsExpression() , яка перевіряє, чи певний набір лексем є виразом.
3.5.Розробка генератора коду
3.5.1 Розробка граф-схеми алгоритму
Рис 4.Граф-схема роботи генератора коду
3.5.2 Опис програми реалізації генератора коду
Програма починає по черзі перебирати лексеми із таблиці лексем. У відповідності до коду знайденої лексеми буде вставлено відповідний еквівалентний асемблерний текст. Наприклад, при зустрічі ключового слова STARTPROGRAM, в асемблерний файл вставляється текст з описом моделі та сегментів, а при зустрічі ключового слова VARIABLE, вставляється опис сегменту даних.
В даному трансляторі генератор коду послідовно викликає окремі функції, які записують у вихідний файл частини коду. Для кожного ланцюжка вхідної мови існує окрема функція, яка враховуючи послідовність лексем створює відповідний вихідний код.
4. Опис інтерфейсу та інструкції користувачеві
Створений транслятор є DOS програмою, що запускається з командної стрічки з параметром, а саме - іменем вхідного файлу, в якому записана програма на вхідній мові. Файл повинен мати розширення .R20. Отже формат введення повинен бути таким:
RCompiler.exe <ім’я програми>.R80
У випадку некоректного введення програма видасть повідомлення про помилку і завершить своє виконання.
Якщо коректно введене ім’я вхідного файлу та вдалось його відкрити, то транслятор почне його опрацювання. Початковою фазою обробки є лексичний аналіз (розбиття на окремі лексеми), наступною - перевірка на правильність написання програми (вхідної). У випадку, коли виявлені помилки, транслялятор видасть повідомлення про їхню присутність, вкаже в якому файлі можна ці помилки переглянути та завершить своє виконання. Якщо ж програма написана вірно, то транслятор перейде на наступну фазу семантичного розбору та генерації асемблерного коду та вкаже ім’я результуючого файлу з розширенням .asm та завершить своє виконання.
Для отримання виконавчого файлу необхідно скористатись програмами tasm.exe filename.asm для компіляції та tlink filename.obj для лінкування.
5. Відлагодження та тестування програми
Тестування і відлагодження програм – це спосіб покращення якості продукту. По своїй суті відлагодження – це спосіб виявлення дефектів у програмі. Важливо пам’ятати, що якість продукту повинна бути закладена від початку розробки: найкращий спосіб створити хороший, якісний продукт – це добре проаналізувати вимоги, вдало продумати архітектуру і застосувати дієву практику написання програмного коду. В цьому випадку відлагодження є останнім виходом.
Відлагодження та тестування компілятора проводиться з використанням кількох вхідних програм з навмисне введеними помилками та з коректною програмою для
16.02.2014 17:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора