Krok 1

V praxi je možné sa stretnúť s gramatikami, ktoré obsahujú rôzne "nedokonalosti" alebo prvky, ktoré komplikujú ich spracovanie a nie je možné zostrojiť ich syntaktický analyzátor. Transformácie gramatík nám umožňujú tieto nedokonalosti odstrániť a previesť gramatiku do štandardizovanej ekvivalentnej formy, ktorá je vhodnejšia pre praktické použitie a dovoľuje zostrojenie syntaktického analyzátora.

Medzi základné transformácie bezkontextových gramatík patria:

• Odstránenie nadbytočných symbolov gramatiky
• Odstránenie $\varepsilon$-pravidiel
• Odstránenie jednoduchých pravidiel a cyklov
• Odstránenie ľavej rekurzie

Redukovaná bezkontextová gramatika je bezkontextová gramatika bez nadbytočných symbolov.

Vlastná bezkontextová gramatika je bezkontextová gramatika bez cyklu, bez $\varepsilon$-pravidiel a bez nadbytočných symbolov.

Teraz sa na jednotlivé úpravy pozrieme bližšie.

Odstránenie nadbytočných symbolov gramatiky

Nedostupný symbol je taký symbol $\beta \in N \cup T$ (terminál alebo neterminál) gramatiky, ktorý sa neobjavuje v žiadnej vetnej forme. Teda neexistuje derivácia $ S \Rightarrow^* \alpha \beta \gamma $, kde $S$ je počiatočný neterminál a $ \alpha, \gamma \in (N \cup T)^* $.

Nadbytočný symbol je taký symbol $\beta \in N \cup T$ (terminál alebo neterminál) gramatiky, ktorý je nedostupný alebo ktorého výskyt v rámci vetnej formy spôsobí, že žiadnou deriváciou nie je možné túto vetnú formu premeniť na vetu. Teda neexistuje derivácia $ S \Rightarrow^* \alpha\beta\gamma \Rightarrow^* w $, kde $S$ je počiatočný neterminál $\alpha,\gamma\in(N\cup T)^*$ a $ w \in T^*$.

Odstránenie nadbytočných symbolov z bezkontextovej gramatiky pozostáva z nasledujúcich krokov:

1. Iteratívna konštrukcia množiny neterminálov $N_T$, ktoré môžu generovať terminálne reťazce (slová).
2. Všetky neterminály, ktoré nie sú v množine $N_T$ z gramatiky odstránime.
3. Iteratívna konštrukcia množiny dostupných symbolov $V_D$ (možno vykonať až po ukončení predchádzajúcich krokov).
4. Všetky neterminály a terminály, ktoré nie sú prvkami množiny $V_D$ z gramatiky odstránime.

Množinu všetkých neterminálov, ktoré môžu generovať terminálne reťazce určime pomocou nasledujúceho algoritmu.

Algoritmus 1. konštrukcia množiny neterminálov, ktoré môžu generovať terminálne reťazce.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$
Výstup: Množina neterminálov $N_T$, ktoré môžu generovať terminálne reťazce

1. $N_T\leftarrow\emptyset$;
2. opakuj
3.   $\acute{N}_T\leftarrow N_T$;
4.   $N_T\leftarrow\acute{N}_T \cup \{A\;|\;A\to\alpha\in P \;\land\;\alpha\in(\acute{N}_T\cup T)^{*}\}$;
5. pokiaľ $N_T\neq\acute{N}_T$

Množinu všetkých dostupných symbolov gramatiky určime pomocou nasledujúceho algoritmu.

Algoritmus 2. konštrukcia množiny dostupných symbolov gramatiky.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$
Výstup: Množina dostupných symbolov $V_D$ gramatiky $G$.

1. $V_D\leftarrow\{S\}$;
2. opakuj
3.   $\acute{V}_D\leftarrow V_D$;
4.   $V_D\leftarrow\acute{V}_D \cup \{\beta\;|\;A\to\alpha\beta\gamma\in P \;\land\; \beta\in (N\cup T) \;\land\;A\in\acute{V}_D\;\land\;\alpha,\gamma\in(N\cup T)^{*}\}$;
5. pokiaľ $V_D\neq\acute{V}_D$

Odstránenie ε-pravidiel

Pravidlo sa nazýva $\boldsymbol\varepsilon$-pravidlo ak je tvaru $A \rightarrow \varepsilon$, kde $A$ je ľubovoľný neterminál. Intuitívne nám toto pravidlo hovorí, že daný neterminál môže v priebehu derivácie kedykoľvek zmiznúť.

Gramatika sa nazýva gramatika bez $\boldsymbol\varepsilon$-pravidiel ak jej množina pravidiel $P$ neobsahuje žiadne $\varepsilon$-pravidlo alebo v $P$ existuje jediné $\varepsilon$-pravidlo $S\to \varepsilon$, pričom začiatočný symbol gramatiky $S$ sa nevyskytuje na pravej strane žiadneho pravidla.

