Krok 1

Zásobníkové automaty (ZA) zohrávajú pri akceptácii bezkontextových jazykov rovnakú úlohu ako konečné automaty pri akceptácii regulárnych jazykov. To znamená, že každý jazyk, pre ktorý existuje bezkontextová gramatika, ktorá ho generuje, je akceptovateľný nejakým ZA a naopak, každý jazyk akceptovaný nejakým ZA je zároveň generovateľný nejakou bezkontextovou gramatikou.

Schému ZA prezentuje nasledujúci Obrázok 1.

Zásobníkový automat (angl. pushdown automata) je usporiadana sedmica: $$M=(Q,T,\Gamma,\delta,q_0,Z_0,F),$$ kde:

• $Q$ je konečná množina stavov automatu,
• $T$ je konečná množina prípustných vstupných symbolov (alebo vstupná abeceda) automatu,
• $\Gamma$ je konečná množina zásobníkových symbolov (tzv. zásobníková abeceda),
• $\delta$ je prechodová funkcia zásobníkového automatu, $\delta: Q \times T_\varepsilon\times\Gamma_\varepsilon \to 2^{Q\times\Gamma^*}$,
• $q_0$ je počiatočný alebo iniciálny stav automatu, $q_0 \in Q$,
• $Z_0$ je zásobníkový symbol nachádzajajúci sa na začiatku každého výpočtu na dne zásobníka, $Z_0 \in \Gamma$,
• $F$ je množina akceptujúcich (alebo koncových) stavov automatu, $F\subseteq Q$.

Všimnime si, že špecifikácia prechodovej funkcie $\delta$ zodpovedá nedeterministickému ZA. Uprednostnenie tohto variantu vyplýva z jeho univerzálnosti a schopnosti popísať taktiež deterministický variant ZA jednoduchým obmedzením kodomény jeho prechodovej funkcie $\delta$.

Konfigurácia zásobníkového automatu $M=(Q, T, \Gamma, \delta, q_0, Z_0, F)$ je usporiadaná trojica $(q, w, s)\in Q\times T^*\times \Gamma^*$, kde $q$ je aktuálny stav automatu, $w$ je ešte nespracovaná časť vstupu a $s$ je obsah zásobníka. Vo výpočte ZA sa vyskytujú osobitné konfigurácie, ktoré zohrávajú špecifickú úlohu pri akceptácii vstupu:

• Začiatočná konfigurácia ZA $M$ – je konfigurácia v tvare $(q_0, w, Z_0)$, kde $w$ je celý vstupný reťazec.
• Koncová konfigurácia ZA $M$ – je konfigurácia tvaru $(q, \varepsilon, s)$, teda taká, pri ktorej bol celý vstup spracovaný.
• Akceptujúca konfigurácia ZA $M$ – je koncová konfigurácia, v ktorej $q \in F$ alebo $s=\varepsilon$.

Na množine konfigurácií $Q \times T^* \times \Gamma^* $ definujeme binárnu reláciu prechodu (alebo krok výpočtu) ZA označovaného $\vdash$ nasledovne. Nech $q, p \in Q, w \in T^*, x \in T_\varepsilon, Z \in \Gamma, s,t \in \Gamma^*$. Potom

Postupnosť (sekvencia) konfigurácií $ (q_0, w_0, s_0), (q_1, w_1, s_1), \ldots, (q_k, w_k, s_k) $, pre $ k \in \mathbb{N}$ takých, že $$ (q_0, w_0, s_0) \vdash (q_1, w_1, s_1) \vdash \dots \vdash (q_k, w_k, s_k), $$ sa nazýva výpočet ZA $M$ z $(q_0, w_0, s_0)$ do $(q_k, w_k, s_k)$ a vyjadrovať ho budeme v tvare $$ (q_0, w_0, s_0) \vdash^k (q_k, w_k, s_k). $$

Pri zásobníkových automatoch existujú dva spôsoby akceptácie reťazcov. Slovo môže byť akceptované:

• akceptačným stavom – automat prečíta celý vstup a ukončí výpočet v akceptačnom stave, obsah zásobníka je v tomto prípade irelevantný, alebo
• prázdnym zásobníkom – automat prečíta celý vstup a ukončí výpočet s prázdnym zásobníkom, stav je v tomto prípade irelevantný.

Oba spôsoby akceptácie slov sú ekvivalentné. Vždy sa dá automat pracujúci jedným spôsobom previesť na automat pracujúci druhým spôsobom a naopak.

Jazyk $L(M)$ rozpoznávaný (akceptovaný) zásobníkovým automatom $M$ je teda množina:

Riešenie

