Syntaxí řízený překlad

Syntaxí řízený překlad

Překladová gramatika

Speciální typy

Syntaxí řízený překlad Šárka Vavrečková Ústav informatiky, FPF SU Opava [email protected]

Poslední aktualizace: 27. listopadu 2008

Příklady



Speciální typy

Příklady

Definice Překlad z jazyka L1 do jazyka L2 je definován množinou uspořádaných dvojic [zdrojový program, cílový program], kde zdrojový program ∈ L∗1 a cílový program ∈ L∗2 .

Definice (Formální překlad) je binární relace Z ⊆ D × H, která přiřazuje každému prvku z množiny D (zdrojový program) množinu prvků množiny H (jeho překladů). Pokud Z přiřadí pro každý prvek množiny D nejvýše jeden prvek množiny H, pak Z nazýváme funkcí a překlad je jednoznačný. Zapisujeme (x, y) ∈ Z nebo Z(x) = y (pokud překlad není jednoznačný, pak píšeme y ∈ Z(x)). Definičním oborem formálního překladu je množina všech hodnot, kterých může nabývat prvek x, tedy množina D, oborem hodnot je množina všech hodnot, kterých může nabývat prvek y, tedy množina H.



Speciální typy

Příklady

Definice Překlad z jazyka L1 do jazyka L2 je definován množinou uspořádaných dvojic [zdrojový program, cílový program], kde zdrojový program ∈ L∗1 a cílový program ∈ L∗2 .

Definice (Formální překlad) je binární relace Z ⊆ D × H, která přiřazuje každému prvku z množiny D (zdrojový program) množinu prvků množiny H (jeho překladů). Pokud Z přiřadí pro každý prvek množiny D nejvýše jeden prvek množiny H, pak Z nazýváme funkcí a překlad je jednoznačný. Zapisujeme (x, y) ∈ Z nebo Z(x) = y (pokud překlad není jednoznačný, pak píšeme y ∈ Z(x)). Definičním oborem formálního překladu je množina všech hodnot, kterých může nabývat prvek x, tedy množina D, oborem hodnot je množina všech hodnot, kterých může nabývat prvek y, tedy množina H.



Speciální typy

Příklady

Pojmy L1 – vstupní jazyk, gramatika G, L1 = L(G), L2 – výstupní jazyk, M (G) – množina derivačních stromů všech slov generovaných gramatikou G.

Postup překladu Z ⊆ L1 × L2 jako přímý překlad je příliš složitý, Z1 ⊆ L1 × M (G): přeložíme vstup z L1 na derivační strom z M (G), Z2 ⊆ M (G) × L2 : přeložíme derivační strom z M (G) na výstup z L2 .



Speciální typy

Příklady



Z L1

L2



Speciální typy

Příklady



Z L1

L2

Z1

M (G)



Speciální typy

Příklady



Z L1

L2

Z2 Z1

M (G)



Speciální typy

Syntaxí řízený překlad Definice (Syntaxí řízený překlad) Z ⊆ L1 × L2 je složení Z = Z1 · Z2 , kde Z1 je překlad vstupního řetězce na derivační strom a Z2 je překlad takového derivačního stromu na řetězec výstupního jazyka.

Realizace Syntaxí řízený překlad lze popsat překladovou gramatikou a realizovat překladovým automatem.

Příklady



Speciální typy

Syntaxí řízený překlad Definice (Syntaxí řízený překlad) Z ⊆ L1 × L2 je složení Z = Z1 · Z2 , kde Z1 je překlad vstupního řetězce na derivační strom a Z2 je překlad takového derivačního stromu na řetězec výstupního jazyka.

Realizace Syntaxí řízený překlad lze popsat překladovou gramatikou a realizovat překladovým automatem.

Příklady



Speciální typy

Překladová gramatika Definice (Překladová gramatika) je uspořádaná pětice se zápisem P G = (N, T, D, R, S), kde N je neprázdná konečná množina všech neterminálních symbolů gramatiky, T je neprázdná konečná množina vstupních terminálů – vstupní abeceda, D je konečná množina výstupních terminálů – výstupní abeceda (může být prázdná), R je neprázdná konečná množina pravidel ve tvaru N × (N ∪ T ∪ D)∗ , jinak: A → α, A ∈ N, α ∈ (N ∪ T ∪ D)∗ , S je startovací symbol gramatiky a platí T ∩ D = ∅ (jsou disjunktní) a N ∩ T = ∅ a N ∩ D = ∅.

Příklady



Speciální typy

Překladová gramatika generuje slova nad abecedou (T ∪ D), vstupní a výstupní terminály jsou „promíchanéÿ.

Definice (Homomorfismus) Nechť Σ1 a Σ2 jsou abecedy. Homomorfismem nazýváme každé zobrazení h : Σ∗1 → Σ∗2 takové, že pro každé a ∈ Σ∗1 , b ∈ Σ1 platí homomorfní podmínky: h(ε) = ε, h(a · b) = h(a) · h(b).

Příklady



Speciální typy

Překladová gramatika generuje slova nad abecedou (T ∪ D), vstupní a výstupní terminály jsou „promíchanéÿ.