Odstránenie $\varepsilon$-pravidiel z bezkontextovej gramatiky pozostáva z nasledujúcich krokov:

1. Iteratívna konštruukcia množiny $N_\varepsilon$ obsahujúcej všetky neterminály, ktoré možno priamo či nepriamo prepísať na prázdny reťazec.
2. Úprava pravidiel gramatiky na základe množiny $N_\varepsilon$

Najprv si predstavíme algoritmus konštrukcie množiny $N_\varepsilon$.

Algoritmus 3. konštrukcia množiny neterminálov, ktoré môžu generovať $\varepsilon$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$
Výstup: Množina neterminálov $N_\varepsilon$, ktoré môžu generovať $\varepsilon$

1. $N_\varepsilon\leftarrow\emptyset$;
2. opakuj
3.   $\acute{N}_\varepsilon\leftarrow N_\varepsilon$;
4.   $N_\varepsilon\leftarrow\acute{N}_\varepsilon \cup \{A\;|\;A\to\alpha\in P \;\land\;\alpha\in\acute{N}_\varepsilon^{*}\}$;
5. pokiaľ $N_\varepsilon\neq\acute{N}_\varepsilon$

Teraz si predstavíme postup úpravy prepisovacích pravidiel gramatiky na základe množiny $N_\varepsilon$.

Algoritmus 4. Úprava pravidiel gramatiky na základe množiny $N_\varepsilon$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a množina neterminálov $N_\varepsilon$, ktoré môžu generovať $\varepsilon$.
Výstup: Bezkontextová gramatika $G'$ bez $\varepsilon$-pravidiel.

1. $P'\leftarrow P$; kde $P'$ je nová množina prepisovacích pravidiel gramatiky $G'$
2. pre všetky $A \to \varepsilon \in P'$ vykonaj
3.   ak $A\neq S$ potom
4.    $P' \leftarrow P' - \{A \to \varepsilon\}$;
5.   koniec ak
6.   ak $A=S$ a $S$ sa vyskytuje na pravej strane nejakého pravidla z $P'$ potom
7.    $P' \leftarrow P' - \{S \to \varepsilon\}$;
8.    $P' \leftarrow P' \cup \{S' \rightarrow S \mid \varepsilon\}$; kde $S'$ je nový počiatočný symbol gramatiky $G'$
9.   koniec ak
10. koniec pre
11. pre všetky $A \to \beta \in P'$ vykonaj
12.   ak $\beta = \alpha_0B_1\alpha_1B_2\ldots B_k\alpha_k,$ kde $\alpha_0,\ldots, \alpha_k \in ((N-N_\varepsilon)\cup T)^*$, $B_1,\ldots, B_k\in N_\varepsilon$ potom
13.    $P'\leftarrow P'\cup\{A \to \alpha_0X_1\alpha_1X_2\ldots X_k\alpha_k \mid X_i=B_i \;\lor\; X_i=\varepsilon,\text{ pre }i=1,2,\ldots,k\}$;
14.   koniec ak
15.   ak $A\neq S$ potom
16.    $P' \leftarrow P' - \{A \to \varepsilon\}$;
17.   koniec ak
18. koniec pre

Slový opis Algoritmu 4.

1. Z gramatiky najprv odstránime všetky $\varepsilon$-pravidlá, výnimkou je len pravidlo pre počiatočný symbol. Ak $S \in N_\varepsilon$, potom pravidlo $S \rightarrow \varepsilon$:

• v gramatike ponecháme ak sa $S$ nevyskytuje na pravej strane židneho pravidla,
• inak toto pravidlo odstránime, ale do gramatiky pridáme nový počiatočný neterminál $S'$ s pravidlami $S' \rightarrow S \mid \varepsilon$.

2. Postupne prejdeme jednotlivé pravidlá v gramatike, ak sa na pravej strane vyskytuje nejaký neterminál z množiny $N_\varepsilon$, teda pravidlo bude tvaru: $$A \to \alpha_0B_1\alpha_1B_2\ldots B_k\alpha_k,$$ kde $\alpha_0,\ldots, \alpha_k \in ((N-N_\varepsilon)\cup T)^*$, $B_1,\ldots, B_k\in N_\varepsilon$, potom toto pravidlo nahradíme sadou pravidiel tvaru: $$A \to \alpha_0X_1\alpha_1X_2\ldots X_k\alpha_k,$$ kde $X_i=B_i$ alebo $X_i=\varepsilon$, pre $i\in\{1,2,\ldots,k\}$. Ak by pritom vzniklo pravidlo tvaru $A \to \varepsilon$ a $A\neq S$ pravidlo do gramatiky nepridáme.

Odstránenie jednoduchých pravidiel a cyklov

Jednoduché pravidlo je pravidlo tvaru $A \to B$, kde $A$ a $B$ sú ľubovoľné neterminály. Intuitívne nám toto pravidlo hovorí, že neterminál $A$ na ľavej strane sa "vie správať rovnako" ako neterminál $B$ na pravej strane.

Bezkontextová gramatika bez cyklu je taká bezkontextová gramatika, kde nie je pre žiadny neterminál možná derivácia $A \Rightarrow^+ A$. Platí, že ak je gramatika bez jednoduchých a $\varepsilon$-pravidiel, potom je bez cyklu (obrátene platiť nemusí).

Odstránenie jednoduchých pravidiel z bezkontextovej gramatiky pozostáva z nasledujúcich krokov:

1. Iteratívna konštruukcia množiny neterminálov $N_A$, ktoré je možné odvodiť z daného neterminálu $A$.
2. Úprava pravidiel gramatiky na základe množiny $N_A$

Najprv si predstavíme algoritmus konštrukcie množiny $N_A$.

Algoritmus 5. konštrukcia množiny neterminálov, ktoré je možné odvodiť z daného neterminálu $A$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a neterminál $A\in N$.
Výstup: Množina neterminálov $N_A$, ktoré je možné odvodiť z daného neterminálu $A$.

1. $N_A\leftarrow\{A\}$;
2. opakuj
3.   $\acute{N}_A\leftarrow N_A$;
4.   $N_A\leftarrow\acute{N}_A \cup \{C\;|\;B\to C\in P \;\land\;B\in\acute{N}_A\}$;
5. pokiaľ $N_A\neq\acute{N}_A$

Teraz sa bližšie pozrieme na úpravu prepisovacích pravidiel gramatiky na základe množiny $N_A$.

Algoritmus 6. Úprava pravidiel gramatiky na základe množín $N_A$, pre každý neterminál $A\in N$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a množina neterminálov $N_A$, ktoré je možné odvodiť z daného neterminálu $A$ pre každý neterminál $A\in N$.
Výstup: Bezkontextová gramatika $G'=(N,T,P',S)$ bez jednoduchých pravidiel.

