4

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

Міністерство Освіти і Науки України

ДВНЗ «Криворізький Національний Університет»

Факультет інформаційних технологій

Кафедра комп'ютерних систем та мереж

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

з дисципліни «Системне програмування»

на тему: «РОЗРОБКА КОМПІЛЯТОРА З ЗАДАНОГО ПІДМНОЖИНИ МОВИ ПАСКАЛЬ»

Студента 3-го курсу групи ЗКІ-16

Бондарук Є. Г.

Керівник доцент, к.т.н. КСМ,

Кузнецов Д. І.

м. Кривий Ріг 2019 рік



Реферат

Пояснювальна записка: 35сторінок, 16рисунків, 6таблиць, 3додаток, 17використаних джерел.

Мета проектування -розробка редактора ресурсних файлів для програмних додатків у операційній системі Windows.

Проект складається з трьох розділів.Перший розділ присвячений детальному огляду існуючих рішень визначення індитифікатори.У другому розділі Програмна реалізація синтаксичного аналізатора представлена у вигляді модулів SynAnalyser і графічного модуля SynTab. Модуль SynAnalyser проводить синтаксичний аналіз послідовного набору лексем, що надходить від лексичного аналізатора на основі правил остовно граматики.Третій розділ присвячений розробці програми компілятора.

КОМПІЛЯТОР, СИСТЕМНЕ ПРОГРАМУВАННЯ, ASM, Microsoft VISUAL STUDIO.NET, МОДУЛЯ SYNTAB,МОДУЛЬ SYNANALYSER.



Abbstract

Explanatory note: 35pages, 16scripts, 6tables, 3addocs, 17sources used.

The purpose of designing is to develop a resource file editor for software applications in the Windows operating system.

The project consists of three sections. The first section is devoted to a detailed review of existing solutions for determining the index. In the second section, the issues are solved. The software implementation of the parser analyzer. Using the assembler language, a DLL library was developed to implement the most resource-intensive data processing functions. The third section is devoted to the development of a compiler program.

COMPUTER, SYSTEM PROGRAMMING, ASM, Microsoft VISUAL STUDIO.NET, WINAPI,MODUL SYNTAB, MODUL SYNANALYSER.



Перелык скорочень

MVS- Microsoft Visual Studio.NET2015;

СП- СИСТЕМНЕ ПРОГРАМУВАННЯ;

АК- АРХІТЕКТУРА КОМП'ЮТЕРА;

ASL - ASSEMBLY LANGUAGE;

AT&T-СИНТАКСИС.



Зміст

Реферат

Перелік скорочень

Вступ

1. Постановка таблиця ідентифікаторів

1.1 Вихідні дані

1.2 Принципи роботи лексичного аналізатора

1.2.1 Схема розпізнавачів

1.3 Побудова дерева виведення

Висновки за 1 розділом

2. Програмна реалізація синтаксичного аналізатора

2.1 Програмна реалізація синтаксичного аналізатора

2.1.1 Лексичний аналіз вхідного тексту

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

2.3 Генерація і оптимізація об'єктного коду

Висновки за другим розділом

3. Опис програми компілятора

3.1 Реалізація таблиці ідентифікаторів

3.2 Програмна реалізація лексичного аналізатора

3.3 Програмна реалізація синтаксичного аналізатора

Висновок у третьому розділу

Додаток A

Висновки

Список використаних джерел



Вступ

компілятор аналізатор редактор програма

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

З одного боку, комп'ютери традиційної архітектури вміють розуміти лише мову машинних команд. З іншого боку, розробники не мають можливості створювати прикладні та системні програми на рівні машинних кодів - занадто великий відсоток помилок і непомірно велика трудомісткість такої роботи. Тому давно виникла потреба у появі "перекладачів" з різних мов програмування (мов асемблера і мов високого рівня) на мову машинних кодів. Такими перекладачами стали транслятори. Є і більш вузьке поняття подібного роду - "компілятор".

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

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



1. Постановка таблиця ідентифікаторів

1.1 Вихідні дані

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

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

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

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

Метод ланцюжків працює за наступним алгоритмом:

