PŘEKLADAČE Flashcards
Základní struktura překladače
Překlad programu - Preprocesor, Překladač, Assembler, Linker
Překladač (compiler) se obvykle skládá z několika fází, které jsou rozděleny do dvou hlavních FE a BE. Mezi nimi často funguje stř. část ME.
Front-End
Cílem je analyzovat vstupní kód, ověřit jeho správnost a převést do reprezentace, která je jednodušší pro další zpracování. Výstupem 2. Interní forma.
- Lexikální analýza
Source code -> seznam tokenů.
Tokeny jsou základní stavební prvky jako keywords, identifiers, operators či literály (int x = 10 -> int, x, =, 10) - Syntaktická analýza
Vytváří syntaktický strom na základě pravidel deklarace proměnných nebo rozsah platnosti
(odpovídá var x = 10 správné struktuře deklarace proměnné?) - Sémantická analýza
Ověřuje, zda má kód smysl z pohledu logiky jazyka. Kontroluje datové typy, deklarace, rozsah platnosti.
(př. je proměnná x deklarovaná před jejím použitím nebo zda přiřazení do proměnné odpovídá jejímu typu)
Middle-End
V této fázi se kód optimalizuje aniž by byla změněna funkčnost.
Optomalizace lokální, globální, sloučení cyklů, mezifunkční, okénková, dead code elimination.
Back-End
Převádí interní formu do kódu specifického pro cílovou platformu (př. strojový kód procesoru)
- přidělování registrů, volba instrukcí, optimalizace
Formy cílového programu
- jazyk stroje
- modul s relativními adresami
- jazyk symbolických adres
- jiný programovací jazyk
Další komponenty překladače:
- Error Handler - zpr. chyby v průběhu všech fází překladu a poskytuje srozumitelné hlášky
- Tabulka symbolů - uchovává informace o identifikátorech (proměnné, funkce, třídy atd.), jejich typech, rozsahu platností a další metadata
- Správa paměti - řídí přidělování paměti pro proměnné, funkce a další obj v překladu i za běhu
Překladač tedy pracuje jako pipeline:
1. Zdroj kód
2. FrontEnd (LE, SynE, SemE)
3. MiddleEnd (Opt)
4. BackEnd (Gen Stroj K)
5. Cílový program
Každá fáze má spec. úlohu a společně zajišťují správný a efektivní překlad programu.
Interpret - negeneruje cílový kód, ale vypočítá interní formu.
( + ) jednodušší na sestavení
( – ) pomalejší na výpočet
1. Zdroj kód
2. Front End
3. Interpretace
4. Výsledek
Fáze analýzy a syntézy překladu
Analýza
- Lex
- Syntax
- Sém
Výstupem je IF - nezávislá na platformě
Syntéza
- Opt
- Generace cílového kódu
- Opt pro cílový jazyk
Zpracuje analyzovaný kód na spustitelný program.
Lexikální analýza, její úloha a konstrukce lex. analyzátoru
První část překladače.
Úloha
- převádí zdrojový kód programu (text) na základní stavební jednotky - tokeny
- tokeny - významové prvky kódu, zpracovávány v dalších fázích překladu.
Zjednodušuje následné fáze překladu, detekuje lexikální chyby, než se program dostane do složitějších analýz.
Čte kód a vykonává:
1. Rozpoznává atomy a program převádí do 1. IF (což je posloupnost symbolů)
2. Odstraňuje whitespaces (mezery, tabulátory, nové řádky)
3. Vynechává poznámky a komentáře
Atomy jsou: klíčová slova, identifikátory, konstanty, oddělovače, operátory
Lexikální analýzu lze popsat regulárními gramatikami a realizovat konečným automatem.
Interní forma posloupnosti symbolů:
- každému lexikálnímu symbolu je přiřazeno celé číslo
- jednoznakové symboly (ASCII), víceznakové (celé číslo > ASCII), symboly s hodnotou (identifikátor + konstanta)
Lexikální analyzátor musí zjistit, kde symbol končí, oddělit znaky, postupné přidávání symbolů
Klíčová slova v programu
- stejná syntax jako identifikátory (spec. případ id.)
- 2 způsoby rozpoznání: Lex. analyzátorem / Syntakt. analyz (lex an nerozpozná a předává jako identifikátor)
- efektivní způsob zjistění, zda je identifikátor keyword - přes hashovací tabulku klíčových slov
Rozpoznatelné chyby lex. analyz.
1. identifikátor má vysoký počet znaků
2. chybný zápiš čísla
3. číslo má nepřípustnou hodnotu
4. chybný zápis znaku/řetězce
5. řetězec moc dlouhý
6. znak netvořící žádný lex. symbol
Lex analyzátor je začleněn do překladu jako jedna funkce volající syntaktickým analyzátorem pokaždé, když potřebuje další symbol pro syntakt. anal.
Konstrukce:
1. Ruční konstrukce
– Lexikální analyzátor je naprogramován ručně pomocí podmínek a smyček. Tento přístup je vhodný pro jednoduché jazyky nebo speciální účely.
– Lze přizpůsobit specifickým požadavkům, ale obtížné na údržbu
- Regulární výrazy
– Lexikální analyzátor lze sestavit pomocí regulárních výrazů, které odpovídají jednotlivým druhům tokenů. Tento přístup je efektivní a přehledný. - Generátory lexikálních analyzátorů
– Existují nástroje, které automaticky generují lexikální analyzátor na základě pravidel tokenů a gramatiky (Lex/Flex)
Syntaktická analýza shora-dolů, gramatiky LL(1)
- syntaktická analýza je k rozpoznávání syntaktických celků programu a ty následně předává k sémantické analýze.
- nelze popsat regulární gramatikou (protože závorky), používá se bezkontextová gramatika.
- synt. an. je založena na konstrukci determin. zásob. automatu, který analýzu provádí.
- při analýze se sestavuje derivační strom odp. překladu programu.
- strom se sestavuje buď shora-dolů, nebo zdola-nahoru.
Princip analýzy shora-dolů:
- používá se zásobníkový automat bez stavů, pracuje se pouze s vrcholem zásobníku
- operace:
a) Expanze - na vrcholu zásobníku je neterminál -> derivován na pravou stranu pravidla gramatiky
b) Srovnání - na vrcholu zásobníku je terminál, srovná se se symbolem na vstupu, pokud shoda -> odebrání
- program je syntakticky správný, je-li na konci zásobník prázdný
LL(1) znamená
L - vstup čten zleva
L2 - derivace nejlevějšího neterminálu
(1) - stačí číst vstupní řetězec po 1 symbolu
Množina First - množina terminálů, které se mohou vyskytnout na prvním místě větné formy
Množina Follow - množina terminálů, které se derivacemi z počátečního symbolu mohou nacházet hned za daným neterminálem ve větné formě
Gramatika musí být bez levé rekurze, a pokud ji obsahuje, je třeba ji eliminovat:
A → Aα | β
…lze převést na ↓
A → βA’
A’ → αA’ | ε
Konstrukce zásob. aut. pro gram. LL(1):
1. Očíslování derivačních pravidel gramatiky (vnořená pravidla expandujem)
2. Pro každé pravidlo A→a spočítáme množinu First(aFollow(A))
3. Sestavíme tabulku - sloupce terminály + epsilon, řádky neterminály;
- pokud se daný terminál nachází v množině firstFollow daného neterminálu, na danou pozici vepíšeme číslo derivačního pravidla, jinak empty
4. Čteme vstup, na zásobník jde počáteční symbol pravidel gramatiky, následuje posloupnost akcí Expanze/Srovnání
5. Jakmile je prázdný zásobník, vstupní řetězec je syntakticky správný
Konstrukce syntaktického analyzátoru metodou rekurzivního sestupu
Co je to syntakt. anal. krátce
- metoda spočívá v tom, že pro každé pravidlo gramatiky se vytvoří samostatná procedura, která rozpoznává odpovídající syntaktické konstrukce. Tato metoda je jednoduchá a intuitivní, ale funguje pouze pro určité typy gramatik, konkrétně pro LL(1) gramatiky
Pro každý neterminál sestavíme funkci, která dělá analýzu podle všech derivačních pravidel s tímto symbolem na levé straně.
func Stovnani(u):
if u==v: lex()
else: chyba()
ParseA()
switch (u):
- každý case odpovídá každému pravidlu a prochází pravou stranu pravidla postupně
u = lex() always na začátku, Srovnani pro terminal, Parse pro neterminal, return na konci
case pro epsilon je # a vždy následuje return
default: chyba(); return;
Výhody metody rekurzivního sestupu:
- Jednoduchost: Lze snadno implementovat přímo v kódu, procedurálně.
- Přehlednost: Struktura analyzátoru přímo odpovídá struktuře gramatiky.
- Dobrá efektivita: Vhodné pro jednoduché gramatiky.
Nevýhody:
- Omezené použití: Nelze použít pro gramatiky s levou rekurzí nebo složitější konflikty.
- Náchylnost na chyby: Nutné přesně eliminovat konflikty v gramatice.
Rekurzivní sestup je často používaný v menších projektech nebo při výuce syntaktické analýzy. Pro složitější gramatiky se používají automaticky generované analyzátory (např. pomocí nástroje YACC nebo ANTLR).
Ošetření konfliktů:
1. Levá faktorizace - pro konflikty v množině First
– pokud více alternativ začíná stejným prefixem, nelze rozhodnout, kterou alternativu použít
A → αβ | αγ
Vyjmeme společný prefix a vytvoříme nové pravidlo:
A → αA’
A’ → β | γ
- Pohlcení řetězce - FIRST FOLLOW konflikt
– tento problém nastává, když pravidlo obsahuje epsilon-derivaci (prázdný přechod) a není jednoznačné, kdy tuto derivaci použít. - Odstranění levé rekurze
– levá rekurze je problémem, protože způsobuje nekonečnou rekurzi při použití rekurzivního sestupu. Pravidla s levou rekurzí mají tvar:
A → Aα | β
Transformace na pravidlo bez levé rekurze zavedením nového neterminálu:
A → βA’
A’ → αA’ | ε - Substituce
– aplikace více technik najednou (levá faktorizace, odstranění levé rekurze, případně rozložení pravidel). Pokud jedno pravidlo závisí na jiném, můžeme provést substituci jeho definicí, aby vznikla jednodušší gramatika.
A → Bc | d
B → ef | g
Subst. nahradíme B v pravidle A:
A → efc | gc | d - Ruční ošetření: Některé konflikty v gramatice nelze vyřešit automaticky. Je třeba ručně modifikovat gramatiku tak, aby byla deterministická (vhodná pro LL(1)).
- Přechod na synt. analýzu zdola nahoru: Pokud gramatiku nelze převést na LL(1), je nutné použít metodu analýzy zdola nahoru (např. LR, SLR, LALR).
Syntaktická analýza zdola-nahoru
Syntaktická analýza analyzuje posloupnosti formálních prvků s cílem určit jejich gramatickou strukturu vůči předem dané (byť ne nutně explicitně vyjádřené) formální gramatice.
Zdola-nahoru je metoda analýzy, která se snaží zrekonstruovat derivaci pravé věty gramatiky (tj. zpětnou derivaci), a to postupným skládáním terminálních a neterminálních symbolů do vyšších struktur, dokud se nedosáhne počátečního symbolu gramatiky.
Syntaktická analýza zdola nahoru je robustní metoda, která je základem mnoha moderních kompilátorů. Díky své obecnosti a schopnosti zvládat širokou škálu gramatik (včetně těch, které obsahují levou rekurzi nebo složité FIRST/FOLLOW vztahy) je často preferována v praxi. Její použití zahrnuje zejména generované analyzátory, jako jsou ty vytvořené pomocí nástrojů YACC, Bison nebo ANTLR.
Princip a Hlavní charakteristiky syntaktické analýzy zdola nahoru
- Postup od listů k vrcholu stromu:
- Analýza začíná zpracováním vstupních terminálních symbolů a hledá, zda je možné je postupně redukovat podle pravidel gramatiky na neterminály.
Cílem je získat kořenový symbol (počáteční symbol gramatiky). - Pracuje se zásobníkem:
- Symboly zpracované z vstupu se ukládají na zásobník.
Podle pravidel gramatiky se na zásobníku provádějí operace posunu (shift) nebo redukce (reduce). - Determinismus:
- U deterministických analyzátorů jsou rozhodnutí (posun/redukce) vždy jednoznačná, což je zajištěno vhodnou gramatikou (např. třída LR). - Typ derivace:
- Zdola nahoru odpovídá derivaci pravé derivace pozpátku (rightmost derivation in reverse).
Operace a Kroky syntaktické analýzy zdola nahoru
1. Posun:
Terminální symbol z vstupu je přesunut na zásobník.
Používá se, pokud aktuální symbol nelze ještě redukovat.
- Redukce:
Sekvence symbolů na vrcholu zásobníku je nahrazena odpovídajícím neterminálem podle pravidla gramatiky.
Např. pokud pravidlo říká A → xyz a na zásobníku je xyz, je tato sekvence nahrazena symbolem A. - Přijetí:
Analyzátor úspěšně dokončil analýzu, pokud byl celý vstup zpracován a zásobník obsahuje pouze počáteční symbol. - Error (chyba):
Pokud žádná akce (shift/reduce) není možná a vstup není zcela zpracován, analyzátor hlásí chybu.
vstup, zásobník, akce - naznačit příklad
Výhody syntaktické analýzy zdola nahoru
1. Obecnost:
Zvládá širší třídu gramatik než analýza shora dolů (např. zvládá levou rekurzi).
- Efektivita:
Deterministické metody (např. LALR(1)) jsou výpočetně efektivní a často používané v generátorech parserů (např. YACC, Bison). - Podpora složitějších gramatik:
Analýza zdola nahoru zvládá gramatiky, které nejsou LL(1), což je častý limit analýzy shora dolů.
Deterministickou analýzu zdola-nahoru umožňuje třída gramatik LR - LR(0), SLR(1), LALR(1), LR(1)
L - vstupní řetězec čten zleva
R - derivace nejpravějšího symbolu (neterminálu) na zásobníku
SLR - Simple LR, LALR - Lookahead LR
Nevýhody syntaktické analýzy zdola nahoru
1. Komplexita implementace:
Konstrukce tabulek pro LR analyzátory může být složitá (zejména u LR(1)).
Vytváří velké tabulky, což může být paměťově náročné.
- Menší srozumitelnost:
Postup zpětné derivace může být pro člověka méně intuitivní než postup shora dolů.
Konstrukce syntaktického analyzátoru pro gramatiky SLR(1) a LALR(1)
z’ - nový zásobníkový symbol
Z - výchozí zásobníkový symbol
NuT - přesouvaný zásobníkový symbol
M/U(M) - vytvořená množina při přesunu / její uzávěr
- první řádek S’→.S a její uzávěr
- z’ ++, Z je podle z’, kde bereme další posun tečky
- epsilon mívá tečku rovnou za
- pokud se něco opakuje, z’ nemá nové číslo, nýbrž číslo předchozího výskytu M/U(M)
- takto pokračujem, dokud z’ > Z
- vytvoříme tabulku, sloupce N, #, T; řádky čísla z’ (včetně 0)
- přesuny se zapisují easy, projedeme všechny řádky zprava sloupec NuT a řádek Z bude mít číslo z’
8a. k redukcím potřeba vytvořit množiny Follow ke všem neterminálům a derivační pravidla expandovat a očíslovat včetně S’→S
8b. u redukčních položek (zakroužkovaných pravidel s tečkou vpravo) - prvky Follow množiny levého neterminálu zakroužk. pravidla jako sloupce, z’ jako řádek a číslo zakrouž. pravidla s pluskem je hodnota do tabulky - u zakrouž S’→S. jde do tabulky H jako Halt pro sloupec # a řádek z’ na kterém se zakroužk pravidlo S’→S. nachází
Poté můžeme ověřit na větě aac:
Vstup, zásobník, akce, fráze
aac 0 a0 -> 3 - přesun a na zásobník 3
ac 03 a3 -> 3 —ll—
c 033 c3 -> +4 tj. redukce dle pravidla 4, odebereme počet čísel ze zásobníku kolik symbolů je na levé straně derivačního pravidla a přidáme na zásobník číslo pro neterminál na levé straně derivačního pravidla podle čísla na zásobníku (sloupec neterminál, řádek číslo na zásobníku)
LALR(1) podobně, akorát navíc prediktivní množina v položkách M i jejího uzávěru
Sémantická analýza
- klíčová fáze překladu kódu v překladači (compileru), která následuje po lexikální a syntaktické analýze
- jejím cílem je zajistit, že zdrojový kód má sémantický (významový) smysl
- tzn. ověřuje pravidla, která nejsou zachytitelná pouhou syntaxí; například typovou správnost, deklaraci proměnných a další kontextové informace
Proměnné
- deklarace proměnných
- viditelnost proměnných
Typy
- operace nad daty odpovídá jejím typům
- typová správnost přiřazení hodnot
- bezpečnost konverze mezi typy
Fce
- existence funkcí před voláním
- kontrola počtu a typů argumentů
- kontrola návratových hodnot
Zatímco syntaxe programovacích jazyků bývá často podobná, sémantika se může výrazně lišit (např. imperativní, funkcionální, logická, simulační paradigmata). Sémantická analýza je složitější než syntaktická, a proto místo univerzálních automatických nástrojů, které fungují dobře pro syntaxi (např. syntaktické analyzátory), se často používají specifické přístupy, jako jsou atributové gramatiky, pro formální popis a kontrolu sémantických vlastností programu.
Atributová gramatika
Zatímco syntaxe programovacích jazyků bývá často podobná, sémantika se může výrazně lišit (např. imperativní, funkcionální, logická, simulační paradigmata). Sémantická analýza je složitější než syntaktická, a proto místo univerzálních automatických nástrojů, které fungují dobře pro syntaxi (např. syntaktické analyzátory), se často používají specifické přístupy, jako jsou atributové gramatiky, pro formální popis a kontrolu sémantických vlastností programu.
AtribGram
- nadstavba bezkontextové gramatiky G, která popisuje syntax
- přidává sémantické informace ve formě atributů a sém. pravidel
- Atributy jsou sém. údaje přiřazené symbolům NuT
- symbol x€NuT může mít lib. počet atributů
-A(x) → množina atributů symbolu x - a€A(x) - X.a
- atribut má lib. dat. typ
- sém. pravidla jsou vázána k syntakt. pravidlům
- sém. pravidlo má libovolný tvar funkce
X0.a - syntetizovaný atribut
- sém. info se šíří směrem nahoru
Xi.a - dědičný atribut
- i > 0
- sém. info. se šíří směrem dolů
Definice AG = (G, A, R)
G - bezkontxt gram
A - množina atributů
R - množina sém pravidel
AS(x) - množ. syntet. atrib sym x
AI(x) - množ dědič atrib sym x
AG je “dobře definovaná” pokud:
1. v každém deriv. stromu pro každý v něm obs atribut exist prav pro jeho výpočet
2. je acyklická - existuje posloupnost závislostí při počítání atributu
L-Atributová gramatika
- umožňuje průběžný výpočet atributů při analýze shora-dolů, (pro výpočet atributů je analýza zdola nahoru méně výhodná, lze počítat atrib jen pro levou stranu pravidla)
- pro L-atrib.gram AG, kde G je LL(1) lze sestavit deterministický sémantický automat se 2 zásobníky:
- syntaktický - ukládání zásobníkových symbolů automatu
- sémantický - ukládání atributů
syntakt. X0; X1, X0
séman. AI(X0), AI(X1), AI(X0)
E→E+E
if E[2].typ == pointer and E[3].typ == int:
E[1].typ = pointer ……
zkus E → identifikator
S-Atributová gramatika
- umožňuje průběžný výpočet atributů při analýze zdola-nahoru
- obsahuje pouze syntetizované atributy
- realizace jedním zásobníkem
přesun + redukce
vstup E float
symbol ◘
(◘E int & j int … redukce E→j
redukce E→E&E
Interní formy programu
IF jsou reprezentace kódu uvnitř překladače nebo interpretu, které slouží k efektivní analýze, transformaci a generování strojového kódu. Tyto formy umožňují překladači abstrahovat od konkrétního zdrojového jazyka a přiblížit se úrovni, která je vhodná pro optimalizaci a cílový stroj.
Základní druhy interní formy jsou
- Stromová AST
- Literární - trojice, čtveřice
Stromová:
Abstract Syntax Tree
- odvozena z derivačního stromu
- vynechání nepotřebných částí (neterminálů) (-> př. uzly jsou pouze operátory a listy terminály)
Literární forma
- běžná
- trojadresová (čtveřice):
operace / 1. operand / 2. operand / výsledek
a = b * (c+d-e)
+ / c / d / t1
- / t1 / e / t2
* / b / t2 / t3
= / t3 / / a
Forma trojic: sloupec výsledku nahrazen číslem řádku
Další formy jsou
- grafová reprezentace toku dat
- graf repr bloků kódu
Účel interních forem:
- Modularita překladače:
Odděluje syntaktickou, sémantickou analýzu a generování kódu.
Umožňuje snadnější implementaci více cílových jazyků. - Optimalizace kódu:
Interní reprezentace je vhodná pro aplikaci různých optimalizací, jako je eliminace mrtvého kódu, zřetězení smyček nebo přeskupení instrukcí. - Přenositelnost:
Mezikód umožňuje překladači generovat kód pro různé architektury z jedné společné reprezentace. - Efektivita analýzy:
Strukturované formy jako AST a grafy usnadňují analýzu sémantiky a kontrolu správnosti programu.
Překlad základních příkazů programovacích jazyků do interní formy
Základní druhy interní formy jsou
- Stromová AST
- Literární - trojice, čtveřice
Stromová:
Abstract Syntax Tree
- odvozena z derivačního stromu
- vynechání nepotřebných částí (neterminálů) (-> př. uzly jsou pouze operátory a listy terminály)
Literární forma
- běžná
- trojadresová (čtveřice):
operace / 1. operand / 2. operand / výsledek
a = b * (c+d-e)
+ / c / d / t1
- / t1 / e / t2
* / b / t2 / t3
= / t3 / / a
Forma trojic: sloupec výsledku nahrazen číslem řádku
Tabulky symbolů
Tabulky symbolů jsou klíčovou komponentou překladačů, které slouží k uchovávání informací o identifikátorech používaných v programu. Tyto tabulky jsou datovou strukturou, která pomáhá překladači zpracovávat deklarativní části programu, analyzovat kód a zajistit správnou interpretaci nebo překlad zdrojového kódu.
Účel tabulek symbolů:
- Tabulky symbolů jsou používány zejména k:
1. Ukládání informací o identifikátorech
Identifikátory zahrnují proměnné, konstanty, funkce, třídy, metody a další pojmenované entity. Tabulka symbolů pro každý identifikátor uchovává informace jako:
- Název identifikátoru.
- Typ (např. datový typ proměnné, návratový typ funkce).
- Rozsah (scope), ve kterém je identifikátor platný.
- Umístění (adresu v paměti nebo offset).
- Případné další atributy (např. přístupová práva, modifikátory).
- Podpora sémantické analýzy
Při sémantické analýze překladač využívá tabulky symbolů ke kontrole:
- Typové konzistence (type checking).
- Existence deklarace identifikátorů před jejich použitím.
- Rozsahové viditelnosti (scope resolution). - Podpora generování kódu
Informace v tabulkách symbolů se využívají při překladu do cílového kódu, zejména pro přiřazení paměti a přístup k proměnným nebo funkcím.
Organizace tabulek symbolů
Tabulka symbolů může být organizována různými způsoby v závislosti na konkrétní implementaci překladače. Obvyklé struktury zahrnují:
1. Hashovací tabulky
Pro rychlé vyhledávání identifikátorů. Hashovací tabulky se často používají díky jejich efektivitě.
2. Stromy
Např. binární vyhledávací stromy (BST) nebo vyvažované stromy (AVL, Red-Black), které poskytují dobrý výkon při vyhledávání i vkládání.
3. Lineární seznamy
Používají se v jednodušších překladačích nebo tam, kde není prioritou rychlost.
Typy tabulek symbolů:
- Globální tabulka symbolů
Obsahuje informace o identifikátorech dostupných v celém programu, jako jsou globální proměnné a funkce. - Lokální tabulky symbolů
Uchovávají informace o identifikátorech specifických pro určité bloky, funkce nebo metody. Při vstupu do nového bloku se vytvoří nová tabulka a při jeho opuštění se zruší. - Hierarchické tabulky symbolů
Používají se v jazycích s hierarchickou strukturou rozsahů, jako je C++, kde mohou třídy nebo namespace mít své vlastní tabulky symbolů.
Význam pro překladače
Tabulky symbolů umožňují překladači efektivně analyzovat a generovat kód. Díky nim je možné:
- Správně spravovat paměťové zdroje.
- Detekovat chyby v programu (např. redefinici proměnných, nesprávné typové operace).
- Vytvářet optimalizovaný a dobře strukturovaný cílový kód.
Bez tabulek symbolů by proces překladu byl mnohem složitější, neefektivní a náchylný k chybám. Tyto tabulky tedy tvoří základní kámen moderních překladačů.
Generování kódu, úloha přidělování registrů
Generování kódu je klíčovou fází překladu programu, kdy překladač transformuje interní formu reprezentaci kódu do cílového kódu (př. strojový kód nebo kód v jazyce assembler)
Generování kódu přináší různé výzvy, přičemž mezi ty nejdůležitější patří:
- Stanovení pořadí výkonu instrukcí
- Přidělování registrů
Stanov. poř. výk. instr.
- souvisí s pipeline architekturou procesorů, v nichž jsou vykonávané instrukce rozděleny na pevný počet fází
- typicky 5:
1. načtení instrukce
2. dekódování operačního kódu
3. výpočet operace nebo výpočet adresy pro čtení/zápis
4. přístup do paměti
5. zápis výsledku do registru - procesor může vykonávat všech 5 fází současně (každou u jiné instrukce)
- prohození operací může výpočet zrychlit
Přidělování registrů
- klíčová činnost pro generování kódu je sestavení efektivního využití registrů
- optimální využití registrů je však NP-úplný problém
- používá se metoda barvení grafu
Základní pojmy
Proměnná je:
- definována - jestliže ji byla přiřazena hodnota
- živá - jestliže byla proměnná definována, někde dále je na ni reference a mezitím nebyla znovu definována
- oblast života proměnné - část programu mezi definicí a referencí
Vlastnosti grafu interferencí:
- uzly - oblasti života proměnných
- spojení dvou uzlů hranou - pokud se oblasti života (repr. těmito uzly) překrývají (tzn hodnoty nemohou být uchovány ve stejném registru)
ALGORITMUS PŘIDĚLOVÁNÍ REGISTRŮ BARVENÍM GRAFU
- Výchozí podmínky:
- je dán graf interferencí I
- je k dispozici m registrů reprezentovaných m barvami
Hledání obarvení:
1. Vychází se z počátečního grafu G, který je postupně upravován
- nechť G je úplný podgraf grafu I
- z grafu G postupně odebíráme uzly a ukládáme je na zásobník Z s postupem:
- Je-li v grafu G uzel se stupněm < m ? (tj menší počet sousedů než počet barev)
- tzn. je obarvitelný -> uložíme ho na zásobník Z
- ELSE jinak krok 3 - Odebereme z G jakýkoliv uzel (snížíme počet sousedů), uložíme na zásobník a opět zkusíme krok 2
- Po ulložení všech uzlů na zásobník uzly odebíráme ze zásobníku a barvíme uzly grafu I postupem:
- Odebereme uzel u ze Z
- najdeme barvu s nejmenším číslem takovou, kterou lze uzel obarvit (s ohledem na obarvené sousefy v grafu I)
- pokud taková barva neexistuje, vezmeme z neobarvených uzlů uzel s největším stupněm a odebereme z I a celý proces opakujeme od 1
Po ukončení algoritmů - obarvené uzly představují proměnné, jejichž hodnoty lze uchovávat v registrech.
Příklad:
1. Oblasti života proměnných
2. Graf interferencí
