4

Размещено на http://www.allbest.ru/

Міністерство освіти, науки, молоді та спорту України.

Національний університет "Львівська політехніка"

ІКТАМ

Кафедра ЕОМ

КУРСОВА РОБОТА

з дисципліни:

"Системне програмування"

на тему: "Розробка системних програмних модулів та компонент систем програмування"

Виконав:

Ст.гр. КІ-35

Жміковський Ю. С.

Перевірив: Грос В. В

Львів-2013



ЗАВДАННЯ

Варіант 30;

Розробити транслятор вхідної мови програмування , короткий опис якої подано нижче:

- тип даних: integer_4;

- арифметичні операції над цілими: add; sub; *; /; %;

- операції порівняння: =; <>; !>; !<

- операції над логічними !!; &&; ||

- символи групування арифметичних операцій: "(", ")";

- оператор присвоєння: ">>" ;

- оператори блоку: " startblok variable…; ", "endblock";

- коментар //…

- оператор циклу IF [-ELSE] (СІ)

- оператори вводу, виводу: read, write

Для отримання виконавчого файлу на виході розробленого транслятора скористатися програмами MASM32.



АНОТАЦІЯ

В даній курсовій роботі розроблено транслятор з мови Z30 на мову асемблер. Даний транслятор розроблений в середовищі програмування Visual Studio 2010. Мова програмування на якій написано проект С#. Також тут подано огляд існуючих методів розробки трансляторів, детальний опис мови, описано процес розробки програми транслятора на рівні тексту програми, граф схеми алгоритму усіх етапів трансляції. До роботи додано результати тестування програми та текст програми транслятора.

ЗМІСТ

ВСТУП

1. Огляд методів та способів проектування трансляторів

1.1 Введення в трансляцію

1.2 Структура транслятора

1.3 Проходи транслятора

1.4 Засоби побудови трансляторів

2. Формальний опис вхідної мови програмування

2.1 Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура

2.2 Термінальні символи та ключові слова

3. Розробка транслятора вхідної мови програмування

3.1 Вибір технології програмування

3.2 Проектування таблиць транслятора

3.3 Розробка лексичного аналізатора

3.4 Розробка синтаксичного аналізатора

3.5 Розробка генератора коду

4. Опис інтерфейсу та інструкція користувача

5. Відлагодження та тестування програми

5.1 Виявлення помилок

5.2 Загальна перевірка коректності роботи транслятора

ВИСНОВКИ

СПИСОК ЛІТЕРАТУРИ

Додаток A. Завдання на курсову роботу

Додаток Б. Загальний алгоритм роботи транслятора

Додаток В. Текст коректної програми на мові Z30



ВСТУП

Транслятори та компілятори є одною з невід'ємних частин системного програмного забезпечення. Одним із їх завдань є переведення написаного тексту програми у машинний код чи код іншої мови програмування, який повинен відповідати комп`ютерній системі. Оскільки теперішній час - час стрімкого розвитку комп`ютерної техніки, то створений машинний код з часом стає застарілим, тобто не відповідає принципу оптимального використання апаратних ресурсів. І одним із способів запобігання цієї проблеми стало створення нових трансляторів, які б відповідали потребам теперішнього часу.

По своїй суті транслятор - це той самий компілятор, з тією різницею, що генерую він не об'єктний код а код на іншій мові програмування. [1]

Проблема трансляції полягає в пошуку відповідності тексту вхідної програми конструкціям, що визначені граматикою. Граматика визначає форму або синтаксис допустимих виразів мови. Тому текст вхідної мови зручно подавати у вигляді послідовності лексем, що є неподільними одиницями мови. За допомогою транслятора програміст повинен мати можливість редагувати текст вхідної мови. Для цього він має виявляти всі невідповідності тексту програми конструкціям мови і у випадку відсутності помилок генерувати код.

На сьогодні існує досить багато мов програмування. Нарівні з традиційними мовами, такими, як Fortran, широке поширення отримали так звані "універсальні мови" (Паскаль, Сі, Модула-2, Ада та інші), а також деякі спеціалізовані (наприклад, мова обробки облікових структур Лісп).

Для деяких мов є досить багато реалізацій. Наприклад, реалізацій Паскаля, Модули-2 або Сі для ЕОМ типу IBM/PC на ринку десятки. З іншого боку, постійно зростаюча потреба в нових компіляторах пов'язана з бурхливим розвитком архітектури ЕОМ. Цей розвиток йде у різних напрямах. Удосконалюється стара архітектура, як в концептуальному відношенні, так і по окремих, конкретних лініях. Отже, це вимагає нових компіляторів, трансляторів (або модифікації старих).



1. ОГЛЯД МЕТОДІВ ТА СПОСОБІВ ПРОЕКТУВАННЯ ТРАНСЛЯТОРІВ