Крок 1. У всі осередки хеш-таблиці помістити порожнє значення, таблиця ідентифікаторів порожня, змінна FreePtr (покажчик першої вільної комірки) вказує на початок таблиці ідентифікаторів; i: = 1.

Крок 2. Обчислити значення хеш-функції ni для нового елемента Ai. Якщо осередок хеш-таблиці за адресою ni порожня, то помістити в неї значення змінної FreePtr і перейти до кроку 5; інакше перейти до кроку 3.

Крок 3. Покласти j: = 1, вибрати з хеш-таблиці адресу комірки таблиці ідентифікаторів mj і перейти до кроку 4.

Крок 4. Для комірки таблиці ідентифікаторів за адресою mj перевірити значення поля посилання. Якщо воно порожнє, то записати в нього адресу з змінної FreePtr і перейти до кроку 5; інакше j: = j + 1, вибрати з поля посилання адреса mj і повторити крок 4.

Для наочності на малюнку 1 зображена блок-схема алгоритму.

Крок 5. Додати в таблицю ідентифікаторів новий осередок, записати в неї інформацію для елемента Ai (поле посилання повинно бути порожнім), в змінну FreePtr помістити адреса був призначений додатковий кінцем доданої осередки. Якщо більше немає ідентифікаторів, які треба розмістити в таблиці, то виконання алгоритму закінчено, інакше i: = i + 1 і перейти до кроку 2.

Пошук елемента в таблиці ідентифікаторів, організованої таким чином, буде виконуватися за наступним алгоритмом:



4

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

.

Рисунок 1.1 Блок-схема організації таблиці ідентифікаторів за алгоритмом «метод ланцюжків»



4

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

Рисунок 1.2 Блок-схема пошуку елемента в таблиці ідентифікатора організованою за алгоритмом «метод ланцюжків»

Крок 1. Обчислити значення хеш-функції n для A. Якщо осередок хеш-таблиці за адресою n порожня, то елемент не знайдений і алгоритм завершений, інакше вибрати з хеш-таблиці адресу комірки таблиці ідентифікаторів m.

Крок 2. Порівняти ім'я елемента в комірці таблиці ідентифікат за адресою m з ім'ям шуканого елемента А. Якщо вони співпадуть, то шуканий елемент знайдений, і алгоритм завершеній, інакше перейти до кроку 3Крок 3. Перевірити значення поля посилання в комірці таблиці ідентифікаторів за адресою m. Якщо воно порожнє, то шуканий елемент не знайдений і алгоритм завершенж інакше вибрати з поля посилання адреса m і перейти до кроку 2. Для наочності на малюнку 1.3 зображено блок-схема.

Для вирішення проблеми колізії можна використовувати метод рехешірованія. Відповідно до цього методу, якщо для елемента А адреса п () = h (A), обчислений за допомогою хеш-функції h, вказує на вже зайняту комірку, то необхідно обчислити значення функції n1 = h1 {A) і перевірити зайнятість комірки за адресою n1. Якщо і вона зайнята, то ви-обчислюється значення h2 (A), і так до тих пір, поки або не буде знайдена вільна осередок, або чергове значення hi (A) не співпаде з h (A). В останньому випадку вважається, що таблиця ідентифікаторів заповнена і місця в ній більше немає - видається інформація про помилку розміщення ідентифікатора в таблиці.

Пошук елемента А в таблиці ідентифікаторів буде виконуватися за наступним алгоритмом:

Крок 1. Обчислити значення хеш-функції n = h (A) для шуканого елемента А.

Крок 2. Якщо осередок за адресою п порожня, то елемент не знайдений, алгоритм завершений, інакше необхідно порівняти ім'я елемента в комірці п з ім'ям шуканого елемента А. Якщо вони збігаються, то елемент знайдений і алгоритм завершений, інакше i: = 1 і перейти до кроку 3.

Крок 3. Обчислити Пi = hi (A). Якщо осередок за адресою ni порожня або п = Пi, то елемент не знайдений і алгоритм завершений, інакше - порівняти ім'я елемента в комірці Пi з іме¬нем шуканого елемента А. Якщо вони збігаються, то елемент знайдений і алгоритм завершений, інакше i: = i + 1 і повторити крок 3.

