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, Z0, F

Q – stavy

T – vstupy

Z – zásobníková abeceda

δ – přechody

q – počáteční stav

Z0 – 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 <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 <\$, q0> (q0 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 → X1X2…Xd odpovídající akčnímu číslu

Ověř, že vrchní symboly na zásobníku jsou ve tvaru <X1, ?><X2, ?>…<Xd, ?>, jinak syntaktická chyba!

Zjisti stav před X1

Nastav aktuální stav podle čísla na souřadnicích [stav před X1, levá strana pravidla] přechodové části tabulky.

Odstraň ze zásobníku <X1, ?><X2, ?>…<Xd, ?>

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.