{{predmet|Konstrukce překladačů|David Bednárek|SWI002}}
[[Image:Jazyky.png]]
...navyše zjednotenie všetkých LR(n) dáva DBKJ.
----
<h3>Analýza zhora-nadol</h3>
<ul>
<li>aká je definícia gramatiky LL(1)</li>
<li>ako sú nadefinované operátory FIRST a FOLLOW, a čo to predstavuje</li>
<li>pri LL(1) je potrebné vedieť, akým spôsobom skonštruujeme jednoduchý automat.</li>
</ul>
<h3>Analýza zdola-nahor</h3>
<ul>
<li>hlavne je potrebné vedieť konštrukciu SLR(1) automatu</li>
<li>ako sa konštruuje LR(0) - to sú tie "množiny otečkovaných pravidiel"</li>
<li>potom treba vedieť, ako vyplníme tabuľky ACTION a GOTO</li>
<li>čo to znamená KOLÍZIA</li>
<li>ako dosiahnuť kolíziu SHIFT/REDUCTION a REDUCTION/REDUCTION</li>
</ul>
<h3>kolízia SHIFT/REDUCTION</h3>
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).
<h3>kolízia REDUCTION/REDUCTION</h3>
dostaneme tak, ze v jednej množine bude znak "." v dvoch pravidlách s rôznymi neterminálmi na ľavej strane
<pre>
A -> x.
B -> y.
</pre>
a zároveň musí platiť že: <b>FOLLOW(A) ∩ FOLLOW(B) ≠ ∅</b>
<h3>príklad gramatiky s kolíziami S/S, R/R</h3>
<pre>
S -> Q
Q -> D
D -> Cxz
Q -> Ax
Q -> Bxy
A -> C
B -> C
C -> t
</pre>
<h3>Operátor FIRST</h3>
Je to funkcia, ktorá dostane <b>terminály alebo neterminál</b> a vráti množinu <b>terminálov</b>. Yaghob sa vás určite spýta, čo vlastne tento operátor predstavuje. Je potrebné vedieť, že FIRST(X) je množina <b>terminálov</b> 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).
<br/>
Ako vytvoríme FIRST(X)?
<ol>
<li>ak je X terminál, potom FIRST(X)={X}</li>
<li>ak je X neterminál, potom:
<ul>
<li>Dalej nás aujímajú nás len pravidlá z gramatiky, ktoré majú na ľavej strane neterminál X.</li>
<li>Ak je v gramatike pravidlo X -> λ, potom do FIRST(X) pridáme λ.</li>
<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>
<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 λ.
<br/>
Potom do FIRST(X) dáme všetko z FIRST(Y<sub>1</sub>) ... FIRST(Y<sub>k+1</sub>)
</li>
</ul>
</li>
</ol>
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.
<h3>Operátor FOLLOW</h3>
Je to funkcia, ktorá dostane <b>neterminál</b> a vráti množinu <b>terminálov</b>. Znova sa vás Yaghob spýta, čo vlastne tento operátor v skutočnosti predstavuje. <b style="font-size:24pt;color:red">TODO-doplňte sem niekto, čo to vlastne predstavuje</b>.
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).
<p><b>POZNÁMKA k SLR(1) parseru</b>: 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: <b>FOLLOW(X) ∩ FOLLOW(Y) ≠ ∅</b>
</p>
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.
<b style="font-size:24pt;color:red">TODO-doplňte sem niekto, konštrukciu</b>
--[[User:Vlx|Vlx]] 15:29, 4 Jun 2005 (CEST)
[[category:Informatika]]