SW54. Základná štruktúra prekladača vyššieho programovacieho jazyka:
Rozdiel medzi prekladačom a interpretátorom, fázy prekladu a ich charakteristika.
Prekladač: Prekladá vyšší programovací jazyk do strojových inštrukcií počítača.
Interpréter: Zdrojový kód sa prekladá do vnútornej formy (virtuálny kód) a ten sa
interpretuje
Fázy prekladu:
-
Lexikálna analýza: Lexikálna analýza slúži na rozpoznanie lexikálnych jednotiek
v zdrojovom texte a ich transformáciu do medzijazyka (postupnosť symbolov).
Poradie symbolov zo vstupného textu ostáva zachované. Lexikálna analýza sa dá
reprezentovať konečným automatom (bez zásobníka)
-
Syntaktická analýza: Syntaktická analýza analyzuje, či daná veta (napr. zdrojový
text) patrí do jazyka, ktorý je reprezentovaný jeho gramatikou. Reprezentovaná je
zásobníkovým automatom. Existujú dve metódy syntaktickej analýzy:
o zdola nahor: umožňuje analyzovať jazyky LR(0), redukuje sa krok po kroku
z vety na pravidlá. Pritom vznikajú vetné formy so začiatkom z (VN ∪ VT )*
a zvyšok vstupu z VT * , pričom začiatky musia byť odvoditeľné prefixy správnych
vetných foriem. Tieto začiatky sú potom použiteľnými prefixami – prehľadávame
všetky možnosti. Ďalej redukujeme týmto spôsobom pokiaľ je to možné
o zhora nadol: začína sa začiatočným symbolom a postupným použitím pravidiel
gramatiky sa generuje postupnosť vetných foriem αi (reťazcov terminálnych
a neterminálnych symbolov) so snahou generovať v poslednom kroku odvodenia
vstupný reťazec ω ( S ⇒ α 1 ⇒ α 2 ⇒ ... ⇒ αn ⇒ ω , resp. S ⇒ ω )
-
Sémantická analýza
o analýza mien (rozsahu platnosti – cez tabuľku zásobníka mien US): Cieľ analýzy
mien: priradiť identifikátoru meno a ostatné atribúty v US, určiť úroveň l mena.
Režimy analýzy: zavedenie, použitie, uvoľnenie.
o analýza deklarácií
1. vytvoriť typové prostredie {(Ci, TEi ), (Vj , TEj ) | i = 1,2,..., nc, j = 1,2,..., nv}
2. priradiť relatívne adresy premenným (aj funkciám a parametrom)
3. vypočítať veľkosť pamäte pre lokálne premenné
Robí sa analýza deklarácií konštánt, typov, premenných, procedúr a funkcií.
o kontrola typov
o analýza tela
-
SW55. Chyby pri preklade:
Klasifikácia chýb počas prekladu a spôsob ich spracovania. Princíp zotavenia po chybe
pri prediktívnej syntaktickej analýze zhora nadol.
Typy chýb:
• lexikálne (nesprávny tvar konštanty a pod.)
• syntaktické (z hľadiska štruktúry jazyka)
• sémantické (z hľadiska významu jazykovej konštrukcie)
Zotavenie pri výskyte chýb pri syntaktickej analýze - podmienky
• každý terminálny symbol by sa mal vyskytovať v gramatike iba raz
• všetky bloky hierarchického usporiadania programu by mali mať jednoznačné
oddeľovače (begin/end, if/endif a pod.) - nebýva to tak (napr. viacznačný end), čo
znižuje účinnosť zotavenia (zbytočne sa preskakujú príliš dlhé bloky vstupného reťazca)
Prístup ku zotaveniu
• parametrom procedúry reprezentujúcej neterminálny symbol je množina kľúčových
symbolov (keys), ktorá obsahuje všetky terminálne symboly, ktoré sú na vstupe
prístupné po odvodení z tohoto neterminálneho symbolu. Táto množina nie je vo
všeobecnosti zhodná s množinou FOLLOW. Množina K je konštruovaná dynamicky pri
preklade.
• pred každým vetvením je treba skontrolovať pomocou procedúry check, či aktuálny
symbol na vstupe je prípustný symbol
• v prípade, že terminálny symbol na vstupe nie je prípustný, je potrebné čítať symboly zo
vstupného reťazca procedúrou error, kým sa nenachádza na vstupe symbol z množiny K,
t.j. preklad môže pokračovať
• množina K je použitá pri volaní procedúry reprezentujúcej neterminálny symbol,
procedúry error a check
Implementácia procedúry error a check:
procedure error(n, keys);
begin
print_error(n);
while symbol not in keys do getsymbol;
end;
procedure check(n, keys);
begin
if not symbol in keys error(n, keys);
end;
Konštrukcia množiny kľúčových slov H a množiny kľúčov K
Príklad: pre gramatiku zátvorkovaných výrazov:
Generovanie kódu
o selekcia kódu
o generovanie cieľového kódu
Určenie množiny kľúčov pre postupnosť symbolov
pre A → X 1 X 2 ... X m , kde X i ∈ V N ∪ VT
otázky PREKL.doc
Strana 1 z 20
otázky PREKL.doc
Strana 2 z 20
K(X m ) = K
K ( X i ) = H ( X i +1 ) ∪ K ( X i +1 )
kde K je parameter procedúry A (t.j. kľúče pre A) a H(Xi), i= 1,2, ... ,m sú dopredu
vypočítané.
Príklad:
A → H ( B ) ∪ H (C )∪ {d } ∪ K
Zotavenie pri výskyte chyby:
a
H (C ) ∪ {d }∪ K
B
{d }∪ K
C
d
K
Určenie množiny kľúčov pre cyklus
pre A → Y1Y2 ...YK {X 1 | X 2 | ... | x m }Z 1 Z 2 ...Z n , kde Yi , X j , Z k ∈ (V N ∪ VT ) * :
K(Zn) = K
K ( Z i ) = H ( Z i +1 ) ∪ K ( Z i +1 )
Pretože za Xm môže nasledovať postupnosť X1, X2, ..., Xm, definujeme množinu kľúčov
cyklu:
KL = H ( X 1 ) ∪ H ( X 2 ) ∪ ... ∪ H ( X m )
a množinu všetkých kľúčov
KA = KL ∪ H ( Z 1 ) ∪ K ( Z 1 )
Potom:
K ( X i ) = KA
K (Yk ) = KA
K (Yi ) = H (Yi +1 ) ∪ K (Yi +1 )
kde X1, X2, ..., Xm sú preložené podľa transakčnej schémy Z, ktorá definuje reprezentáciu
X i = B ∈ Vn alebo X i = a ∈ VT v analyzátore:
Z [[a ]] =
Procedúra analyzátora rozšírená o zotavenie sa z chýb:
procedure A(K)
begin
KL = H ( x1 ) ∪ H ( X 2 ) ∪ ... ∪ H ( X m )
KA = KL ∪ H ( Z 1 ) ∪ H ( Z 2 ) ∪ ... ∪ H ( Z n ) ∪ K
Z [[Y1 ]], Z [[Y2 ]],..., Z [[Yk ]]
loop
check(n,KA)
if not symbol in KL then exitloop
Z [[ X 1 ]], Z [[ X 2 ]],..., Z [[X m ]]
endloop
Z [[Z 1 ]], Z [[Z 2 ]],..., Z [[Z m ]]
if symbol = a then
getsymbol
else
error(n, K(a))
end
Z [[B ]] =
B(K(B))
end
Určenie kľúčov pre vetvenie
pre A → X 1 | X 2 | ... | X m , kdeX i ∈ (V N ∪ VT ) * :
K(Xi)=K
kde K je množina kľúčov prípustných po odvodení z A.
kde
Rozšírenie o zotavenie z chýb ( R[[A → X 1 | X 2 | ... | X m ]]) :
procedure A(K)
begin
check( n1 , H ( X 1 ) ∪ H ( X 2 ) ∪ ... ∪ H ( X m ) ∪ K )
if symbol in H(X1) then
Z [[ X 1 ]]
else if symbol in H(X2) then
Z [[ X 1 ]]
.
.
.
else error(n2, K)
end
kde
Z [[a ]] =
if symbol = a then
getsymbol
else
error(n,K(a))
end
Z [[B ]] = B(K(B))
Z [[a ]] = getsymbol
Z [[B]] = B(K(B))
otázky PREKL.doc
Strana 3 z 20
otázky PREKL.doc
Strana 4 z 20
SW56. Generovanie kódu a pamäť
Výpočet a prideľovanie pamäti pre konštanty, premenné a kód v cieľovom kóde.
Strojovo závislá optimalizácia kódu.
Prideľovanie pamäte
Metódy použité v prekladačoch pre pridelenie operačnej pamäte rozličným objektom
zdrojového programu (dáta, funkcie). Stratégie prideľovania OP ovplyvňujú pravidlá pre
rozsah platnosti a trvania objektov v konkrétnom jazyku a dostupnosť informácií o veľkosti
a umiestnení objektov v pamäti.
Prideľovanie:
• statické
- pre jazyky bez blokovej štruktúry
- pre jazyky s blokovou štruktúrou
• dynamické
- pomocou zásobníka
- pomocou haldy / hromady
Statické prideľovanie pamäte pre jazyky bez blokovej štruktúry
1. v čase prekladu je známy rozsah a počet objektov
2. každý objekt sa v danom okamihu vyskytuje len v jednom exemplári (nemožná
rekurzia)
3. objekt má vždy rovnakú adresu
Výsledkom prekladu je tabuľka symbolov s vyplnenými všetkými informáciami (meno, druh,
typ, veľkosť, adresa).
1. D → integer i
D.typ=int, D.sirka=2, PRIDAJ(i, D.typ, D.sirka, adr), adr = adr+2
2. D → real i
D.typ=real, D.sirka=4, PRIDAJ(i, D.typ, D.sirka, adr), adr = adr+4
3. D0 → D1, i
D0.typ = D1.typ, D0. sirka = D1. sirka
PRIDAJ(i, D1.typ, D1.sirka, adr), adr = adr+D.sirka
4. D → integer i(I)
D.typ=int, D.sirka=2, PRIDAJ(i, D.typ|pole, D.sirka*I.pocet, adr),
adr = adr+ D.sirka*I.pocet
5. D → real i(I)
D.typ= real, D.sirka=4, PRIDAJ(i, D.typ|pole, D.sirka*I.pocet, adr),
adr = adr+ D.sirka*I.pocet
6. D0 → D1, i(I)
D0.typ = D1.typ, D0. sirka = D1. sirka
PRIDAJ(i, D1.typ|pole, D1.sirka*I.pocet, adr), adr = adr+D.sirka*I.pocet
7. I → k
I.pocet = k
8. I0 → I1,k
I0.pocet → I1.pocet*k
Nevýhoda: Neoptimálne využitie pamäte
Statické prideľovanie pamäte pre jazyky s blokovou štruktúrou
Realizuje sa pomocou zásobníka
• rozsah platnosti lokálnych premenných bloku - zásobníkový prístup
• predpoklad: čítanie a zmena hodnôt položiek možné v ľubovoľnom mieste zásobníka
Aktivačný záznam: blok pamäte pre lokálne premenné
Zásobníkový prístup sa dá použiť aj pre tabuľku symbolov.
Statické vnáranie blokov - adresa objektu v bloku vypočítaná počas prekladu, hierarchia
blokov, rozsah platnosti objektov – statický
otázky PREKL.doc
Strana 5 z 20
1. S → BLOK
BLOCK.dts=0, BLOK.dap = konštanta
2. BLOK → {ZD, ZP}
ZD.dap=BLOK.dap, ZP.dap=ZD.sap
ZD.dts=BLOK.dts, ZP.dts = ZD.sts
3. ZD0 → D, ZD1i
D.dap=ZD0.dap, ZD1.dap=D.sap, ZD0.sap = ZD1.sap
D.dts=ZD0. dts, ZD1. dts =D.sts, ZD0. sts = ZD1. sts
4. ZD → D
D.dap=ZD.dap, ZD.sap=D.sap, D.dts=ZD.dts, ZD.sts=D.sts
5. D → real i
D. sts = ULOZ(D.dts, i.meno, prem, real, D.dap), D.sap=D.sap + sirka
6. ZP0 → P, ZP1
P.dap=ZP0.dap, P.dts=ZP0.dts
ZP1.dap=ZP0.dap, ZP1.dts=ZP0.dts - bloky sekvenčne za sebou použijú tú
istú pamäť pre premenné
7. ZP → P
P.dap=ZP.dap, P.dts=ZP.dts
8. P → BLOK
BLOK.dap=P.dap, BLOK.dts=P.dts
•
•
statické pridelenie zásobníka - dočasné premenné sú až za statickou oblasťou, niektoré
by mohli byť v nej - optimalizácia využitia zásobníka
pre lokálne premenné v bloku sa miesto vytvorí cez PUSH / POP inštrukcie
Optimalizácia a generovanie kódu
Generovanie kódu
Program v jazyku virtuálnych inštrukcií:
program <L1>{(virtinst<attrs>|label<Li>)}eof
Transformácia na ASlab - strojový jazyk s návestiami (závisí na architektúr) , obsahuje:
• constans <cn> - tabuľka konštánt
• registers <rn> / tabuľka pomocných registrov
• {instr| instr <val>|instr<Li> label <L>}eof
Jazyk ASlab je možné transformovať do:
• ASabs - strojový jazyk s absolútnami adresami
• ASrel - strojový jazyk s relatívnymi adresami
• ASsrc - zdrojový tvar (assembler)
Selekcia kódu je popísaná translačnými schémami C [[...]].
Preklad
Dvojprechodový assembler:
1. prechod - vytvorí tabuľku adries návestí
2. prechod - návestia prepíše na adresy
Assembler používa tieto pomocné premenné:
• PA - počítadlo adries
• B - začiatok kódu
• E - koniec kódu
• PC - vstupný bod programu
• TADR - tabuľka adries návestí
otázky PREKL.doc
Strana 6 z 20
Prvý prechod:
SW57. Statické prideľovanie pamäti:
Jednoduché statické prideľovanie pamäti v jazykoch s blokovou štruktúrou, výhody a
nevýhody.
Prideľovanie pamäti v cieľových programoch
Pre vykonanie cieľ. programu je nutné prideliť pamäť pre všetky údajové objekty,
spojovacie informácie podprogramov, pomocné premenné, vstupné a výstupné operácie.
Prideľovanie pamäti môže byť statické a dynamické.
• Statické sa používa v jazykoch, v ktorých možno počas kompilácie určiť veľkosť a
relatívne umiestnenie údajov.
• Dynamické v jazykoch, v ktorých sú definované dynamické premenné a (alebo)
rekurzívne procedúry.
Druhý prechod:
Jednoduché statické prideľovanie pamäti
Táto metóda nevyžaduje žiadnu činnosť pre prideľovanie pamäti v čase výpočtu.
Používa sa napr. pre jazyk FORTRAN. Kompilátor musí vypočítať veľkosť oblasti údajov v
každej programovej jednotke. Pretože veľkosť každého údaju je známa, stačí mu k tomu
jednoduché počítadlo. Veľkosť spoločnej oblasti COMMON sa určí ako max. z požiadaviek
všetkých programových jednotiek na túto oblasť. Pri prideľovaní pamäti vloží prekladač do
tabuľky symbolov tieto údaje o premennej:
meno, typ, druh (premenná, pole), adresa.
Pri kompilovaní zdrojového programu sa všetko okrem úpravy adries dá spraviť v prvom
prechode (od zdrojového tvaru až po ASlab).
Optimalizácia kódu
• optimalizácia registrov
• optimalizácia adresovania
• optimalizácia prehľadávacím oknom
Optimalizácia registrov
Množina registrov systému je rôzna od množiny registrov potrebných pre vykonanie
programu - dajú sa využiť nasledovne:
• registre pre mechanizmus volania - rýchly prístup k premenným
• registre pre výpočet tela (medzivýsledky, dočasné premenné) - využiteľnosť registrov
klesá so zložitosťou výrazov
Prideľovanie pamäti v jazykoch s blokovou štruktúrou
Jazyky s jednoduchým statickým prideľovaním nevyužívajú pamäť efektívne, pretože
pamäť ostáva pridelená premennej aj vtedy, keď sa táto už nepoužíva. Tento nedostatok je v
jazyku s blokovou štruktúrou odstránený.
Pre veličiny lokálne v danom bloku sa pamäť prideľuje dočasne. Pri otvorení bloku sa pridelí,
pri zatvorení uvoľní. Ak jazyk nemá rekurzívne procedúry ani dynamické premenné, možno
použiť statické prideľovanie. Všetky adresy sa určia už počas prekladu. Na prideľovanie
pamäti sa používa zásobník. Každý blok má v zásobníku aktivačný záznam, kde sú jeho
lokálne premenné, pomocné premenné a iné. Položky sa pridávajú a uberajú len z vrchu
zásobníka, ich hodnoty však možno meniť kdekoľvek v zásobníku.
Optimalizácia adresovania
Súvisí s dostupnými spôsobmi adresovania - minimalizácia času prístupu do pamäte
• bezprostredné adresovanie - výhodné pre konštanty
• relatívne adresovanie - krátke (<-127,+127>) - napríklad pre skoky
• indexové adresovanie - pre prístup k položkám záznamov, polí a k premenným na
vyšších úrovniach
• nepriame adresovanie - najmenej efektívny spôsob adresovania
• adresovanie špecifických stránok pamäte - veľmi obmedzené použite, napr. I/O
zariadenia
Optimalizácia pomocou okna
Prezeraním oknom malého rozsahu je možné odstrániť zbytočné inštrukcie ako:
• PUSH / POP
• MOV R, ADDR - MOV ADDR, R a podobne
Túto optimalizáciu treba robiť na kóde s návestiami.
otázky PREKL.doc
Strana 7 z 20
otázky PREKL.doc
Strana 8 z 20
SW58. Dynamické prideľovanie pamäti pomocou zásobníka:
Dôvody vedúce k dynamickému prideľovaniu, dynamická adresa, aktivačný záznam.
Prideľovanie pamäte
• metódy používané v prekladačoch pre pridelenie operačnej pamäte (OP) rozličným
objektom zdrojového programu (objekty - triedy, premenné, ...)
• stratégiu prideľovania OP určujú pravidlá pre rozsah platnosti a trvanie objektu
v konkrétnom prog. jazyku
Stratégiu prideľovania OP určujú pravidlá pre rozsah platnosti a trvania objektov
v konkrétnom programovacom jazyku. (dostupnosť, info o veľkosti a umiestnení objektu)
- pre jazyky bez blokovej štruktúry
Prideľovanie: - statické
- pre jazyky s blokovou štruktúrou
- dynamické - pomocou zásobníka
- pomocou hromady
Dynamické prideľovanie pamäte pomocou zásobníka
Dynamické vnáranie blokov
- Hierarchia blokov závisí od okamžiku v procese vykonávania programu.
Aktivačný záznam (AZ)
- blok pamäti pridelený pre lokálne pamäťové objekty (lokálne premenné, ...)
- AZ sa aktivuje v zásobníkovej oblasti.
Dôvody vedúce k dynamickému spôsobu prideľovania:
1. rekurzívne volania blokov - funkcií s lokálnymi premennými
2. vnáranie funkcií (podprogramov) na úrovni definície
3. dynamické polia a iné dynamické údajové objekty
Pri rôznych úrovniach volania tej istej funkcie je relatívna adresa rôzna, potom môže nastať
situácia kedy je funkcia staticky vnorená v jednom bloku a v ďalšom je dynamicky vnorená.
Blok 1
Blok 2 - funkcia f()
Blok 3
f()
situácia 1
situácia 2
2
5
1
(h1, p)
2
2
1
(h2, p)
inú aktiváciu procedúry s inými údajmi. Počet aktivácií nemôžeme počas prekladu poznať,
teda pridelenie adries počas prekladu je nemožné. Adresy sa musia vytvoriť až počas výpočtu
(tzv. dynamické adresy).
Dynamická adresa je v tvare (h, p):
Dynam. adresa objektu = (hladina, posun v bloku) = (h, p)
kde
• hladina - úroveň vnorenia bloku (poradové číslo AZ na vrchole), dyn. zložka adresy
• posun - statická zložka adresy objektu (relatívna adresa vzhľadom na začiatok AZ)
(h, p) potom prepočítame na fyzické umiestnenie v zásobníku
Prístup k nelokálnym premenným pri dynamickom prideľovaní pamäti do zásobníka
Bloky
Uvedeným spôsobom sú prístupné všetky premenné definované v bloku, nie však nelokálne
veličiny. To sa vyrieši tým, že do aktivačného záznamu sa pridá číslo bloku a smerník na
nadradený blok.
Procedúry
Zložitejší prípad je ten, keď sú v programe procedúry. Nelokálne veličiny sú v staticky
nadradenom bloku, ale návrat z procedúry smeruje do dynamicky nadradeného bloku (tam,
kde je príkaz volania). V aktivačnom zázname musia byť teda smerníky na oba bloky. (V
prípade bloku, nie procedúry, sú oba smerníky rovnaké.)
DISPLAY
Hľadanie veličiny pomocou uvedenej štruktúry je náročné na čas, preto sa buduje vektor
smerníkov na aktivačné záznamy všetkých aktívnych blokov nazývaný DISPLAY. (V
záznamoch, na ktoré ukazuje, treba hľadať nelokálne veličiny bloku alebo procedúry, ktorá je
na vrchu zásobníka. DISPLAY sa tvorí pri vstupe do bloku zostupom po smerníkoch staticky
nadradených blokov.)
Adresa veličín je určená nasledovne:
DISPLAY [h]+p
kde
• h - úroveň vnorenia
• p - relatívna adresa vo vnútri bloku.
Určenie alokácie nelokálnej premennej s dynamickou adresou (h, p)
(sumarizácia - stručný popis informácií uvedených vyššie)
1. AZ obsahuje info o hladine
- pre nájdenie nelokálnej premennej (h, p) sa hľadá najbližší AZ s hladinou h
- nemáme žiadne smerníky - sekvenčné prehľadávanie spojkového zoznamu AZ-ov
v zásobníku
- označenie: AZ.hladina
2. AZ obsahuje smerník na najbližší statický nadradený blok
- prehľadávanie spojkového zoznamu AZ-om
- označenie: AZ.st_smer
3. Pri vstupe do bloku a vytvorení AZ sa vytvorí aj pole smerníkov na všetky staticky
nadradené bloky
- DISPLAY (podľa hodnôt st_smer)
- priamy prístup k nelokálnej premennej cez DISPLAY. Táto metóda má
najrýchlejšie vykonávanie kódu.
- Adresa premennej (h, p) = DISPLAY [ h ] + p
Blok 4
Blok 5
volanie f()
volanie f()
Popis obr.:
Relatívna adresa lok. prem. bloku 2 je rôzna v situácii 1 a v sit. 2
Funkcia f() je staticky vnorená v bloku 1
Funkcia f() je dynamicky vnorená v blokoch 5,1
Z toho vyplýva, že adresy lokálnych objektov funkcie nemôžu byť statické !
Ak jazyk pripúšťa rekurzívne procedúry, nemožno adresovať staticky. V zásobníku môže byť
niekoľko aktivačných záznamov pre tú istú procedúru alebo blok. Každý záznam predstavuje
Zrýchlený prístup na AZ-y
otázky PREKL.doc
otázky PREKL.doc
Strana 9 z 20
-
Použitie poľa smerníkov na AZ-y aktívnych blokov - DISPLAY (prehľad)
Strana 10 z 20
-
DISPLAY obsahujú smerníky na AZ-y všetkých aktívnych blokov
Adr n = (2, 1) = DISPLAY [2] + 1
SW59. Deterministická syntaktická analýza zhora-nadol:
Definícia jazyka a spôsoby implementácie, vzťahy analýzy zhora-nadol ku gramatike,
determinizmus gramatiky a jazyka.
Organizácia AZ v zásobníku
Syntaktická analýza
V každom bloku sú 2 smerníky:
SSM - statický smerník pre vyhľadávanie nelokálnych veličín
DSM - dynamický smerník pre znižovanie zásobníka pri výstupe z bloku
Používame ešte dva smerníky
BP - bázový smerník - používa sa pre adresáciu lokálnych premenných
SP - smerník na vrchol zás. - pre adresáciu dočasných premenných a ďalšie činnosti
Pre AZ bloku statický smerník = dynamický smerník
Pre AZ procedúry statický smerník ? dynamický smerník
Syntaktická analýza (SA) je fáza prekladu, ktorá nasleduje za lexikálnou analýzou a pred
sémantickou analýzou. Základnou funkciou SA je kontrola syntaxe – gramatickej správnosti
zdrojového kódu (vstupného reťazca terminálnych symbolov - lexikálnych jednotiek). Syntax
jazyka, v ktorom je napísaný vstupný reťazec, je definovaná gramatikou G=(VN,VT,P,S), kde
VN je množina neterminálov, VT je množina terminálov, P je množina pravidiel a S je
neterminálny začiatočný symbol. Súčasné prog. jazyky sú bezkontextové (tvar
pravidla A → β , β ∈ (V N ∪ VT ) * ).
Adresa(h, p) – pre lokálne premenné bloku je vypočitateľná počas prekladu
– pre lokálne premenné procedúry je (h, p) dynamické
SA zhora nadol (SA↓) začína začiatočným symbolom gramatiky a postupným použitím
pravidiel gramatiky sa generuje postupnosť vetných foriem αi – reťazcov terminálnych a
neterminálnych symbolov, so snahou vygenerovať v poslednom kroku vstupný reťazec w.
Deterministická syntaktická analýza zhora nadol
i1
k
m
SSM
2 | DSM
z
y
x
3 |
c
b
a
dynamick
ý
smerník
i2
i3
in
i n +1
S ⇒ α1 ⇒ α 2 ⇒ ...⇒ α n ⇒ w Výstupom SA↓ je postupnosť použitých pravidiel
(i1),(i2)...,(in+1).
Pri deterministickej SA musí byť v každom kroku odvodenia jednoznačné, ktoré pravidlo
gramatiky sa použije. Podmienkou deterministickej SA↓ je definícia jazyka gramatikou
LL(1):
- Gramatiku je možné analyzovať zhora nadol čítaním vstupného reťazca zľava.
- Používa sa najľavejšie odvodenie – v každej vetnej forme nahradzujeme najprv
najľavejší neterminál.
- Rozhodovanie na základe jedného symbolu.
Gramatika, ktorá nie je LL(1), môže byť upravená na LL(1) použitím týchto pravidiel
(algoritmov):
- Vyčlenenie spoločných postupností zľava – úprava pravidiel tak, aby neexistoval
spoločný prefix v žiadnych dvoch alternatívach na pravej strane žiadneho pravidla
(napríklad pravidlo A → B + C | B + D má spoločné prefixy).
- Odstránenie ľavej rekurzie (napríklad pravidlo E → E + T je rekurzívne zľava a môže
spôsobiť zacyklenie programu).
- Odstránenie epsilonových pravidiel ( A → ε , kde ε je prázdny symbol) – aby bolo
možné použiť algoritmus odstránenia ľavej rekurzie.
Pre formálny zápis gramatiky jazyka LL(1) je vhodná EBNF – rozšírená Backus-Naurova
forma.
Gramatika
G = ({E , A, M , F , T }, {=, <>,+,−,∗, /, ^ , (, ), const , id }, P, E )
jazyka
Príklad:
zátvorkových výrazov v EBNF. V príklade vidno spôsob určovania priorít (hĺbkou vnorenia
pri odvodení) a asociatívnosti operácií (tvarom pravidla).
E → A [(" ="|" <>") A]
- asociatívnosť nie je, priorita najnižšia
A → M {("+"|"−") M }
- asociatívnosť doľava
M → F {("∗"|" /") F }
- asociatívnosť doľava
F → T [" ^ " F ]
- asociatívnosť doprava, priorita najvyššia
T → const | id | " (" E " )"
S
statický
smerník
Vzťah SA↓
↓ ku gramatike jazyka
Syntax jazyka je definovaná jeho gramatikou a pri konštrukcii syntaktického analyzátora
vychádzame z pravidiel tejto gramatiky.
Podmienkou deterministickej SA↓ je definícia gramatiky pre bezkontextový jazyk LL(1).
Táto gramatika musí spĺňať tieto podmienky:
- Na ľavej strane každého pravidla je iba jeden neterminálny symbol, pretože je to
bezkontextový jazyk.
- Gramatika nie je rekurzívna zľava, čo je príznakom jazyka LL.
otázky PREKL.doc
Strana 11 z 20
otázky PREKL.doc
Strana 12 z 20
-
V ľubovoľnom bode vetvenia možno pokračovať v odvodení na základe jedného
terminálneho symbolu vstupného reťazca, čo je príznakom jazyka LL(1).
Implementácia SA↓
↓ metódou rekurzívneho spádu
Najjednoduchšou implementáciou SA↓ je syntaktický analyzátor, ktorý rozpoznáva, či
vstupný reťazec patrí do jazyka (ak sa prečíta celý reťazec) alebo nie. Konštruuje sa
priamočiarym prepísaním pravidiel gramatiky jazyka LL(1) z EBNF do programu
v programovacom jazyku, ktorý umožňuje rekurziu:
- Každému pravidlu gramatiky zapísanej v EBNF zodpovedá deklarácia procedúry
s menom neterminálneho symbolu na ľavej strane tohto pravidla.
- Neterminálnemu symbolu na pravej strane pravidla zodpovedá volanie procedúry.
- Terminálnemu symbolu zodpovedá volanie procedúry (getsymbol), ktorá prečíta zo
vstupného reťazca ďalší terminálny symbol.
- Postupnosti symbolov na pravej strane každého pravidla zodpovedá postupnosť volaní
procedúr uvedených v predchádzajúcich bodoch.
- Operácii sumy (zjednotenia) | zodpovedá príkaz vetvenia (if, case, switch v jazyku C).
Vstup do príkazu vetvenia je bodom rozhodnutia.
- Výrazu v hranatých zátvorkách [] zodpovedá príkaz vetvenia (if).
- Uzáveru {…} zodpovedá príkaz cyklu (while, do). Vstup do cyklu je bodom
rozhodnutia.
- Hlavný program volá procedúru reprezentujúcu začiatočný symbol (S) gramatiky.
Syntaxou riadený preklad (rekurzívny, zhora nadol) je rozšírenou implementáciou SA a
konštruuje sa v troch krokoch, pričom každý ďalší krok je modifikáciou predošlého:
1. Programová realizácia syntaktického analyzátora, ktorý dá odpoveď, či vstupný
reťazec je alebo nie je správny. Neumožňuje pokračovať v analýze pri výskyte chyby
a nič negeneruje na výstupe.
2. Rozšírenie o zotavenie pri výskyte chyby (error recovery). Program nič negeneruje,
len prečíta celý vstupný reťazec a zistí maximum syntaktických chýb.
3. Rozšírenie o generovanie výstupného kódu. Program generuje vždy syntakticky
správny výstupný kód a niekedy aj sémanticky správny.
Program používa:
- Zásobník, lebo matematickým modelom bezkontextového jazyka je zásobníkový
automat.
- Rozkladovú tabuľku, ktorá sa implementuje množinami FIRST a FOLLOW. Pre
rekurzívnu SA↓ stačí vypočítavať množinu FIRST(X), kde X je neterminálny alebo
terminálny symbol a množina FIRST(X) obsahuje všetky terminálne symboly,
ktorými môžu začínať vetné formy odvoditeľné z X.
Zotavenie pri výskyte chyby:
Syntaktický analyzátor sa doplní o definíciu typu množina symbolov (symbolset) a dve
procedúry:
- error(n:integer,k:symbolset) – vypíše (alebo iným spôsobom zaznamená chybu
s číslom n) a číta symboly zo vstupného reťazca, kým sa na vstupe neobjaví symbol,
ktorý sa nachádza v množine kľúčov k.
- check(n:integer,k:symbolset) – kontroluje, či aktuálny symbol patrí do množiny
kľúčov. Ak nie, volá procedúru error, ktorá to zabezpečí.
Základný prístup k zotaveniu:
- Parametrom každej procedúry (zodpovedajúcej neterminálnemu symbolu) je množina
kľúčových symbolov K, ktorá obsahuje všetky terminálne symboly, ktoré sú prípustné
na vstupe po odvodení z tohto neterminálneho symbolu. Množina K je konštruovaná
dynamicky počas prekladu.
- Pred každým vetvením sa pomocou proc. check skontroluje, či aktuálny symbol na
vstupe je kľúčový symbol.
- V prípade, že terminálny symbol na vstupe nie je prípustný, je potrebné čítať symboly
zo vstupného reťazca procedúrou error, kým sa nenachádza na vstupe symbol
z množiny K a preklad môže pokračovať.
otázky PREKL.doc
Strana 13 z 20
SW60. Deterministická syntaktická analýza zdola-nahor:
Matematická model a jeho implementácia, vzťah ku gramatike, riešenie kolízií
vedúcich k nedeterminizmu.
1. Matematický model syntaktickej analýzy zdola nahor.
Matematickým modelom tejto analýzy je rozšírený zásobníkový automat RZA, ktorý
definujeme podľa nasledujúcej definície.
Def.: Rozšírený zásobníkový automat RZA je usporiadaná sedmica:
R=( Q, T, G, δ, q0, z0, F )
Q - množina stavov
T - množina terminálov
G - množina zásobníkového automatu
q0 - počiatočný stav
z0 - symbol na dne zásobníka
F - množina finálnych (koncových) stavov
δ: Q x (T∪{ε}) x G* → 2QxG*
konfigurácia: (q, au, αβ)∈ Q x T* x G*
β - vrchol zásobníka
α - dno zásobníka
Prechod (p, au, αβ) ֏ (q, u, αγ) existuje práve vtedy ak (q, γ) ∈ δ(p, a, β)
Jazyk ktorý rozpozná automat RZA R je L(R) = {w ∈ T* | (q0, w, z0) ֏ (qf, ε, γ)}
Pri rozšírenom zásobníkovom automate sa používa rozpoznávanie len prechodom do finálového stavu.
Príklad: L={wwR | w∈ {0,1}*}
R=( {q,z}, {0,1}, {0,1,S,#}, δ, q, #, {r} )
δ:
1. δ(q, 0, ε) = {(q, 0)}
zápis do zásobníka
2. δ(q, 1, ε) = {(q, 1)}
detto
3. δ(q, ε, ε) = {(q, S)}
myslíme si že sme v strede
4. δ(q, ε, 0S0) = {(q, S)}
redukcia na S
5. δ(q, ε, 1S1) = {(q, S)}
detto
6. δ(q, ε, #S) = {(r, ε)}
finálový stav
Ukážka prechodov:
(q, 00100100, #) ֏ (q, 0100100, #0) ֏ (q, 100100, #00) ֏ (q, 00100, #001) ֏
֏
(q, 0100, #0010) ֏ (q, 0100, #0010S) ֏ (q, 100, #0010S0) ֏ (q, 100, #001S) ֏
֏ (q, 00, #001S1) ֏ (q, 00, #00S) ֏ (q, 0, #00S0) ֏ (q, 0, #0S) ֏ (q, ε, #0S0) ֏
֏ (q, ε, #S) ֏ (r, ε, ε)
2. Deterministický - rozšírený zásobníkový automat.
Platí obmedzenie, že bude jednoznačný prechod automatu z každého stavu.
Majme RZA R=( Q, T, G, δ, q0, z0, F ),
RZA R je deterministický práve vtedy,
ak pre každé (q, a, α) ∈ Q x (T∪{ε}) x G* platí:
1. | δ(q, a, α) | ≤ 1
2. a) δ(q, a, α) ≠ 0 ∧ δ(q, a, β) ≠ 0 tak potom platí α≠γβ, β≠γα
- ak máme situáciu v rovnakých stavoch ale na vrchole sú 2 rôzne symboly nesmie byť jeden príponou druhého - nejednoznačnosť v určení redukčného
jadra.
b) ak δ(q, a, α) ≠ 0 ∧ δ(q, ε, β) ≠ 0 potom platí α≠γβ, β≠γα
- nevieme či robiť akciu čítania zo vstupu alebo nečítať a tiež nejednoznačnosť v
určení jadra.
Základné vlastnosti RZA.
Veta: Ku každej bezkotextovej gramatike (CFG) G=(N, T, P, S) existuje rozšírený zásobníkový
automat (RZA) R taký že L(R) = L(G).
otázky PREKL.doc
Strana 14 z 20
3. Algoritmus konštrukcie RZA podľa CFG.
VSTUP: bezkontextová gramatika (cfg) G = (N, T, P, S)
VÝSTUP: rozšírený zás. automat RZA R=( Q, T, G, δ, q0, z0, F )
1. Q = {q, r}
G = N∪T∪{#}
# - symbol dna zásobníka
z0 = #
q0 = q
F = {r}
2. pre každé (A→α) ∈ P bude v RZA existovať:
(q, A) ∈ δ(q, ε, α) - bez ohľadu na to čo je na vstupe; redukcia reťazca na vrcole zásob.
3. pre každé a∈T existuje (q,a) ∈ δ(q, a, ε) - posun (shift)
4. δ(q, ε, #S) = (r, ε) - nasleduje finálový stav; prijatie (accept)
Algoritmus spočíva v tom že sa presúvajú symboly so vstupu do zásobníka kým na vstupe nie je
nejaká pravá strana pravidla - redukcia podľa daného pravidla.
Príklad: Navrhnite RZA podľa gramatiky: E→E + T | T
T→T * F | F
F→(E) | i
R = ( {q, r}, {+, *, (, ), i}, {E, T, F, +, *, (, ), i, #}, δ, q, #, {r} )
δ:
1. pre každé a∈{+, *, (, ), i} | δ(q, a, ε) = {(q, a)} -posun do zásobníka
2. δ(q, ε, E+T) = {(q, E)}
3. δ(q, ε, T) = {(q, E)}
4. δ(q, ε, T*F) = {(q, T)}
5. δ(q, ε, F) = {(q, T)}
6. δ(q, ε, (E)) = {(q, F)}
7. δ(q, ε, i) = {(q, F)}
8. δ(q, ε, #E) = {(r, ε)}
Ukážka prechodov:
(q, i+i*i, #) ֏ (q, +i*i, #i) ֏ (q, +i*i, #F) ֏ (q, +i*i, #T) ֏ (q, +i*i, #E) ֏
֏ (q, *i, #E+i) ֏ (q, *i, #E+F) ֏ (q, *i, #E+T) ֏ (q, ε, #E+T*i) ֏
֏ (q, ε, #E+T*F) ֏ (q, ε, #E+T) ֏ (q, ε, #E) ֏ (r, ε, ε)
Ku každému ZA vieme skonštruovať RZA ale naopak to neplatí pretože trieda jazykov rozpoznaných
RZA pokrýva triedu jazykov rozpoznanych ZA.
Predpokladajme, že G = (N, T, P, S) je jednoznačná gramatika a že reťazec w = a1a2.....an je veta v
jazyku L(G). Potom existuje pravá derivácie S = γ1⇒γ2⇒....⇒γm = w ∈ T*.
Vzhľadom na to, že táto derivácia je pravá, má každá vetná forma γi, i = 1,2,...,m-1 tvar
γi = αAajaj+1.......an , kde A∈N, α∈(N∪T)* a reťazec ajaj+1.......an∈T* je príponou vety w.
Ak γi-1 = αBz a pravidlo B → β je použité v kroku γi-1 ⇒ γi, alebo αBz ⇒ αβz, tak základný problém
deterministickej SA metódou zdola nahor spočíva v najdení reťazca βz vo vetnej forme γi tak, aby
vetná forma γi mohla byť redukovaná na vetnú formu γi-1.
Definovanie redukčnej časti (jadro vetného tvaru).
Nech G=(N,T,P,S) je cfg a nech existuje pravá derivácia S⇒* αAw ⇒ αγw ⇒* xw, kde x,w∈T*.
Vetný tvar αγw môže byť redukovaný pomocou A→α na αAw.
Perspektívna predpona.
γ∈(N∪T)* je perspektívnou predponou, práve vtedy ak existuje S⇒* αAw ⇒ αβw ⇒* xw, kde
x,w∈T* a platí že reťazec γ je prefixom (predponou) reťazca αβ.
Rozšírená gramatika.
Majme gramatiku: G=(N,T,P,S) rozšírená gramatika G' ku gramatike G je taká gramatika, ku ktorej
doplníme nový štartovací symbol. Tento symbol sa zaraďuje z toho dôvodu aby sa štartovací symbol
nemohol vyskytnúť na pravej strane pravidiel.
G=(N, T, P, S)
G'=(N∪{S'}, T, P∪{S'→S}, S')
L(G)=L(G')
LR gramatika.
Gramatika G je LR(K) K≥0 ak zo splnenia podmienok:
1. S⇒* αAw ⇒ αβw
2. S⇒* γβx ⇒ αβy
3. FIRSTK(w) = FIRSTK(y)
vyplýva:
γβx = αAy
γ = α, A = B, x = y
4. Syntaktická analýza zdola nahor.
Je taká analýza pri ktorej konštruujeme syntaktický strom od listov k vrcholu. Tiež sa nazýva aj
bottom up parsing. Zatiaľ čo pri analýze zhora na dol predstavovali jednotlivé kroky priame derivácie,
pri analýze zdola na hor postupujeme prostredníctvom priamych redukcií, t.j. náhrady pravej strany
pravidla ľavou stranou.
Riešením SA zhora na dol je riešenie nasledujúcich úloh:
1.
najdenie jadra vetného tvaru - tá časť, ktorú redukujeme(redukčná časť, L-fráza)
2.
redukcia jadra vetného tvaru na príslušný neterminál.
Nedeterminizmus SA sa dá riešiť viacerými spôsobmi.
Jeden zo spôsobov je: SA s návratmi.
SA s návratmi spočíva v tom, že pri presúvaní symbolov do zásobníka, ak dôjde k alternatíve, tak jednu si vyberieme a preveríme ak sa
dostaneme do chybného stavu tak sa vratíme do uzla odkiaľ sme vybrali alternatívu a preverujeme inú.
5.
LR gramatiky.
Najväčšia trieda gramatiky pre ktorú sa dá vytvoriť syntaktický analyzátor.
Pokrýva triedu LL gramatík.
Používa sa LR analyzátor.
Algoritmy LR analýzy čítajú vstupný reťazec zľava a vytvárajú pravý rozklad, z toho ich nazývame
LR analyzy. Pritom využívajú informácie o najbližších k symboloch v doteraz neprečítanej časti
vstupného reťazca. Gramatiky, pre ktoré je možné takéto algoritmy vytvoriť, sa nazývajú LR(k)
gramatiky.
Základný princíp SA pre LR gramatiky môžeme formulovať takto:
otázky PREKL.doc
Strana 15 z 20
otázky PREKL.doc
Strana 16 z 20
SW61. Definícia sémantiky jazyka a aplikácia pri preklade.
-
-
SW62. Analýza deklarácií a kontrola typov.
sémantická analýza zahŕňa:
- analýza mien - využívané pre analýzu deklarácií a analýzu tela
ma 3 režimy: - režim zavedenia
- režim použitia
- režim uvoľnenia
- analýza deklarácií - podstatnou úlohou je vytvorenie typového prostredia
- analýza tela - typová kontrola a transformácia tela (príkazov a výrazov) do formy
jazyka virtuálnych inštrukcií
úlohou sémantickej analýzy deklarácií je konštrukcia typového prostredia, čiže väzby
mien na typy
je potrebné transformovať identifikátory na mená a skonštruovať typy premenných,
procedúr a funkcií
je potrebné určiť veľkosť pamäte, ktorá je potrebná na uloženie hodnôt premenných,
funkcií, parametrov funkcii, procedúr.
na transformáciu identifikátorov na mená sa v analýze deklarácií využíva analýza
mien - režim zavedenia
pri začiatku každého tela (BEGIN) sa analýza mien prepne do režimu použitia
na konci každého tela sa prepne do režimu uvoľnenia, po uvoľnení deklarovaných
objektov sa opäť prepne do režimu zavedenia
v programe sa striedajú deklarácie a telá => sémantická analýza deklarácií sa strieda
so sémantickou analýzou tela
otázky PREKL.doc
Strana 17 z 20
otázky PREKL.doc
Strana 18 z 20
SW63. Optimalizácia a generovanie kódu:
Význam strojovo nezávislej optimalizácie, generovanie kódu a metódy strojovo závislej
optimalizácie.
Optimalizácia a generovanie kódu
Generovanie kódu
Program v jazyku virtuálnych inštrukcií:
program <L1>{(virtinst<attrs>|label<Li>)}eof
Transformácia na ASlab - strojový jazyk s návestiami (závisí na architektúr) , obsahuje:
• constans <cn> - tabuľka konštánt
• registers <rn> / tabuľka pomocných registrov
• {instr| instr <val>|instr<Li> label <L>}eof
Jazyk ASlab je možné transformovať do:
• ASabs - strojový jazyk s absolútnami adresami
• ASrel - strojový jazyk s relatívnymi adresami
• ASsrc - zdrojový tvar (assembler)
Selekcia ódu je popísaná ttranslačnými schémami C [[...]].
Preklad
Dvojprechodový assembler:
1. prechod - vytvorí tabuľku adries návestí
2. prechod - návestia prepíše na adresy
Assembler používa tieto pomocné premenné:
• PA - počítadlo adries
• B - začiatok kódu
• E - koniec kódu
• PC - vstupný bod programu
• TADR - tabuľka adries návestí
Pri kompilovaní zdrojového programu sa všetko okrem úpravy adries dá spraviť v prvom
prechode (od zdrojového tvaru až po ASlab).
Optimalizácia kódu
• optimalizácia registrov
• optimalizácia adresovania
• optimalizácia prehľadávacím oknom
Optimalizácia registrov
Množina registrov systému je rôzna od množiny registrov potrebných pre vykonanie
programu - dajú sa využiť nasledovne:
• registre pre mechanizmus volania - rýchly prístup k premenným
• registre pre výpočet tela (medzivýsledky, dočasné premenné) - využiteľnosť registrov
klesá so zložitosťou výrazou
Optimalizácia adresovania
Súvisí s dostupnými spôsobmi adresovania - minimalizácia času prístupu do pamäte
• bezprostredné adresovanie - výhodné pre konštanty
• relatívne adresovanie - krátke (<-127,+127>) - napríklad pre skoky
• indexové adresovanie - pre prístup k položkám záznamov, polí a k premenným na
vyšších úrovniach
• nepriame adresovanie - najmenej efektívny spôsob adresovania
• adresovanie špecifických stránok pamäte - veľmi obmedzené použite, napr. I/O
zariadenia
Optimalizácia pomocou okna
Prezeraním oknom malého rozsahu je možné odstrániť zbytočné inštrukcie ako:
• PUSH / POP
• MOV R, ADDR - MOV ADDR, R a podobne
Túto optimalizáciu treba robiť na kóde s návestiami.
Prvý prechod:
Druhý prechod:
otázky PREKL.doc
Strana 19 z 20
otázky PREKL.doc
Strana 20 z 20
Download

( ) ( ) { }v