Для наочності на малюнку 3 зображено блок-схема пошуку.

Для організації таблиці ідентифікаторів за методом рехешірованія необході¬мо визначити всі хеш-функції hi для всіх i. Найчастіше функції hi визначають як деякі модифікації хеш-функції h. У цій роботі використовується рехешірованіе з псевдовипадковими числами за формулою hi (A) = (h (A) + pi) mod Nm., Де pi - псевдовипадкове число.



4

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

Рисунок 1.3 Блок-схема алгоритму пошуку по методу рехешірованія з псевдовипадковим числом



1.2 Принципи роботи лексичного аналізатора

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

В результаті роботи програми отримані наступні дані:

- метод ланцюжків:

- всього порівнянь: 690;

- в середньому порівнянь: 3,63;

- метод рехешірованія з псевдовипадковим числом:

- всього порівнянь: 639;

- в середньому порівнянь: 3,36.

На основі отриманих результатів можна зробити наступні висновки: при відносно невеликій кількості ідентифікаторів обидва методи показують приблизно однакові результати. У нашому випадку при використанні 1068 ідентифікаторів середня кількість необхідних порівнянь для методу ланцюжків виявилося на 0,27 порівнянь більше, ніж для методу рехешірованія з псевдовипадковим числом.

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

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

Робота автомата виконується по тактам. На кожному черговому такті i автомат, перебуваючи в деякому стані qi?Q, зчитує черговий символ w?? з вхідний ланцюжка символів і змінює свій стан на qi + 1 = ? (qi, w), після чого покажчик в ланцюжку вхідних символів пересувається на наступного символ і починається такт i + 1. Так триває до тих пір, поки ланцюжок вхідних символів не закінчиться. Кінець ланцюжка символів часто позначають особливим символом ?. Вважається також, що перед тактом 1 автомат знаходиться в початковому стані q0.

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

1.2.1 Схема розпізнавачів

Граф кінцевого детермінованого автомата, використовуваного для розпізнавання вхідних ланцюжків мови.

Початковий і кінцевий стани при нормальній роботі лексичного аналізатора збігаються (на малюнку стан "q"). У разі помилкової вхідний ланцюжка автомат потрапляє в стан помилки ERROR. При цьому робота автомата зупиняється.

Крім того, типовими для автомата є стану ID (змінна) і CONSTANT (константа). Решта стану автомата визначаються допустимими для компілятора вихідного мови лексемами.

Кожен перехід в кінцевий стан "q" повідомляє про кінець поточної вхідний ланцюжка. У цьому випадку проводиться аналіз розпізнаної ланцюжка і перезапуск автомата для чергової вхідний ланцюжка символів. Зауважимо також, що можлива повторна обробка деяких символів вхідного ланцюжка символів. Це необхідно в тих випадках, коли символ, який призвів до переходу автомата в кінцевий стан, є початком наступного ланцюжка символів.

Схема распознователя представлена в додатку А.

1.2.2 Результати програми

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

program

(* Это

комментарий * (* **)

begin

a:=11010111;

for i:=10101 downto 0 do

begin

a:=a+1;

end;

if a>0 then a:=11 else i:=0 endif

end; end.

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



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

Переммение виду "5per" будуть распозанаватся як помилки, так само помилкою буде вважатися не двійкове число, або число значення якого більше 255, так як числа за завданням повинні бути двійковими і типу Byte.

1.3 Побудова дерева виведення

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

1.3.1 Синтаксичний аналізатор

Вихідна граматика:

G ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;,:=}, {S, L, O, B, C, K, D, H, E, T, M}, P, S)

S > program L end.

L > O | O ; O | L ;

O > if B then O else O endif | if B then O endif | begin L end | for M downto E do O| M

M > a:= E

B > B or C | C

C > C and D | D

D > not D | H

H > E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E > E - T | E + T | T

T > (E) | a | c

Де a це змінна а з констатив

Безлічі крайніх лівих і крайніх правих нетермінальних символів L (U), R (U) представлені в таблиці 1.3.1.