Definice (Homomorfismus) Nechť Σ1 a Σ2 jsou abecedy. Homomorfismem nazýváme každé zobrazení h : Σ∗1 → Σ∗2 takové, že pro každé a ∈ Σ∗1 , b ∈ Σ1 platí homomorfní podmínky: h(ε) = ε, h(a · b) = h(a) · h(b).

Příklady



Speciální typy

Základní princip Homomorfismus se uplatňuje takto: rozložíme zdrojový řetězec na jednotlivé symboly, tyto symboly všechny přeložíme (uplatníme zobrazení h), výsledky překladu symbolů zřetězíme podle původního pořadí.

Uplatnění na překladovou gramatiku Vstupní homomorfismus:  hi (X) =

X ε

; ;

X ∈ (T ∪ N ) X∈D

Výstupní homomorfismus:  ho (X) =

X ε

; ;

X ∈ (D ∪ N ) X∈T

Příklady



Speciální typy

Základní princip Homomorfismus se uplatňuje takto: rozložíme zdrojový řetězec na jednotlivé symboly, tyto symboly všechny přeložíme (uplatníme zobrazení h), výsledky překladu symbolů zřetězíme podle původního pořadí.

Uplatnění na překladovou gramatiku Vstupní homomorfismus:  hi (X) =

X ε

; ;

X ∈ (T ∪ N ) X∈D

Výstupní homomorfismus:  ho (X) =

X ε

; ;

X ∈ (D ∪ N ) X∈T

Příklady



Speciální typy

Definice Překlad Z v překladové gramatice P G je definován jako množina uspořádaných dvojic vstupních a výstupních homomorfismů všech řetězců generovaných překladovou gramatikou: Z(P G) = {(hi (w), ho (w)) ; S ⇒∗ w, w ∈ (T ∪ D)∗ }.

Příklady



Speciální typy

Příklady

Překladová gramatika P G = (N, T, D, P, S) je kombinací dvou gramatik, vstupní a výstupní.

Definice (Vstupní a výstupní gramatika) Vstupní gramatika překladové gramatiky P G je bezkontextová gramatika Gi = (N, T, Pi , S), kde Pi = {A → hi (α); (A → α) ∈ P }. Výstupní gramatika překladové gramatiky P G je bezkontextová gramatika Go = (N, D, Po , S), kde Po = {A → ho (α); (A → α) ∈ P }.

Poznámka Vstupní i výstupní gramatika jsou běžné bezkontextové gramatiky.



Speciální typy

Příklady

Překladová gramatika P G = (N, T, D, P, S) je kombinací dvou gramatik, vstupní a výstupní.

Definice (Vstupní a výstupní gramatika) Vstupní gramatika překladové gramatiky P G je bezkontextová gramatika Gi = (N, T, Pi , S), kde Pi = {A → hi (α); (A → α) ∈ P }. Výstupní gramatika překladové gramatiky P G je bezkontextová gramatika Go = (N, D, Po , S), kde Po = {A → ho (α); (A → α) ∈ P }.

Poznámka Vstupní i výstupní gramatika jsou běžné bezkontextové gramatiky.



Speciální typy

Bezkontextová gramatika: Větná forma v bezkontextové gramatice je kterýkoliv člen derivací v této gramatice.

Definice (Formy v překladové gramatice) Překladová forma α v překladové gramatice P G je je řetězec symbolů nad abecedou (N ∪ T ∪ D), který lze v P G odvodit ze startovacího symbolu – S ⇒∗ α. Jestliže α je překladová forma v překladové gramatice P G, pak hi (α) je vstupní větná forma a ho (α) výstupní větná forma v této gramatice.

Poznámka Vstupní větná forma překladové gramatiky je větnou formou vstupní gramatiky, výstupní větná forma překladové gramatiky je větnou formou výstupní gramatiky.

Příklady



Speciální typy

Bezkontextová gramatika: Větná forma v bezkontextové gramatice je kterýkoliv člen derivací v této gramatice.

Definice (Formy v překladové gramatice) Překladová forma α v překladové gramatice P G je je řetězec symbolů nad abecedou (N ∪ T ∪ D), který lze v P G odvodit ze startovacího symbolu – S ⇒∗ α. Jestliže α je překladová forma v překladové gramatice P G, pak hi (α) je vstupní větná forma a ho (α) výstupní větná forma v této gramatice.

Poznámka Vstupní větná forma překladové gramatiky je větnou formou vstupní gramatiky, výstupní větná forma překladové gramatiky je větnou formou výstupní gramatiky.

Příklady



Speciální typy

Speciální typy překladových gramatik Definice (Regulární překladová gramatika) Překladovou gramatiku P G = (N, T, D, R, S) nazýváme regulární, jestliže má pouze pravidla ve tvaru A → xγB, A, B ∈ N, x ∈ T, γ ∈ D∗ , A → xγ, A ∈ N, x ∈ T, γ ∈ D∗ , S → ε, jestliže S se nevyskytuje na pravé straně žádného pravidla.

