====== Tahák IFJ ====== ===== Gramatika ===== N, T, P, S *N -- neterminály *T -- terminály *P -- pravidla *S -- počáteční symbol ===== Nedeterministický konečný automat ===== Q, T, δ, s, F *Q -- stavy *T -- vstupy *δ -- přechody *s -- počáteční stav *F -- koncové stavy ===== Zásobníkový automat ===== Q, T, Z, δ, q, Z₀, F *Q -- stavy *T -- vstupy *Z -- zásobníková abeceda *δ -- přechody *q -- počáteční stav *Z₀ -- počáteční zásobníkový symbol *F -- koncové stavy Přechod: zásobník stav vstup -> zásobník stav (vstup lze vynechat) U rozšířeného zásobníkového automatu nemusíme číst ze zásobníku a můžeme zpracovávat více symbolů ze zásobníku zároveň. ==== Konfigurace zásobníkového automatu ==== q, w, z *q -- stav *w -- vstup *z -- zásobník ===== Konstrukce LL tabulky ===== ==== Empty ==== Když se daný neterminál (nebo celá posloupnost neterminálů) dá rozložit na ε, bude množina //Empty(N) = {ε}//, jinak ∅. ==== First ==== Obsahuje všechny terminály které se mohou v neterminálu (posloupnosti) vygenerovat jako první (úplně vlevo). Pokud se může ze začátku generovat i ε, je potřeba řešit i následující neterminály. ==== Follow ==== Ukazuje jaké terminály mohou následovat po neterminálech. -//Follow(S) = {\$}; Follow(neterminály) = ∅// -Zpracovávej pravidla které mají na pravé straně aspoň jeden neterminál -Pravidla rozkládej do tvarů: //A -> xBy// (//x// a //y// (//y// může být i ε) je posloupnost neterminálů i terminálů, //B// je neterminál) -Pokud //y ≠ ε// tak //Follow(B) = First(y)// -Pokud //Empty(y) = {ε}// tak //Follow(B) = Follow(A)// -Krok 2 dělej tak dlouho, dokud v průchodu nedojde k žádné změně Bacha! First a Empty se dělají pro posloupnosti! ==== Predict ==== Pro pravidlo číslo //n: A -> x// //Predict(n) =// *//First(x) ∪ Follow(A)// pokud //Empty(x) = {ε}// *//First(x)// v ostatních případech ==== Tabulka ==== ^ ^T^T^T^ ^N| | | | ^N| | | | ^N| | | | Buňky se vyplňují tak, že se zvolí řádek podle levé strany pravidla a do buněk se doplní číslo pravidla do těch sloupců, které jsou v množině Predict daného pravidla. Pokud by do nějaké buňky mělo přijít více než jedno pravidlo, nastane zhroucení vesmíru a gramatika není LL. ==== Průchod tabulkou ==== -Na zásobník nacpi \$ a počáteční neterminál -Prováděj cyklus dokud vstup ≠ zásobník ≠ \$ -Když je na vrcholu neterminál a existuje v LL tabulce pravidlo které by jej společně se vstupním terminálem zpracovalo, proveď toto pravidlo (starý neteminál zanikne) a na zásobník ho dej v opačném pořadí. Pokud není pravidlo, chyba. -Když je na vrcholu terminál a na vstupu terminál, musejí být stejné, jinak chyba. Levý rozbor je pak posloupnost čísel použitých pravidel od začátku. ===== Precedenční tabulka ===== ^ ^vstup^vstup^vstup^ ^zásobník| | | | ^zásobník| | | | ^zásobník| | | | Symboly (terminály) budou zřejmě stejné, poslední je \$ (dno zásobníku, konec vstupu). ==== Operátory ==== *Pokud má operátor na zásobníku vyšší prioritu než na vstupu (* > +), doplň > *Pokud má operátor na zásobníku nižší prioritu než na vstupu (+ < *), doplň < *Pokud mají operátory stejnou prioritu a oba jsou levě asociativní (+-*/), doplň > *Pokud mají operátory stejnou prioritu a oba jsou pravě asociativní (^), doplň < ==== Identifikátory ==== Jako proměnné Když dáš vedle sebe symbol na zásobníku a symbol na vstupu (jeden ze symbolů je identifikátor), "vetší" bude indentifikátor. Bacha na závorky (//identifikátor(// a //)identifikátor// nelze), a identifikátor/identifikátor (taktéž nelze)! ==== Závorky ==== *Celý sloupec i řádek s ( vyplň < *Celý sloupec i řádek s ) vyplň > *Do buňky () doplň = *Smaž obsah buněk (\$ i( )( )i ==== \$ ==== Řeší se jen s operátory. Když dám vedle sebe symbol ze zásobníku a symbol ze vstupu (\$ a operátor), bude //\$ < operátor//. Hint: Řádek s \$ obsahuje pouze < a prázdné buňky, sloupec s \$ obsahuje pouze > a prázdné buňky. ==== Průchod tabulkou ==== -Vlož na zásobník \$ -Prováděj úpravy, dokud nejvrchnější terminál zásobníku ≠ vstupní symbol ≠ \$ -Najdi v tabulce znaménko pro nejvrchnější terminál zásobníku a vstupní symbol *= -Šoupni vstupní symbol na zásobník *< -Za nejvrchnější terminál zásobníku (nemusí být vrchol) dej < -Na vrchol zásobníku dej vstupní symbol *> -Najdi na zásobníku nevrchnější < -Mezi < a vrcholem najdi pravou stranu nějakého pravidla -Odstraň tuto část zásobníku včetně < -Nahraď ji levou stranou pravidla *Prázdné políčko -Syntaktická chyba! Pravý rozbor je pak posloupnost čísel použitých pravidel od začátku. ===== LR tabulka ===== ^ ^ Akční část ^^^ Přechodová část ^^^ ^ ^vstup^vstup^vstup^neterminál^neterminál^neterminál^ ^stav| | | | | | | ^stav| | | | | | | ^stav| | | | | | | Zásobník ukládá dvojice ////. V akční části jsou dvojice //s// nebo //r// a číslo stavu, také je v jedné buňce :-) značící úspěšný konec. V přechodové části jsou jen číslice stavů. ==== Analýza ==== -Vlož na zásobník //<\$, q₀>// (//q₀// je počáteční stav, většinou 0). -Opakuj cyklus, dokud neskončí: -Najdi v akční části buňku odpovídající aktuálnímu stavu a vstupnímu symbolu. *s číslo -Vlož na zásobník dvojici ////. -Aktuální stav nastav na akční číslo. *r číslo -Najdi pravidlo //A -> X₁X₂...X_d// odpovídající akčnímu číslu -Ověř, že vrchní symboly na zásobníku jsou ve tvaru //1, ?>2, ?>...d, ?>//, jinak syntaktická chyba! -Zjisti stav před X₁ -Nastav aktuální stav podle čísla na souřadnicích //[stav před X₁, levá strana pravidla]// přechodové části tabulky. -Odstraň ze zásobníku //1, ?>2, ?>...d, ?>// -Vlož na zásobník //// *:-) -OK, hotovo *Prázdná buňka -Syntaktická chyba Pravý rozbor: použitá pravidla u //r// buněk.