Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмування. Розробка транслятора з вхідної мови програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Інші
Предмет:
Системне програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет "Львівська Політехніка"
Кафедра ЕОМ
/
Пояснювальна записка
до курсової роботи
з предмету: "Системне програмування"
на тему:"Розробка системних програмних модулів та компонент систем програмування. Розробка транслятора з вхідної мови програмування"
Анотація
В даній курсовій роботі реалізується програма, яка транслює файл з деякої віртуальної мови, заданої завданням, в файл Асемблера з подальшою його компіляцією і створенням виконавчого файлу. Крім того, дана програма перевіряє на помилки (синтаксичні, семантичні, лексичні) вхідний файл і при їх присутності видає у файл повідомлення про помилки і зупиняє свою роботу до їх виправлення.
В даній курсовій роботі показано розробку і виконання наступних фаз компіляції:
лексичний аналіз;
синтаксичний аналіз;
генерація коду.
Результатом виконання курсової роботи повинна бути повноцінна функціональна програма на мові Assembler, яка є інтерпретованою програмою реалізованої на заданій вхідній мові програмування.
На прикладі даної програми нами вивчалася можливість створення достатньо потужних трансляторів в мову низького рівня (наприклад, Асемблер), - завдання, реалізація якого є достатньо потрібною на сучасному етапі розвитку програмування.
В ході виконання курсової роботи студенти повинні навчитися самостійно працювати з літературою, розробляти типові елементи системних програм, програмуючи роботу з таблицями, словниками, інформаційними базами, виконуючи лексичний та синтаксичний аналіз, а також семантичну обробку, здійснювати їх програмну реалізацію та відлагодження на сучасних обчислювальних системах.
Зміст
Завдання на курсову роботу 5
Деталізований опис вхідної мови 5
Вступ 6
1. Огляд методів та способів проектування трансляторів 8
2. Формальний опис вхідної мови програмування 13
2.1. Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура 13
2.2. Опис термінальних символів та ключових слів 14
3. Розробка транслятора вхідної мови програмування 15
3.1. Вибір технології програмування 15
3.2. Проектування таблиць транслятора та вибір структур даних 15
3.3. Розробка лексичного аналізатора 16
3.3.1. Опис лексичного аналізатора 17
3.4. Розробка синтаксичного та семантичного аналізатора 19
3.4.1. Опис синтаксичного аналізатора 21
3.5. Повне дерево граматичного розбору 23
3.6. Розробка генератора коду 25
3.6.1. Опис генератора коду 25
4. Опис інтерфейсу та інструкція користувачеві 28
5. Відлагодження та тестування програми 29
5.1. Виявлення лексичних помилок 29
5.2. Виявлення синтаксичних помилок 29
5.3. Загальна перевірка коректності роботи транслятора 30
Висновок 31
Література 32
Додаток А. Текст програми-транслятора на мові С++ 33
ДОДАТОК Б. Приклад програми із лексичними та синтаксичними помилками та текст файлу з повідомленням про помилки 62
ДОДАТОК В. Приклад програми із семантичними помилками та текст файлу з повідомленнями про помилки. 64
ДОДАТОК Г. Приклад коректної програми та результат її виконання 65
Приклад виконання програми: 68
ДОДАТОК Д. Граф-схема алгоритму виконання програми через використання функцій. 69
Завдання на курсову роботу
Цільова мова транслятора асемблер (iх86).
Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами tasm і tlink.
Мова розробки транслятора: ANSI C або C++.
Реалізувати оболонку або інтерфейс з командного рядка.
На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
На виході розробленого транслятора мають створюватись чотири файли:
файл з повідомленнями про помилки (або про їх відсутність);
файл на мові асемблера;
об’єктний файл;
виконавчий файл.
Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування. Для мого варіанту це буде .s21
Деталізований опис вхідної мови
тип даних: знакове ціле (Int16_t);
регістр ключових слів: Up-Low перший символ Up
регістр ідентифікаторів: Up-Low4 перший символ _
арифметичні операції: +; -; Mul; Div; Mod
операції порівняння Eg; Ne; >; <
логічні операції: !!; &&; ||
оператор присвоєння: <-
блок тіла програми: MainProgram Data…; Start - End
коментар: {* ... *}
оператор циклу:Repeat - Until
оператори вводу/виводу: Input, Output
Вступ
Транслятором називається програма перекладу (трансляції) початкової програми, записаною вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна – вихідною, то такий транслятор називається компілятором.[5]
Транслятори бувають двох типів: компілятори і інтерпретатори. Процес компіляції складається з двох частин: аналізу і синтезу. На етапі аналізу вхідну програму розбивають на окремі елементи (лексеми), перевіряють її на відповідність правилам граматики і створюють проміжне представлення вхідної програми. На етапі синтезу із проміжної форми створюють програму в машинних кодах. Така програма називається об’єктною програмою. В подальшому об’єктну програму можна виконати на комп’ютері без пере трансляції.[5]
На відміну від компіляторів, інтерпретатор не створює нової програми, а просто виконує – інтерпретує кожен оператор вхідної мови програмування. Подібно компілятору, інтерпретатор аналізує вхідну програму, створює проміжне представлення, однак не створює об’єктної програми, а зразу виконує передбачені вхідною програмою.
Компілятор переводить програму з однієї мови на іншу. На вхід компілятора поступає ланцюг символів, який є вхідною програмою на певній мові програмування. На виході компілятора (об’єктна програма) також представляє собою ланцюг символів, який вже належить іншій мові програмування, наприклад машинній мові деякого комп’ютера. При цьому сам компілятор може бути написаний третьою мовою.
Метою даної курсової роботи є вивчення та закріплення знать про створення компіляторів, трансляторів, інтерпретаторів.
У даній курсовій роботі необхідно буде реалізувати транслятор з заданої мови програмування в ассемблерний код. Даний транслятор повинен виконувати лексичний аналіз. Результатом цього аналізу має стати файл, який буде містити таблицю лексем даної програми. Ця таблиця необхідна для наступного етапу аналізу, зокрема для синтаксичного аналізу. Результатом роботи синтаксичного аналізатора має стати повідомлення про відсутність помилок, або про їх наявність з зазначенням місць виявлення помилок. Якщо попередні дві стадії (лексичний аналіз та синтаксичний аналіз) пройдені успішно, транслятор виконує генерацію коду, який і є результатом роботи даного транслятора. Якщо все ж таки помилки знайдені, транслятор повідомляє користувача про них.
Після отримання асемблерного коду необхідно буде відкомпілювати його за допомогою відповідних програм (TASM i TLINK, тощо). Відкомпільований файл можна буде запустити на виконання.
Огляд методів та способів проектування трансляторів
Транслятор - обслуговуюча програма, що перетворює вихідну програму, надану на вхідній мові програмування, у робочу програму, представлену на об'єктному мовою.[2]
Наведене визначення відноситься до всіх різновидів транслюють програм. Однак у кожної з таких програм можуть бути свої особливості щодо організації процесу трансляції. В даний час транслятори поділяються на три основні групи: асемблери, компілятори та інтерпретатори.
Асемблер - системна обслуговуюча програма, яка перетворить символічні конструкції в команди машинної мови. Специфічною рисою асемблером є те, що вони здійснюють дослівну трансляцію однієї символічної команди в одну машинну. Таким чином, мова асемблера (ще називається автокодом) призначена для полегшення сприйняття системи команд комп'ютера і прискорення програмування в цій системі команд.[3]
Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову програми, записаної мовою оригіналу програмування. Також як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншу (найчастіше, в мову конкретного комп'ютера). Разом з тим, команди вихідної мови значно відрізняються з організації та потужності від команд машинної мови. Існують мови, в яких одна команда вихідного мови транслюється в 7-10 машинних команд. Однак є й такі мови, в яких кожній команді може відповідати 100 і більше машинних команд (наприклад, Пролог). Крім того, у вихідних мовах до часто використовується строга типізація даних, що здійснюється через їх попередній опис. [3]
Інтерпретатор - програма або пристрій, що здійснює пооператорну трансляцію і виконання вихідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму на машинній мові. Розпізнавши команду вихідного мови, він тут же виконує її. Як у компіляторах, так і в інтерпретатора використовуються однакові методи аналізу вихідного тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і налагодження програм більш гнучким. Крім того, відсутність вихідного машинного коду дозволяє не "захаращувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна досить легко адаптувати до будь-яких машинних архітектур, розробивши його тільки один раз на широко поширеному мовою програмування. [3]
Емулятор - програма або програмно-технічний засіб, що забезпечує можливість без перепрограмування виконувати на даній ЕОМ програму, що використовує коди чи способи виконання операція, відмінні від даної ЕОМ. Емулятор схожий на інтерпретатор тим, що безпосередньо виконує програму, написану на деякій мові. Однак, частіше за все це машинна мова або проміжний код. І той і інший представляють команди в двійковому коді, які можуть виконуватися відразу після розпізнавання коду операцій. На відміну від текстових програм, не потрібно розпізнавати структуру програми, виділяти операнди.
Кодувач - програма або програмне пристрій, що переводять програми, написані на машинному мовою однієї ЕОМ до програм на машинну мову іншої ЕОМ. Якщо емулятор є менш інтелектуальним аналогом інтерпретатора, то кодувач виступає в тій же якості по відношенню до компілятору. Точно так вихідний (і зазвичай двійковий) машинний код або проміжне уявлення перетворюються в інший аналогічний код по одній команді і без будь-якого загального аналізу структури вихідної програми. Кодувачі бувають корисні при переносі програм з одних комп’ютерних архітектур на інші. Вони можуть також використовуватися для відновлення тексту програми на мові високого рівня з наявного бінарного коду.[3]
Макропроцесори - програма, що забезпечує заміну однієї послідовності символів іншої. Це різновид компілятора. Він здійснює генерацію вихідного тексту шляхом обробки спеціальних вставок, які розташовуються у вихідному тексті. Ці вставки оформлюються спеціальним чином і належать конструкціям мови, званого макромовою.
Макропроцесори підвищують ефективність програмування без зміни синтаксису і семантики мови.
Синтаксис - сукупність правил деякої мови, що визначають формування його елементів. Інакше кажучи, це сукупність правил освіти семантично значущих послідовностей символів в даній мові. Синтаксис задається за допомогою правил, які описують поняття деякоїмови. Прикладами понять є: змінна, вираз, оператор, процедура. [5]
Семантика - правила та умови, що визначають співвідношення між елементами мови та їх смисловими значеннями, а також інтерпретацію змістовного значення синтаксичних конструкцій мови. Об'єкти мови програмування не тільки розміщуються в тексті у відповідності з певною ієрархією, а й додатково пов'язані між собою.[5]
Всі мови програмування мають ряд загальних характеристик і параметрів.. Ця спільність визначає і схожі для всіх мов принципи організації трансляторів.
Мови програмування призначені для полегшення програмування. Тому їхні оператори та структури даних більш потужні, ніж в машинних мовах.
Для підвищення наочності програм замість числових кодів використовуються символічні або графічні представлення конструкцій мови, більш зручні для їх сприйняття людиною.
Для будь-якої мови визначається:
набір символів, які можна використовувати для запису правильних програм (алфавіт), основні елементи.
набірправильних програм (синтаксис).
"Сенс" кожної правильної програми (семантика).
Незалежно від специфіки мови будь-який транслятор можна вважати функціональним перетворювачем F, що забезпечує однозначне відображення X в Y, де X - програма мовою оригіналу, Y - програма на вихідному мовою.
З огляду на схожість компілятора й інтерпретатора, розглянемо фази, що існують в компіляторі. У них виділяються:
Фаза лексичного аналізу.
Фаза синтаксичного аналізу, що складається з:
розпізнавання синтаксичної структури;
семантичного аналізу, в процесі якого здійснюється робота з таблицями, породження проміжного семантичного подання або об'єктної моделі мови.
Фаза генерації коду, що здійснює:
семантичний аналіз компонент проміжного подання або об'єктної моделі мови;
переклад проміжного подання або об'єктної моделі в об'єктний код.
Поряд з основними фазами процесу трансляції можливі також додаткові фази:
Фаза дослідження та оптимізації проміжного представлення, що складається з:
аналізу коректності проміжного представлення;
оптимізації проміжного представлення.
3а. Фаза оптимізації об’єктного коду.
Узагальнена структура компілятора, що враховує існуючі в ньому фази, представлена на рис. 1.1:
/
Рис. 1.1 - Узагальнена структура аналізатора
Він складається з лексичного аналізатора, синтаксичного аналізатора, генератора коду, аналізатора помилок. У інтерпретаторі замість генератора коду використовується емулятор, до якого, крім елементів проміжного представлення, передаються вихідні дані.
Формальний опис вхідної мови програмування
Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
Однією з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких я застосував розширену нотацію Бекуса-Наура.
Таблиця 1 – Розширена нотація Бекуса-Наура для заданої згідно варіанту мови програмування
<program>
MainProgram Data <declatation> ; Start <body> End
< blok>
::= < operator > | [{< operator>}]
<declaration>
::= <type><ident> [ <is><const> ]
<type>
::= Int16_t
<is>
::= <-
<ident>
::= _<h_letter>[{<l _letter>}]
<leter>
::=< 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}] ;
<name_const>
::=”{<letter >|<number> [{<letter>}]|[{<number>}]}”
<operator>
::= <equation >| <print> | <scan>| <circle>|<operator_block>
<equation>
::= <ident><is><expression>
<expression>
::= [(] <operand> [)] [{ [)]<operation>[(]<operand> [)] }]
<operand>
::= <ident>|<const> |<ident>
<operation>
::= <arifmetic>|<logic>
<arifmetic>
::= <arifmetic>+<harifmetic>|<arifmetic>-<harifmetic> |<harifmetic>
<harifmetic>
::=<harifmetic>Mul<farifmetic>|<harifmetic>DIV<farifmetic> |< harifmetic>MOD<farifmetic>| <farifmetic>
<farifmetic>
::=<operand>|(<arifmetic>)
<logic>
::=<egual>[ ||<egual>]|<logic_b>
logic_b>
::=<logic_b>&&<logic_h>|<logic_h>
<logic_h>
::=!!< logic_h>| <logic_bh>
<logic_bh>
::=(<logic>)|<egual>
<egual>
::= (< operand ><eg_op><operand>)
<eg_op>
::= Eg| Ne| >| <
<cyrcle>
::= Repeat <BODY> Until <EXPRESSION>
<scan>
::= Input <ident>;
< print>
::= Output <ident> | <name_const>;
<operator_block>
::= Start < operator > | [{< operator>}] End
Опис термінальних символів та ключових слів
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
MainProgram
Data
Start
End
Input
Output
<-
Repeat
Until
+
-
Mul
Div
Mod
Eg
Ne
>
<
!!
&&
||
Int16_t
{* ... *}
(
)
;
,
До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z), символи табуляції,символ переходу на нову стрічку, пробілу, знаку "-".
Розробка транслятора вхідної мови програмування
Вибір технології програмування
Перед тим як розпочинати створювати програму, для більш швидкого і ефективного її написання необхідно розробити алгоритм її функціонування, та вибрати технологію програмування, середовище програмування.
Для виконання поставленого завдання найбільш доцільніше було використання середовища програмування Microsoft Visual Studio 2010, та мову програмування С++.
Для більш якісного і зручного використання розробленої програми користувачем, було прийнято рішення створення консольного інтерфейсу. Також даний метод передбачає використання багатьох різних стандартних структур, які дозволяють спростити і полегшити написання, та спростити читабельність програми.
Проектування таблиць транслятора та вибір структур даних
Використання таблиць значно полегшує створення трансляторів, тому у даному випадку використовуються кілька таблиць:
Таблиця лексем з елементами, які мають таку структуру:
enum eTypesOfTokens
{
ltProgram, // MainProgram
ltVar, // Data…
ltType, // type
ltBegin, // Start
ltEnd, // End
ltRead, // Input
ltWrite, // Output
ltUntil, // until
ltRepeat, // repeat
ltNewValue, // <-
ltAdd, // +
ltSub, // -
ltMul, // *
ltDiv, // /
ltMod, // %
ltEqu, // ==
ltNotEqu, // !=
ltLess, // <
ltGreate, // >
ltNot, // !
ltAnd, // &&
ltOr, // ||
ltEOF, // EOF
ltEndGroup, // ;
ltComma, // ,
ltIdentifier, //
ltNumber, //
ltLBraket, // (
ltRBraket, // )
ltUnknown
};
typedefstruct tokens_
{
char name[50];
int value;
eTypesOfTokens type;
int line;
} tokens;
Структура tokens використовується для опису кожної лексеми. Вона містить інформацію про ім’я лексеми, її значення (якщо це число), тип лексеми та рядок у якому вона знаходиться. Ця інформація є необхідною для синтаксичного аналізу та для генерації коду.
Перелік eTypesOfTokens – використовується лише для полегшення сприйняття програмістом інформації. Адже для спрощення процесу аналізу назви лексем замінюються цифрами (цифри легше порівнювати, ніж символи), але використання цифр у коді ускладнює його наглядність, а перелік дозволяє поставити у відповідність кожному числу, яке необхідне для опису лексем, відповідний псевдонім, і за цим псевдонімом звертатись до нього.
Таблиця ідентифікаторів з елементами типу Identificator та додатковою цілочисельною змінною в якій зберігається кількість визначених змінних. Ця структура необхідна для збереження інформації про ідентифікатори: назва змінної, її значення.Структура елементів така:
typedefstruct identifier_
{
char name[50];
int value;
} identifier;
Розробка лексичного аналізатора
Лексичний аналізатор - це частина компілятора, яка читає вихідну програму і виділяє в її тексті лексеми вхідної мови. На вхід лексичного аналізатора надходить текст вихідної програми, а вихідна інформація передається для подальшої обробки компілятором на етапі синтаксичного аналізу [1].
Існує кілька причин, з яких до складу практично всіх компіляторів включають лексичний аналіз:
застосування лексичного аналізатора спрощує роботу з текстом вихідної програми на етапі синтаксичного розбору;
для виділення в тексті та розбору лексем можливо застосовувати просту, ефективну і теоретично добре пророблену техніку аналізу;
Результатом роботи лексичного аналізатора є виділення лексем, що розізнаються та записуються у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компіляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми – для місця помилки – та додаткова інформація.
Опис лексичного аналізатора
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо рядка відповідної лексеми – для місця помилки – та додаткова інформація.
Лексичний аналізатор (сканер) не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора.
В даному курсовому проекті реалізовано прямий лексичний аналізатор, який виділяє з вхідного тексту програми окремі лексеми і на основі цього формує таблицю.
Для реалізації лексичного аналізатора використовуються наступні функції:
int LexicalAnalyze(FILE*); - виконує лексичний аналіз і створює таблицю лексем;
Lexema* GetLexema(FILE*); - зчитує з вхідного файлу інформацію до тих пір, доки не ідентифікує її з певним типом лексеми чи визначить, що дана частина коду не відноситься до заданої мови програмування. У головну підпрограму повертає тип наступної лексеми, чи повідомлення що наступну лексему виділити не вдається;
void MakeLexOutFile(); - створює файл з таблицею лексем;
/
Рис. 3.2. Блок-схема роботи лексичного аналізатора
Розробка синтаксичного та семантичного аналізатора
Основне завдання синтаксичного аналізу [1] - розбір структури програми. Як правило, під структурою розуміється дерево, відповідне розбору в контекстно-вільної граматики мови. В даний час найчастіше використовується або LL (1)-аналіз (і його варіант - рекурсивний спуск), або LR (1)-аналіз та його варіанти (LR (0), SLR (1), LALR (1) та інші) .
Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблиці об'єктів. У процесі синтаксичного аналізу також виявляються помилки, пов'язані зі структурою програми.
В основі синтаксичного аналізатора лежить Розпізнавач тексту вхідної програми на основі граматики вхідного мови. Як правило, синтаксичні конструкції мов програмування можуть бути описані за допомогою КС-граматик, рідше зустрічаються мови, які можуть бути описані за допомогою регулярних граматик. Найчастіше регулярні граматики застосовні до мов асемблера, а мови високого рівня побудовані на основі КС-мов.
Розпізнавач дає відповідь на питання про те, належить або немає ланцюжок вхідних символів заданому мови. Однак, як у випадки лексичного аналізатора, завдання синтаксичного розбору не обмежується тільки перевіркою приналежності ланцюжка заданому мови. Синтаксичний аналізатор виконує ще ряд важливих функцій і вже не є різновидом МП-автомата - його функції можна трактувати ширше. Синтаксичний аналізатор повинен мати якусь вихідну у за допомогою якої він передає наступним фаз компіляції всю інформацію про знайдені і розібраних синтаксичних структурах. У такому випадки він вже є перетворювачем з магазинної пам'яттю - МП-перетворювачем.
Синтаксичний розбір [1] - це основна частина компіляції на етапі аналізу. Без виконання синтаксичного розбору робота компілятора безглузда, у той час як лексичний аналізатор є зовсім необов'язковим. Усі завдання з перевірки лексики вхідного мови можуть бути вирішені на етапі синтаксичного розбору. Сканер тільки дозволяє позбавити складний за структурою лексичний аналізатор від рішення примітивних завдань з виявлення та запам'ятовування лексем вхідний програми.
Виходом лексичного аналізатора є таблиця лексем. Ця таблиця утворює вхід семантичного аналізатора, який досліджує тільки один компонент кожної лексеми - її тип. Інша інформація про лексеми використовується на більш пізніх фазах компіляції при семантичному аналізі, підготовці до генерації та генерації коду результуючої програми. Синтаксичний аналіз - це процес, в якому досліджується таблиця лексем і встановлюється, чи задовольняє вона структурним умовам, явно сформованим у визначенні синтаксису мови.
В даній курсовій роботі синтаксичний аналіз можна виконувати лише після виконання лексичного аналізу, він являється окремим етапом трансляції.
На вхід даного синтаксичного аналізатора подається файл з лексемами, який був сформований на попередньому етапі трансляції. Крім цього, на базі цього файлу здійснюється формування таблиці ідентифікаторів.
В кінці роботи аналізатора у файл виводиться список знайдених помилок, чи генерується повідомлення про їх відсутність.
Опис синтаксичного аналізатора
В даному курсовому проекті реалізовано синтаксичний аналізатор, який вирисовує метод операторного передування.
Він заснований на аналізі пар послідовно розташованих операторів вихідної програми та вирішенні питання про те, який з них повинен виконуватися першим.
Розглянемо, наприклад, арифметичне вираження А + В * З - D
У відповідності зі звичайними правилами арифметики множення і ділення здійснюються до додавання і віднімання. Можна сказати, що множення і ділення мають більш високий рівень передування, ніж додавання і віднімання. При аналізі перших двох операторів (+ і *) з'ясується, що оператор + має більш низький рівень передування, ніж оператор *. Часто це записують наступним чином + <• *
Аналогічно для наступної пари операторів (* і -) оператор * має більш високий рівень передування, ніж оператор -. Ми можемо записати це у вигляді * •> -
Метод операторного передування використовує подібні відносини між операторами для управління процесом граматичного розбору. Зокрема, для розглянутого арифметичного виразу ми отримали наступні відносини передування: A + B * C-D <• •> Звідси випливає, що підвираз В * С повинно бути обчислене до обробки будь-яких інших операторів аналізованого виразу. У термінах дерева граматичного розбору це означає, що операція * розташована на більш низькому рівні вузлів дерева, чим операції + або -. Таким чином, розглянутий метод граматичного розбору повинен розпізнати конструкцію В * С, інтерпретуючи її в термінах заданої граматики, до аналізу сусідніх термів пропозиції.
У рамках цього методу аналізоване пропозицію сканується зліва направо до тих пір, поки не буде знайдено підвираз, оператори якого мають більш високий рівень передування, ніж сусідні оператори. Далі це підвираз розпізнається в термінах правил виведення використовуваної граматики. Цей процес продовжується до тих пір, поки не буде досягнутий корінь дерева, що і буде означати закінчення процесу граматичного розбору.
/
Рис.3.3. блок-схема роботи синтаксичного аналізатора
Повне дерево граматичного розбору
Дерево граматичного розбору є дерево, де:
Корінь початку позначається символом G
Внутрішні вузли є нетерміналов G
Листки є термінальними символами G .
Дітям вузла T (зліва направо) відповідає символ на правій стороні деякої представлення для T в G. [5]
Кожен рядок терміналу, породжений граматикою має відповідне дерево розбору, кожне дерево розбору є рядком породженого граматикою (так званий вихід з дерева розбору).
На основі дерева розбору аналізується черговий набір послідовних лексем та викликається відповідна генерація асемблерного коду.
/
Рис.3.4 повне дерево граматичного розбору
Розробка генератора коду
Генерація коду – це машинно-залежний етап компіляції, під час якого відбувається побудова машинного еквівалента вхідної програми. Зазвичай входом для генератора коду служить проміжна форма представлення програми, а на виході може з’являтися об’єктний код або модуль завантаження.[5]
Генерація коду – остання фаза на якій на базі оптимізованого проміжного представлення генерується об’єктна програма.[1] На цьому етапі вирішують такі проблеми як:
розподіл імен;
розподіл пам'яті, тобто відображення імен вихідної програми в адреси пам'яті;
розподіл регістрів, тобто визначення для кожної точки програми змінні, які повинні знаходитись в регістрах;
Генератор асемблерного коду приймає масив лексем без помилок. Якщо на двох попередніх етапах виявлено помилки, то ця фаза не виконується.
В даному курсовому проекті генерація коду реалізується як окремий етап. Можливість його виконання є лише за умови, що попередньо успішно виконався етап синтаксичного аналізу. І використовує результат виконання попереднього аналізу, тобто два файли: в перший в якому міститься з генерований асемблерний код відповідно операторам які були в програмі, другий файл містить таблицю змінних. Інформація з них зчитується в відповідному порядку, основні константні конструкції записуються в файл asm, для цього щоб це робити використовуються константи текстові.
Опис генератора коду
У компілятора, реалізованого в даній курсовій роботі, вихідна мова - програма на мові Assembler. Ця програма записується у файл, що має таку ж саму назву, як і файл з вхідним текстом, але розширення “asm”. Генерація коду відбувається одразу ж після синтаксичного аналізу.
В даному трансляторі генератор коду послідовно викликає окремі функції, які записують у вихідний файл частини коду.
BeginASMFile();Записує код заголовку програми.
PrintData(f);Записує сегмент даних (визначені змінні та службові буфери та змінні),
BeginCodeSegment();Записує код ініціалізації сопроцесора.
PrintCode(f);Записує сегмент коду.
PrintEnding(f);Записує завершення програми та необхідні процедури.
void BeginASMFile(); - записує до вихідного файлу стандартну „шапку”;
void BeginCodeSegm();- записує до вихідного файлу стандартний початок сегменту коду;
void CheckPresentInputOutput();- перевіряє наявність в коді операторів вводу-виводу;
void CodeGenerator(FILE*); - за таблицями ідентифікаторів та лексем генерує вихідний код на мові асемблера;
int ConvertToPostfixForm(int); - перетворює вирази в постфіксну форму;
void GenASMCode(const char *, FILE*); - генерує код для окремих операцій;
void PrintData(FILE*); - видруковує в вихідний файл сегмент коду, який крім введених змінних за умови присутності операторів вводу/виводу (CheckPresentInputOutput();) і службову інформацію для них та додаткові буфери;
void PrintCode(FILE*); - видруковує в вихідний файл основний код програми;
void PrintAND(FILE*); - видруковує в вихідний файл процедуру ltAnd;
void PrintOR(FILE*); - видруковує в вихідний файл процедуру ltOr;
void PrintNOT(FILE*); - видруковує в вихідний файл процедуру ltNot;
void PrintEQ(FILE*); - видруковує в вихідний файл процедуру ltEq;
void PrintGE(FILE*); - видруковує в вихідний файл процедуру ltGreate;
void PrintLE(FILE*); - видруковує в вихідний файл процедуру ltLess;
void PrintMOD(FILE*); - видруковує в вихідний файл процедуру ltMod;
void PrintEnding(FILE*); - видруковує в вихідний файл стандартне завершення *.asm-файлу;
void PrintInput(FILE*); - видруковує в вихідний файл процедуру вводу;
void PrintOutput(FILE*); - видруковує в вихідний файл процедуру виводу;
bool Prioritet(LexemType,StackType); - перевіряє пріорітет операцій (використовується при перетворенні виразу у посифіксну форму).
Опис інтерфейсу та інструкція користувачеві
Створений транслятор є DOS програмою, що запускається з командної стрічки з параметром, а саме - іменем вхідного файлу, в якому записана програма на вхідній мові. Файл повинен мати розширення .S21 . Отже формат введення повинен бути таким:
CWork_S21.exe input.s21
У випадку некоректного введення програма видасть повідомлення про помилку і завершить своє виконання.
Якщо коректно введене ім’я вхідного файлу та вдалось його відкрити, то транслятор почне його опрацювання. Початковою фазою обробки є лексичний аналіз (розбиття на окремі лексеми), наступною - перевірка на правильність написання програми (вхідної). У випадку, коли виявлені помилки, транслялятор видасть повідомлення про їхню присутність, вкаже в якому файлі можна ці помилки переглянути та завершить своє виконання. Якщо ж програма написана вірно, то транслятор перейде на наступну фазу семантичного розбору та генерації асемблерного коду та вкаже ім’я результуючого файлу з розширенням .asm та завершить своє виконання.
Для отримання виконавчого файлу необхідно скористатись програмами tasm.exe filename.asm для компіляції та tlink filename.obj для лінкування.
Відлагодження та тестування програми
Тестування івідлагодження програм – це спосіб покращення якості продукту. По своїй суті відлагодження – це спосіб виявлення дефектів у програмі. Важливо пам’ятати, що якість продукту повинна бути закладена від початку розробки: найкращий спосіб створити хороший, якісний продукт – це добре проаналізувати вимоги, вдало продумати архітектуру і застосувати дієву практику написання програмного коду. В цьому випадку відлагодження є останнім виходом.
Відлагодження та тестування компілятора проводиться з використанням кількох вхідних програм з навмисне введеними помилками та з коректною програмою для загальної перевірки роботи транслятора.
Виявлення лексичних помилок
Виявлення лексичних помилок відбувається на стадії лексичного аналізу. Під час розбиття вхідної програми на окремі лексеми відбувається перевірка чи відповідає вхідна лексема граматиці. Якщо ця лексема є в граматиці то вона ідентифікується і в таблиці лексем визначається. У випадку неспівпадіння лексемі присвоюється тип "невідомої лексеми". Повідомлення про такі помилки можна побачити лише після виконання процедури перевірки таблиці лексем, яка знаходиться в файлі.
Текст програми з лексичними помилками в вхідній програмі, а також вмістиме файлу з повідомленнями про стан таблиці лексем при цьому наведено в додатку Б.
Виявлення синтаксичних помилок
Виявлення синтаксичних помилок відбувається на стадії перевірки програми на коректність окремо від синтаксичного аналізу. При цьому перевіряється окремо кожне твердження яке може бути або виразом, або оператором (циклу, вводу/виводу), або оголошенням, та перевіряється структура програми в цілому.
Текст програми з синтаксичними помилками в вхідній програмі, а також вмістиме файлу з повідомленнями про стан таблиці лексем при цьому наведено в додатку В.
Загальна перевірка коректності роботи транслятора
Для того щоб здійснити перевірку коректності роботи транслятора необхідно завантажити коректну до заданої вхідної мови програму (текст такої програми наведено в Додатку Г).
Оскільки дана програма відповідає граматиці то результати виконання лексичного, синтаксичного аналізів, а також генератора коду будуть позитивними.
В результаті буде отримано асемблерний файл, який є результатом виконання трансляції з заданої вхідної мови на мову Assembler даної програми (його вміст наведений в Додатку Г).
Після виконання компіляції і лінкування даного файлу на виході отримаєм наступний результат роботи
07.02.2013 20:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора