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.

• Začiatočná konfigurácia automatu $M$ je konfigurácia $ (q_0, w, Z_0) $, kde $w$ je celý vstupný reťazec.
• Koncová (alebo akceptujúca) konfigurácia automatu $M$ je konfigurácia $ (q, \varepsilon, s) $ kde $ q \in F $ a $s \in \Gamma^*$.

Na množine konfigurácií $Q \times T^* \times \Gamma^* $ definujeme binárnu reláciu prechodu (alebo krok výpočtu) ZA $\vdash\;\subseteq (Q \times T^* \times \Gamma^*)^2$ 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 čítaní 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ď zo vstupu čítame symbol $a$ na vrchol zásobníka sa pridá nejaký (konkrétny) symbol zásobníkovej abecedy.
2. Po prečítaní prvého symbolu $b$ zo vstupu automat zmení svoj stav a vykoná operáciu $\mathit{POP}$ nad zásobníkom.
3. Po prečítaní každého ďalšieho symbolu $b$ zo vstupu automat vykoná operáciu $\mathit{POP}$ nad zásobníkom.
4. Ak po prečítaní celého reťazca zo vstupu v zásobníku ostane len počiatočný zásobníkový symbol, automat zmeni svoj stav na akceptujúci.

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 slova odvodeného z vetnej formy $\alpha$. Ak z danej vetnej formy $\alpha$ možno odvodiť prazdne slovo, $\varepsilon$ taktiež patrí do tejto množiny.

Algoritmus 1. 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)$.

$\mathit{FIRST}(\alpha):$

1. ak $\alpha=\varepsilon$ potom vráť $\{\varepsilon\}$;
2. ak $\alpha=a\beta$, kde $a\in T\;\land\;\beta\in(N\cup T)^{*}$ potom vráť $\{a\}$;
3. ak $\alpha=A\beta$, kde $A\in N\;\land\;\beta\in(N\cup T)^{*}$ potom
4.   $\mathit{FST}_A \leftarrow \emptyset$;
5.   pre všetky $A\to\gamma \in P$ vykonaj
6.    ak $A$ nie je prefixom $\gamma$ potom
7.     $\mathit{FST}_A \leftarrow \mathit{FST}_A \cup \mathit{FIRST}(\gamma)$;
8.    koniec ak
9.   koniec pre
10.   ak $\varepsilon\in \mathit{FST}_A$ potom
11.    $\mathit{FST}_A\leftarrow (\mathit{FST}_A-\{\varepsilon\})\cup\mathit{FIRST}(\beta)$;
12.   koniec ak
13.   vráť $\mathit{FST}_A$;
14. koniec ak

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

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:

Rozkladová tabuľka $RT$ je spravidla parciálne (neúplné) 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. Zásobníkový symbol nachádzajajúci sa na dne jeho zásobníka je $.

Schéma nerekurzívneho syntaktického analyzátora je uvedená na Obrázku 4. Tento syntaktický analyzátor

• číta symboly vstupného reťazca,
• má prístup k vrcholu zásobníka,
• realizuje prediktívnu syntaktickú analýzu na základe obsahu rozkladovej tabuľky $RT$ a
• na výstupe produkuje odvodenie (pre jednoduchosť možno uvažovať o pravidlách použitých pri najľavejšom odvodení).

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

Algoritmus 3. 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. pokiaľ zásobnik nie je prázdny vykonaj
4.   $X\leftarrow \mathit{POP}()$;
5.   ak $X\in N$ potom
6.    ak $RT[X,t]=X\to\alpha$ potom
7.     $\mathit{PUSH}(\alpha^R)$;
8.     výstup $X\to\alpha$;
9.    v opačnom prípade
10.    výstup $\mathit{SYNTAX\ ERROR}$;
11.    koniec ak
12.   v opačnom prípade
13.    ak $X\in T\;\land\;X=t$ potom
14.     $t\leftarrow$ nasledujúci symbol $w$;
15.    v opačnom prípade
16.     výstup $\mathit{SYNTAX\ ERROR}$;
17.    koniec ak
18.   koniec ak
19. koniec pokiaľ

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.