Таблиця 1.3.1

нетермінальних символів L (U), R (U)

U	L(U)	R(U)
T	(, a, c	), a, c
E	E, T	T
H	(, E	E, )
D	not, H	D, H
C	C, D	D
B	B, C	C
O	if, begin, for, M	endif, end, O, M
M	a	E
L	L, O	O, ;
S	program	end.

У Таблиця 1.3.2 описані результуючі безлічі крайніх лівих і крайніх правих нетермінальних символів L(U), R(U).



Таблиця 1.3.2

нетермінальних символів L (U), R (U)

U	L(U)	R(U)
T	(, a, c	), a, c
E	E, T, (, a, c	T, ), a, c
H	E, T, (, a, c	E, ), T, a, c
D	not, H, E, T, (, a, c	D, H, E, ), T, a, c
C	C, D, not, H, E, T, (, a, c	D, H, E, ), T, a, c
B	B, C, D, not, H, E, T, (, a, c	C, D, H, E, ), T, a, c
O	if, begin, for, M, a	endif, end, O, M, E, T, ), a, c
M	a	E, T, ), a, c
L	L, O, if, begin, for, M, a	O, ;, endif, end, M, E, T, ), a, c
S	program	end.

Безлічі крайніх лівих і крайніх правих термінальних символів Lt (U), Rt (U) представлені в Таблиця 1.3.3.

Таблиця 1.3.3

термінальних символів Lt (U), Rt (U)

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +	-, +
H	<, >, =, <>, (, <<, >>	<, >, =, <>, ), <<, >>
D	not	not
C	and	and
B	or	or
O	if, begin, for	endif, end, do
M	a	:=
L	;	;
S	program	end.

Підсумкові безлічі крайніх лівих і крайніх правих термінальних символів Lt (U), Rt (U) щодо всіх нетермінальних символів граматики представлені в таблиці 4



Таблиця 1.3.4

термінальних символів Lt (U), Rt (U) щодо всіх нетермінальних символів граматики

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +, (, a, c	-, +, ), a, c
H	<, >, =, <>, (, <<, >>, -, +, a, c	<, >, =, <>, ), <<, >>, -, +, a, c
D	not, <, >, =, <>, (, <<, >>, -, +, a, c	not, <, >, =, <>, ), <<, >>, -, +, a, c
C	and, not, <, >, =, <>, (, <<, >>, -, +, a, c	and, not, <, >, =, <>, ), <<, >>, -, +, a, c
B	or, and, not, <, >, =, <>, (, <<, >>, -, +, a, c	or, and, not, <, >, =, <>, ), <<, >>, -, +, a, c
O	if, begin, for, a	endif, end, do,:=, -, +, ), a, c
M	a	:=, -, +, ), a, c
L	;, if, begin, for, a	;, endif, end, do,:=, -, +, ), a, c
S	program	end.

Таблиця 1.3.5

Матриця операційного передування представлена

U	Lt(U)	Rt(U)
T	(, a, c	), a, c
E	-, +, (,a, c	-, +, ), a, c
H	<, >, =, <>, (, <<, -, +, a, c	<, >, =, <>, ), >>, -, +, a, c
D	not, <, >, =, <>, (, <<, -, +, a, c	not, <, >, =, <>, ), >>, -, +, a, c
C	and, not, <, >, =, <>, (, <<, -, +, a, c	and, not, <, >, =, <>, ), >>, -, +, a, c
B	or, and, not, <, >, =, <>, (, <<, -, +, a, c	or, and, not, <, >, =, <>, ), >>, -, +, a, c
O	if, begin, repeat, a	endif, end,:=, until, or, and, not, <, >, =, <>, ), >>, -, +, a, c
L	;, if, begin, repeat, a	;, endif, end,:=, until, or, and, not, <, >, =, <>, ), >>, -, +, a, c
S	program	end.

Матриця операційного передування представлена у вигляді таблиці, в додатку Б.

Остовно граматика, отримана на основі вихідної граматики:

G' ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;,:=}, {E}, P', S)

E > program E end.

