8. GENEROVÁNÍ CÍLOVÉHO PROGRAMU
Generátor cílového programu je poslední částí kompilačních <překladačů. Jeho vstupem je program ve vnitřní formě, vytvořený při zpracování sémantiky a jeho výstupem je cílový program. •
8.1 Druhy cílových programu
Cílový program kompilátoru může být:
1) Posloupnost strojových instrukcí s absolutními adresami.
2) Posloupnost strojových instrukcí s relativními adresami.
3) Posloupnost příkazů jazyka symbolických adres.
Překlad zdrojového programu do strojových instrukcí s absolutními adresami je nejefektivnějším způsobem kompilace. Vytvořený program lze okamžitě spustit a celý proces překladu a výpočtu lze provést během krátké doby.- Hlavní nevýhodou tohoto typu překladu je skutečnost, že musí být překládán celý program-- není možné použití předem připravené knihovny. Z tohoto důvodu se generování strojových instrukcí s ebsolutními adresami používá jen pro malé programy a v případě, že se jedná především o ladění programů (zejména při výuce). Překlad do strojových instrukcí s absolutními adresami provádějí inkrementální překladače.
Posloupnost strojových instrukcí s relativními .adresami je nejčastějším a nejběžjiějším výstupem kompilátoru. Výstupem kompilátoru jsou tzv. přemistitel-né moduly, které je ovšem nutno zpracovat sestavovacím programem. V tomto případě je možné použití předem připravených knihoven, které obsahuji jednotlivé programy opět ve formě přemístitelných modulů.
Program v jazyce symbolických adres je z hlediska konstrukce překladače nejjednodušším výstupem. Překladač v tomto případě neprovádí určování edres e v cílovém programu jsou obvykle zachovane jména veličin zdrojového programu. Nevýhodou tohoto přístupu je nutnost použití překladače jazyk8 symbolických adres k překladu cílového programu kompilátoru do strojového kódu. Tím vlastně přidáváme k celému procesu další fázi, která může být stejně časově náročná jako celá předchozí kompilace.
8.2 Hypotetický počítač
Vytvoření cílového programu závisí ve velké míře na použitém cílovém počítači. Proto budeme definovat hypotetický počítač, jehož vlastnosti budou blízké skutečným počítačům a při tom bude dostatečně jednoduchý, abychom mohli ukázat hlavní myšlenky generování instrukcí dostatečně přehledně.
Hypotetický počítač má peměí s pevnou délkou sIovb a střadeč. Budeme předpokládat, že hypotetický počítač má tyto instrukce:
LOAD    P      ulož obsah paměiového místa P do střadače,
STORE  P      ulož obsah středače na paměíové místo P,
ADD      P       přičti k obsahu střadače obsah peměíového místa P,
SUB      P      odečti od obsahu střadače obsah paměíového místa P,
MPY       P      vynásob obseh střadače obsahem paměťového místa P,
DIV      P      vyděl obsah střadače obsahem peměíového místa P,
CHS               změň znaménko obsahu střadače.
165
8.3 Generováni instrukci pro obrácený polský zápis
Předpokládejme, že vstupem generátoru cílového programu bude program v postfixovém zápisu. Úkolem generátoru cílového programu je přeložit tento program do jazyka hypotetického počítače. Takový překl8<i je jistou obdobou vyhodnocování programu nebo výřezu v postfixovém (obráceném'polském zápisu). Rozdíl spočívá pouze v tom, že potřebné operace se neprovádí okamžitě, ale do cílového programu se vkládejí instrukce, které zajistí provedení potřebných operací v době výpočtu.
Do zásobníku nebudeme ukládat hodnoty operendů, ale adresy nebo případně jiné ^informace o umístěni operandů. Možnosti pro uložení operandů bývají v počítačích různé. Ve výše definovaném hypotetickém počítači může být operand uložen v paměti (P) nebo ve střsdači. Proto si pro operátory, které budeme pře-kládet (+, -, x, /, NEG) sestrojíme tabulky, ve kterých budou uvedeny vytvářené instrukce pro různé možnosti uložení operandů v hypotetickém počítači.
Tabulky pro operátory + a - budou vypadat takto:
+	STR	P (P)
STR		ADD P(P) STR
		
P (L),	ADD P (L) STR	LOAD P (L) ADD P (P) STR
	STR	P (P)
STR		SUB P (P) STR
		
P (L)	STORE Ti LOAD P (L) SUB Ti .STR	LOAD P (L) SUB P (P) STR
Poznámka:
V každé položce tabulky je uveden nakonec údaj o tom, kde bude uložen výsledek operace. Písmeno v závorce udává, zda se jedná o pravý (P) nebo levý (L) operand.
Pro násobení a dělení jsou tabulky podobné jako pro sečítání a odčítání. Pouze se změní operační kód ADD na MPY a SUB na DIV.
Tabulka pro změnu znaménka (NEG) má tvar:
NEG	STR	P
	CHS STR	LOAD P CHS STR
166
Algoritmus 8.1
Generování cílového programu pro obrácený polský zápis (postfixový zápis).
Vstup: Program v obráceném polském zápisu.
Výstup: Posloupnost instrukcí hypotetického počítače.
Metoda: Algoritmus používá zásobník, do kterého ukládá údaje o operandech.
1.  Čti instrukci z vnitřní formy programu. Je-li to popis operandu ulož jej do zásobníku a opakuj 1. Neni-li to popis operandu, přejdi ne ?
2.  Vyber tabulku pro čtený operátor a z této tabulky vyber položku podle druhu operandů (operandu) na vrcholí zásobníku.
3.  Je-li některý z operandů,jehož popis je v zásobníku,uložen ve střa-dači - s výjimkou těch operandů, které vstupují do právě generovaných instrukcí - proved uložení střadače a v zásobníku náhrad STR' označením pomocné proměnné.
(uložení střadače: generuj (STORE Ti), i:=i+1)
4.  Generuj instrukce vybrané v 2.
5.  V zásobníku zruš použité operandy a na vrchol přidej označeni místa, kam byl uložen výsledek.
Přiklad 8,1
Ukážeme si postup generování instrukcí pro výraz
- (A + B) h (C - D), který v obráceném polském zápisu vy« psdá takto:
;i)      TA adr(A)
[2)      DR
.3)      TA adr(B)
!4)      DR
15)     +
!6)      TA adr(C)
(7)  DR
(8)  TA adr(D)
(9)  DR
(10) _ ( 11) * (12) NEG
Generování cílového programu bude probíhat takto:
čtené instrukce	Obsah zásobníku	Vybraná položka z tabulky	Generované instrukce
TA edr(A),DR	adr(A)		
TA adr(B),DR	adr(A),adr(B)		
■¥	STR	+ (P,P)	LOAD adr(A) ADD adr(B)
TA edr(C),BR	STR,8dr(C)		
TA adr(D),DR	STR,adr(C),8dr(D)		
■                         ______________________________	TI, adr(C),adr(D)	'-	STORE TI
	Ti, STR	- (P,P)	LOAD adr(C) SUB adr(D)