1.1. Введення в трансляцію

Транслятором називається програма перекладу (трансляції) початкової програми, записаної вхідною мовою, в еквівалентну їй об`єктну програму. Якщо мова високого рівня є вхідною, а мова асемблера чи машинна - вихідною, то такий транслятор називається компілятором. Програма, записана мовою високого рівня, найчастіше має два етапи - компіляції та виконання. На першому початкова програма перекладається машиною А в об`єктну програму мовою машини, на другому вона заноситься в пам`ять машини В. При її виконанні, за необхідності вводяться початкові дані та виводяться результати. Якщо А і В -різні машини, то говорять, що на ЕОМ А виконується крос-компіляція, і такий транслятор називається крос-компілятором.[1]

Інтерпретатором є різновид транслятора для перекладу початкової програми в програму, записану простою проміжною алгоритмічною мовою, та для її виконання. Деякі програми в проміжну форму не перекладається, а відразу виконуються. Інтерпретатор простіший від компілятора, але працює повільніше.

Транслятор з різними вхідною та об`єктною мовами високого рівня називається препроцесором. Як частина компілятора, він при бажанні може використовуватися самостійно для розширення можливостей конкретної мови програмування (наприклад мови Сі).

1.2 Структура транслятора

Компілятор - це велика за розмірами програма. Складання компілятора ділять на фази, на яких перетворюють одне зображення програми в інше. [1]

Фази лексичного (ЛА) та синтаксичного (СА) аналізів розкладають початкову програму на частини. Генерація коду проміжною мовою (ГПК), оптимізація (ОК) та генерація коду (ГК) асемблера синтезують програму на вихідній мові. Керування таблицями (КТ) та обробка помилками (ОП) використовуються на всіх фазах трансляції.

Лексичний аналіз об`єднує літери в лексеми - службові слова, ідентифікатори, знаки операцій та пунктуації. Лексеми можна кодувати цілими числами, наприклад, do-одиницею, "+" - двійкою, ідентифікатор - трійкою, константу - четвіркою тощо. До коду лексем ідентифікаторів і констант додається ще одна величина - вид чи значення лексеми.

Синтаксичний аналіз групує лексеми в синтаксичні структури, які можуть бути складовими інших синтаксичних структур; наприклад, А+В може входити в оператор чи вираз. Як рекурсивні структури даних, вони зображуються (явно чи неявно) у формі дерева з лексемами в вузлах і з позначенням синтаксичних конструкцій у внутрішніх вузлах. Крони піддерев відтворюють частини програми відповідної синтаксичної конструкції.

Необов`язкова оптимізація коду має призначенням створення проміжного коду, за якого асемблерна програма буде ефективніша.

