{{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ýza|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|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|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 back-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 v jeho mysli 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:
#*Ďalej nás zaujímajú 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]]
* přehledný popis [http://en.wikipedia.org/wiki/LL_parser LL parseru] a [http://en.wikipedia.org/wiki/LR_parser LR parseru] na Wikipedii - hodí se pro případ, že vás Bednárkův výklad občas trochu mátl :-)
== Zápočet ==
Zápočet je za písemku - tvorba LR(1) automatu.
* [http://groups.yahoo.com/group/zkouzky/message/412 starší zadání]
* [http://mff.modry.cz/diskuse/index.php?nop&diskuse_select_sekce=vse&tree=4527#prispevek4527 novější zadání]
== Zkouška ==
* maily o zkoušce z mff-info: [http://groups.yahoo.com/group/mff-info/message/1496 1] [http://groups.yahoo.com/group/mff-info/message/1456 2] [http://groups.yahoo.com/group/mff-info/message/885 3] [http://groups.yahoo.com/group/mff-info/message/879 4] [http://groups.yahoo.com/group/mff-info/message/796 5] [http://groups.yahoo.com/group/mff-info/message/294 6] [http://groups.yahoo.com/group/mff-info/message/700 7]
* [http://mff.modry.cz/diskuse/index.php?nop&diskuse_select_sekce=vse&tree=6273#prispevek6273 novější zadání]
