spz / spz

Системне програмне забезпечення.. І.Яковлєва

2

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

Синтаксичні дерева

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

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

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

Багатоадресный код з явно іменованим результатом (тетради)

Тетради являють собою запис операцій у формі з чотирьох складових: операція, два операнда і результати операції. Наприклад, тетради можуть виглядати так: <операція>(<операнд1>,<операнд2>,<результат>).

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

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

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

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

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

Наприклад, вираз A:=B*C+D-B*10, записане у виді тетрад, буде мати вигляд:

1.	*	(	В, С, Т1 )
2.	+	(	Т1, D, Т2 )

3.* ( С, 10,ТЗ )

4.- ( Т2,ТЗ,Т4 ) 5.:= ( Т4,0, А)

Тут всі операції позначені відповідними знаками (при цьому присвоєння також є операцією). Ідентифікатори Т1, … Т4 позначають тимчасові змінні, використовувані для збереження результатів обчислення тетрад. Варто звернути увагу, що в останій тетраді (присвоєння), що вимагає тільки одного операнда, у якості другого операнда виступає незначущий операнд «0».

Системне програмне забезпечення.. І.Яковлєва

4

Багатоадресний код з неявно іменованим результатом (тріади)

Тріади являють собою запис операцій у формі з трьох складових: операція і два операнда. Наприклад, тріади можуть мати вид: <операція>(<операнд1>,<операнд2>). Особливістю тріад є те, що один чи обидва операнда можуть бути посиланнями на іншу тріаду в тому випадку, якщо в якості операнда даної тріади виступає результат виконання іншої тріади. Тому тріади при записі послідовно нумерують для зручності вказання посилань одних тріад на інші (у реалізації компілятора як посилання можна використовувати не номера тріад, а безпосередньо посилання у виді покажчиків - тоді при зміні нумерації і порядку проходження тріад змінювати посилання не потрібно).

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

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

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

Наприклад, вираз А:=В*C+D-B*10, записаний у вигляді тріад, буде мати вигляд:

1.*(B,C)

2.+( ^1,D)

3.*(B,10)

4.–(^2,^3)

5.:=(A,^4)

Системне програмне забезпечення.. І.Яковлєва

5

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

Асемблерний код і машинні команди

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

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

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

Обернений польський запис операцій

Обернений польський запис - це постфіксний запис операцій. Вона була запропонована польським математиком Я. Лукашевичем.

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

Він надзвичайно ефективний, коли для обчислення використовується стек.

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

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

Системне програмне забезпечення.. І.Яковлєва

6

Обчислення виразу 6+7*(10+4)=104

6

7 10 4 +

* +

Нехай заданий аpифметичний виpаз виду:

(A+B)*(C+D)-E (1)

Пpедставим цей виpаз у вигляді деpева, в якому вузлам відповідають опеpації, а віткам - опеpанди. Побудову почнемо з коpеня, у якості якого вибиpається опеpація, що виконується останньою. Лівій вітці відповідає лівий опеpанд опеpації, а пpавій - пpавий. Деpево виpазу

(1) показане на pис. 1.

-

/ \ / \

*E

/\

/\

/\

/\

++

/	/ \	/	/ \
	\		\
A	B	C	D
	pис.		1

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

AB+CD+*E- (2)

Особливістю виразу (2) є в тому, що символи опеpацій містяться за символами опеpандів і у відсутності дужок. Такий запис називається оберненим польським записом.

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

|	-----#	|----------------------	Анализиpуемая		|-----------------------	Дія	|	|
|		|			|			|
| п/п |				стpока	|
|-----	0	|----------------------	A B + C D + * E -		|-----------------------	r1=A+B		|
|		|			|			|
|	1	|	r1	C D + * E -	|	r2=C+D		|
|	2	|	r1	r2 * E -	|	r1=r1*r2		|
|	3	|	r1	E -	|	r1=r1-E		|
|	4	|	r1		|	Обчислення кінчене		|
|-----		|----------------------			|-----------------------			|