V 4. cvičení sme dokázali, že tento jazyk nie je regulárny, preto neexistuje KSA, ktorý by ho akceptoval. Problém spočíva v tom, že pri postupnom spracovávaní reťazca musíme zabezpečiť taktiež počítanie výskytov jeho jednotlivých symbolov. Keďže jediným kvázi-pamäťovým prvkom KSA je jeho vnútorny stav, túto informáciu nemáme ako zaznamenať. V prípade ZA však máme k dispozícii skutočnú pamäťovú jednotku – zásobník, nad ktorým možeme vykonávať základné operácie $\mathit{PUSH}$ a $\mathit{POP}$. Uveďme teda princíp fungovania ZA akceptujúceho jazyk $L$.

1. Vždy keď sa na vstupe spracuje symbol $a$, na vrchol zásobníka sa pridá nejaký (konkrétny) symbol zásobníkovej abecedy, napr. symbol $a$.
2. Po spracovaní prvého symbolu $b$ zo vstupu ZA zmení svoj stav a vykoná operáciu $\mathit{POP}$ nad zásobníkom.
3. Po spracovaní každého ďalšieho symbolu $b$ zo vstupu ZA vykoná operáciu $\mathit{POP}$ nad zásobníkom.
4. Ak po spracovaní celého reťazca zo vstupu v zásobníku ostane len počiatočný zásobníkový symbol, ZA zmení svoj stav na akceptačný.

Výsledný automat má tvar $M=(\{q_0,q_1,q_2\},\{a,b\},\{a,Z_0\},\delta,q_0,Z_0,\{q_2\})$, kde prechodová funkcia $\delta$ je určená nasledujúcim diagramom.

Výpočet nad slovom $aabb$:
$(q_0,aabb,$$\phantom{a}Z_0$$)\vdash(q_0,abb,$$\phantom{a}aZ_0$$)\vdash(q_0,bb,$$\phantom{a}aaZ_0$$)\vdash(q_1,b,$$\phantom{a}aZ_0$$)\vdash(q_1,\varepsilon,$$\phantom{a}Z_0$$)\vdash(q_2,\varepsilon,$$\phantom{a}Z_0$$)\nvdash$
Slovo bolo akceptované akceptačným stavom.

Výpočet nad slovom $aab$:
$(q_0,aab,$$\phantom{a}Z_0$$)\vdash(q_0,ab,$$\phantom{a}aZ_0$$)\vdash(q_0,b,$$\phantom{a}aaZ_0$$)\vdash(q_1,\varepsilon,$$\phantom{a}aZ_0$$)\nvdash$
Slovo nebolo akceptované, keďže výpočet neskončil v konečnom stave ani s prázdnym zásobníkom.

Riešenie

$M=(\{q_0,q_1\},\{a,b\},\{a,Z_0\},\delta,q_0,Z_0,\emptyset)$, kde prechodová funkcia $\delta$ je určená nasledujúcim diagramom.

Výpočet nad slovom $aabb$:
$(q_0,aabb,$$\phantom{a}Z_0$$)\vdash(q_0,abb,$$\phantom{a}a$$)\vdash(q_0,bb,$$\phantom{a}aa$$)\vdash(q_1,b,$$\phantom{a}a$$)\vdash(q_1,\varepsilon,\varepsilon)\nvdash$
Slovo bolo akceptované prázdnym zásobníkom.

Výpočet nad slovom $aab$:
$(q_0,aab,$$\phantom{a}Z_0$$)\vdash(q_0,ab,$$\phantom{a}a$$)\vdash(q_0,b,$$\phantom{a}aa$$)\vdash(q_1,\varepsilon,$$\phantom{a}a$$)\nvdash$
Slovo nebolo akceptované, keďže výpočet neskončil s prázdnym zásobníkom ani v konečnom stave.

Krok 2

Základnou požiadavkou na v praxi použiteľný syntaktický analyzátor je jeho schopnosť deterministicky spracovať vstupné reťazce s lineárnou časovou zložitosťou. V kontexte syntaktickej analýzy zhora nadol to znamená, že v každom kroku (najľavejšieho) odvodenia je možné jednoznačne (deterministicky) určiť, ktoré pravidlo gramatiky je potrebné aplikovať. Takéto sytaktické analyzátory potom označujeme ako prediktívne. Aby sme mohli rozhodnúť o tom, či je daná gramatika deterministická potrebujeme ju najprv analyzovavať, a to prostredníctvom konštukcie nasledujúcich analytických množín bezkontextových gramatík.

$\mathit{FIRST}(\alpha)$ je množina takých terminálnych symbolov, ktoré môžu stáť na začiatku reťazcov odvodených z $\alpha$. Ak možno z $\alpha$ odvodiť prázdny reťazec, $\varepsilon$ taktiež patrí do tejto množiny.

Výpočet množiny $\mathit{FIRST}(\alpha)$ pre ľubovoľný reťazec $\alpha \in (N \cup T)^{*}$ je praktické rozdeliť na dve časti. Najprv sa pre každý neterminálny symbol gramatiky $A$ vypočíta množina $\mathit{FST}_A$ – teda množina terminálnych symbolov, ktoré sa môžu objaviť na začiatku reťazcov odvodených z tohto neterminálneho symbolu $A$. Keďže tieto pomocné množiny $\mathit{FST}_A$ závisia iba od pravidiel gramatiky, stačí ich vytvoriť iba raz. Tento krok predstavuje akési predspracovanie gramatiky, ktoré umožní neskôr jednoduchšie a efektívne určovať množinu $\mathit{FIRST}(\alpha)$ aj pre ľubovoľne dlhé reťazce.

Tento dvojkrokový postup môžeme formalizovať nasledujúcou dvojicou algoritmov.

Algoritmus 1. konštrukcia množín $\mathit{FST}_A$ pre všetky $A \in N$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a množina $N_\varepsilon$.
Výstup: Množiny $\mathit{FST}_A$ pre všetky $A \in N$.

1. for all $a \in T$ do
2.   $\mathit{FST}_a \leftarrow \{a\}$;
3. end for
4. for all $A \in N$ do
5.   $\mathit{FST}_A \leftarrow \emptyset$;
6. end for
7. for all $A \in N_\varepsilon$ do
8.   $\mathit{FST}_A \leftarrow \{\varepsilon\}$;
9. end for
10. do
11.   for all $A\to\beta_1\beta_2\ldots\beta_k \in P$, kde $\beta_1\beta_2\ldots\beta_k \in (N\cup T)$ do
12.    for all $\beta_i \in \{\beta_1\beta_2\ldots\beta_k\}$ do
13.     $\mathit{FST}_A \leftarrow \mathit{FST}_A \cup \mathit{FST}_{\beta_i}$;
14.     if $\beta_i \notin N_\varepsilon$ then
15.      break;
16.     end if
17.    end for
18.   end for
19. while nastala zmena niektorej z množín $\mathit{FST}_A$ pre všetky $A\in N$

Slovný opis:

Algoritmus 1 iteratívnej konštrukcie pomocných množín $\mathit{FST}_A$ pre všetky neterminálne symboly $A \in N$ možno rozdeliť do troch fáz:

1. Pre každý terminálny symbol $a \in T$ sa vytvorí pomocná množina $\mathit{FST}_a = \{a\}$.
2. Pomocné množiny $\mathit{FST}_A$ pre všetky neterminálne symboly $A \in N$ sa inicializujú prázdnou množinou. Následne sa do pomocných množín $\mathit{FST}_A$ vloží $\varepsilon$ pre neterminálne symboly $A \in N_\varepsilon$, z ktorých možno odvodiť prázdny reťazec pridá $\varepsilon$.
3. Iteratívne sa prechádzajú všetky pravidlá $A \to \beta_1 \beta_2 \dots \beta_k$, kde $\beta_1,\beta_2,\ldots,\beta_k$ predstavujú jednotlivé terminálne a neterminálne symboly pravej strany pravidla. Do množiny $\mathit{FST}_A$ sa postupne pridáva obsah množín $\mathit{FST}_{\beta_i}$, až kým nenarazíme na symbol $\beta_i$ z ktorého nemožno odvodiť prázdny reťazec a spracovávanie daného pravidla sa v tomto okamihu preruší. Tento proces sa opakuje, až kým sa všetky množiny $\mathit{FST}_A$ nestabilizujú.

Algoritmus 2. konštrukcia množiny $\mathit{FIRST}(\alpha)$ pre $\alpha \in (N \cup T)^{*}$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a vetná forma $\alpha\in(N \cup T)^{*}$.
Výstup: Množina $\mathit{FIRST}(\alpha)$.

1. function $\mathit{FIRST}(\alpha)$
2.  if $\alpha=\varepsilon$ then
3.    return $\{\varepsilon\}$;
4.  end if
5.  if $\alpha=a\beta$, kde $a\in T\;\land\;\beta\in(N\cup T)^{*}$ then
6.    return $\{a\}$;
7.  end if
8.  if $\alpha=A\beta$, kde $A\in N\;\land\;\beta\in(N\cup T)^{*}$ then
9.    if $A\in N_\varepsilon$ then
10.     return $(\mathit{FST}_A - \{\varepsilon\})\cup \mathit{FIRST}(\beta)$;
11.    else
12.     return $\mathit{FST}_A$;
13.    end if
14.  end if
15. end function

Množina $\mathit{FOLLOW}(A)$ je množina všetkých terminálnych symbolov, ktoré môžu stáť bezprostredne za neterminálom A v nejakej vetnej forme (reťazci odvoditeľnom zo začiatočného symbolu gramatiky). Ak neterminál A môže stáť na konci niektorej vetnej formy, symbol $ patrí taktiež do tejto množiny.

Algoritmus 3. konštrukcia množiny $\mathit{FOLLOW}(A)$ pre všetky $A \in N$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a množina neterminálnych symbol $N$.
Výstup: Množiny $\mathit{FOLLOW}(A)$ pre všetky $A \in N$.

1. pre všetky $A \in N$ vykonaj
2.  $\mathit{FLW}_A\leftarrow \emptyset$;
3. koniec pre
4. $\mathit{FLW}_S\leftarrow\{$$$\};$
5. opakuj
6.  pre všetky $A \in N$ vykonaj
7.   pre všetky $B\to\alpha A\beta \in P$, kde $\alpha,\beta\in (N\cup T)^{*}$ vykonaj
8.    $\mathit{FLW}_A \leftarrow \mathit{FLW}_A \cup (\mathit{FIRST}(\beta)-\{\varepsilon\});$
9.     ak $\varepsilon \in \mathit{FIRST}(\beta)$ potom
10.      $\mathit{FLW}_A\leftarrow \mathit{FLW}_A \cup \mathit{FLW}_B;$
11.     koniec ak
12.   koniec pre
13.  koniec pre
14. pokiaľ nenastala zmena niektorej z množín $\mathit{FLW}_A$ pre všetky $A \in N$.
15. pre všetky $A \in N$, $\mathit{FOLLOW}(A)=\mathit{FLW}_A$

Slovny opis: Algoritmus 3 iteratívne konštruuje množiny $\mathit{FOLLOW}(A)$ pre všetky neterminálne symboly $A \in N$. Jeho činnosť možno opísať prostredníctvom troch základných pravidiel, ktoré zodpovedajú jednotlivým častiam tohto algoritmu:

1. Na začiatku sa všetky pomocné množiny $\mathit{FLW}_A$ pre všetky neterminálne symboly $A \in N$ inicializujú prázdnou množinou.
2. Do pomocnej množiny $\mathit{FLW}_S$ pre začiatočný symbol $S$ gramatiky sa pridá špeciálny koncový symbol $. Tento symbol indikuje, že existuje taká vetná forma, v ktorej $S$ stojí na jej konci. Je pritom zrejmé, že tento symbol bude vždy súčasťou množiny $\mathit{FOLLOW}$ pre začiatočný symbol gramatiky.
3. Ak neterminálny symbol $A$ stojí na pravej strane pravidla pre neterminálny symbol $B$ a je nasledovaný zvyškom pravej strany pravidla $\beta$,

• do $\mathit{FLW}_A$ sa pridá $\mathit{FIRST}(\beta)$ okrem prázdneho reťazca $\varepsilon$,
• ak $\mathit{FIRST}(\beta)$ obsahuje prázdný reťazec, do $\mathit{FLW}_A$ sa pridá taktiež obsah $\mathit{FLW}_B.$

Táto fáza sa opakuje, až kým sa všetky množiny $\mathit{FLW}_A$ nestabilizujú.

Na záver platí, že $\mathit{FOLLOW}(A)=\mathit{FLW}_A\text{ pre všetky }A\in N.$

Aby sme zistili, či gramatika povoľuje konštrukciu prediktívneho syntaktického analyzátora, je nutné konštruovať množiny $\mathit{PREDICT}(A\to\alpha)$ pre každé pravidlo danej gramatiky a následne konštruovať tzv. rozkladovú tabuľku $RT$ (z angl. parse table). Táto tabuľka na základe aktuálne odvodzovaného (expandovaného) netermináleho symbolu $A$ a terminálneho symbolu zo vstupu $t$ špecifikuje, ktoré z pravidiel gramatiky možno aplikovať, ide teda o zobrazenie:

V prípade, že vstupný symbol neurčuje použitie žiadneho pravidla pre expanziu neterminálu $A$, signalizuje to syntaktickú chybu.

Najprv teda definujme množinu $\mathit{PREDICT}(A\to\alpha)$, ktorá predstavuje množinu všetkých takých terminálnych symbolov (prípadne symbolu $), ktoré pokiaľ sa nachádzajú na vstupe, signalizujú možnosť použiť na expanziu neterminálu $A$ pravidlo $A\to\alpha$. Formálne túto množinu definujeme nasledovne:

$$ \mathit{PREDICT}(A\to\alpha)=\left\{\begin{array}{ll} \mathit{FIRST}(\alpha), & \text{ak } \varepsilon \notin \mathit{FIRST}(\alpha),\\ (\mathit{FIRST}(\alpha)-\{\varepsilon\})\cup \mathit{FOLLOW}(A), & \text{ak } \varepsilon \in \mathit{FIRST}(\alpha). \end{array}\color{transparent}\right\} $$

Rozkladovú tabuľku potom možno konštruovať pomocou nasledujúceho pravidla:

Ak platí, že rozkladová tabuľka danej gramatiky jazyka neobsahuje konflikty, teda pre jeden neterminálny symbol $A$ a jeden terminálny symbol $t$ poskytuje nanajvýš jedno pravidlo, túto gramatiku označujeme ako $LL(1)$ gramatiku. Formálna špecifikácia zobrazenia RT v prípade $LL(1)$ gramatík má preto tvar:

Na základe takejto gramatiky možno zostaviť deterministický (prediktívny) syntaktický analyzátor, ktorého princíp fungovania predstavíme v ďalšom kroku.

Konflikty v rozkladovej tabuľke pre gramatiku z vyššie uvedeného príkladu sú spôsobené ľavo rekurzívnymi prepisovacími pravidlami. Gramatika s ľavo rekurzívnymi neterminálnymi symbolmi preto nikdy nebude $LL(1)$ gramatikou.

Ďalším zdrojom nedeterminizmu v gramatike je prítomnosť viacerých pravidiel pre neterminálny symbol $A,$ ktorých pravé strany začínajú rovnakou vetnou formou $\alpha$. Keďže princípy eliminácie oboch týchto problémov sme vysvetlili a precvičili na predchádzajúcom cvičení, v nasledujúcom príklade sa už len presvedčíme, že odstránením týchto zdrojov nedeterminizmu možno gramatiku determinizovať.

Riešenie

a) $T = \{$x, y, z, w$\}$, $N=\{$ S, A, B, C$\}$.

b)

${}$	${}$
$\phantom{\overset{(2)}{\Rightarrow}}$S	$\overset{(1)}{\Rightarrow}$ A
${}$	$\overset{(2)}{\Rightarrow}$ xAx
${}$	$\overset{(3)}{\Rightarrow}$ xCx
${}$	$\overset{(6)}{\Rightarrow}$ xzBzx
${}$	$\overset{(5)}{\Rightarrow}$ xzCzx
${}$	$\overset{(8)}{\Rightarrow}$ xzzx

Strom odvodenia vyplýva priamo z derivácie.

c)

${}$	${}$	${}$
$\mathit{FIRST}($S$) = \{$ x, z, w $\varepsilon\}$	${}$	$\mathit{FOLLOW}($S$) = \{$$$\}$
$\mathit{FIRST}($A$) = \{$ x, z, w, $\varepsilon\}$	${}$	$\mathit{FOLLOW}($A$) = \{$$, x, w $\}$
$\mathit{FIRST}($B$) = \{$ y, z, w, $\varepsilon\}$	${}$	$\mathit{FOLLOW}($B$) = \{$ y, z $\}$
$\mathit{FIRST}($C$) = \{$ z, w, $\varepsilon\}$	${}$	$\mathit{FOLLOW}($C$) = \{$$, x, y, z, w$\}$

d)

${}$
$\mathit{PREDICT}(1) = \{$ x, z, w, $$\}$
$\mathit{PREDICT}(2) = \{$ x $\}$
$\mathit{PREDICT}(3) = \{$ z, w, x, $$\}$
$\mathit{PREDICT}(4) = \{$ y $\}$
$\mathit{PREDICT}(5) = \{$ z, w, y $\}$
$\mathit{PREDICT}(6) = \{$ z $\}$
$\mathit{PREDICT}(7) = \{$ w $\}$
$\mathit{PREDICT}(8) = \{$$ , x, y, z, w $\}$

e)

$RT$	x	y	z	w	$
S	$\textcolor{green}{1}$		$\textcolor{green}{1}$	$\textcolor{green}{1}$	$\textcolor{green}{1}$
A	$\textcolor{red}{2, 3}$		$\textcolor{green}{3}$	$\textcolor{green}{3}$	$\textcolor{green}{3}$
B		$\textcolor{red}{4, 5}$	$\textcolor{green}{5}$	$\textcolor{green}{5}$
C	$\textcolor{green}{8}$	$\textcolor{green}{8}$	$\textcolor{red}{6, 8}$	$\textcolor{red}{7, 8}$	$\textcolor{green}{8}$

Uvedená gramatika nie je $LL(1)$ gramatikou, pretože v rozkladovej tabuľke sú konflikty.

f) Analyzátor by nemohol analyzovať daný reťazec, pretože v tabuľke analýzy sú konflikty.

Riešenie

a) $T = \{$ x, y, z, $\}$, $N=\{$ S, A, B $\}$.

b)

c)

${}$	${}$	${}$
$\mathit{FIRST}($S$) = \{$ x, y, z $\}$	${}$	$ \mathit{FOLLOW}($S$) = \{$$$\}$
$\mathit{FIRST}($A$) = \{$ x, y, z $\}$	${}$	$ \mathit{FOLLOW}($A$) = \{$ y, z $\}$
$\mathit{FIRST}($B$) = \{$ y, z $\}$	${}$	$ \mathit{FOLLOW}($B$) = \{$ y, z, $$\}$

d)

${}$
$\mathit{PREDICT}(1) = \{$ x, y, z $\}$
$\mathit{PREDICT}(2) = \{$ x $\}$
$\mathit{PREDICT}(3) = \{$ y, z $\}$
$\mathit{PREDICT}(4) = \{$ y $\}$
$\mathit{PREDICT}(5) = \{$ z $\}$

e)

$RT$	x	y	z	$
S	$\textcolor{green}{1}$	$\textcolor{green}{1}$	$\textcolor{green}{1}$
A	$\textcolor{green}{2}$	$\textcolor{green}{3}$	$\textcolor{green}{3}$
B		$\textcolor{green}{4}$	$\textcolor{green}{5}$

Uvedená gramatika je $LL(1)$ gramatikou, pretože v rozkladovej tabuľke nie sú konflikty.

f) Označme nové pravidlo $A \rightarrow \varepsilon$ poradovým číslom $(6)$. Množiny $\mathit{FIRST}$ a $\mathit{FOLLOW}$ sa zmenia nasledovne:

${}$	${}$	${}$
$\mathit{FIRST}($S$) = \{$ x, y, z $\}$	${}$	$ \mathit{FOLLOW}($S$) = \{$$$\}$
$\mathit{FIRST}($A$) = \{$ x, y, z, $\varepsilon \}$	${}$	$ \mathit{FOLLOW}($A$) = \{$ y, z $\}$
$\mathit{FIRST}($B$) = \{$ y, z $\}$	${}$	$ \mathit{FOLLOW}($B$) = \{$ y, z, $$\}$

Pozn. Žiadna z množín $\mathit{FOLLOW}$ sa nezmenila.

Množiny $\mathit{PREDICT}$

${}$
$\mathit{PREDICT}(1) = \{$ x, y, z $\}$
$\mathit{PREDICT}(2) = \{$ x $\}$
$\mathit{PREDICT}(3) = \{$ y, z $\}$
$\mathit{PREDICT}(4) = \{$ y $\}$
$\mathit{PREDICT}(5) = \{$ z $\}$
$\mathit{PREDICT}(6) = \{$ y, z $\}$

Pozn. Množina $\mathit{PREDICT}(6)$ je rovnaká ako $\mathit{FOLLOW}(A)$.

Ak by sme zostavili rozkladovú tabuľku pre túto novú gramatiku, dostaneme:

$RT$	x	y	z	$
S	$\textcolor{green}{1}$	$\textcolor{green}{1}$	$\textcolor{green}{1}$
A	$\textcolor{green}{2}$	$\textcolor{red}{3,6}$	$\textcolor{red}{3,6}$
B		$\textcolor{green}{4}$	$\textcolor{green}{5}$

Gramatika teda nie je $LL(1)$ gramatikou.

Krok 3

Teoretický model nerekurzívneho sytaktického analyzátora jazyka generovaného $LL(1)$ gramatikou je zásobníkový automat, ktorý namiesto rekuzívneho volania procedúr (pozri cvičenie 6.) používa zásobník pre ukladanie terminálnych a neterminálnych symbolov, resp. jednotlivých vetných foriem odvodenia. Začiatočný symbol pritom predstavuje počiatočný zásobníkový symbol nachádzajúci sa na dne jeho zásobníka.

Keďže väčšina bezkontextových gramatík obsahuje viacero pravidiel pre jeden neterminálny symbol, efektívne spracovanie vstupu vyžaduje, aby syntaktický analyzátor jednoznačne vybral správny variant pravidla a zabránil tak nedeterministickému vetveniu výpočtu. Z tohto dôvodu sa syntaktický analyzátor na báze zásobníkového automatu často implementuje so schopnosťou nahliadať na niekoľko nasledujúcich symbolov vstupného reťazca, tzv. "look-ahead" symbolov, bez posunu čítacej hlavy. Je pritom zrejmé, že pre gramatiky typu $\mathit{LL(1)}$ postačuje jeden takýto symbol. Tieto symboly následne umožňujú predikciu vhodného pravidla pomocou $RT$, pričom výsledkom činnosti analyzátora je odvodenie, konkrétne postupnosť pravidiel použitých pri najľavejšom odvodení vstupného reťazca. Z tohto dôvodu sa tento prístup označuje ako prediktívna syntaktická analýza. Schéma nerekurzívneho prediktívneho syntaktického analyzátora je znázornená na nasledujúcom obrázku

Samotný princíp nerekuzívnej prediktívnej syntaktickej analýzy definujeme prostredníctvom nasledujúceho algoritmu.

Algoritmus 4. Algoritmus nerekurzívnej prediktívnej syntaktickej analýzy.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$, k nej zostrojená rozkladová tabuľka syntaktického analyzátora $LL(1)$, vstupný reťazec (slovo) $w$.
Výstup: Ak $w\in L(G)$ výstupom je najľavejšie odvodenie reťazca $w$, v opačnom prípade je výstupom informácia o chybe.

1. $\mathit{PUSH}(S)$;
2. $t\leftarrow$ prvý symbol $w$;
3. while zásobnik nie je prázdny do
4.   $X\leftarrow \mathit{POP}()$;
5.   if $X\in N$ then
6.    if $RT[X,t]=X\to\alpha$ then
7.     $\mathit{PUSH}(\alpha^R)$;
8.     write $X\to\alpha$;
9.    else
10.    write $\mathit{SYNTAX\ ERROR}$;
11.     halt;
12.    end if
13.   else
14.    if $X\in T\;\land\;X=t$ then
15.     $t\leftarrow$ nasledujúci symbol $w$;
16.    else
17.     write $\mathit{SYNTAX\ ERROR}$;
18.     halt;
19.    end if
20.   end if
21. end while

Algoritmus 4 rozlišuje iba úspešné spracovanie vstupného reťazca a výskyt syntaktickej chyby. Pre praktické použitie syntaktického analyzátora je však žiaduce poskytovať detailnejšiu informáciu o povahe chyby, najmä o očakávaných a skutočne získaných symboloch zo vstupu.

Riešenie

Keďže všetky výpočty výsledného ZA sú realizované výlučne na báze zásobníka tento automat obsahuje len len jeden jediný stav s počtom prechodov 13.

Krok 4

V tomto kroku pristúpime ku konštrukcii nerekurzívneho syntaktického analyzátora jazyka aritmetických výrazov, ktorý je definovaný transformovanou $LL(1)$ gramatikou $G^T$, prezentovanou v predchádzajúcom kroku. Samotný analyzátor bude realizovaný na báze zásobníkového automatu, ktorého zásobník bude v priebehu analýzy slúžiť na uchovávanie terminálnych a neterminálnych symbolov gramatiky. Z tohto dôvodu je nevyhnutné, aby boli tieto symboly reprezentované jednoznačným a programovo spracovateľným spôsobom. Keďže terminálne symboly možno reprezentovať prostredníctvom enumeračného typu TokenType, pre zabezpečenie analogickej reprezentácie neterminálnych symbolov zavedieme vlastný enumeračný typ Nonterminal.

# Definícia enumeračného typu neterminálov 
class Nonterminal(Enum):
    E = auto()
    E_PRIME = auto()
    T = auto()
    T_PRIME = auto()
    F = auto()

Inicializácia syntaktického analyzátora: Do internej premennej syntaktického analyzátora sa uloží referencia na zvolený lexikálny analyzátor.

class Parser:
    def __init__(self, scanner):
        self.scanner = scanner          # Lexikálny analyzátor na získavanie tokenov
        self.current_token = None       # Aktuálne rozpoznaný token zo vstupu
        self.stack = None               # Zásobník

