Krok 1

V praxi sa možeme stretnúť s gramatikami, ktoré obsahujú rôzne 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 najdôležitejšie transformácie bezkontextových gramatík patria tieto úpravy:

• odstránenie nadbytočných symbolov,
• odstránenie $\varepsilon$-pravidiel,
• odstránenie jednoduchých pravidiel a cyklov,
• odstránenie ľavej rekurzie a ľavá faktorizácia.

Následne, 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 začiatočný symbol $\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 $N_T$ – neterminálych symbolov, ktoré môžu generovať terminálne reťazce.
2. Odstránenie všetkých neterminálnych symbolov, ktoré nepatria do množiny $N_T$ – ak sa takýto symbol nachádza v niektorom pravidle, toto pravidlo 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. Odstránenie všetkých symbolov z gramatiky, ktoré nepatria do množiny $V_D$ – ak sa takýto symbol nachádza v pravidle, toto pravidlo z gramatiky odstránime.

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. do
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. while $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. do
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. while $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$ – určuje 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. do
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. while $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. for all $A \to \varepsilon \in P'$ do
3.   if $A\neq S$ then
4.    $P' \leftarrow P' - \{A \to \varepsilon\}$;
5.   end if
6.   if $A=S$ a $S$ sa vyskytuje na pravej strane nejakého pravidla z $P'$ then
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.   end if
10. end for
11. for all $A \to \beta \in P'$ do
12.   if $\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$ then
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.   end if
15.   if $A\neq S$ then
16.    $P' \leftarrow P' - \{A \to \varepsilon\}$;
17.   end if
18. end for

Slovný opis Algoritmu 4.

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

• pravidlo $S \rightarrow \varepsilon$ ponecháme, ak sa $S$ nevyskytuje na pravej strane žiadneho pravidla,
• v opačnom prípade pravidlo $S \rightarrow \varepsilon$ odstránime a do gramatiky pridáme nový začiatočný symbol $S'$ s pravidlami $S' \rightarrow S \mid \varepsilon$.

2. Postupne prechádzame jednotlivé pravidlá gramatiky. 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$ sa môže správať rovnako ako neterminál $B$.

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 $N_A$ – neterminálnych symbolov, 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. do
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. while $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. for all $N_A$, kde $A \in N$ do
4.   for all $B\in N_A$ do
5.    for all $B\to \alpha \in P$ do
6.     if $B\to \alpha$ nie je jednoduché pravidlo then
7.      $P'\leftarrow P'\cup\{A\to\alpha\}$
8.     end if
9.    end for
10.   end for
11. end for

Odstránenie ľavej rekurzie a ľavá faktorizácia

Posledné dve transformačné metódy zohrávajú kľúčovú úlohu pri tvorbe deterministických syntaktických analyzátorov. Jednou z najčastejších prekážok použitia bezkontextovej gramatiky v deterministickej analýze zhora nadol je výskyt ľavej rekurzie. Tento jav spôsobuje, že parser môže uviaznuť v nekonečnom odvodení, čo znemožňuje vytvorenie efektívneho analyzátora. Odstránenie ľavej rekurzie je preto nevyhnutným krokom, ktorý musí predchádzať samotnej syntaktickej analýze.

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

Ľavá faktorizácia, teda vyčlenenie spoločných predpôn pravých strán pravidiel s rovnakou ľavou stranou, je transformačný postup, ktorého cieľom je upraviť gramatiku do tvaru vhodného pre deterministickú syntaktickú analýzu zhora nadol. ktorá predstavuje nasledujúci princíp transformácie gramatiky. Princíp tejto transformácie možno formalizovať nasledovne. 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 tejto časti sa pozrieme na to, ako výskyt ľavej rekurzie ovplyvňuje praktickú použiteľnosť gramatiky pri tvorbe rekurzívneho syntaktického analyzátora. Na konkrétnom príklade ukážeme, prečo ľavá rekurzia spôsobuje problémy, ako sa odstraňuje a aký dopad má výsledná transformácia na štruktúru gramatiky, priebeh parsovania a následnú interpretáciu.

Aby sme lepšie porozumeli súvislostiam, nadviažeme na predchádzajúce cvičenia, kde sme podrobne opísali proces návrhu gramatiky jazyka pre implementáciu jeho syntaktického analyzátora a interpretera metódou rekurzívneho zostupu. Ukázali 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.