167
'---------------- Ctené instrukce	Obsah zásobníku	Vybraná položka z tabulky	Generované instrukce
>	STR	x (P,STR)	MPY TI
NBG	STR	NEG (STR)	CHS
Přiklad 8.2
Pro výraz (A ♦ B) / (C - D) má program v obráceném polském zápisu tvar:
(1)  TA edr(A)
(2)  DR
(3)  TA edr(B)
(4)  DR
(5)  ♦
(6)	TA	adr(C)
(7)	DR	
(8)	TA	adr(D)
(9)	DR	
(10)	-	
(11)	/	
.--------------- Ctené instrukce í	Obsah zásobníku	Vybrané položka z tabulky	Generované instrukce
i TA adr(A),DR	adr(A)		
TA adr(B),DR	adr(A), 8dr(B)		
+	STR	+ (P,P)	LOAD adr(A) ADD adr(B)
TA adr(C),DR	STR, adr(C)		
TA adr(D),DR	STR, adr(C),adr(Di		,',
"	T1,8dr(C),adr(D)		STORE TI
	T1,STR	- (P,P)	LOAD adr(C) SUB Bdr(D)
/	STR	/ (P,STR)	STORE T2 LOAD TI DIV T2
Poznámka:
Kombinaci instrukcí TA, DR chápeme jako popis jednoho operandu.
8.4 Generování instrukcí pro program v jazyce tříadreaových instrukcí
Nejdříve si ukážeme, jak generovat cílový program v případě, ž® program ve vnitřní formě je reprezentován trojicemi. V zásadě lze použít podobného postu* pu jako při generování cílového programu pro postfixový zápis. Je možné dokonce použít stejných tabulek vytvářených instrukci pro jednotlivé operátory« Informace o operandech je součástí trojic. Pouze informace o operandech, které jsou výsledkem předchozích trojic je uvedena v zásobníku.
168
Algoritmus pro preklad trojic do strojového kódu hypotetického počítsče můžeme zspset takto:
Algoritmus 8.2
Generování cílového programu pro trojice.
Vstup: Program ve formě trojic.
Výstup; Posloupnost instrukcí hypotetického počítsče.
Matoda: Algoritmus používá zásobník, do kterého ukládá informace o operandech, které jsou výsledkem jednotlivých trojic.
1. Přečti jednu trojici z vnitřní formy programu.
2. Vyber tabulku pro operátor uvedený v trojici a z této tabulky vyber položku podle
a) operandů uvedených v trojici,
b) operandů uvedených na vrcholu zásobníku v případě, že ve zpracovávané trojici je použit výsledek některé předchozí trojice.
3.  Je-li některý z operandů v zásobníku uložen ve středači - s výjimkou operandů, které vstupují do právě generovaných instrukcí - proved" uložení středače a v zásobníku nahraS STR označením pomocné proměnné.
4. Generuj instrukce vybrané v 2.
5. V zásobníku zruš použité operandy 8 na vrchol přidej označení místa, kam byl uložen výsledek.
-Příklad 8,3
Výřez {'A + B) / (C - D) pomocí trojic zapíšeme takto:
( 1)  + A, B
(2)  - C, D Í3)  / (D, (2)
Proces překladu těchto trojic do strojového kódu hypotetického počítače probíhá takto:
Překládaná trojice	Vybraná položka z tabulky	Generované instrukce	Obsah zásobníku			
(1) + A, B	+ (P, P)	LOAD A ADD B				
					STR	
						
uložení sti-a-deče		STORE T,				
					T1	
						
(2) - C, D	- (P, P)	LOAD C SUB  D				
				STR	TI	
						
(3) / (1),(2)	/ (STR, P)	STORE T2 LOAD T1 DIV   T2				
					STR	
						._
169
Výsledek je úplně stejný jako v případě obráceného polského zápisu.
Nyní si ukážeme algoritmus generováni instrukcí pro trojice, který se nazývá stromový algoritmus (KOMP). Algoritmus je rekurzivní a zpracovává jednotlivé trojice počínaje poslední. Opět si vytvoříme tabulky, ve kterých budou uvedeny činnosti algoritmu pro různé kombinace operandů v trojicích a různé operátory.
Pro operátor + vypadá tabulka takto:
+-	STR	PÍP)	číslo (P)
STR		ADD P(P) STR	STORE Ti KOMP (číslo (P)) ADD Ti STR
			