1. $P'\leftarrow P$
2. odstráň všetky jednoduché pravidlá z $P'$
3. pre všetky $N_A$, kde $A \in N$ vykonaj
4.   pre všetky $B\in N_A$ vykonaj
5.    pre všetky $B\to \alpha \in P$ vykonaj
6.     ak $B\to \alpha$ nie je jednoduché pravidlo potom
7.      $P'\leftarrow P'\cup\{A\to\alpha\}$
8.     koniec ak
9.    koniec pre
10.   koniec pre
11. koniec pre

Odstránenie ľavej rekurzie

Neterminálny symbol $A$ je rekurzívny zľava, ak existuje derivácia $A \Rightarrow^+ A\beta$, kde $\beta \in (N \cup T)^*$. Rozlišujeme dva typy ľavej rekurzie:

• priama ľavá rekurzia ak $A \Rightarrow^1 A\beta$, v množine pravidiel preto musí existovať prepisovacie pravidlo tvaru $A \to A\beta$ (tento typ ľavej rekurzie je viditeľný priamo v pravidlách pre daný neterminál, napríklad $A \to Aa$),
• nepriama ľavá rekurzia ak $A \Rightarrow^k A\beta$, kde $k>1$ (tento typ ľavej rekurzie nie je viditeľný priamo v pravidlách pre daný neterminál, napríklad $A \to Ba$, $B \to Ac$).

ľavo rekurzívna gramatika je taká gramatika, ktorá má aspoň jeden ľavo rekurzívny neterminálny symbol.

Pravidlá, ktoré sú zdrojom priamej ľavej rekurzie, je možné z gramatiky odstrániť nasledujúcou transformáciou:

$$A \rightarrow A\alpha \mid \beta \quad $$ možno zameniť za sadu pravidiel: $$ \begin{align*} A &\rightarrow \beta A' \mid \beta\\ A' &\rightarrow \alpha A' \mid \alpha, \end{align*} $$ kde $\alpha, \beta \in (N \cup T)^*, A \in N$.

Pre viac alternatív $\alpha, \beta $ možno schému intuitívne rozšíriť nasledovne: $$A \rightarrow A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m $$ možno zameniť za sadu pravidiel: $$ \begin{align*} A &\rightarrow \beta_1 A' \mid \ldots \mid \beta_m A' \mid \beta_1 \mid \ldots \mid \beta_m\\ A' &\rightarrow \alpha_1 A' \mid \ldots \mid \alpha_n A' \mid \alpha_1 \mid \ldots \mid \alpha_n, \end{align*} $$ kde $\alpha_i, \beta_i \in (N \cup T)^*, A \in N$.

Krok 2

Dotazník na ohodnotenie učiva

Vážení študenti,
poprosil by som Vás o vyplnenie tohto dotazníka .

Tento dotazník slúži na ohodnotenie vašich skúseností s pripravenými materiálmi z siedmeho cvičenia. Na vylepšovaní učiva sa aktívne pracuje a Vaše odpovede nám pomôžu zlepšiť kvalitu výučby.

Ďakujem