Керування таблицями розв`язує задачу зберігання імен, використаних у програмі, інформації про них (наприклад, типу даних) та доступу до цієї інформації. Переважно використовується таблиця символів як структура даних. Обробка помилок відбувається кожного разу, коли помічені дефекти у програмі. Вона полягає у формуванні повідомлення про помилку та її нейтралізації, тобто виправленні інформації для передачі наступній фазі, щоб остання могла виконуватися. Основна мета - за одну обробку програми транслятором виявити максимум помилок.[1]



1.3 Проходи транслятора

При реалізації транслятора одна чи декілька фаз (можлива частина фази) об'єднуються в програмні модулі, названі проходами. За кожного проходу прочитується з файлу початкова програма чи результат попереднього проходу; здійснюється перетворення, задане його фазами; записується результат у проміжний або в результатний файл. Число проходів та методика об`єднання фаз у прохід визначаються особливостями вхідної та вихідної мов. Так, у мові ПЛ-1 описи даних можуть з`явитися після їхнього використання, як наприклад у групі операторів goto M; . . . ; M: a:=b+c;, де до ідентифікатора М звертаються раніше, ніж до опису. За такої ситуації скласти повністю код для оператора goto M; не можна до обробки опису М (оператора М: а:=b+c). Реалізація таких мов потребує щонайменше двох проходів.[2]. Кілька проходів можна скомбінувати в один, виконуючи їх паралельно із взаємною синхронізацією - таким чином створюється однопрохідний транслятор. Результат одного проходу, потрібний іншому, завдяки синхронізації та буферам дозволяє побудувати необхідний інтерфейс між фазами. Як правило, в однопрохідному трансляторі ведучою є фаза синтаксичного аналізу, яка кожного разу, коли потрібна їй лексема, запрошує фазу лексичного аналізу, керує генерацією проміжного коду, передає команди цього коду генератору коду для створення програми вихідною мовою. Проблеми, що виникають при використанні елемента даних раніше його означення за єдиного проходу, можна розв`язати методом оберненого заповнення: при генерації коду для команди goto M; за невизначеного М формується неповна команда і запам`ятовується її місце, а в момент визначення мітки М заповнюються всі порожні місця. Проте цей метод працює тоді, коли віддаль між точками використання та означення імені невелика.[3]

1.4 Засоби побудови трансляторів

Існують спеціальні засоби (компілятори компіляторів, генератори компіляторів тощо) для полегшення конструювання компіляторів чи трансляторів. Ідеальною вважається ситуація, коли є програма (або система програм), яка автоматично будує компілятор, маючи на вході описи лексики, синтаксису вхідної мови, результатів перетворень синтаксичних конструкцій та опис цільової машини.

Для полегшення побудови трансляторів розроблені такі основні інструментальні засоби: генератор лексичних аналізаторів, в якому інформація про лексеми задається регулярними виразами, а можливі дії обробки - операторами мови Сі; генератор, який за граматикою початкової мови створює СА з діями обробки; засоби генерації коду - спеціальні мови, зручні для опису процесу генерації вихідного коду.



2. ФОРМАЛЬНИЙ ОПИС ВХІДНОЇ МОВИ ПРОГРАМУВАННЯ

Одною з перших задач, що виникають при побудові компілятора, є визначення вхідної мови програмування.

Для цього використовують різні способи формального опису, серед яких я використаю розширену нотацію Бекуса-Наура (Backus/Naur Form - BNF).

2.1 Деталізований опис вхідної мови в термінах EBNF

Правила написання правил у розширеній нотації Бекуса-Наура:

· нетермінальні вирази записуються у кутових дужках: "<", ">" ;

· термінальні вирази записуються жирним шрифтом або у подвійних лапках;

· усі нетермінальні вирази мають бути "розкриті" за допомогою термінальних;

· символ "::=" відділяє праву частину правила від лівої;

· символ "|" розділяє альтернативи;

· символи "[", "]" означають необов'язковість (вираз в дужках може бути відсутнім);

· символи "{", "}" означають повторення.

Таблиця 2.1 Деталізований опис вхідної мови

<program>	::= startprogram startblock <declaration> {<statement>} endblock
<statement>	::= <condition> | <input> | <output>| <assign>
<declaration>	::= variable <var> [>> <number>] {,<var> [>> <number>] } integer_4;
<assign>	::= <var> >> <expression>;
<var>	::= <letter>{<letter> | <digit>}
<letter>	::= a..z
<digit>	::= 0..9
< condition >	::= if <expression> startblock {<statement>} endblock else startblock {<statement>} endblock
<number>	::= <digit> {<digit>}
<input>	::= read <var>;
<output>	::= write <var> | <string> | <num> {,<var> | <string> | <num>};
<equality>	::= =| <>
<comparison>	::= !> | !<
<addition>	::= add | sub
<multiplication>	::= * | / | %
<expression>	::= <atom> [{ || <atom> }]
<atom>	::= <eq> [{ && <eq> }]
<eq>	::= <comp> [{ <equality> <comp> }]
<comp>	::= <term> [{ <comparison> <term> }]
<term>	::= <mult> [{ <addition> <mult> }]
<mult>	::= <operand> [{ <multiplication> <operand> }]
<operand>	::= <var> | <number> | (<expression>) | !!<var> | !!<number> | !!(<expression>)

2.2 Опис термінальних символів та ключових слів

Визначаємо окремі термінальні символи та нерозривні набори термінальних символів (ключові слова):

startprogram startblock endblock variable;

add sub*/ % = <> !< !> !! && || if else ( ) , read write integer_4

До термінальних символів треба віднести також усі цифри (0..9), символ пробілу і табуляції.

Це "цеглинки", з яких має будуватися текст будь-якої вхідної програми.

Типи даних integer_4;

Арифметичні операції над числами add, sub, /, *, %;

Логічні операції =, <>, !<, !>, !!, &&, ||;

Оператор присвоєння значень змінним >> ;

Круглі дужки ( );

Оператори вводу-виводу read, write;

Оператор оголошення змінних variable;

Початок програми startprogram;

Позначення початку і кінця блоку startblock та endblock;

Оператор умови if - else;



3. РОЗРОБКА ТРАНСЛЯТОРА ВХІДНОЇ МОВИ

Створення трансляторів є одною з невід'ємних частин системного програмного забезпечення. Транслятор розроблений в даній курсовій роботі працює за схемою поданою в додатку Б. Він включає в себе три головні фази:

- лексичний аналіз

- синтаксичний аналіз

- генерація коду

Також тут реалізоване збереження проміжних результатів роботи: списку лексем, ідентифікаторів, міток, проміжного представлення мови. При виявлені помилок вони також додатково зберігаються в файл

3.1 Вибір технології програмування

Технологією програмування було обране об'єктно-орієнтоване програмування На відміну від традиційних поглядів, коли програму розглядали як набір підпрограм, або як перелік інструкцій комп'ютеру, ООП програми можна вважати сукупністю об'єктів. Відповідно до парадигми об'єктно-орієнтованого програмування, кожний об'єкт здатний отримувати повідомлення, обробляти дані, та надсилати повідомлення іншим об'єктам. Кожен об'єкт - своєрідний незалежний автомат з окремим призначенням та відповідальністю.

Цільовою мовою програмування було обрано Microsoft C#. Дана мова програмування широко використовується для розв'язання задач різного рівня складності. Перевагами даної мови порівняно з іншими є широкий набір бібліотек класів для роботи з стрічками, регулярними виразами, файлами, різноманітними структурами даних: список, словник, стек, черга. Також дана мова забезпечує високу гнучкість і відносну простоту побудови користувацького інтерфейсу, взаємодії з файловою системою комп'ютера.



3.2 Проектування таблиць транслятора та вибір структур даних

Транслятор в даній роботі представлено класом Translator, який інкапсулює в собі дані та методи потрібні для роботи програми.

До методів відноситься лексичний, синтаксичний аналізатор, генератор коду, методи для збереження проміжних даних у файл, процедури для перевірки операторів мови. До даних відносяться регулярні вирази для лексичного аналізу, таблиця змінних, таблиця міток, таблиця стрічок, таблиця помилок, таблиця лексем, таблиця результатів синтаксичного аналізу.

Для зберігання таблиць обрано стандартну структуру даних список, так як вона дозволяє легко працювати з даними різного типу, підтримує індексацію (можна працювати так як з масивом), містить багато готових методів для пошуку вставки, заміни. Окремі складові елементи таблиці представлені кожна своїм класом.

Клас Token відповідає певній лексемі, містить інформацію про її місце розташування в тексті, унікальний номер лексеми, адресу в таблицях стрічок, змінних чи міток. Детальний опис полів і методів подано в таблиці 3.1.

Таблиця 3.1. Опис методів і полів класу Token

Клас містить наступні поля:
Lexem	поле задане перечисленням enum однзначно ідентифікує кожну лексему. (див. таблицю 3.6)
Value	поле задає стрічку яка представляє лексему в тексті програми
Address	поле задає посилання та таблицю міток, ідентифікаторів, стрічок, якщо лексема має відповідний тип
Pos	поле задає положення лексеми в тексті програми
Клас містить наступні методи:
Token	Конструктор класу, який відповідає за створення об'єкту і ініціалізацію полів
ToString	Метод для представлення лексеми в текстовому вигляді
Equals	Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.



Клас Identifier представляє кожну конкретну змінну в програмі. Містить методи для генерації асемблерного коду оголошення змінних, отримання унікального імені змінної для генератора коду. Детальний опис полів і методів подано в таблиці 3.2.

Таблиця 3.2. Опис методів і полів класу Identifier

Клас містить наступні поля:
Number	поле задає число яке початково записується в змінну при ініціалізації
Value	поле задає стрічку яка представляє ім'я змінної в тексті програми
IsInitialized	Поле містить істину якщо змінна ініціалізована початковим значенням і хибу якщо початкової ініціалізації немає
IsDeclared	Поле містить істину якщо змінна оголошена і хибу якщо не оголошена
Клас містить наступні методи:
Identifier	Конструктор класу, який відповідає за створення об'єкту і ініціалізацію полів
ToString	Метод для представлення лексеми в текстовому вигляді
Equals	Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.
GetAsmName	Метод повертає стрічку яка представляє унікальне ім'я змінної для генератора коду. Базується на використанні хеш-функції.
GetAsmDef	Метод повертає стрічку яка представляє спеціальне оголошення змінної для побудови сегменту коду.

Клас TextLiteral представляє кожний конкретний текстовий літерал в програмі. Містить методи для генерації асемблерного коду оголошення літералу, отримання унікального імені літералу для генератора коду. Детальний опис полів і методів подано в таблиці 3.3.

Таблиця 3.3. Опис методів і полів класу TextLiteral

Клас містить наступні поля:
Value	поле задає стрічку яка представляє текст стрічки в програмі.
Клас містить наступні методи:
TextLiteral	Конструктор класу, який відповідає за створення об'єкту і ініціалізацію полів.
Equals	Метод для порівняння двох лексем за значеннями. Використовується для пошуку в стандартних структурах даних.
GetAsmName	Метод повертає стрічку яка представляє унікальне ім'я літералу для генератора коду. Базується на використанні хеш-функції.
GetAsmDef	Метод повертає стрічку яка представляє спеціальне оголошення літералу для побудови сегменту коду.

Клас Error представляє кожну конкретну помилку. Містить методи для видачі текстових повідомлень про помилки.

Детальний опис полів і методів подано в таблиці 3.5.

Таблиця 3.5. Опис методів і полів класу Error

Клас містить наступні поля:
Code	Поле представлене перечисленням для представлення коду помилки.
Pos1	Початкове положення помилки в тексті програми.
Pos2	Кінцеве положення помилки в тексті програми.
Клас містить наступні методи:
Error	Конструктор класу, який відповідає за створення об'єкту і ініціалізацію полів.
Equals	Метод для порівняння двох міток за значеннями. Використовується для пошуку в стандартних структурах даних.
ToString	Метод повертає стрічкове представлення помилки в залежності від коду.

Перечислення Lexems представляє кожнен тип лексеми унікальним номером.

В таблиці 3.6 подані усі існуючі типи лексем і означення до кожного типу.

Таблиця 3.6. Список усіх можливих лексем

Лексема	Означення	Лексема	Означення
Startblock	Початок блоку	Bigger	Більше ніж
Startprogram	Почакток програим	Fewer	Менше ніж
Var	Оголошення змінних	Not	Логічне Не
Endblock	Кінець блоку	And	Логічне І
Read	Оператор вводу	Or	Логічне АБО
Write	Оператор виводу	Assign	Оператор присвоювання
Do	Початок циклу	Comma	Кома
While	Кінець циклу	LBracket	Відкриваюча дужка
Error	Лексема помилкова	Equal	Рівно
Mod	Остача від ділення	Whitespace	Пробільні символи
NEqual	Не рівно	Variable	Змінна
Integer	Тип даних	Literal	Числовий літерал
Add	Додавання	String	Стрічковий літерал
Sub	Віднімання	Comment	Коментар
Mul	Множення	Colon	Двокрапка
Semicolon	Крапка з комою	RBracket	Закриваюча дужка

3.3 Розробка лексичного аналізатора

Лексичний аналізатор є першою фазою компілятора. Основна задача лексичного аналізу - розбити вихідний текст, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів для передачі в синтаксичний аналізатор. Всі символи вхідної послідовності розділяються на символи, що належать яким-небудь лексемам, і символи, що розділяють лексеми.

Розробка граф-схеми алгоритму

Алгоритм лексичного аналізу базується на використанні засобів регулярних виразів. При цьому за допомогою регулярних виразів задаються правила виділення лексем, ідентифікаторів, міток з подальшим утворенням таблиці лексем і ідентифікаторів. Процес задання правил виділення лексем є достатньо простим і надзвичайно гнучким. Розбір виконується взалежності від правила виділення лексеми, заданого регулярним виразом, при чому ними можна виділити не лише базові одиниці мови, але й коментарі, пробільні символи і навіть лексичні помилки.



Рис. 3.1. Алгоритм лексичного аналізу.

Опис програми реалізації лексичного аналізатора

Для виділення лексем використовуються правила задані регулярними виразами. Вхідна програма проглядається послідовно з початку. Початок тексту аналізується на відповідність певному регулярному виразові (блоки 5, 6, 7, 8, 9). При співпадінні виділена лексема записується при необхідності в таблицю лексем, змінних, стрічок чи генерується помилка і видаляється з початку тексту (блоки 10-18). Так повторюється доки вхідний текст не стане порожнім (блок 3).

При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись до лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора: легко перевіряти належність лексеми до відповідної синтаксичної конструкції та є можливість легкого перегляду програми, як вгору, так і вниз, від текучої позиції аналізу. Також в таблиці лексем ведуться записи, щодо місця розташування відповідної лексеми у вхідному тексті (для локалізації місця помилки) та інша додаткова інформація.

При лексичному аналізі виявляються i відзначаються лексичні помилки (наприклад, недопустимі символи i неправильні iдентифiкатори). Лексична фаза відкидає також i коментарі, пробільні символи оскільки вони не мають ніякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду.

Рис 3.2. результат побудови лексичної таблички.

3.4 Розробка синтаксичного та семантичного аналізатора

Першим етапом синтаксичного аналізу є синтаксичний розбір. На етапі його виконання підтверджується то, що вхідний ланцюжок лексем є програмою, а окремі лексеми складають синтаксично правильні програмні об'єкти.

Розбір призначений для перевірки того, чи ланцюжок відповідає певному правилу з сукупності правил визначеної граматикою. Синтаксичний розбір виконується методом рекурсивного спуску. Якщо на будь-якому рівні ланцюжок не відповідає ніякому правилу,то ми дістанемо помилку.

Основним завданням семантичного аналізатора є перевірка типів, ініціалізації змінних. Сама програма перевірки типів базується на інформації про синтаксичні конструкції мови, представлення типів і правилах присвоєння типів конструкціям мови.

Розробка граф-схеми алгоритму

Алгоритм синтаксичного аналізу використовує низхідний метод розбору. Для кожної конструкції мови розроблена певна процедура, яка і робить перевірку чи відповідає ланцюжок лексем певному правилу граматики. Також дані процедури формують проміжне представлення мовних конструкції для генератора коду. Спочатку перевіряється заголовок програми і розділ оголошення змінних, далі йде перевірка головного блоку і вкладених блоків. При неможливості спів ставити ланцюжок лексем певному правилу граматики генерується помилка.

Опис програми реалізації синтаксичного та семантичного аналізатора

Для аналізу синтаксичний аналізатор отримує на вхід послідовність лексем сформовану лексичним аналізатором. Спочатку перевіряється заголовок програми (блок 2): початок головного блоку, розділ оголошення змінних, після цього відбувається перевірка коректності команд розміщених в головному блоці і вкладених блоках. Для кожної команди передбачена окрема процедура. Команди розпізнаються по черговій лексемі, відбувається зчитування ланцюжка лексем до крапки з комою.



Рис. 3.3. Алгоритм синтаксичного аналізу.

Прочитаний ланцюжок (блоки 3 - 18) передається на перевірку певній процедурі аналізу (блоки 7, 10, 14), яка проводить аналіз і при успішному завершенні формує проміжне представлення команди для генератора коду(блоки 15, 16, 17).

Проміжним представленням програми є списки лексем які представляють конкретні вирази, оператори. Вирази представлені зворотнім польським записом. При знаходженні помилки в список помилок додається відповідний запис з інформацією про тип помилки і місце її локалізації в коді програми (блоки 11, 12, 13, 16). Список помилок є глобальним і доступним в будь-якому місці програми.



Рис 3.4. результат побудови синтаксичної таблиці.

3.5 Розробка генератора коду

Генерація коду - це перетворення вхідної програми на деякій мові в еквівалентну програму на мові асемблер або у машинні коди. Проте, зважаючи на неможливість здійснити оцінку смислу вхідної програми загалом та існуючі обмеження мов програмування на етапі генерації коду ми ніколи не отримаємо на 100% еквівалентну програму мовою асемблер.

Генерація і оптимізація коду є завершальним етапом роботи компілятора чи транслятора. Вона виконується після виконання операцій лексичного, синтаксичного і семантичного аналізу, ідентифікації імен змінних і функцій, розподілу адресного простору для функцій і змінних.

Розробка граф-схеми алгоритму

Генерація коду є поетапним процесом, який відбувається на основі закінчених мовних конструкцій вхідної програми. Генератор вибирає закінчену синтаксичну конструкцію з тексту вхідної програми породжує для неї фрагмент результуючого коду і розміщує його в тексті результуючої програми. Далі береться наступна конструкція. Так відбуваються доти, доки не буде розібрана вся програма.

Рис. 3.5 Алгоритм генератора коду.

Опис програми реалізації генератора коду

Генерація коду відбувається поетапно. Генератор коду аналізує проміжне представлення (списки лексем) сформовані синтаксичним аналізом і генерує для них відповідний ассемблерний код.

Спочатку генератор коду аналізує список ідентифікаторів і формує їхнє оголошення в сегменті даних (блоки 4, 6, 8). Далі відбувається подібна генерація машинного коду для списку стрічок (блоки 3, 5, 7). Після цього генератор формує заголовок машинного коду (блок 9). Далі зчитуються списки з проміжним представленням команд і формуються еквівалентні машинні інструкції (блоки 11, 13, 15). Далі в готовий асемблерний текст додаються сформовані машинні команди і код необхідних процедур (блоки 10, 12). Результати зберігаються у вихідний файл (блок 14).

Вихідна програма на машинній мові організована у вигляді готових процедур, кожна з яких відповідає за ввід/вивід результатів роботи, конкретну обчислювальну арифметичну чи логічну операцію, вивід повідомлення про помилки. Для обчислень використовується програмний стек, який представлений ділянкою пам'яті і зміщенням (вершина стеку). Даний метод має наступні переваги:

- розмір стеку достатньо великий щоб уникнути помилок переповнення, як у випадку зі стеком математичного співпроцесора;

- проста реалізація обчислень за допомогою готових процедур;

- можливість виявлення помилок на етапі виконання:

- ділення на нуль;

- помилка ініціалізації змінної;

- помилка переповнення;

- помилка введення

Організація лексичного аналізатора:

private static bool Lex(String CodeText)

{

. . .

}

Опис функції збереження лексичної таблички:

private static void SaveLex(String FileName)

{

{

. .

}

}

Повне дерево граматичного розбору



Результат роботи генератора коду:

.586

.model flat, C ,stdcall

option casemap: none

include c:\masm32\include\msvcrt.inc

includelib c:\masm32\lib\msvcrt.lib

include c:\masm32\include\kernel32.inc

includelib c:\masm32\lib\kernel32.lib

.data

. . .

.code

start:

mainmodule proc

. . .

mainmodule endp

Plus proc

. . .

Plus endp

Minus proc

. . .

Minus endp

Mult proc

. . .

Mult endp

Divd proc

. . .

Divd endp

ModOp proc

. . .

ModOp endp

EQUALOP proc

. . .

EQUALOP endp

NOTEQUALOP proc

. . .

NOTEQUALOP endp

GREATEROP proc

. . .

GREATEROP endp

LESSOP proc

. . .

LESSOP endp

NOTOP proc

. . .

NOTOP endp

OROP proc

. . .

OROP endp

ANDOP proc

. . .

ANDOP endp

ASSOP proc

. . .

ASSOP endp

Read proc

. . .

Read endp

PushVar proc

. . .

PushVar endp

IsInit proc

. . .

IsInit endp

PushNum proc

. . .

PushNum endp

NotInitErr proc

. . .

NotInitErr endp

DivBy0Err proc

. . .

DivBy0Err endp

OverFlowErr proc

. . .

OverFlowErr endp

InputErr proc

. . .

InputErr endp

ErrorEnd proc

. . .

ErrorEnd endp

end start



4. ОПИС ІНТЕРФЕЙСУ ТА ІНСТРУКЦІЇ КОРИСТУВАЧА

Програма транслятор має простий інтерфейс SDI. Стандартне меню з командами збереження (Ctrl+S), відкриття (Ctrl+O), створення нового файлу (Ctrl+N). Також тут є меню з командами виконання всіх фаз трансляції і компіляції(F5). Меню довідки містить команду показу вікна з інформацією про програму. Головна робоча область складається з поля введення тексту і поля зі списком помилок.

Рис. 4.1 Середовище розробки мови Z30.

Рис. 4.2 Користувацькі меню середовища розробки.



5. ВІДЛАГОДЖЕННЯ ТА ТЕСТУВАННЯ ПРОГРАМИ

Відлагодження програми відбувається в покроковому режимі в середовищі Microsoft Visual Studio 2010 з використанням точок зупинки, що дає можливість знайти місце логічної помилки. В покроковому режимі у нас є можливість прослідкувати за значеннями змінних.

Тестування програми буде відбуватися з допомогою готових прикладів на вхідній мові в яких можуть використовуватися різноманітні оператори вхідної мови, можуть бути допущені різноманітні лексичні, граматичні та синтаксичні помилки.

5.1 Виявлення лексичних помилок

На етапі лексичного аналізу виникають наступні помилки: Нерозпізнана лексема - це помилка яка може виникнути на етапі лексичного аналізу, коли лексема відповідає регулярному виразу лексичної помилки. Завеликий числовий літерал - це помилка яка може виникнути на етапі лексичного аналізу, коли числовий літерал є завеликим для типу Integer_4. Коли виникає будь-яка помилка, то вона записується в глобальний список помилок.

Виявлені лексичні помилки можуть підсвічуватися в редакторі після виконання лексичного аналізу (рис. 6).

startprogram

startblock

variable n >> 0 integer_4;

write "n = ";

read n;

dfhfhf;

if n !> 0

startblock

write "n is positive";

endblock

else

startblock

write "n is negative";

endblock

endblock

Рис. 5.1 Виявлення лексичних помилок.

Виявлення синтаксичних помилок

На етапі синтаксичного аналізу виявляється основна кількість помилок. Ці помилки пов'язані з невірними записами конструкцій вхідної мови, незавершеність програми, неправильним форматом виразів. Всі помилки виявленні на етапі синтаксичного аналізу заносяться в таблицю помилок.

Для початку протестуємо наступний код в якому навмисно допущено різноманітні помилки. Як видно з (рис. 5.2) транслятор коректно виявляє різноманітні синтаксичні помилки.



startprogram

startblock

variable n >> 0 integer_4;

write "n = "

read n;

if n !> 0

startblock

write "n is positive";

endblock

else

startblock

write "n is negative";

endblock

endblock

Рис. 5.2 Програма з багатьма помилками



Виявлення семантичних помилок

Основною метою семантичного аналізу є перевірка типів операндів. Оскільки згідно варіанту присутній тільки один тип integer_4, то така перевірка не буде проводитися. Виявлення семантичних помилок зводиться до перевірки того, чи змінні ініціалізовані початковими значеннями. Ця перевірка виконується на етапі виконання. Це досягається наявність додаткової інформації про ініціалізацію в сегменті коду. При виникненні такої помилки видасться повідомлення про помилку, виконання програми завершиться і вона поверне одиницю.

Синтаксично слідуючий код правильний, проте в ньому допущена семантична помилка: змінній і присвоюється не ініціалізована змінна tmp, тому на етапі виконання згенерується помилка (рис. 5.3).

startprogram

startblock

variable n integer_4;

write "n = ", n;

endblock

Рис. 5.3 Виявлення помилок ініціалізації.

Схожим чином відбувається перевірка на деякі інші типи помилок. Наприклад помилка ділення на нуль. В наступному прикладі змінна tmp ділиться на нуль, тому генерується помилка.

startprogram

startblock

variable n >> 0 integer_4;

n >> 10 / 0;

endblock

Рис. 5.4 Виявлення помилок виконання.

5.2 Загальна перевірка коректності роботи транслятора

Загальна перевірка коректності роботи транслятора полягає в транслюванні коректної вхідної програми з використанням всіх можливостей мови в асемблерний код та перевірці на правильність виконання програми, яку потрібно попередньо скомпілювати і транслювати за допомогою ml.exe.



Висновки

В процесі виконання курсової роботи було складено формальний опис мови програмування Z30, в термінах розширеної нотації Бекуса-Наура, виділено усі термінальні символи та ключові слова.

Створено транслятор мови програмування Z30, а саме: Розроблено лексичний аналізатор, який виявляє лексичні помилки , та на виході дає таблицю лексем таблицю ідентифікаторів, з якими потім працює синтаксично-семантичний аналізатор .

Розроблено синтаксичний та семантичний аналізатор, який виявляє синтаксичні та семантичні помилки на етапі аналізу та виконання, та на виході будує проміжне представлення, яке потім використовує генератор коду .

Розроблено генератор коду, який генерує код, записаної нами програми на заданій мові програмування, у програму на мові асемблера . На виході ми отримуємо файл на мові асемблера , з якого ми отримаємо виконавчий файл, за допомогою ml i link.

Проведене тестування транслятора на тестових програмах за наступними пунктами:

- На виявлення лексичних помилок.

- На виявлення синтаксичних помилок.

- Загальна перевірка роботи компілятора.

Тестування виявило деякі помилки в роботі транслятора , які були успішно усунуті. В результаті виконання даної курсової роботи було успішно засвоєно методи розробки та реалізації компонент системного програмування.

транслятор компілятор лексичний аналізатор



Список літератури

1. Хантер Р. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984. - 232 с.

2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. - М.: Мир, 1978. - т.1, 612 с.

3. Серебряков В.А. Лекции по конструированию компиляторов. - М.: МГУ, 1993.

4. Н.Г.Голубь "Исскуство программирования на ассемблере. Лекции и упражнения". -Киев "DiaSoft", 2002 - 642с.

5. Л.Бэк "Введение в системное програмирование". - М.: Мир, 1999

6. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. - М.: Мир. 1975. - 554 с.

7. Шильдт Г. С#. - Санкт-Петербург: BXV, 2007. - 688 с.



Додаток А: Завдання на курсову роботу

Розробити транслятор заданої вхідної мови програмування, до якої висуваються наступні вимоги:

Кожна програма починається зі слова startprogram. Після йде розділ оголошення змінних і оператор головного блоку startblock кожен блок завершується ключовим словом endblock. Наприклад як у мові Паскаль begin end. Програма має надавати можливість працювати зі змінними таких типів: integer_4 - цілі числа. Змінні перед використанням мають бути попередньо оголошені та ініціалізовані, в іншому випадку генерується помилка на етапі трансляції чи на етапі виконаня. Регістр ключових слів і ідентифікаторів нижній. Довжина ідентифікаторів не повинна бути більшою за вісім символів.

Присвоєння змінних виконується оператором присвоєння >> . Наприклад x >> y add 5;

Над змінними виконуються наступні операції.

· Арифметичні: +, -, *, /, % додавання, віднімання, ділення, множення, остача від ділення;

· Логічні: !!, &&, || логічні операції NOT, AND, OR.

· Порівняння: ==, !=, >=, <= рівність, нерівність, більше, менше;

Ввід даних зі стандартного вводу відбувається оператором read, а вивід оператором write. Наприклад read _X; write "y = ", _Y.

Для виконання циклічних операції використовується оператор циклу if - else.

Коментування певних частин коду здійснюється оператором коментаря \\ Коментар

Потрібно також розробити середовище, яке б включало текстовий редактор з можливістю набору, редагування програми; зчитування та запису її на диск, запуску трансляції.

На вхід розробленого компілятора має подаватися текстовий файл, написаний на заданій мові програмування. На виході розробленого компілятора мають з'являтися три файли:

· файл з результатом лексичного аналізу,

· файл з результатом синтаксичного аналізу,

· файл з результуючим програмним кодом на мові асемблер,

· файл з інформацією про помилки, якщо вони є,

· об'єктний файл,

· виконавчий файл



Додаток Б: Загальний алгоритм роботи транслятора



Додаток В. Текст коректної програми на мові Z30

startprogram

startblock

variable n >> 0 integer_4;

write "n = ";

read n;

if n !> 0

startblock

write "n is positive";

endblock

else

startblock

write "n is negative";

endblock

endblock

Размещено на Allbest.ru

...