{{predmet|Konstrukce překladačů|David Bednárek|SWI002}}
== Schéma překladače ==
:''Práce překladače připomíná studenta, když se učí z ručne psaných (typicky vlastních) poznámek. Začíná to lexikální analýzou, kdy student zkoumá, co jsou ty čmáranice vlastně za písmenka, kde jsou hranice slov a podobně. Syntaktická analýza probíhá většinou paralelně s lexikální. Student ověřuje, zda jsou jeho poznámky vůbec česky (případně slovensky, anglicky, ...) a zda to nejsou čiré nesmysly.''
:''Následuje sémantická analýza, kdy student bádá, co tím chtěl básník (tedy on) vlastně říct, pídí se po nějakém hlubším smyslu poznámek a snaží se odhalit nějaké souvislosti mezi jednotlivými odstavci, sekcemi a kapitolami. Jednotlivým elementům textu jsou přiřazeny atributy, které postupně (v k průchodech, kde k je často mnohem větší než 1) doplňuje hodnoty těchto atributů. Příkladem atributů mohou být odkazy na související oblasti učiva nebo různé pomůcky a analogie pro snadnější pochopení a zapamatování jednotlivých elementů. Fáze sémantické analýzy bývá obvykle kritická a většinou se neobejde bez potíží (minimálně warningů). Student kleje, že poznámky nedávají smysl, a lamentuje nad tím, že si to nepoznačil lépe a nenapsal si toho víc. Nedostatky poznámek, způsobené obvykle nepozorností nebo dokonce absencí na přednášce, obvykle končí chybami při překladu, méně často učení proběhne bez větších potíží a výsledkem je pouze několik (desítek) varování. O jiných případech asi nemá cenu mluvit, jsou příliš vzácné.''
:''Do beck-endu už tolik nevidíme, je však nutné poznamenat, že choulostivou fází jsou optimalizace. Je potřeba se vyhnout přeoptimalizování. High-level optimalizace často způsobují nepřesnosti zásadního rozsahu ve znalostech studenta. Low-level optimalizace můžou zastínit některé důležité detaily.''
== Syntaktická analýza ==
=== Síla gramatik ===
[[Image:Jazyky.png]]
...navyše zjednotenie všetkých LR(n) dáva DBKJ (? bez kontextové jazyky).
----
=== Analýza zhora-nadol ===
*aká je definícia gramatiky LL(1)
*ako sú nadefinované operátory FIRST a FOLLOW, a čo to predstavuje
*pri LL(1) je potrebné vedieť, akým spôsobom skonštruujeme jednoduchý automat.
==== Operátor FIRST ====
Je to funkcia, ktorá dostane '''terminály alebo neterminál''' a vráti množinu '''terminálov'''. Yaghob sa vás určite spýta, čo vlastne tento operátor predstavuje. Je potrebné vedieť, že FIRST(X) je množina '''terminálov''' takých, ktoré sa môžu vyskytnúť na začiatku slova, zderivovateľného z X.
Túto množinu potrebujeme pre vytvorenie FOLLOW(X) a pre definíciu gramatiky LL(1).
===== Definice =====
Pro množinu slov <math>L \subseteq P(V^*) \,\!</math> je
<math>FIRST_k^G(L)= \{x \in V_T^* | (\exists y \in L)((y\Rightarrow_G^* x \ \and\ |x| \leq k) \ \or\ (\exists z \in V_T^*)(y\Rightarrow_G^* xz \ \and\ |x| = k)) \}.</math>
===== Konstrukce =====
:Ako vytvoríme FIRST(X)?
#ak je X terminál, potom FIRST(X)={X}
#ak je X neterminál, potom:
#*Dalej nás aujímajú nás len pravidlá z gramatiky, ktoré majú na ľavej strane neterminál X.</li>
#*Ak je v gramatike pravidlo X -> λ, potom do FIRST(X) pridáme λ.</li>
#*Ak je pravidlo v tvare: X -> Y<sub>1</sub>Y<sub>2</sub>Y<sub>3</sub>Y<sub>...</sub> a všetky FIRST(Y<sub>i</sub>) obsahujú λ, potom do FIRST(X) znova pridáme λ.</li>
#*Ak je pravidlo v tvare: X -> Y<sub>1</sub>Y<sub>2</sub>Y<sub>3</sub>Y<sub>...</sub> ale existuje FIRST(Y<sub>i</sub>), ktoré neobsahuje λ, potom nájdeme zľava prvé také Y<sub>k</sub>, aby FIRST(Y<sub>k</sub>) obsahovalo λ ale FIRST(Y<sub>k+1</sub>) neobsahovalo λ Potom do FIRST(X) dáme všetko z FIRST(Y<sub>1</sub>) ... FIRST(Y<sub>k+1</sub>)
Navyše môžeme celý postup zobecniť na reťazce. V tom prípade ak je (S<sub>i</sub>)<sub>i=1..n</sub> postupnosť terminálov a neterminálov, pre ktoré už FIRST máme spočítané, potom FIRST(S) vytvoríme
z FIRST(S<sub>1</sub>)..FIRST(S<sub>k</sub>), ktoré obsahujú λ a FIRST(S<sub>k+1</sub>), ktoré už λ neobsahuje.
==== Operátor FOLLOW ====
Je to funkcia, ktorá dostane '''neterminál''' a vráti množinu '''terminálov'''. Znova sa vás Yaghob spýta, čo vlastne tento operátor v skutočnosti predstavuje.
{{TODO|doplňte sem niekto, čo to vlastne predstavuje}}
Túto množinu potrebujeme pre definíciu gramatiky LL(1) a hlavne pre konštrukciu SLR(1) parseru (podľa toho zistíme, kam patria redukcie).
'''POZNÁMKA k SLR(1) parseru:''' Pokiaľ sa niekde vyskytne kolizia v redukcii, znamena to, že nejake neterminaly X,Y mali neprazdny prienik vo svojich množinách FOLLOW, čo sa dá zapísať takto:
FOLLOW(X) ∩ FOLLOW(Y) ≠ ∅
===== Definice =====
Pro neterminál <math>A \in V_T \,\!</math> je
<math>FOLLOW_k^G(A)= FIRST_k^G(\{z \in V^* | (\exists u \in V^*)(S\Rightarrow_G^* uAz) \}).</math>
===== Konstrukce =====
Konštrukcia je znova rekurzívna. Na začiatku je FOLLOW(X) prázdna množina pre všetky X neterminály z gramatiky. Postupne prechádzame všetky pravidlá, ale tentokrát sa pozeráme na pravé strany pravidiel.
{{TODO|doplňte sem niekto, konštrukciu}}
=== Analýza zdola-nahor ===
*hlavne je potrebné vedieť konštrukciu SLR(1) automatu
*ako sa konštruuje LR(0) - to sú tie "množiny otečkovaných pravidiel"
*potom treba vedieť, ako vyplníme tabuľky ACTION a GOTO
*čo to znamená KOLÍZIA
*ako dosiahnuť kolíziu SHIFT/REDUCTION a REDUCTION/REDUCTION
==== kolízia SHIFT/REDUCTION ====
dostaneme tak, ze v jednej množine bude znak "." na konci pravidla (A -> x). a zároven z tejto množiny dostaneme inú množinu prechodom cez terminál, ktorý sa nachádza v množine FOLLOW(A).
==== kolízia REDUCTION/REDUCTION ====
dostaneme tak, ze v jednej množine bude znak "." v dvoch pravidlách s rôznymi neterminálmi na ľavej strane
A -> x.
B -> y.
a zároveň musí platiť že: '''FOLLOW(A) ∩ FOLLOW(B) ≠ ∅'''
==== príklad gramatiky s kolíziami S/S, R/R ====
S -> Q
Q -> D
D -> Cxz
Q -> Ax
Q -> Bxy
A -> C
B -> C
C -> t
=== Externí odkazy ===
*[http://www.devincook.com/goldparser/concepts/ Slovníček pojmů LL, LR, LALR, kolize, atd.] na stránkách [http://www.devincook.com/goldparser/index.htm GOLD parseru]
*[http://compilers.iecc.com/comparch/article/99-02-109 Mail o rozdílech mezi SLR, LALR, atd.] z fora na [http://compilers.iecc.com/ compilers.iecc.com]
[[category:Informatika]]
