Tahák IFJ

N, T, P, S

• N – neterminály
• T – terminály
• P – pravidla
• S – počáteční symbol

Q, T, δ, s, F

• Q – stavy
• T – vstupy
• δ – přechody
• s – počáteční stav
• F – koncové stavy

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ň.

q, w, z

• q – stav
• w – vstup
• z – zásobník

Když se daný neterminál (nebo celá posloupnost neterminálů) dá rozložit na ε, bude množina Empty(N) = {ε}, jinak ∅.

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.

Ukazuje jaké terminály mohou následovat po neterminálech.

1. Follow(S) = {\$}; Follow(neterminály) = ∅
2. Zpracovávej pravidla které mají na pravé straně aspoň jeden neterminál
   1. 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)
      1. Pokud y ≠ ε tak Follow(B) = First(y)
      2. Pokud Empty(y) = {ε} tak Follow(B) = Follow(A)
3. Krok 2 dělej tak dlouho, dokud v průchodu nedojde k žádné změně

Bacha! First a Empty se dělají pro posloupnosti!

Pro pravidlo číslo n: A → x

Predict(n) =

• First(x) ∪ Follow(A) pokud Empty(x) = {ε}
• First(x) v ostatních případech

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.

1. Na zásobník nacpi \$ a počáteční neterminál
2. Prováděj cyklus dokud vstup ≠ zásobník ≠ \$
   1. 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.
   2. 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.

Symboly (terminály) budou zřejmě stejné, poslední je \$ (dno zásobníku, konec vstupu).

• 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ň <

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)!

• 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.

1. Vlož na zásobník \$
2. Prováděj úpravy, dokud nejvrchnější terminál zásobníku ≠ vstupní symbol ≠ \$
   1. Najdi v tabulce znaménko pro nejvrchnější terminál zásobníku a vstupní symbol
      • =
        1. Šoupni vstupní symbol na zásobník
      • <
        1. Za nejvrchnější terminál zásobníku (nemusí být vrchol) dej <
        2. Na vrchol zásobníku dej vstupní symbol
      • >
        1. Najdi na zásobníku nevrchnější <
        2. Mezi < a vrcholem najdi pravou stranu nějakého pravidla
        3. Odstraň tuto část zásobníku včetně <
        4. Nahraď ji levou stranou pravidla
      • Prázdné políčko
        1. Syntaktická chyba!

Pravý rozbor je pak posloupnost čísel použitých pravidel od začátku.

Zásobník ukládá dvojice <symbol, stav>. 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ů.

1. Vlož na zásobník <\$, q₀> (q₀ je počáteční stav, většinou 0).
2. Opakuj cyklus, dokud neskončí:
   1. Najdi v akční části buňku odpovídající aktuálnímu stavu a vstupnímu symbolu.
      • s číslo
        1. Vlož na zásobník dvojici <vstupní symbol, akční číslo>.
        2. Aktuální stav nastav na akční číslo.
      • r číslo
        1. Najdi pravidlo A → X₁X₂…X_d odpovídající akčnímu číslu
        2. Ověř, že vrchní symboly na zásobníku jsou ve tvaru <X₁, ?><X₂, ?>…<X_d, ?>, jinak syntaktická chyba!
        3. Zjisti stav před X₁
        4. Nastav aktuální stav podle čísla na souřadnicích [stav před X₁, levá strana pravidla] přechodové části tabulky.
        5. Odstraň ze zásobníku <X₁, ?><X₂, ?>…<X_d, ?>
        6. Vlož na zásobník <levá strana pravidla, stav z kroku d>
      • 
        1. OK, hotovo
      • Prázdná buňka
        1. Syntaktická chyba

Pravý rozbor: použitá pravidla u r buněk.