Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка системних програмних модулів та компонент систем програмування. Розробка транслятора з вхідної мови програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Інші
Предмет:
Системне програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет "Львівська Політехніка"
Кафедра ЕОМ
/
Пояснювальна записка
до курсової роботи
з предмету: "Системне програмування"
на тему:"Розробка системних програмних модулів та компонент систем програмування. Розробка транслятора з вхідної мови програмування"
Анотація
Завдання, яке виконується в даному курсовому проекті є розробка транслятора вхідної мови програмування. Транслятор розроблений за допомогою мови програмування С++, на основі програмного продукту “Visual Studio 2010”, в якому використовується стандартний набір користувацького інтерфейсу на основі компонентів пакету “.Net Framework”, який значно спрощує процес тестування, відлагодження та редагування програми.
У пояснювальній записці подано опис кожного етапу написання транслятора, структурні схеми, які дають змогу краще зрозуміти призначення кожного етапу, та взаємозв’язок між ними. Для перевірки на коректність комплексу виконаних робіт наводяться тестові програми, які демонструють основні можливості даної мови програмування.
Зміст
Анотація ------------------------------------------------------------------------------------ 2
Зміст -------------------------------------------------------------------------------------------3
Завдання --------------------------------------------------------------------------------------4
Вступ ------------------------------------------------------------------------------------------5
1.Огляд методів та способів проектування трансляторів --------------------------6
2. Формальний опис вхідної мови програмування ----------------------------------11
2.1. Деталізований опис вхідної мови на термінах розширеної нотації мови
Опису Бекуса-Наура---------------------------------------------------------------------12
2.2. Опис термінальних символів та ключових слів ------------------------------13
3. Розробка транслятора вхідної мови---------------------------------------------------15
3.1. Вибір технології програмування--------------------------------------------------15
3.2. Проектування таблиць транслятора ---------------------------------------------17
3.3. Розробка лексичного аналізатора ------------------------------------------------19
3.3.1.Розробка граф-схеми аналізатора---------------------------------------------20
3.3.2.Опис програми реалізації лексичного аналізатора -----------------------21
3.4.Розробка синтаксичного та семантичного аналізатора-----------------------21
3.4.1 Розробка граф-схеми алгоритму-----------------------------------------------21
3.4.2. Опис п-ми реалізації синтаксичного та семантичного аналізатора—23
3.5.Розробка генератору коду-------------------------------------------------------------25
3.5.1. Розробка граф-схеми генератора------------------------------------------------25
3.5.2. Опис програми реалізації генератора коду ----------------------------------26
4.Опис інтерфейсу та інструкції для користувача-------------------------------------28
5.Відлагодження та тестування програми-----------------------------------------------31
5.1. Виявлення лексичних помилок----------------------------------------------------31
5.2. Виявлення синтаксичних помилок------------------------------------------------32
5.3. Виявлення семантичних помилок-------------------------------------------------32
5.4. Загальна перевірка роботи коректності транслятора--------------------------33
Висновок---------------------------------------------------------------------------------------34
Список літератури----------------------------------------------------------------------------35
Завдання на курсову роботу
Цільова мова транслятора асемблер (iх86).
Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами tasm і tlink.
Мова розробки транслятора: ANSI C або C++.
Реалізувати оболонку або інтерфейс з командного рядка.
На вхід розробленого транслятора має подаватися текстовий файл, написаний на заданій мові програмування.
На виході розробленого транслятора мають створюватись чотири файли:
файл з повідомленнями про помилки (або про їх відсутність);
файл на мові асемблера;
об’єктний файл;
виконавчий файл.
Назва вхідної мови програмування утворюється від першої букви у прізвищі студента та останніх двох цифр номера його варіанту. Саме таке розширення повинні мати текстові файли, написані на цій мові програмування. Для мого варіанту це буде .k36
Деталізований опис вхідної мови
тип даних: знакове ціле (int_2(short))
регістр ключових слів: Low
регістр ідентифікаторів: Low-Up4 перший символ _
арифметичні операції: add; sub; *; /; %
операції порівняння eq; ne; >; <
логічні операції: !; and; or
оператор присвоєння: <-
блок тіла програми: mainprogram start data…; end
коментар: #*…*#
оператор циклу: if – goto; goto (Бейсік)
оператори вводу/виводу: input output
Вступ
Незважаючи на більш ніж піввікову історію обчислювальної техніки, формально роком народження теорії трансляторів можна вважати 1957, коли з’явився перший транслятор мови Фортан, створений Бекасом. До цього часу створення трансляторів було досить ‘творчим’ процесом. Лише поява теорії формальних мов і строгих математичних моделей дозволило перейти від ‘творчості’ до ‘науки’.
Саме завдяки цьому стала можливим поява сотень нових мов програмування. Більше того, формальна теорія трансляторів дала новий стимул розвитку математичної лінгвістики і методам штучного інтелекту, пов’язаних із природними і штучними мовами. Основу теорії трансляторів становить теорія формальних мов – досить складними, насиченими термінами, визначеннями, математичними моделями і іншими формалізмами розділ математики.
Отже, транслятори є невід’ємною частиною будь-якої обчислювальної системи – без них нам довелося б усе програмувати на автокоді або навіть у машинних командах. Тому транслятори стали важливою практичною областю наукових досліджень, пов’язаних з обчислювальними машинами.
Огляд методів та способів проектування трансляторів
Транслятор - обслуговуюча програма, що перетворює вхідну програму, надану вхідною мовою програмування, у робочу програму, представлену об'єктною мовою.[2]
Наведене визначення відноситься до всіх різновидів транслюють програм. Однак у кожної з таких програм можуть бути свої особливості щодо організації процесу трансляції. В даний час транслятори поділяються на три основні групи: асемблери, компілятори та інтерпретатори.
Асемблер - системна обслуговуюча програма, що перетворює символічні конструкції в команди машинної мови. Специфічною рисою асемблерів є те, що вони здійснюють дослівну трансляцію однієї символічної команди в одну машинну. Таким чином, мова асемблера (ще називається автокодом) призначена для полегшення сприйняття системи команд комп'ютера і прискорення програмування в цій системі команд.[3]
Компілятор - це обслуговуюча програма, що виконує трансляцію на машинну мову програми, записаною вхідною мовою програмування. Також як і асемблер, компілятор забезпечує перетворення програми з однієї мови на іншу (найчастіше, у мову конкретного комп'ютера). Разом з тим, команди вхідної мови значно відрізняються по організації і потужності від команд машинної мови. Існують мови, у яких одна команда вхідного мови транслюється в 7-10 машинних команд. Однак є і такі мови, у яких кожній команді може відповідати 100 і більше машинних команд (наприклад, Пролог). Крім того, у вхідних мовах досить часто використовується строга типізація даних, здійснювана через їхній попередній опис. [3]
Інтерпретатор - програма або пристрій, що здійснює по-операторну трансляцію і виконання вхідної програми. На відміну від компілятора, інтерпретатор не породжує на виході програму на машинній мові. Розпізнавши команду вхідної мови, він одразу виконує її. Як у компіляторах, так і в інтерпретаторах використовуються однакові методи аналізу вхідного тексту програми. Але інтерпретатор дозволяє почати обробку даних після написання навіть однієї команди. Це робить процес розробки і налагодження програм більш гнучким. Крім того, відсутність вихідного машинного коду дозволяє не "засмічувати" зовнішні пристрої додатковими файлами, а сам інтерпретатор можна досить легко адаптувати до будь-яких машинних архітектур, розробивши його тільки один раз на широко розповсюдженній мові програмування. [3]
Емулятор - програма або програмно-технічний засіб, що забезпечує можливість без перепрограмування виконувати на даній ЕОМ програму, що використовує коди чи способи виконання операцій, відмінні від даної ЕОМ. Емулятор схожий на інтерпретатор тим, що безпосередньо виконує програму, написану на деякій мові. Однак, частіше за все, це машинна мова або проміжний код. І той і інший представляють команди в двійковому коді, які можуть виконуватися одразу після розпізнавання коду операцій. На відміну від текстових програм, не потрібно розпізнавати структуру програми, виділяти операнди.
Кодувач - програма або програмний пристрій, що переводить програми, написані машинною мовою однієї ЕОМ до програм на машинній мові іншої ЕОМ. Якщо емулятор є менш інтелектуальним аналогом інтерпретатора, то кодувач виступає в тій же якості по відношенню до компілятора. Точно так вихідний (і зазвичай двійковий) машинний код або проміжне уявлення перетворюються в інший аналогічний код по одній команді і без будь-якого загального аналізу структури вихідної програми. Кодувачі бувають корисні при переносі програм з одних комп’ютерних архітектур на інші. Вони можуть також використовуватися для відновлення тексту програми на мові високого рівня з наявного бінарного коду.[3]
Макропроцесори - програма, що забезпечує заміну однієї послідовності символів іншою. Це різновид компілятора. Він здійснює генерацію вхідного тексту шляхом обробки спеціальних вставок, які розташовуються у вихідному тексті. Ці вставки оформлюються спеціальним способом і належать конструкції мови, яка називається макромовою.
Макропроцесори підвищують ефективність програмування без зміни синтаксису і семантики мови.
Синтаксис - сукупність правил деякої мови, що визначають формування її елементів. Інакше кажучи, це сукупність правил семантично-значущих послідовностей символів в даній мові. Синтаксис задається за допомогою правил, які описують поняття деякої мови. Прикладами понять є: змінна, вираз, оператор, процедура. [5]
Семантика - правила та умови, що визначають співвідношення між елементами мови та їх смисловими значеннями, а також інтерпретацію змістовного значення синтаксичних конструкцій мови. Об'єкти мови програмування не тільки розміщуються в тексті у відповідності з певною ієрархією, а й додатково пов'язані між собою.[5]
Всі мови програмування мають ряд загальних характеристик і параметрів. Ця одноманітність і визначає схожі для всіх мов принципи організації трансляторів.
Мови програмування призначені для полегшення програмування. Тому їхні оператори та структури даних більш потужні, ніж в машинних мовах.
Для підвищення наочності програм замість числових кодів використовуються символічні або графічні представлення конструкцій мови, більш зручні для їх сприйняття людиною.
Для будь-якої мови визначається:
набір символів, які можна використовувати для запису правильних програм (алфавіт), основні елементи.
Набір правильних програм (синтаксис).
"Сенс" кожної правильної програми (семантика).
Незалежно від специфіки мови будь-який транслятор можна вважати функціональним перетворювачем F, що забезпечує однозначне відображення X в Y, де X - програма мовою оригіналу, Y - програма на вихідній мові.
З огляду на схожість компілятора й інтерпретатора, розглянемо фази, що існують в компіляторі. У них виділяються:
Фаза лексичного аналізу.
Фаза синтаксичного аналізу, що складається з:
а) розпізнавання синтаксичної структури;
б) семантичного аналізу, в процесі якого здійснюється робота з таблицями, породження проміжного семантичного представлення або об'єктної моделі мови.
Фаза генерації коду, що здійснює:
а) семантичний аналіз компонентів проміжного представлення або об'єктної моделі мови;
б) переклад проміжного представлення або об'єктної моделі в об'єктний код.
Поряд з основними фазами процесу трансляції можливі також додаткові фази:
Фаза дослідження та оптимізації проміжного представлення, що складається з:
а) аналізу коректності проміжного представлення;
б)оптимізації проміжного представлення.
Фаза оптимізації об’єктного коду.
Структура компілятора, яка враховує існуючі в ньому фази, представлена на рис. 1.1:
/
Рис. 1.1 - Структура компілятора
Він складається з лексичного аналізатора, синтаксичного аналізатора, генератора коду, аналізатора помилок. В інтерпретаторі замість генератора коду використовується емулятор, до якого, крім елементів проміжного представлення, передаються вихідні дані.
Формальний опис вхідної мови програмування
Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
Однією з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування. Для цього використовують різні способи формального опису, серед яких я застосував розширену нотацію Бекуса-Наура.
<програма>
::= mainprogram <назва> start data {int_2<змінні>}; <блок коду> end
< назва>
::= <буква> {< символ>}
<змінні>
::= <змінна>|(<змінна> {, <змінна>});
<змінна>
::= _<буква><буква><буква><буква>
<м_буква>
::= 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
<в_буква>
::= 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
<цифра>
::= 0|1|2|3|4|5|6|7|8|9
<символ>
::= +|-|*|/|\|`|”|.|,|;|:|!|(|)|#|?|<цифра>|<ціле>
<буква>
::=<в_буква>|<м_буква>
<ціле>
::= [+|-]<цифра>{<цифра>}
<адитивна операція>
::= add|sub
<мультиплікативна операція>
::=*|/|%
<логічна операція>
::=!|and|or
<операнд>
::= <змінна>|<ціле>
<оператор порівняння>
::= eq|ne|>|<
<оператор присвоєння>
::= <змінна><-<вираз>
<оператор виводу>
::= output([<string>] <змінна>|<ціле>);
<оператор вводу>
::= input(<змінна>);
<string>
::= “{<символ>|<знак>}”
<цикл>
::=[if(<умова>)] goto start <блок коду> end;
<умова >
::=[!]<операнд><оператор порівняння><операнд>|true|false
<блок коду>
::=[start]{<вираз>|<оператор вводу>|<оператор виводу>|<цикл>;}[end;]
<доданок>
::=<операнд>|<операнд>{<мультиплікативна операція><операнд>}
<вираз>
::=<доданок>|<доданок>{<адитивна операція><доданок>}
<булеві вирази>
::= [!]<вираз>|(<вираз><логічна операція><вираз>)
Опис термінальних символів та ключових слів
Визначимо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):
mainprogram – початок тексту програми, наступним описується імя програми;
start – початок тіла програми блоку;
data - блок опису змінних;
; - ознака кінця оператора;
end - кінець тіла програми (циклу);
input – оператор вводу змінних;
output – оператор виводу (змінних і рядкових констант);
<- - оператор присвоєння;
if – goto; goto - цикл;
add – операція додавання;
sub – операція віднімання;
* - операція множення;
/ - операція ділення;
% - операція остачі від ділення;
eq – перевірка чи рівне;
ne – перевірка чи не дорівнює;
> - перевірка чи більше;
< - перевірка чи менше;
! – операція логічного заперечення;
and – логічна операція “I”;
or - логічна операція “АБО”
int_2 - тип даних;
#*…*# - коментар;
, - розділювач між деклараціями змінних;
( - відкриваюча дужка;
) – закриваюча дужка;
До термінальних символів віднесемо також усі цифри (0-9), латинські букви (a-z, A-Z), символи табуляції,символ переходу на нову стрічку, пробілу, знаку "-".
3. Розробка транслятора вхідної мови
Створення трансляторів є одною з невід’ємних частин системного програмного забезпечення. Транслятор розроблений в даній курсовій роботі працює за схемою поданою в додатку Б. Він включає в себе три головні фази:
лексичний аналіз
синтаксичний аналіз
генерація коду
Також тут реалізоване збереження проміжних результатів роботи: списку лексем, ідентифікаторів, міток, проміжного представлення мови. При виявлені помилок вони також додатково зберігаються в файл.
3.1 Вибір технології програмування
Для розробки транслятора вхідної мови програмування було вибрано обєктно орієнтовану технологію програмування під платформу .NET.
Використання технології ООП полягає у розробці окремих, не пов'язаних між собою класів і використанні їх як необхідних програмісту базових типів даних, відсутніх у мові. При цьому загальна структура програми залишається традиційною. Об'єктно-орієнтоване програмування (ООП) це сукупність понять (клас, об'єкт, інкапсуляція, поліморфізм, наслідування), прийомів їх використання при проектуванні програм, а Сі++ інструмент цієї технології. Суворе дотримання технології ООП припускає, що будь-яка функція в програмі представляє собою метод для об'єкта деякого класу. Це не означає, що потрібно вводити в програму які потрапило класи заради того, щоб написати необхідні для роботи функції. Навпаки, клас повинен формуватися в програмі природним чином, як тільки в ній виникає необхідність опису нових фізичних предметів або абстрактних понять (об'єктів програмування). З іншого боку, кожен новий крок у розробці алгоритму також повинен представляти собою розробку нового класу на основі вже існуючих. Врешті-решт уся програма в такому вигляді являє собою об'єкт деякого класу з єдиним методом run (виконати). Саме цей перехід (а не поняття класу і об'єкту, як такі) створює психологічний бар'єр перед програмістом, яке освоює технологію ООП. Програмування "від класу до класу" включає в себе ряд нових понять.
Перш за все, це - інкапсуляція даних, тобто логічне зв'язування даних з конкретною операцією. Інкапсуляція даних означає, що дані є не глобальними - доступними всій програмі, а локальними - доступними тільки малої її частини. Інкапсуляція автоматично має на увазі захист даних. Для цього в структурі class використовується специфікатор розділу private, що містить дані і методи, доступні тільки для самого класу. Якщо дані і методи містяться в розділі public, вони доступні ззовні класу. Розділ protected містить дані і методи, доступні з класу і будь-якого його похідного класу. Наявність останніх дозволяє говорити про ієрархію класів, де є класи - батьки - шаблони для створення класів - нащадків. Об'єкти, отримані з опису класу, називають екземплярами цього класу.
Другим по значущості поняттям є наслідування. Новий, або похідний клас може бути визначений на основі вже наявного, або базового. При цьому новий клас зберігає всі властивості старого: дані об'єкта базового класу включаються в дані об'єкта похідного, а методи базового класу можуть бути викликані для об'єкта похідного класу, причому вони будуть виконуватися над даними включеного в нього об'єкта базового класу. Інакше кажучи, новий клас успадковує як дані старого класу, так і методи їх обробки. Якщо об'єкт успадковує свої властивості від одного батька, то говорять про одиночному успадкування. Якщо ж об'єкт успадковує атрибути від декількох базових класів, то говорять про множинне успадкування. Третім за значимістю поняттям є поліморфізм. Він грунтується на можливості включення в дані об'єкта також і інформації про методи їх обробки (у вигляді вказівників на функції). Принципово важливо, що такий об'єкт стає "самодостатнім". Будучи доступним в деякій точці програми, навіть при відсутності повної інформації про його тип, він завжди може коректно викликати властиві йому методи. Поліморфної називається функція, незалежно визначена в кожному з групи похідних класів і має у них спільне ім'я.
Цільовою мовою програмування було обрано Microsoft C#. Дана мова програмування широко використовується для розв’язання задач різного рівня складності. Перевагами даної мови порівняно з іншими є широкий набір бібліотек класів для роботи з стрічками, регулярними виразами, файлами, різноманітними структурами даних: список, словник, стек, черга. Також дана мова забезпечує високу гнучкість і відносну простоту побудови користувацького інтерфейсу, взаємодії з файловою системою комп’ютера.
3.2 Проектування таблиць транслятора та вибір структур даних
Транслятор в даній роботі представлено класом Translator, який інкапсулює в собі дані та методи потрібні для роботи програми. До методів відноситься лексичний, синтаксичний аналізатор, генератор коду, методи для збереження проміжних даних у файл, процедури для перевірки операторів мови. До даних відносяться регулярні вирази для лексичного аналізу, таблиця змінних, таблиця міток, таблиця стрічок, таблиця помилок, таблиця лексем, таблиця результатів синтаксичного аналізу. Для зберігання таблиць обрано стандартну структуру даних список, так як вона дозволяє легко працювати з даними різного типу, підтримує індексацію (можна працювати так як з масивом), містить багато готових методів для пошуку вставки, заміни. Окремі складові елементи таблиці представлені кожна своїм класом.
Клас lex містить у собі структуру в якій містяться змінні типу string в яких записані наші символьні представлення токенів. Це зроблено для того, щоб спростити виправлення токенів та зробити проект легшим для його модифікації та реалізації нових версій. Завдяки цьому ми легко можем доповнити нашу програму новими лексемами та швидко виявити помилки.
Основні методи даного класу описані в таблиці 3.1
Таблиця 3.1. Опис методів і полів класу Lex
Клас містить наступні поля:
Token
поле задане структурою tokens і однзначно ідентифікує кожну лексему.
str_input
поле задає стрічку яка представляє лексему в тексті програми
str_output
поле задає посилання на таблицю міток, ідентифікаторів, стрічок, якщо лексема має відповідний тип
Клас містить наступні методи:
Lex
Конструктор класу, який відповідає за створення об’єкту і ініціалізацію полів структури
Клас Form1 містить в собі змінні та методи для функціонування компілятора, а саме функції для звязування ядра програми та інтерфейсу за допомогою тимчасових файлів, та каскадного створення нових проектів, які відбуваються у прихованому режимі. Опис аргументів для даних процесів описані у файлах сценарію, а саме файли Детальний опис полів і методів подано в таблиці 3.2.
Таблиця 3.2. Опис методів і полів класу Form1
Клас містить наступні поля:
Tokens
В дане поле записуються утворені токени
path
поле задає шлях до папки з проектом
Filename
Вказує назву створюваного файлу
Token_table
Таблиця токенів
Клас містить наступні методи:
Gen_tokens
Створює таблицю токенів
Del_spaces
Метод, що використовується для видалення пробілів та знаків табуляції
Del_comments
Метод,що видаляє коментарі
Клас TextLiteral представляє кожний конкретний текстовий літерал в програмі. Містить методи для генерації асемблерного коду оголошення літералу, отримання унікального імені літералу для генератора коду. Детальний опис полів і методів подано в таблиці 3.3.
Таблиця 3.3. Опис додаткових методів
Додаткові методи, що використовуються:
IsOperation
Метод, що перевіряє рядок на належність до операції
IsExpression
Метод, що перевіряє чи рядок є виразом
Balans
Цей метод перевіряє баланс дужок у виразі
ErrorChecking
Перевіряє код на наявність помилок, та відповідно їх класифікує
Таблиця 3.4 Опис методів класу newfile
Isopen
Повертає значення того, чи відкрити форма
Directory
Тут записано шлях вибраної директорії
InitialDirectory
Шлях початкової директорії
FileName
Назва створеного файлу
Перечислення Lexems представляє кожнен тип лексеми унікальним номером. В таблиці 3.6 подані усі існуючі типи лексем і означення до кожного типу.
Таблиця 3.6. Список усіх можливих лексем
Лексема
Означення
Лексема
Означення
BODYSTART
Початок блоку
ABOWE
Більше ніж
PRSTART
Почакток програим
BELOW
Менше ніж
DATASTART
Оголошення змінних
NOT
Логічне Не
BODYEND
Кінець блоку
AND
Логічне І
IN
Оператор вводу
OR
Логічне АБО
OUT
Оператор виводу
Assign
Оператор присвоювання
FOR
Початок циклу
COMMA
Кома
TO
Закінчення циклу
LBRACKET
Відкриваюча дужка
MOD
Остача від ділення
EQ
Ріно
NEQ
Не рівно
ID
Змінна
TYPE
Тип даних
CONST
Числовий літерал
ADD
Додавання
STRING
Стрічковий літерал
SUB
Віднімання
RBRACKET
Закриваюча дужка
MUL
Множення
ENDLINE
Крапка з комою
3.3 Розробка лексичного аналізатора
Лексичний аналізатор є першою фазою компілятора. Основна задача лексичного аналізу – розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів для передачі в синтаксичний аналізатор. Всі символи вхідної послідовності розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.
3.3.1 Розробка граф-схеми алгоритму
Алгоритм лексичного аналізу базується на використанні засобів регулярних виразів. При цьому за допомогою регулярних виразів задаються правила виділення лексем, ідентифікаторів, міток з подальшим утворенням таблиці лексем і ідентифікаторів. Процес задання правил виділення лексем є достатньо простим і надзвичайно гнучким. Розбір виконується взалежності від правила виділення лексеми, заданого регулярним виразом, при чому ними можна виділити не лише базові одиниці мови, але й коментарі, пробільні символи і навіть лексичні помилки.
/
Рис. 1. Алгоритм лексичного аналізу.
3.3.2 Опис програми реалізації лексичного аналізатора
Для виділення лексем використовуються правила задані регулярними виразами. Вхідна програма проглядається послідовно з початку. Початок тексту аналізується на відповідність певному регулярному виразові (блоки 5, 6, 7, 8, 9). При співпадінні виділена лексема записується при необхідності в таблицю лексем, змінних, стрічок чи генерується помилка і видаляється з початку тексту (блоки 10-18). Так повторюється доки вхідний текст не стане порожнім (блок 3).
При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись до лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо місця розташування відповідної лексеми у вхідному тексті (для локалізації місця помилки) та інша додаткова інформація.
При лексичному аналізі виявляються i відзначаються лексичні помилки (наприклад, недопустимі символи i неправильні iдентифiкатори). Лексична фаза відкидає також i коментарі, пробільні символи оскільки вони не мають ніякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.
3.4 Розробка синтаксичного та семантичного аналізатора
Першим етапом синтаксичного аналізу є синтаксичний розбір. На етапі його виконання підтверджується то, що вхідний ланцюжок лексем є програмою, а окремі лексеми складають синтаксично правильні програмні об'єкти. Розбір призначений для перевірки того, чи ланцюжок відповідає певному правилу з сукупності правил визначеної граматикою. Синтаксичний розбір виконується методом рекурсивного спуску. Якщо на будь-якому рівні ланцюжок не відповідає ніякому правилу,то ми дістанемо помилку.
Основним завданням семантичного аналізатора є перевірка типів, ініціалізації змінних. Сама програма перевірки типів базується на інформації про синтаксичні конструкції мови, представлення типів і правилах присвоєння типів конструкціям мови.
3.4.1 Розробка граф-схеми алгоритму
Алгоритм синтаксичного аналізу використовує низхідний метод розбору. Для кожної конструкції мови розроблена певна процедура, яка і робить перевірку чи відповідає ланцюжок лексем певному правилу граматики. Також дані процедури формують проміжне представлення мовних конструкції для генератора коду. Спочатку перевіряється заголовок програми і розділ оголошення змінних, далі йде перевірка головного блоку і вкладених блоків. При неможливості співставити ланцюжок лексем певному правилу граматики генерується помилка.
Рис. 2. Алгоритм синтаксичного аналізу.
3.4.2 Опис програми реалізації синтаксичного та семантичного аналізатора
Для аналізу синтаксичний аналізатор отримує на вхід послідовність лексем сформовану лексичним аналізатором. Спочатку перевіряється заголовок програми (блок 2): початок головного блоку, розділ оголошення змінних, після цього відбувається перевірка коректності команд розміщених в головному блоці і вкладених блоках. Для кожної команди передбачена окрема процедура. Команди розпізнаються по черговій лексемі, відбувається зчитування ланцюжка лексем до крапки з комою. Прочитаний ланцюжок (блоки 3 - 18) передається на перевірку певній процедурі аналізу (блоки 7, 10, 14), яка проводить аналіз і при успішному завершенні формує проміжне представлення команди для генератора коду(блоки 15, 16, 17).
Проміжним представленням програми є списки лексем які представляють конкретні вирази, оператори. Вирази представлені зворотнім польським записом.
При знаходженні помилки в список помилок додається відповідний запис з інформацією про тип помилки і місце її локалізації в коді програми (блоки 11, 12, 13, 16). Список помилок є глобальним і доступним в будь-якому місці програми.
На рис. 1 зображено граф-схему роботи дерева синтаксичного розбору
/
Рис1. Дерево розбору
3.5 Розробка генератора коду
Генерація коду – це перетворення вхідної програми на деякій мові в еквівалентну програму на мові асемблер або у машинні коди. Проте, зважаючи на неможливість здійснити оцінку смислу вхідної програми загалом та існуючі обмеження мов програмування на етапі генерації коду ми ніколи не отримаємо на 100% еквівалентну програму мовою асемблер.
Генерація і оптимізація коду є завершальним етапом роботи компілятора чи транслятора. Вона виконується після виконання операцій лексичного, синтаксичного і семантичного аналізу, ідентифікації імен змінних і функцій, розподілу адресного простору для функцій і змінних.
3.5.1 Розробка граф-схеми алгоритму
Генерація коду є поетапним процесом, який відбувається на основі закінчених мовних конструкцій вхідної програми. Генератор вибирає закінчену синтаксичну конструкцію з тексту вхідної програми породжує для неї фрагмент результуючого коду і розміщує його в тексті результуючої програми. Далі береться наступна конструкція. Так відбуваться доти, доки не буде розібрана вся програма.
Рис. 3. Алгоритм генератора коду.
3.5.2 Опис програми реалізації генератора коду
Генерація коду відбувається поетапно. Генератор коду аналізує проміжне представлення (списки лексем) сформовані синтаксичним аналізом і генерує для них відповідний асемблерний код.
Спочатку генератор коду аналізує список ідентифікаторів і формує їхнє оголошення в сегменті даних (блоки 4, 6, 8). Далі відбувається подібна генерація машинного коду для списку стрічок (блоки 3, 5, 7). Після цього генератор формує заголовок машинного коду (блок 9). Далі зчитуються списки з проміжним представленням команд і формуються еквівалентні машинні інструкції (блоки 11, 13, 15). Далі в готовий асемблерний текст додаються сформовані машинні команди і код необхідних процедур (блоки 10, 12). Результати зберігаються у вихідний файл (блок 14).
Вихідна програма на машинній мові організована у вигляді готових процедур, кожна з яких відповідає за ввід/вивід результатів роботи, конкретну обчислювальну арифметичну чи логічну операцію, вивід повідомлення про помилки. Для обчислень використовується програмний стек, який представлений ділянкою пам’яті і зміщенням (вершина стеку). Даний метод має наступні переваги:
розмір стеку достатньо великий щоб уникнути помилок переповнення, як у випадку зі стеком математичного співпроцесора;
проста реалізація обчислень за допомогою готових процедур;
можливість виявлення помилок на етапі виконання:
ділення на нуль;
помилка ініціалізації змінної;
помилка переповнення;
помилка введення.
4. Опис інтерфейсу та інструкції користувачу
Підменю Файл Рис. 4. , що має наступні команди: Створити, Відкрити, Зберегти, Зберегти.
Підменю Правка Рис. 5. що має наступні команди: Вирізати, Копіювати, вставити , Очистити.
Підменю Проект Рис. 6. що має наступні команди: Генерувати, Запустити.
Підменю Довідка Рис. 7. що має наступні команди: Список команд, Про програму.
Інтерфейс містить три поля.
Поле вводу де буде міститися код заданої мови програмування Рис. 8. , Код мовою Аssembler- поле виводу згенерованого коду на мові Assembler Рис.9. і поле виводу помилок
Таблиця лексем – поле згенерованої таблиці токенів у результаті роботи лексичного аналізатора, заборажено на рисунку 10.
/
Рис. 4. Підменю Файл
/
Рис. 5. Підменю Правка
/
Рис. 6. Підменю Проект
/
Рис. 7. Підменю Довідка
/
Рис. 8. Код мовою Assembler
/
Рис. 9. Поле виводу помилок
/
Рис. 10 Поле виводу лексем
5. Відлагодження та тестування програми
Відлагодження програми відбувається в покроковому режимі в середовищі Microsoft Visual Studio 2010 з використанням точок зупинки, що дає можливість знайти місце логічної помилки. В покроковому режимі у нас є можливість прослідкувати за значеннями змінних.
Тестування програми буде відбуватися з допомогою готових прикладів на вхідній мові в яких можуть використовуватися різноманітні оператори вхідної мови, можуть бути допущені різноманітні лексичні, граматичні та синтаксичні помилки.
5.1 Виявлення лексичних помилок
На етапі лексичного аналізу виникають наступні помилки: Нерозпізнана лексема – це помилка яка може виникнути на етапі лексичного аналізу, коли лексема відповідає регулярному виразу лексичної помилки. Завеликий числовий літерал – це помилка яка може виникнути на етапі лексичного аналізу, коли числовий літерал є завеликим для типу Int_2. Коли виникає будь-яка помилка, то вона записується в глобальний список помилок Рис. 13.
При помилці виводиться повідомлення рис. 12.
Приклад програми з помилкою.
mainprogram LALA;
data
_a int_2;
start
input("Hello, world!");
outputahaha(_a);
input(_a);
end
Рис. 12 Повідомлення невдачі створення виконавчих файлів
/
Рис. 13. Список помилок
5.2 Виявлення синтаксичних помилок
На етапі синтаксичного аналізу виявляється основна кількість помилок. Ці помилки пов’язані з невірними записами конструкцій вхідної мови, незавершеність програми, неправильним форматом виразів. Всі помилки виявленні на етапі синтаксичного аналізу заносяться в таблицю помилок.
Для початку протестуємо наступний код в якому навмисно допущено помилка. Як видно з (Рис. 14. ) транслятор коректно виявляє різноманітні синтаксичні помилки.
/
Рис. 14. Програма з синтаксичною помилкою
5.3 Виявлення семантичних помилок
Основною метою семантичного аналізу є перевірка типів операндів. Оскільки згідно варіанту присутній тільки один тип integer_2, то така перевірка не буде проводитися. Виявлення семантичних помилок зводиться до перевірки того, чи змінні ініціалізовані початковими значеннями. Ця перевірка виконується на етапі виконання. Це досягається наявність додаткової інформації про ініціалізацію в сегменті коду. При виникненні такої помилки видасться повідомлення про помилку, виконання програми завершиться і вона поверне одиницю.
Синтаксично слідуючий код правильний, проте в ньму допущена семантична помилка:
04.06.2014 15:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора