Překladový automat je v podstatě zásobníkový automat, který však obsahuje navíc ještě výstupní pásku a je definován rozkladovou tabulkou.
Definice překladového automatu
Tvar konfigurace (stav) překladového automatu: (x, Z, π) x = nepřečtená část vstupní pásky Z = obsah zásobníku π = obsah výstupní pásky
Tvar počáteční konfigurace: (w, S#, ε) w = vstupní řetězec S = startovací symbol # = zásobníkový symbol, který představuje dno zásobníku
Popis překladového automatu
Překladový automat obsahuje zásobník, vstupní pásku, výstupní pásku a rozkladovou tabulku. Rozkladová tabulka nahrazuje přechodovou funkci. Překladový automat postupně čte symboly ze vstupní pásky, stejným způsobem pak pracuje i se zásobníkem, na výstupní pásku nakonec zapisuje levý rozklad vstupní věty (tj. čísla použitých pravidel).
Rozkladová tabulka
Rozkladová tabulka je zobrazení M: (∑ ∪ N ∪ {#}) ∙ (∑ ∪ {$}) ∪ {expand i, pop, accept, error}
Jednotlivé funkční hodnoty mají tento význam:
expand i Je-li A::= α i-té pravidlo gramatiky, pak na vrcholu zásobníku je neterminál A, na vstupu je symbol x, M[A,x] = expand i. Automat provede změnu konfigurace (xm, Aβ, π) |– (xm, αβ, πi) – tzn. že do zásobníku umístí pravou stranu pravidla A::= α (řetězec α od konce). Vstupní pásky si automat nevšímá a na výstupní pásku zapíše číslo i.
pop Jestliže je na vrcholu zásobníku a též na vstupní pásce tentýž terminál symbol x, pak automat provede změnu konfigurace (xm, xβ, π) |– (m, β, π), tzn. že automat odstraní symbol x z vrcholu zásobníku a na vstupní pásku se posune na další znak.
accept K této hodnotě dojde automat v koncové konfiguraci, ale jen pokud přečte celou vstupní pásku a zároveň při tom vyprázdní zásobník. Na výstupní pásce se objeví úplný levý rozklad vstupní věty.
error Znamená, že automat vstup nepřijal, vstupní řetězec tedy není větou jazyka.
Pravidla
je-li A::= α i-té pravidlo gramatiky a α ≠ ε, pak pro všechny a ∈ FIRST(α) platí M[A,a] = expand i jestliže ε ∈ FIRST(α), pak pro všechna b ∈ FOLLOW(A) M[A,b] = expand i M[a,a] = pop, m[#,$] = accept, jinak M[X,a] = error
Příklad rozkladu tabulky
Zadaná pravidla:
{| border=1 ! Předpis !! číslo pravidla !! množina FOLLOW |- | | S ::= aAd | ε || align=center | 1,2 ||FOLLOW(S) = {$} |- | | A ::= bB || align=center | 3 ||FOLLOW(A) = {d} |- | | B ::= cbB | ε || align=center | 4,5 ||FOLLOW(B) = {d}
Rozkladová tabulka:
{| border=1 ! !! colspan=5 | Vstupní symbol |- ! Zásobník !! a !! b !! c !! d !! $ |- ! S || expand1 || || || || expand2 |- ! A || || expand3 || || || |- ! B || || || expand4 || expand5 || |- ! a || pop || || || || |- ! b || || pop || || || |- ! c || || || pop || || |- ! d || || || || pop || |- ! # || || || || || accept
Související články Překladač
Kategorie:Automaty (teorie automatů)