E > E | E ; E | E ;

E > if E then E else E endif | if E then E endif | begin E end | for E downto E do E | E

E > a:=E

E > E or E | E

E > E and E | E

E > not E | E

E > E < E | E > E | E = E | E <> E | (E) | E << E | E >> E

E > E - E | E + E | E

E > (E) | a | c

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

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

G' ({ program, end., if, then, else, endif, begin, end, for, downto, do, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;,:=}, {E}, P', S)

E > program E end.

E > E | E ; E | E ;

E > if B then E else E endif | if B then E endif | begin E end | for E downto E do E | E

E > a:=E

B > B or B | B

B > B and B | B

B > not B | B

B > E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E > E - E | E + E | E

E > (E) | a | c

Помилки при синтаксичному аналого виникають при недотримання правил граматики. Наприклад "if a> c else a-1 ten a + 1" викличе синтаксичну помилки.

Нехай на вхід подається наступний текстовий файл:

program

(* Это

комментарий * (* *

*)

begin

a:=11010111;

for i:=10101 downto 0 do

begin

a:=a+1;

end;

if a>0 then a:=11 else i:=0 endif

end;

end.

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



Рисунок 1.3.1 Результат побудови дерева виведення

Оригінальний текст програми наведено у додатку B.

Остовная грамматика, полученная на основе исходной грамматики:

G' ({ program, end., if, then, else, endif, begin, end, repeat, until, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;,:=}, {E}, P, S)

E > program E end.

E > E | E ; E | E ;

E > if E then E else E endif | if E then E endif | begin E end | repeat E until E | a:= E

E > E or E | E

E > E and E | E

E > not E | E

E > E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E > E - E | E + E | E

E > (E) | a | c

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

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

G' ({ program, end., if, then, else, endif, begin, end, repeat, until, and, or, not, <<, >>, =, <, >, <>, (, ), -, +, a, c, ;,:=}, {E, B}, P, S)

E > program E end.

E > E | E ; E | E ;

E > if B then E else E endif | if B then E endif | begin E end | repeat E until B | a:= E

B > B or B | B

B > B and B | B

B > not B | B

B > E < E | E > E | E = E | E <> E | (B) | E << E | E >> E

E > E - E | E + E | E

E > (E) | a | c

Висновки за 1 розділом

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

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



2. Програмна реалізація синтаксичного аналізатора

2.1 Програмна реалізація синтаксичного аналізатора

Програмна реалізація синтаксичного аналізатора представлена ??у вигляді модулів SynAnalyser і графічного модуля SynTab. Модуль SynAnalyser проводить синтаксичний аналіз послідовного набору лексем, що надходить від лексичного аналізатора на основі правил остовно граматики. Результатом його роботи є структура, яка відображає дерево синтаксичного виводу. У разі помилки на екрані з'являється повідомлення про синтаксичну помилку і рядок з помилкою виділяється червоним кольором. Графічний модуль SynTab відповідає за графічне представлення дерева виведення, а також виводить докладний звіт про послідовність дій, що проводяться синтаксичним аналізатором, і їх результати.

Розглянемо роботу синтаксичного аналізатора при обробці наступного файлу:

program

(* Это

комментарий * (***)

begin

c:= c - b +d;

repeat

if a>3 then a:=3 else i:=0 endif

until i=0

end;

end.

Графічно результат побудови дерева виведення представлений на рисунке 2.1.

Рисунок 2.1 Результат побудови дерева виведення

2.1.1 Лексичний аналіз вхідного тексту

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

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

Робота автомата виконується по тактам. На кожному черговому такті i автомат, перебуваючи в деякому стані qi?Q, зчитує черговий символ w?? з вхідний ланцюжка символів і змінює свій стан на qi + 1 =?(qi, w), після чого покажчик в ланцюжку вхідних символів пересувається на наступного символ і починається такт i + 1. Так триває до тих пір, поки ланцюжок вхідних символів не закінчиться. Кінець ланцюжка символів часто позначають особливим символом ?. Вважається також, що перед тактом 1 автомат знаходиться в початковому стані q0.

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

Граф кінцевого детермінованого автомата, використовуваного для розпізнавання вхідних ланцюжків мови.Початковий і кінцевий стани при нормальній роботі лексичного аналізатора збігаються (на малюнку стан "q"). У разі помилкової вхідний ланцюжка автомат потрапляє в стан помилки ERROR. При цьому робота автомата зупиняється.Крім того, типовими для автомата є стану ID (змінна) і CONSTANT (константа). Решта стану автомата визначаються допустимими для компілятора вихідного мови лексемами.

Кожен перехід в кінцевий стан "q" повідомляє про кінець поточної вхідний ланцюжка. У цьому випадку проводиться аналіз розпізнаної ланцюжка і перезапуск автомата для чергової вхідний ланцюжка символів. Зауважимо також, що можлива повторна обробка деяких символів вхідного ланцюжка символів. Це необхідно в тих випадках, коли символ, який призвів до переходу автомата в кінцевий стан, є початком наступного ланцюжка символів.



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

Програмна реалізація лексичного аналізатора представлена ??у вигляді модулів LexFSM і LexAnalyser. LexFSM - відображає роботу автомата, що розпізнає вхідні ланцюжка символів. LexAnalyser готує текст вхідного файлу для відправки його символів модулю LexFSM за запитами останнього. Він ігнорує незначні символи вхідного тексту (символи табуляції, повернення каретки і т.д.). Коли LexFSM переходить в одне з кінцевих станів, він передає управління модулю LexAnalyser. Той, в свою чергу, виводить результати роботи на екран і сигналізує в разі помилки про рядку, в якій сталася помилка. Крім того, якщо LexFSM переходить в кінцевий стан "q" і таким чином розпізнає вхідні ланцюжок символів, він передає отриману лексему з інформацією про неї модулю LexAnalyser, а той додає її в свій список лексем. По завершенні обробки файлу модуль LexAnalyser посилає список лексем графічного модулю LexTab, який відображає результуючий список лексем у вигляді таблиці 2.2.1.

Список лексем графічного модулю LexTab таблиці- 2.2.1.

Лексема	Тип лексемы	Номер идентификатора в таблице идентификаторов
program	Ключевое слово 'program'
begin	Ключевое слово 'begin'
begine	Переменная	1
:=	Оператор присваивания ':='
5	Константа
;	Разделитель
a	Переменная	2
:=	Оператор присваивания ':='
5	Константа
;	Разделитель
repeat	Ключевое слово 'repeat'
if	Ключевое слово 'if'
a	Переменная	2
>	Знак операции '>'
3	Константа
then	Ключевое слово 'then'
a	Переменная	2
:=	Оператор присваивания ':='
3	Константа

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

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

program

(* Это

комментарий * (* *

*)

begin

c:= c - b +d;

repeat

if a>3 then a:=3 else i:=0 endif

until i=0

end;

end.

Графічно результат побудови дерева виведення представлений на рисунке2.2.1.



Рисунок 2.2.1 Результат побудови дерева виведення

2.3 Генерація і оптимізація об'єктного коду

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

Результатом роботи повинна бути побудована на підставі заданого пропозиції граматики програма на об'єктному мовою. Як об'єктного мови пропонується взяти мову асемблера для процесорів типу Intel 80x86 в реальному режимі. Всі зустрічаються у вихідній програмі ідентифікатори вважати простими скалярними змінними, що не вимагають виконання перетворення типів.

Розробка даної частини роботи розбивається на два етапи - побудова списку тріад і генерація ассемблерного коду.Побудові списку тріад:

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

- Тріада if (a, b), де операнди a і b обов'язково є посиланнями на тріади. Сенс цієї тріади полягає в наступному: якщо результат обчислення тріади a, що є логічним виразом, дорівнює нулю, то проводиться перехід по посиланню b. Інакше виробляється послідовний перехід до наступної за списком тріаді.

- Тріада jmp (1, a), де перший операнд не несе смислового навантаження, а другий вказує посилання на тріаду, до якої на наступному етапі повинен бути проведений безумовний перехід.

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

Решта вираження однозначно перетворюються в одну або кілька послідовних тріад.

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

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

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

Висновки за другим розділом

За генерацію списку тріад відповідають модулі Triad, TriListMaker і TriListOptimizer. Клас Triad визначає структуру, відповідну однієї тріаді. Модуль TriListMaker генерує початковий список тріад на основі синтаксичного дерева виведення, а модуль TriListOptimizer виробляє його оптимізацію як виняток зайвих операцій. Як тільки закінчується оптимізація тріад, результуючий список тріад відправляється модулю AsmGenerator - модулю, який відповідає за генерацію ассемблерного коду. Результатом роботи модуля AsmGenerator є результуючий об'єктний код на основі вхідного текстового файлу. Результати даних операцій виводяться на екран за допомогою модулів TriTab і AsmTab відповідно.

3. Опис програми компілятора

3.1 Реалізація таблиці ідентифікаторів

На рисунке 3.1 представлено головне вікно програмної реалізації таблиці ідентифікаторів.

Рисунок 3.1 Головне вікно

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



Рисунок 3.2 Статистика порівнянь при пошуку ідентифікаторів

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

Рисунок 3.3 Ілюстрація структури таблиці ідентифікаторів

Оригінальний текст програми наведено у додатку А.

3.2 Програмна реалізація лексичного аналізатора

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

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

Рисунок 3.2.1 Вкладка завантаження файлу

Результати роботи лексичного аналізатора виводяться у вкладці "Таблиця лексем" (Рисунок 3.2.2). Там же наводиться докладний лог його роботи.

Рисунок 3.2.2 Вкладка "Таблиця лексем"

У разі лексичної помилки у вхідному файлі на екран виводиться повідомлення про помилку і у вкладці завантаження файлу рядок з помилкою підсвічується червоним кольором (Рисунок 3.2.3).

Рисунок 3.2.3 Висновок помилки

3.3 Програмна реалізація синтаксичного аналізатора

Реалізація синтаксичного аналізатора аналогічна програмної реалізації лексичного аналізатора.У вкладці "Синтаксис" виводиться результат роботи аналізатора - дерево виводу (Рисунок 3.3.1). У цій же вкладці виводиться і докладний лог його роботи.



Рисунок 3.3.1 Вкладка "Синтаксис"

Аналогічно тому, як проводиться інформування про виявлену лексичної помилку, реалізовано повідомлення про синтаксичну помилку. Реалізація генерації й оптимізації об'єктного коду. У вкладці "Тріади" виводиться інформація про генерацію тріад і їх оптимізації (рисунок 3.3.2). Виданим варіанту завдання відповідає оптимізація як виняток зайвих операцій. Її результати і докладний лог роботи модуля представлені в цій же вкладці.



Рисунок 3.3.2 Вкладка "Тріади"

Результати перетворення тріад в код асемблера виділені в окрему вкладку "Команди" (рисунок 3.3.3). Ці результати і є результатом роботи всієї програми.

Рисунок 3.3.3 Вкладка "Команди"

Тексти програм для модулів, описаних в підрозділах 3.1, 3.2 і 3.3, представлені в додатку Б.

Висновок у третьому розділу

У процесі виконання курсової роботи була розроблена програма, яка реалізує компілятор заданого підмножини мови Паскаль з незначними модифікаціями. Для її розробки використовували середовище Microsoft Visual Studio.NET 2015 зі додатково інтегрованої бібліотекою класів Trolltech Qt v12.0.3.



Додаток A Вихідний текст програми

main.cpp

#include <QtGui/QApplication>

#include "MainDialog.h"

#include <QTextCodec>

int main(int argc, char *argv[])

{

QApplication a(argc, argv);

QTextCodec::setCodecForTr(QTextCodec::codecForName("CP1251"));

a.setStyle("windowsxp");

MainDialog w;

w.show();

a.connect(&a, SIGNAL(lastWindowClosed()), &a, SLOT(quit()));

return a.exec();

}



Висновки

У цьому КР ми навчилися наводити і описувати генерацію списку тріад відповідають модулі Triad, TriListMaker і TriListOptimizer. Клас Triad визначає структуру, відповідну однієї тріаді. Модуль TriListMaker генерує початковий список тріад на основі синтаксичного дерева виведення, а модуль TriListOptimizer виробляє його оптимізацію як виняток зайвих операцій. Як тільки закінчується оптимізація тріад, результуючий список тріад відправляється модулю AsmGenerator - модулю, який відповідає за генерацію ассемблерного коду. Результатом роботи модуля AsmGenerator є результуючий об'єктний код на основі вхідного текстового файлу. Результати даних операцій виводяться на екран за допомогою модулів TriTab і AsmTab відповідно.

Під час виконання курсової роботи було отримані результати можна зробити наступні висновки: при відносно невеликій кількості ідентифікаторів обидва методи показують приблизно однакові результати. У нашому випадку при використанні 1068 ідентифікаторів середня кількість необхідних порівнянь для методу ланцюжків виявилося на 0,27 порівнянь більше, ніж для методу рехешірованія з псевдовипадковим числом. У процесі виконання курсової роботи була розроблена програма, яка реалізує компілятор заданого підмножини мови Паскаль з незначними модифікаціями. Для її розробки використовували середовище Microsoft Visual Studio.NET 2015 зі додатково інтегрованої бібліотекою класів Trolltech Qt v12.0.3.



Список використаних джерел

1. Системне програмне забезпечення: Підручник для вузів / А.Ю. Молчанов- СПб.: Питер, 2003. 396 с.

2. Системне програмне забезпечення. Лабораторний практикум / А.Ю. Молчанов. СПб.: Питер, 2005. 284 с.

3. Розробка графічного інтерфейсу за допомогою бібліотеки Qt3 / Дж. Бланшетт, М. Саммерфелд, 2003.

4. http://www.fi.ru/~mill/ Особиста сторінка А.Ю. Молчанова.

5. Харт Джонсон. Системное программирование в среде Windows / Джонсон Харт. М.: Вильямс, 2005. 592 с.

6. Побегайло А.П. Системное программирование в Windows/ А.П.Побегайло. -СПб.: БХВ-Петербург, 2006. 1056 с.

7. Шеховцев В.А. Операційні системи / В.А. Шеховцев. К.: Видавнича група BHV, 2005. 576 с.4.БондаренкоМ.Ф.Операційні системи: навч. посібник / М.Ф.Бондаренко, О.Г.Качко. Харків: Компанія СМІТ, 2008. 432 с.

8. Комисаров В. Программирование драйверов для Windows/ В.Комисаров. -BHV-Санкт-Петербург, 2007.

9. НесвижскийВ. Программирование аппаратных средств Windows/ В.Несвижский. БХВ-Петербург, 2004. 880 с.

10. Румянцев П.В. Азбука программирования в Win32 API/ П.В.Румянцев. М.: «Горячая Линия -Телеком», 2004. 310 с.

11. СорокинаС.И.Программирование драйверов и систем безопасности/ Сорокина С.И., Тихонов А.Ю., Щербаков А.Ю. БХВ-Петербург, 2003. 256 с.

12. Гальченко В.Г. Системное программирование в среде Win32. Создание Windows приложений / В.Г. Гальченко. Томск: ТПУ, 2009. 83 с.

13. Вирт Н. -Построение компиляторов / Н. Вирт; [пер. с англ. БорисовЕ.В., ЧернышовЛ.Н.]. М.: ДМК Пресс, 2010. 192 с.

14. Johnson M. Hart. Windows System Programming, 4th edition / Hart Johnson. -Addison-Wesley, 2010. 656 p.

15. Thomas W. Doeppner. Operating Systems In Depth: Design and Programming / W. Thomas. John Wiley & Sons, 2010. 462p.

16. Cooper K.D.. Engineering a Compiler. Second Edition / K.D.Cooper, Linda Torczon. Elsevier, 2012. 825 p.

17. Ахо Альфред В. Компиляторы: принципы, технологии и инструментарий, 2-е изд. / Ахо Альфред В.,Лам Моника С., Сети Рави, Джефри Д.; [пер. с англ.]. М.: Вильямс, 2008. 1184 с.

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

...