Krok 1

V praxi sa možeme stretnúť s gramatikami, ktoré obsahujú rôzne "nedokonalosti" alebo prvky, ktoré komplikujú ich spracovanie, na zákalde čoho nie je možné zostrojiť ich syntaktický analyzátor konkrétneho typu. 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 resp. dovoľuje zostrojenie syntaktického analyzátora konkrétneho typu.

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 a ľavá faktorizácia.

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. Neexistuje teda 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 transformovať na vetu. Neexistuje teda 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álych symbolov $N_T$, ktoré môžu generovať terminálne reťazce (slová).
2. Odstránenie všetkých neterminálnych symbolov z gramatiky, ktoré nepatria do množiny $N_T$.
3. Iteratívna konštrukcia množiny dostupných symbolov $V_D$ (možno vykonať až po ukončení predchádzajúcich krokov).
4. Odstránenie všetkých symbolov z gramatiky, ktoré nepatria do množiny $V_D$.

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

Algoritmus 1. Konštrukcia množiny neterminálnálnych sybolov, 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číme pomocou nasledujúceho Algoritmu 2.

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 $\boldsymbol\varepsilon$-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 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$

Postup úpravy prepisovacích pravidiel gramatiky na základe množiny $N_\varepsilon$ prezentuje nasledujúci Algoritmus 4.

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

Slovný 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 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 postup úpravu prepisovacích pravidiel gramatiky na základe množiny $N_A$ vyjadrený nasledujúcim Algoritmom 6.

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 a ľavá faktorizácia

Posledné dve transformačné metódy zohrávajú kľúčovú úlohu pri tzv. determinizácii bezkontextových gramatík a tvorbe deterministických syntaktických analyzátorov, ktorým sa budeme bližšie venovať v nasledujúcom cvičení 8.

Jednou z najčastejších prekážok pri použití gramatiky v deterministickej analýze zhora nadol je výskyt ľavej rekurzie. Tento jav bráni konštrukcii efektívnych syntaktických analyzátorov, a preto je potrebné ho pred samotnou analýzou odstrániť.

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: Pravidlo

$$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. Predidlo $$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$.

Vyčlenenie spoločných symbolov zľava tzv. ľavá faktorizácia, ktorá predstavuje nasledujúci princíp transformácie gramatiky. Pravidlá

${}$
$A \to \alpha X\beta_1$
$A \to \alpha Y \beta_2$

nahradíme sadou pravidiel:

${}$
$A \to \alpha B$
$B \to X \beta_1$
$B \to Y \beta_2$.

Krok 2

Krok 3

V predchádzajúcom cvičení sme podrobne opísali proces návrhu gramatiky jazyka pre implementáciu jeho syntaktického analyzátora a interpretera metódou rekurzívneho zostupu. Uviedli sme, že asociativitu operátorov možno vyjadriť už na syntaktickej úrovni špecifikácie jazyka t. j. v gramatike prostredníctvom rekurzie (ľavú asosiativitu ľavou rekurziou a pravú asociativitu pravou rekurziou). V skutočnosti sme však pre vyjadrenie ľavej asociativity operátorov v gramatike v EBNF a v jej následnej implementácii nepoužili ľavú rekurziu ale iteráciu (opakovanie):

def E():
    T()
    # iterácia
    while current_symbol in FIRST(op):
        if current_symbol == op:
            get_next_symbol() 
        else: error()
        T()

na rozdiel od pravej asosiativity, ktorú sme vyjadrili a implementovali skutočnou pravou rekurziou:

def E():
    T()
    if current_symbol in FIRST(op):
        if current_symbol == op:
            get_next_symbol()
        else: error()
        E() # rekurzívne volanie

Pozrime sa preto na dôvod, ktorý viedol k tejto zmenne. Ak vychádzame z vyjadrenia ľavej asociativity operátorov v rámci gramatiky v BNF:

a transformujeme ju do EBNF tak, aby bola zachovaná ľavá rekurzia, získame gramatiku:

Problém však nastáva pri jej implementácii, keďže procedúra zodpovedajúca netreminálnemu symbolu E bude ako prvú procedúru v jej tele volať seba samú bez prvotného spracovania (redukcie) vstupu, čo vedie k problému nekonečnej rekurzie.

Ľavú rekurziu však môžeme z gramatiky odstrániť tak, že ju nahradíme pravou rekurziou, čím zároveň eliminujeme potrebu využitia iteratívnych konštrukcií jazyka pri implementácii jeho syntaktického analyzátora metódou rekurzívneho zostupu. Takto navrhnutý analyzátor sa následne stáva plne rekurzívnym — celý proces spracovania vstupu je realizovaný výlučne pomocou volaní rekurzívnych funkcií, bez použitia cyklov.

Teraz pristúpime k návrhu plne rekurzívneho syntaktického analyzátora jazyka aritmetických výrazov. Vychádzať budeme z vyššie uvedenej tranformácie gramatiky tohto jazyka odstránením ľavej rekurzie. Výsledok tejto transtormácie prevedieme do EBNF, čím získame gramatiku $G=(\{$E,E',T,T',F$\}$,$\{$+,*,(,)$\}$,$P'$,E$)$, kde $P'$ je množina nasledujúcich pravidiel:

Nevýhodou tohto prístupu je však skutočnosť, že často vedie k strate prirodzenej väzby medzi syntaktickou štruktúrou a sémantickým významom výrazov, čo prezentuje aj nasledujúce porovnanie odvodzovacích stromov toho istého aritmetického výrazu.

Samotný proces syntaxou riadenej interpretácia výrazov si následne vyžaduje modifikáciu, ktorej cieľom je zabezpečiť korektné priradenie významu jednotlivým výrazom. Nasledujúci obrázok ilustruje túto zmenu procesu itrerpretácie na konkrétnom príklade.