Úvod – z historie Kompilátory
z
nová koncepce počítače (společná paměť pro kód programu a zpracovávaná data) vytvořila podmínky pro vznik softvéru na přípravu programů
RNDr. Miroslav Benedikovič z
Katedra informatiky v dopravě Dopravní fakulta Jana Pernera Univerzita Pardubice
John Louis von Neumann – r. 1946
Katedra informatiky Fakulta riadenia a informatiky
Grace Murray Hopper – r. 1951 vznik myšlenky programu, který umožní přeložit instrukce z vyššího jazyka do strojového kódu.
Žilinská univerzita
Kompilace / Kompilátor Compile / Compiler
Kontakt: •
(+421 41) 513 4 187
•
[email protected]
2
Úvod – z historie z
– – –
z
–
3
První pohled - „Černá skříňka“
Pod jeho vedením byl v r. 1954 až 1957 ve firmě IBM vyvinutý první kompilátor jazyka FORTRAN – formula translation Byl to problémově orientovaný jazyk pro řešení matematických úloh Vývoj spotřeboval 18 člověko-let (staff-years) implementace Stavba tohoto kompilátoru nebyla založena na nějakém teoretickém základě. Jeho struktura, komponenty a techniky vznikali „ad-hoc“
Zdrojový Zdrojový program program
Noam Chomsky –
12.2. - 11.5. 2007
Pojem kompilátoru
John Backus –
Kompilátory
12.2. - 11.5. 2007
Cílový Cílový program program
Chybové Chybové zprávy zprávy protokoly protokoly
Výzkum v oblasti struktury přirozených jazyků. Základy vývoje a tvorby moderních jazyků a jejich kompilátorů .
Kompilátory
KOMPILÁTOR
4
Kompilátory
12.2. - 11.5. 2007
1
Typická Typická organizace organizace kompilátoru kompilátoru
Úvodní pojmy
Zdrojový (Source) kód (posloupnost znaků)
z
Lexikální analyzátor (scanner)
Zdrojový jazyk – jazyk, ve kterém sestavíme zdrojový text, ten je vstupem pro kompilátor (Pascal, C++, Java, ...)
z
Cílový jazyk – jazyk, do kterého přeloží kompilátor
Posloupnost tokenů
zdrojový text, procesor ho dokáže interpretovat z z z
Syntaktický analyzátor (parser) Abstraktní syntaktický strom
Rozšířený označený syntaktický strom
Hostující jazyk – programovací jazyk, ve kterém sestavíme kompilátor
POPREDIE
Analýza – rozeznává nějaký zdrojový jazyk L Syntéza – vytváří cílový kód v cílovém jazyku L'
POZADIE
Kompilátory
Pomocný kód
Optimalizátor
Back end
Optimalizovaný pomocný kód
7
Generátor kódu
12.2. - 11.5. 2007
Fázy kompilátoru
z
Generátor pomocného kódu
Front end
Cílový (Object) kód (může být assemblerovský nebo strojový kód)
5
Sémantický analyzátor
Scanner – lexikální analyzátor z
Lineární analýza, scanning – proud znaků tvořící zdrojový program je čtený zleva doprava, vyhledávané jsou významové posloupnosti znaků tvořící vždy nedělitelný jedno resp. víceznakový symbol - lexému. Každé z lexém je přiřazený token. Této fáze se častěji říká lexikální analýza, anebo scanning
z
Hierarchická analýza, parsing – naskenované symboly anebo tokeny jsou sdružované do syntaktických celků podle přesně stanovených gramatických pravidel jazyka. Tuto fázi voláme syntaktickou analýzou
z
Sémantická analýza – vykonávají se určité kontroly pro zajištění správného významu příslušných komponentů v celkovém kontextu programu, případně jeho částí
Kompilátory
12.2. - 11.5. 2007
z z
z
8
Čte postupně jednotlivé znaky ze zdrojového programu Seskupuje znaky do LEXÉM (jsou to posloupnosti znaků, které „patří k sobě“; popisují nějakou entitu jazyka) Každá lexéma odpovídá jednomu TOKEN-u (je to prvek jazyka s definovaným významem); scanner vrací následující token (případně další přídavnou informaci) a odesílá ho do parseru Scanner odhaluje lexikální chyby (např. nekorektní znaky)
Kompilátory
12.2. - 11.5. 2007
2
Lexéma / Token - jejich vzájemný vztah
z
Scanner čte příslušnou posloupnost znaků – tzv. lexému Přiradí lexémě dohodnutý kód – token
z
Pro scanner je pořadí lexém nevýznamné !!
z
9
Lexéma
Token
:
COLON
index
IDENT
:=
ASSIGN
Příklad v jazyku Pascal z
Pozice := zaklad + posuv * 60
Význam
• Scanner zjistil následující lexémy a tokeny
dvojtečka
Lexémy:
identifikátor
Pozice
tmp
IDENT
identifikátor
37
INT-LIT
celočíselní literál
10.2
REAL-LIT
while
LOOP-WHILE
<=
LE
Tokeny:
z
z
11
IDENT
+
posun
*
60
OP-KRAT
INT-LIT
(například jednobytové hodnoty) ASSIGN
IDENT
OP-PLUS
IDENT
cyklus While relace menší anebo rovný 12.2. - 11.5. 2007
10
Kompilátory
12.2. - 11.5. 2007
Syntaktický strom
Seskupuje tokeny do gramatických vět - fráz Zkoumá gramatickou strukturu zdrojového programu Hledá syntaktické chyby, například následující věta v Pascalu: pozice := * 5 je lexikálně správná, ale syntakticky je chybná !! Může hledat i některé "statické sémantické" chyby, například nedeklarované proměnné, případně víckrát deklarované proměnné Generuje vnitřní reprezentaci programu vyjadřující ve tvaru abstraktního syntaktického stromu a buduje program ve vnitřním jazyku Kompilátory
zaklad
literál reálního čísla
PARSER - syntaktický analyzátor
z
:=
přiřazení
Kompilátory
z
Přiřazovací příkaz:
12.2. - 11.5. 2007
z
Datová struktura s následujícími vlastnostmi: – – – –
vnitřní uzly stromu obsahují OPERÁTORY synové uzlu obsahují OPERANDY příslušné operace počet synů odpovídá počtu operandů operace každá část podstromu je samostatnou "logickou jednotkou„
X+Y
if A<0 then Pr1 else A:=B+1
if
+ X
<
Y A
Pr1 0
:= A
+ B
12
Kompilátory
1 12.2. - 11.5. 2007
3
Příklad v jazyku Pascal z
Sémantický analyzátor
Přiřazovací příkaz:
z
pozice := zaklad + posuv * 60
z ASSIGN IDENT
z
OP-PLUS IDENT
OP-KRAT
13
z
INT-LIT
IDENT
V uzlech stromu jsou tokeny !! Informace o lexémech jsou v tabulce symbolů Kompilátory
12.2. - 11.5. 2007
14
Rozšířený syntaktický strom z
z
:=
z
+ z stupen real
15
z
*
zaklad real
z
Kompilátory
inttoreal()
Doplněný je uzel s funkcí inttoreal() pro převod celočíselné hodnoty na reálnou Kompilátory
12.2. - 11.5. 2007
Generátor vnitřního kódu
Uzly ve stromě jsou doplněny sémantickými informacemi o typu hodnot
pozice real
Jako vstup používá abstraktní strom vytvořený scannerem Zjišťuje kompatibilitu typů jednotlivých hodnot typová kontrola V případě potřeby doplňuje uzly konverzními funkcemi pro změnu typu hodnoty na kompatibilní typ, například integer na ty real Generuje vnitřní reprezentaci programu vyjadřující ve tvaru abstraktního syntaktického stromu
z
60
12.2. - 11.5. 2007
16
Překládá data z abstraktního syntaktického stromu do pomocného vnitřního kódu (intermediate code) Je to zjednodušený kód nezávislý na cílovém jazyku, například tříadresový kód podobný assembleru. V mnohých pascalovských kompilátorech je populární tzv. P-kód Je ho možné lehčeji vytvořit, než konkrétní cílový program Výstupem je tzv. vnitřní tvar programu – intermediate representation, připravený pro zpracování v závěrečné syntetizační části kompilátoru V této etapě kompilace je možno vykonávat optimalizaci programu
Kompilátory
12.2. - 11.5. 2007
4
Popředí / pozadí
Optimalizátor z
Bez Bez vnitřní vnitřní reprezentace: reprezentace:
SS vnitřní vnitřní reprezentací: reprezentací:
Umožňuje vylepšit cílový kód z hlediska – –
PASCAL
procesor 1
PASCAL
C++
procesor 2
C++
FORTRAN
procesor 3
FORTRAN
procesor 1 procesor 2 Vnitřní Vnitřní jazyk jazyk
z procesor 3
procesor 4
BASIC
procesor 4
LOGO
procesor 5
LOGO
procesor 5
–
Kompilátory
12.2. - 11.5. 2007
18
Generuje cílový kód z (optimalizovaného) pomocného kódu. Je úplně závislý na cílovém prostředí, ve kterém má pracovat přeložený program Příklady cílového jazyka podle účelu: – – – –
Kompilátory
Správce hlášení chyb
Zdrojový program
Error Reporting Lexikální analyzátor Syntaktický analyzátor
Jazyk symbolických adres – assemblerovský jazyk Čistý strojový kód – množinu instrukcí procesoru bez předpokladu existence operačního systému a knižnic – nezávislý na jiném softvéru Rozšířený strojový kód – používané jsou rutiny OS a podporné rutiny (V/V operace, alokace paměti, matematické funkce apod.) Virtuální strojový kód – složený je úplně z takzvaných virtuálních instrukcí – technika tvorby přenositelného počítače
z
druh chyby a jej alokace
z
způsob pokračování překladu - zastavení překladu - zotavení
Sémantický analyzátor Generátor vnitřního kódu
Správce tabulky symbolů Symbol Table
Optimalizátor kódu Generátor cílového kódu
z
Cílový program
19
Kompilátory
12.2. - 11.5. 2007
Dekompozice Dekompozicekompilátoru kompilátoru
Generátor cílového kódu
z
popředí, front end – všeobecné metody nezávislé na cílovém jazyku pozadí, back end – optimalizace podřízena cílovému prostředí, například strojovému kódu procesoru (vhodné využívání registrů, používání prostředků pro ekonomičtější organizaci dát...)
10 možností
25 možností
z
Odstraňuje redundantní anebo nepotřebné příkazy Dvě etapy optimalizace –
BASIC
17
–
z
paměťového – úspora operační paměti časového – náhrada pomalých instrukcí rychlejšími, případně vhodný kompromis předcházejících
12.2. - 11.5. 2007
20
Kompilátory
informace o identifikátorech - paměť nutná pro alokaci identifik. - druh identifikátoru - typ odpovídající hodnoty - počet a typ argumentů procedur a funkcí ... 12.2. - 11.5. 2007
5