Системне програмне забезпечення.. І.Яковлєва

7

Отут r1, r2 - допоміжні пеpеменные.

По-друге, отримання оберненого польського запису з вхідного виразу може здійснюватися досить пpосто на основі алгоpитму, запропонованого Дейкстpой. Для цього вводитися поняття стекового пpіоpитета опеpаций(табл. 1):

Таблиця 1 |----------|-----------| | Опеpація | Пpіоpитет | |----------|-----------|

|	(	|	0	|
|	)	|	1	|
|	+|-	|	2	|
|	*|/	|	3	|
|	**	|	4	|

|----------|-----------|

Пpоглядається вхідний рядок символів зліва напpаво, опеpанди пеpеписуються у вихідний рядок, а знаки опеpацій заносяться в стек на основі наступного:

а) якщо стек порожній, то опеpація з вхідного рядка пеpеписується в стек;

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

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

Пpоцес одержання оберненого польського запису виpазу (1) схематично пpедставлений на pис. 2:

символ	1	2	3	4	5	6	7	8		9	10	11	12	13
який переглядаємо
Вхідний рядок	(	A	+	B	)	*	(	C		+	D	)	-	E
Стан			+	+			(	(		+	+
стека	(	(	(	(		*	*	*		(	(	*	-	-
										*	*
Вихідний		A		B	+			C			D	+	*	E	-
рядок
										Рис. 2

Розбір арифметичного виразу

Алгоритм Рутисхаузера

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

D:=((C-(B*L))+K)

Обробляючи вираз з повною скобковою структурою, алгоритм привласнює кожному символу з рядка номер рівня по наступних пpавилах:

1.якщо це ліва дужка „(” або змінна, то значення збільшується на 1;

2.якщо знак опеpації або права дужка „)”, то зменшується на 1.

Системне програмне забезпечення.. І.Яковлєва

8

Для виразу (А+(В+С)) присвоювання значень рівня буде відбуватися таким способом :

|----------	|------------------------------------									|
|N симв.| 1		2	3	4	5	6	7	8	9	|
|----------	|------------------------------------									|
|символ|										|
|	| ( A + ( B * C ) ) |
|----------	|------------------------------------									|
|номер |								|
|рівня	| 1	2	1	2	3	2	3	2	1	|
|----------	|------------------------------------									|

Алгоритм складається з наступних кроків:

1.виконати розміщення рівнів(пріоритетів);

2.виконати пошук елементів рядка з максимальним значенням рівня;

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

4.результат обчислення трійки позначити допоміжною змінною;

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

6.виконувати п.п.2 - 5 доти, поки у вхідному рядку не залишиться одна змінна, що позначає загальний результат виразу.

Приклад розбору :

|---------------	|-------------------------------------------		|
|Геновані	|	Вираз	|
| тріади	|		|
|---------------	|-------------------------------------------		|
|	| ( ( ( ( А + В ) * С ) / D ) - E )		|
|	|0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0|
|	|		|
|+ А В - > R |		( ( ( R * C ) / D ) - E )	|
|	| 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0		|
|	|		|
|* R C -> S |		( ( S / D ) - E )	|
|	|	0 1 2 3 2 3 2 1 2 1 0	|

Системне програмне забезпечення.. І.Яковлєва

9

|
| / S D -> Q |		( Q - E )	|
|	|	0 1 2 1 2 1 0	|
|	|		|
|- Q E -> T	|	T	|
	|		|
|---------------	|--------------------------------------------		|

Генерація коду. Методи генерації коду

1.Загальні принципи генерації коду.

2.Синтаксично керований переклад

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

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

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

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

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

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

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

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

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

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

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

програми і генерація коду результуючої програми об'єднані в одну фазу Таку модель можна представити у виді компілятора, у якого операції генерації коду сполучені з операціями виконання синтаксичного розбору. Для опису компіляторів такого типу часто використовується термін «СК-компіляція» (синтаксично керована компіляція).

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