Definice (Překladová gramatika typu LL, LR) Překladová gramatika P G je typu LL(k) (silná LL(k), LR(k), silná LR(k)) pro nějaké přirozené číslo k, jestliže její vstupní gramatika je typu LL(k) (silná LL(k), LR(k), silná LR(k)).

Příklady



Speciální typy

Speciální typy překladových gramatik Definice (Regulární překladová gramatika) Překladovou gramatiku P G = (N, T, D, R, S) nazýváme regulární, jestliže má pouze pravidla ve tvaru A → xγB, A, B ∈ N, x ∈ T, γ ∈ D∗ , A → xγ, A ∈ N, x ∈ T, γ ∈ D∗ , S → ε, jestliže S se nevyskytuje na pravé straně žádného pravidla.

Definice (Překladová gramatika typu LL, LR) Překladová gramatika P G je typu LL(k) (silná LL(k), LR(k), silná LR(k)) pro nějaké přirozené číslo k, jestliže její vstupní gramatika je typu LL(k) (silná LL(k), LR(k), silná LR(k)).

Příklady



Speciální typy

Prefix, postfix, infix Infixový tvar Prefixový tvar Postfixový tvar

(a + b) ∗ c ∗ + abc ab + c∗

a ∗ (b + c) ∗a + bc abc + ∗

Příklady



Speciální typy

Zadání Vytvořte překladovou gramatiku pro překlad infixových výrazů bez závorek na prefixové.

Řešení a ○, ∗ P G = ({A}, {a, +, ∗}, {○, R, A) + ○}, a○ + ○A a ∗ ○A a a s pravidly A → a + ○ a∗○

V gramatice odvodíme slovo: ∗ ○A a ∗ ○a a + ○A a ∗ ○a a + ○a a ○ a A⇒a∗○ ⇒a∗○ +○ ⇒a∗○ +○ ∗ ○a a + ○a a ○ a hi a ∗ ○ +○ = a∗a+a ∗ ○a a + ○a a ○ a ∗ ○ a ○ +○ a ○ a ho a ∗ ○ +○ = ○ ∗ ○ a ○ +○ a ○) a je prvkem překladu určeného (a ∗ a + a, ○ překladovou gramatikou P G.

Příklady



Speciální typy




Příklady



Speciální typy




Příklady



Speciální typy




Příklady



Speciální typy

Zadání Vytvořte překladovou gramatiku pro překlad infixových výrazů na postfixové, která zachovává priority operátorů.

Řešení + T E → E + T○ ∗ F T → T ∗ F ○ a (E) F → a○ Ukázka odvození slova: + ⇒ T + T○ + ⇒ T ∗ F○ ∗ + T○ + ⇒ E ⇒ E + T○ ∗ + T○ + ⇒ a○ a ∗ F○ ∗ + T○ + ⇒ a○ a ∗ a○ a ○ ∗ + T○ + ⇒ F ∗ F○ a ∗ a○ a ○ ∗ + F○ + ⇒ a○ a ∗ a○ a ○ ∗ + a○ a ○ + a○

hi (w) = x ∗ x + x x ○ x ○ ∗ ○ x ○ + ho (w) = ○

Příklady



Speciální typy



hi (w) = x ∗ x + x x ○ x ○ ∗ ○ x ○ + ho (w) = ○

Příklady



Speciální typy



hi (w) = x ∗ x + x x ○ x ○ ∗ ○ x ○ + ho (w) = ○

Příklady



Speciální typy



hi (w) = x ∗ x + x x ○ x ○ ∗ ○ x ○ + ho (w) = ○

Příklady



Speciální typy

Zadání Vytvořte překladovou gramatiku pro překlad infixových výrazů na postfixové, která zachovává priority operátorů a je typu LL(1).

Řešení E → TA ε + A → +T ○A T → FB ε ∗ B → ∗F ○B a F → a○ (E)

Příklady



Speciální typy

Zadání Vytvořte překladovou gramatiku pro překlad infixových výrazů na postfixové, která zachovává priority operátorů a je typu LL(1).

Řešení E → TA ε + A → +T ○A T → FB ε ∗ B → ∗F ○B a F → a○ (E)

Příklady



Speciální typy

Zadání Vytvořte regulární překladovou gramatiku pro překlad infixových výrazů na postfixové bez závorek.

Řešení a a S → a○A a○ A → ∗B +C a○ a ○A ∗ ∗ B → a○ a○ a ○A + a ○ + C → a○ a○ Ukázka odvození: a a ∗ B ⇒ a○ a ∗ a○ a ○ ∗ S ⇒ a○A ⇒ a○

Příklady



Speciální typy

Zadání Vytvořte regulární překladovou gramatiku pro překlad infixových výrazů na postfixové bez závorek.

Řešení a a S → a○A a○ A → ∗B +C a○ a ○A ∗ ∗ B → a○ a○ a ○A + a ○ + C → a○ a○ Ukázka odvození: a a ∗ B ⇒ a○ a ∗ a○ a ○ ∗ S ⇒ a○A ⇒ a○

Příklady

Syntaxí řízený překlad

Recommend Documents