4.1 Překladové gramatiky

Překladová gramatika je nástroj, který nám zajišťuje generování řetězců z jazyka definičního oboru a k nim odpovídajícího překladu z jazyka oboru hodnot.

Definice (Bezkontextová překladová gramatika)

Bezkontextová překladová gramatika

Bezkontextová překladová gramatika je definována jako uspořádaná pětice \(PG = (N, \Sigma, D, R, S)\), kde:

\(N\) je konečná neprázdná množina neterminálních symbolů,
\(\Sigma\) je konečná množina vstupních symbolů,
\(D\) je konečná množina výstupních symbolů (\(\Sigma \cap D = \emptyset, (\Sigma \cup D) \cap N = \emptyset\)),
\(R\) je konečná množina přepisovacích pravidel ve tvaru:

\[A \to \alpha \quad (A \in N, \alpha \in (N \cup \Sigma \cup D)^*)\]
\(S \in N\) je počáteční neterminální symbol.

Definice (Regulární překladová gramatika)

Regulární překladová gramatika

Regulární překladová gramatika je též uspořádaná pětice \(PG = (N, \Sigma, D, R, S)\), nyní však s pravidly ve tvaru:

\[ A \to ax \quad \text{nebo} \quad A \to axB \quad (A, B \in N, a \in \Sigma, x \in D^*) \]

Jedinou povolenou výjimkou z těchto pravidel je pravidlo \(S \to \varepsilon\). Toto pravidlo se v regulární překladové gramatice může vyskytnout za předpokladu, že počáteční neterminál \(S\) se nevyskytuje na pravé straně žádného pravidla.

Homomorfismy a definice překladu

Abychom mohli formálně definovat překlad, zavedeme pojem homomorfismus.

Definice (Homomorfismus)

Homomorfismus

Uvažujme abecedy \(\Sigma\) a \(D\). Homomorfismem nazýváme každé zobrazení \(h: \Sigma \to D^*\). Definiční obor homomorfismu rozšíříme na \(\Sigma^*\) následovně:

\[ h(w) = \begin{cases} \varepsilon & \text{pokud } w = \varepsilon \\ h(a_1)h(a_2)\dots h(a_n) & \text{pokud } w = a_1a_2\dots a_n \end{cases} \]

Definice (Vstupní a výstupní homomorfismus)

Vstupní a výstupní homomorfismus

Nechť \(PG = (N, \Sigma, D, R, S)\) je překladová gramatika.

Vstupní homomorfismus \(h_i^{PG}: (N \cup \Sigma \cup D) \to (N \cup \Sigma)^*\) je definován takto:

\[h_i^{PG}(a) = \begin{cases} a & \text{pokud } a \in N \cup \Sigma \\ \varepsilon & \text{pokud } a \in D \end{cases}\]

(Ponechává neterminály a vstupní symboly, maže výstupní symboly.)
Výstupní homomorfismus \(h_o^{PG}: (N \cup \Sigma \cup D) \to (N \cup D)^*\) je definován takto:

\[h_o^{PG}(a) = \begin{cases} a & \text{pokud } a \in N \cup D \\ \varepsilon & \text{pokud } a \in \Sigma \end{cases}\]

(Ponechává neterminály a výstupní symboly, maže vstupní symboly.)

Definice (Překlad definovaný překladovou gramatikou)

Překlad definovaný překladovou gramatikou

Nechť \(PG = (N, \Sigma, D, R, S)\) je překladová gramatika. Pak překlad definovaný překladovou gramatikou \(PG\) definujeme následovně:

\[ Z(PG) = \{ (h_i(w), h_o(w)) : w \in (\Sigma \cup D)^* \land S \Rightarrow^* w \} \]

To znamená, že řetězec \(v \in D^*\) (obor hodnot) je překladem řetězce \(u \in \Sigma^*\) (definiční obor) právě tehdy, když oba vznikly ze stejného řetězce \(w\) vygenerovaného gramatikou (po odstranění příslušných symbolů).

Charakteristická, vstupní a výstupní gramatika

Definice (Charakteristická gramatika a jazyk)

Charakteristická gramatika a jazyk

Nechť \(PG = (N, \Sigma, D, R, S)\) je překladová gramatika.

Charakteristickou gramatiku \(G\) definujeme jako \(G = (N, \Sigma \cup D, R, S)\).
Jazyk \(L(G)\) nazýváme charakteristický jazyk překladu \(Z(PG)\).
Řetězec \(w \in L(G)\) nazýváme charakteristickou větou dvojice \((u, v) \in Z(PG)\), kde \(u = h_i(w)\) a \(v = h_o(w)\).

Definice (Vstupní a výstupní gramatika)

Vstupní a výstupní gramatika

Nechť \(PG = (N, \Sigma, D, R, S)\) je překladová gramatika.

Vstupní gramatika \(G_i\) je definována jako \(G_i = (N, \Sigma, P_i, S)\), kde \(P_i = \{A \to h_i(\alpha) : (A \to \alpha) \in R\}\).
Výstupní gramatika \(G_o\) je definována jako \(G_o = (N, D, P_o, S)\), kde \(P_o = \{A \to h_o(\alpha) : (A \to \alpha) \in R\}\).

Vstupní (respektive výstupní) gramatika tedy vznikne z překladové gramatiky tak, že odebereme výstupní (respektive vstupní) symboly. Z pětice se tak stane čtveřice a ve všech pravidlech budou ponechány pouze vstupní (respektive výstupní) symboly a neterminály.