P(L)	ADD P(L) STR	LOAD P(L) ADD P(P) STR	KOMP (číslo (P)) ADD  (P (D) STR
číslo(L)		KOMP(číslo(D) ADD P (P) STR	KOMP (číslo(D) STR OPAKUJ
			
Pro operátor * je tabulka podobné, pouze místo ADD je MPY. Pro operátor - bude tabulka vypadat takto:
-	STR	P(P)	číslo (P)
STR		SUB P(P) STR	
			
P(L)	STORE Ti Ti OPAKUJ	LOAD P(L) SUB P(P) STR	KOMP (číslo (P)) STR OPAKUJ
číslo(L)	STORE Ti Ti OPAKUJ	KOMP(číslo(D) SUB P(P) STR	KOMP (číslo(P)) STR OPAKUJ
Pro operátor / je tabulka podobná, pouze místo SUB obsahuje DIV.
Pro operátor NEG má tabulka tvar
NEG	STR	P	číslo
	CHS	LOAD P CHS	KOMP (číslo) CHS
1 70
V těchto tabulkách znamená:
KOMP    volání procedury KOMP (rekurzivní), OPAKUJ  opakované prohlížení tabulky.
Práci algoritmu KOMP si ukážeme na příkladě.
Přiklad 8.4
Je dán výraz
(A + B) / (C - D) .
V jazyce trojic je tento výraz zapsán tekto:
(1)  + A,B
(2)  - C,D
(3)  / CD,(2)
Vyvoláme K0MP(3). Parametrem KOMP je číslo poslední trojice.
Generování cílového programu bude probíhat takto:
Zpracovávaná trojice	Vybraná položka z tabulky	Obsah vybrané položky	Generované instrukce
(3)/(D,(2)	/(číslo(L),číslo(P))	KOMP(čísloCP)) STR OPAKUJ	
(2) - C,D	- (P(L), P(P))	LOAD P(L) SUB P(P) STR	LOAD C SUB D
(3)/(D,STR	/(číslo(L).STR)	STORE Ti Ti OPAKUJ	STORE T1
(3)/(1),T1	/(číslo(L).P(P))	KOMP(číslo(L)) DIV P(P) STR	
(1) + A, B	+(P(L),P(P))	LOAD P(L) ADD P(P) STR	LOAD A ADD B
(3)/(l),T1	/(číslo(L).P(P)) pokračování	KOMP(číslo(D)  -DIV P(P)	DIV T1
Tato metoda se hodí zejména v případě, že generování cílového programu se provádí v samostatném průchodu. Důvodem je zpětný chod ve vnitřní formě progremu. V případě generování instrukcí pro čtveřice se dá použít vSech předchozích metod» Pomocné proměnné ovSem nevytváří kompilační program sám, ale jsou již uvedeny ve čtveřicích.
171
Také se dá použít přístup takový, že pro každou čtveřici se vytvoří úsek programu bez ohledu na okolí. Toto je ovšem neefektivní, protože vznikne mnoho zbytečných přesunů. Uvedené metody jsou vhodné pro počítač, který má jen jedenregistr a operační pamět. V případě, že počítač má více registrů, nebo víceúrovňovou operační pamět je třeba tyto postupy přizpůsobit počítači tak, aby cílový program optimálním způsobem využíval nejrychlejších registrů pro uchování mezivýsledků.
1?2