Hledat:

Invia.cz Pojeďte do Egypta Kanárské ostrovy Dovolená - Turecko Dominikánská republika Madeira Last minute
 

Překladový automat

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[editovat | editovat zdroj]

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#, ε)

Popis překladového automatu[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  1. je-li A::= α i-té pravidlo gramatiky a α ≠ ε, pak pro všechny a ∈ FIRST(α) platí M[A,a] = expand i
  2. jestliže ε ∈ FIRST(α), pak pro všechna b ∈ FOLLOW(A) M[A,b] = expand i
  3. M[a,a] = pop, m[#,$] = accept, jinak M[X,a] = error

Příklad rozkladu tabulky[editovat | editovat zdroj]

Zadaná pravidla:

Předpis číslo pravidla množina FOLLOW
S ::= aAd | ε  1,2 FOLLOW(S) = {$}
A ::= bB 3 FOLLOW(A) = {d}
B ::= cbB | ε 4,5 FOLLOW(B) = {d}

Rozkladová tabulka:

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[editovat | editovat zdroj]

 
Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „https://cs.wikipedia.org/w/index.php?title=Překladový_automat&oldid=11958463
Stránka byla naposledy upravena 28. 10. 2014 v 12:09. Editovat celý článek Překladový automat.
Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci 3.0 Unported, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.
Další služby: Portál | Katalog | Hledej | Zprávy | Počasí | Kurzy | Práce | Slovník | TV | Online hry | Java hry | SMS | Loga a melodie | Chat | Fórum | Kontakt | Set-top-boxy