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. ==== 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 <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ů. ==== 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 <vstupní symbol, akční číslo>. -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 <X₁, ?><X₂, ?>…<X_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 <X₁, ?><X₂, ?>…<X_d, ?> -Vlož na zásobník <levá strana pravidla, stav z kroku d> * -OK, hotovo *Prázdná buňka -Syntaktická chyba Pravý rozbor: použitá pravidla u r buněk.