Súčasťou inicializácie je taktiež definícia gramatiky a rozkladovej tabuľky syntaktického analyzátora. Obe sú uložené v dátovej štruktúre typu slovník, ktorá predstavuje kolekciu dvojíc kľúč–hodnota. V prípade gramatiky je kľúčom číselný identifikátor pravidla a hodnotou jeho ďalej štrukturovaná reprezentácia. Rozkladová tabuľka využíva ako kľúč kombináciu neterminálneho a vstupného symbolu a ako hodnotu číslo pravidla, ktoré je treba aplikovať. Takto navrhnutá reprezentácia umožňuje efektívne a jednoznačné vyhľadávanie pravidiel počas analýzy vstupného reťazca.

    self.rules = {
        1: {"left_side": Nonterminal.E, "right_side": [Nonterminal.T,Nonterminal.E_PRIME]}, # E -> T E'
        2: {"left_side": Nonterminal.E_PRIME, "right_side": [TokenType.PLUS,Nonterminal.T,Nonterminal.E_PRIME]}, # E' -> + T E'
        3: {"left_side": Nonterminal.E_PRIME, "right_side": []}, # E' -> ε
        4: {"left_side": Nonterminal.T, "right_side": [Nonterminal.F,Nonterminal.T_PRIME]}, # T -> F T'
        5: {"left_side": Nonterminal.T_PRIME, "right_side": [TokenType.MULTIPLY,Nonterminal.F,Nonterminal.T_PRIME]}, # T' -> * F T'
        6: {"left_side": Nonterminal.T_PRIME, "right_side": []}, # T' -> ε
        7: {"left_side": Nonterminal.F, "right_side": [TokenType.NUM_CONST]}, # F -> cislo
        8: {"left_side": Nonterminal.F, "right_side": [TokenType.LPAREN,Nonterminal.E,TokenType.RPAREN]}, # F -> ( E )
        }

    self.parsing_table = {}

    # Riadky rozkladovej tabuľky
    # Riadok E
    self.parsing_table[(Nonterminal.E, TokenType.LPAREN)] = 1
    self.parsing_table[(Nonterminal.E, TokenType.NUM_CONST)] = 1
    # Riadok E'
    self.parsing_table[(Nonterminal.E_PRIME, TokenType.PLUS)] = 2
    self.parsing_table[(Nonterminal.E_PRIME, TokenType.RPAREN)] = 3
    self.parsing_table[(Nonterminal.E_PRIME, TokenType.EOF)] = 3 
    # Riadok T
    self.parsing_table[(Nonterminal.T, TokenType.LPAREN)] = 4
    self.parsing_table[(Nonterminal.T, TokenType.NUM_CONST)] = 4
    # Riadok T'
    self.parsing_table[(Nonterminal.T_PRIME, TokenType.MULTIPLY)] = 5
    self.parsing_table[(Nonterminal.T_PRIME, TokenType.PLUS)] = 6    
    self.parsing_table[(Nonterminal.T_PRIME, TokenType.RPAREN)] = 6  
    self.parsing_table[(Nonterminal.T_PRIME, TokenType.EOF)] = 6     
    # Riadok F
    self.parsing_table[(Nonterminal.F, TokenType.NUM_CONST)] = 7
    self.parsing_table[(Nonterminal.F, TokenType.LPAREN)] = 8

Metóda parse: Na začiatku analýzy sa inicializuje zásobník, na vrchol zásobníka sa vloží počiatočný neterminálny symbol E a načíta sa prvý token zo vstupného reťazca.

def parse(self):
    self.stack=[TokenType.EOF]
    self.stack.append(Nonterminal.E)
    self.current_token = self.scanner.get_next_token()

Hlavný cyklus analýzy: Postupne spracováva symboly z vrchola zásobníka. Ak je na vrchole neterminálny symbol, použije rozkladovú tabuľku na vyhľadanie príslušného pravidla, ktorým neterminál expanduje (vloží do zásobníka symboly pravej strany tohto pravidla v opačnom poradí). Ak je na vrchole terminál, porovná sa s aktuálnym tokenom zo vstupu; ak sa zhodujú, parser načíta ďalší token. V prípade nezrovnalosti ohlási syntaktickú chybu. Proces pokračuje, kým nie je obsah zásobníka úplne spracovaný.

    while self.stack:
        # Vrchol zásobníka
        X = self.stack.pop()

        # Ak je X neterminálny symbol
        if isinstance(X, Nonterminal):
            # Ak existuje pravidlo v rozkladovej tabuľke pre kombináciu (neterminál, token)
            if (X, self.current_token.type) in self.parsing_table:
                # Získame číslo pravidla a pravú stranu pravidla
                rule_number = self.parsing_table[(X, self.current_token.type)]
                right_side = self.rules[rule_number]["right_side"]
    
                # Postupné vloženie symbolov pravej strany pravidla do zásobníka v opačnom poradí
                for symbol in reversed(right_side):
                    self.stack.append(symbol)

                print(f"({rule_number})",end='=>' if len(self.stack)>1 else '\n')
            else:
                # Syntaktická chyba vo vstupnom reťazci
                raise SyntaxError("Syntaktická chyba")
        
        # Ak je X terminál alebo koncový znak a zhoduje sa s aktuálnym tokenom zo vstupu
        elif isinstance(X,TokenType) and X==self.current_token.type:
            # Posun na ďalší token
            self.current_token = self.scanner.get_next_token()
        else:
            # Syntaktická chyba vo vstupnom reťazci
            raise SyntaxError("Syntaktická chyba")

Doplňujúce materialy

Pomocný nastroj pre náplň tohto cvičenia nájdete na tejto stránke prístupnej len z TUKE siete.