Ciele
- Definovať zásobníkový automat (ZA) ako ekvivalentný spôsob určenia bezkontextového jazyka.
- Uviesť základné pojmy analýzy bezkontextových gramatík. Množiny $\mathit{FIRST},$ $\mathit{FOLLOW}$ , $\mathit{PREDICT}$ a definovať $LL(1)$ gramatiku.
- Predstaviť ľavú faktorizáciu (determinizáciu gramatiky) a princíp nerekurzívnej syntaktickej analýzy zhora nadol postavenej na zásobníkovom automate.
- Implementovať jednoduchý nerekurzívny syntaktický analyzátor zhora nadol.
Úvod
Postup
Krok 1
Zásobníkové automaty 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 zásobníkovým automatom a naopak, každý jazyk akceptovaný nejakým zásobníkovým automatom je zároveň generovateľný nejakou bezkontextovou gramatikou.
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$.
Poznámka
Na základe definície ZA je zrejmé, že ZA možno chápať ako rozšírenie NKA o ďalší pamäťový prvok, ktorým je zásobník.
Poznámka
Nad zásobníkom možno vykonávať dve základné operácie, a to:
- $\mathit{POP}()$, ktorá odstráni jeden symbol z vrchola zásobníka a zároveň ho poskytne ako návratovú hodnotu,
- $\mathit{PUSH}(s)$, ktorá postupne pridá na vrchol zásobníka symboly slova $s\in \Gamma^*$ (zľava doprava).
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 momentá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 $a \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$ následovne: Nech $q, p \in Q, w \in T^*, x \in T_\varepsilon, Z \in \Gamma, s,t \in \Gamma^*$. Potom
$(q, xw, Zs) \vdash (p, w, ts)$ vtedy a len vtedy, ak $(p,t) \in \delta(q, x, Z).$
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) \to (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). $$
Poznámka
Číslo $k$ predstavuje počet krokov výpočtu.
-
tranzitívnym uzáverom relácie krok výpočtu nazývame reláciu $ \vdash^+ $ definovanú na množine jeho konfigurácii následovne:
$ (q,w_1,s_1) \vdash^+ (p,w_2,s_2) $ práve vtedy, keď existuje $ n \geq 1$ také, že $(q,w_1,s_1) \vdash^n (p,w_2,s_2) $. -
reflexívnym a tranzitívnym uzáverom relácie krok výpočtu nazývame reláciu $ \vdash^* $ definovanú na množine jeho konfigurácii následovne:
$ (q,w_1,s_1) \vdash^* (p,w_2,s_2) $ práve vtedy, keď existuje $ n \geq 0$ také, že $(q,w_1,s_1) \vdash^n (p,w_2,s_2) $.
Pri zásobníkových automatoch existujú dva spôsoby akceptácie reťazcov. V oboch prípadoch je samozrejmé nutnou podmienkou prečítanie celého vstupu. Slovo je
- akceptované akceptačným stavom – automat prečíta celý vstup a skončí v akceptačnom stave. Obsah zásobníka nie je podstatný.
- akceptované prázdnym zásobníkom – automat prečíta celý vstup a skončí s prázdnym zásobníkom. Stav, v ktorom skončí, nie je podstatný.
Oba spôsoby sú 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:
$L(M) = \{ w \mid (q_0, w, Z_0) \vdash^* (q, \varepsilon, s) \land w \in T^*,$ $s \in \Gamma^* \land (q \in F \lor s=\varepsilon) \}$
Príklad
Navrhnite zásobníkový automat $M$ akceptujúci jazyk $L = \{ a^{n}b^{n}~|~n \geq 1\}$, $n \in \mathbb{N}$. Na automate $M$ vykonajte výpočty nad slovami $aabb$, $aab$.
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 pamäťovým prvkom KSA je len jeho vnútorny stav túto informáciu nemáme ako zachytiť. V prípade ZA však máme k dispozícii ďalšiu pamäťovú jednotku – zásobník, nad ktorým možeme vykonávať základné operácie push a pop. Uveďme teda princíp zostrojenia ZA akceptujúceho jazyk $L$.
- Vždy keď zo vstupu čítame symbol
ana vrchol zásobníka sa pridá nejaký (konkrétny) symbol zásobníkovej abecedy. - Po prečítaní prvého symbolu
bzo vstupu automat zmení svoj stav a vykoná operáciu pop nad zásobníkom. - Po prečítaní každého ďalšieho symbolu
bzo vstupu automat vykoná operáciu pop nad zásobníkom. - 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.
$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.
Poznámka
Označenie prechodu $a,b/s$ znamená, že zo vstupu čítame symbol $a\in T$ na vrchole zásobníka sa musí nachádzať symbol $b\in \Gamma$, ktorý pop-neme a následne do zásobníka push-neme postupnosť symbolov zásobníka $s\in\Gamma^*$
Poznámka
Kvôli jednoznačnosti budeme pre zásobník využívať nasledujúcu notáciu, napríklad $\phantom{a}aZ_0$ reprezentuje zásobník, na vrchole ktorého je zásobníkový symbol $a$ a na dne symbol $Z_0$.
Príklad
Transformujte ZA $M$ z predchádajúcého príkladu na ZA $M'$, ktorý bude akceptovať slová prázdnym zásobníkom. Vykonajte na ňom výpočty nad slovami $aabb$, $aab$.
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.
Úloha 1.1
Navrhnite zásobníkový automat $M$ akceptujúci jazyk $L = \{ a^{n}b^{2n}~|~n \in \mathbb{N} \;\land\;n \geq 1\}$.
Úloha 1.2
Navrhnite zásobníkový automat $M$ akceptujúci jazyk $L = \{ ww^{R}~|~w \in \{0,1\}^{*}\}$.
Ďalšie riešené príklady konštrukcie ZA nájdete v štvrtej kapitole tejto zbierky úloh.
Krok 2
$\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.
$\mathit{FIRST}(\alpha)=\{a \mid \alpha \Rightarrow^{*} a\beta \;\land$ $a\in T \;\land\; \beta\in (N\cup T)^{*}\}\cup\{\varepsilon\ \mathit{ak}\ \alpha \Rightarrow^{*} \varepsilon\}$
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):$
- ak $\alpha=\varepsilon$ potom vráť $\{\varepsilon\}$;
- ak $\alpha=a\beta$, kde $a\in T\;\land\;\beta\in(N\cup T)^{*}$ potom vráť $\{a\}$;
- ak $\alpha=A\beta$, kde $A\in N\;\land\;\beta\in(N\cup T)^{*}$ potom
- $\mathit{FST}_A \leftarrow \emptyset$;
- pre všetky $A\to\gamma \in P$ vykonaj
- ak $A$ nie je prefixom $\gamma$ potom
- $\mathit{FST}_A \leftarrow \mathit{FST}_A \cup \mathit{FIRST}(\gamma)$;
- koniec ak
- koniec pre
- ak $\varepsilon\in \mathit{FST}_A$ potom
- $\mathit{FST}_A\leftarrow (\mathit{FST}_A-\{\varepsilon\})\cup\mathit{FIRST}(\beta)$;
- koniec ak
- vráť $\mathit{FST}_A$;
- 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áť nakonci niektorej vetnej formy, symbol $ patrí taktiež do tejto množiny.
Poznámka
$ je špeciálny symbol signalizujúci koniec vstupu (implicitne sa nachádza na konci každého reťazca). Predstavuje niečo ako string terminator \0 v jazyku C.
$\mathit{FOLLOW}(A)=\{a \mid S \Rightarrow^{+} \beta_{1} Aa\beta_{2} \;\land\; a\in T\;\land$ $\beta_{1},\beta_{2}\in(N \cup T)^{*}\}\cup$
$\{$$$\ \mathit{ak}\ S \Rightarrow^{*} \beta A \;\land\; \beta\in(N \cup T)^{*}\}$
Algoritmus 2. konštrukcia množiny $\mathit{FOLLOW}(A)$ pre $A \in N$.
Vstup: Bezkontextová gramatika $G=(N,T,P,S)$ a neterminálny symbol $A\in N$.
Výstup: Množina $\mathit{FOLLOW}(A)$.
$\mathit{FOLLOW}(A):$
- $\mathit{FLW}_A\leftarrow \emptyset$;
- ak $A = S$ potom
- $\mathit{FLW}_A\leftarrow\{$$$\};$
- koniec ak
- pre všetky $B\to\alpha A\beta \in P$, kde $\alpha,\beta\in (N\cup T)^{*}$ vykonaj
- $\mathit{FLW}_A \leftarrow \mathit{FLW}_A \cup (\mathit{FIRST}(\beta)-\{\varepsilon\});$
- ak $\varepsilon \in \mathit{FIRST}(\beta)$ potom
- $\mathit{FLW}_A\leftarrow \mathit{FLW}_A \cup \mathit{FOLLOW(B);}$
- koniec ak
- koniec pre
- vráť $\mathit{FLW}_A$
Základnou požiadavkou na v praxi použiteľný syntaktický analyzátor je, aby bol schopný deterministicky spracovať vstupné reťazce s lineárnou časovou zložitosťou. Pri syntaktickej analýze zhora nadol to znamená, že v každom kroku (najľavejšieho) odvodenia je možné jednoznačne (deterministicky) určiť, ktoré pravidlo je treba aplikovať. Takéto sytaktické analyzátory potom označujeme pojmom prediktívne.
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:
$RT: N\times (T\cup\{$$$\})\rightharpoonup P$.
Ako je možné vidieť 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íp. terminátora $), 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 v tabuľka neobsahuje konflikty teda pre jeden neterminálny symbol $A$ a jeden terminálny symbol $t$ poskytuje nanajvýš jedno pravidlo na základe takejto gramatiky možno zostaviť deterministický (prediktívny) syntaktický analyzátor, ktorého princíp práce si predstavíme v nasledujúcom kroku a danú gramatiku označujeme ako $LL(1)$ gramatiku.
Príklad
Zistite, či gramatika $G$ je LL(1) gramatikou. $G = (\{$E,F,T$\}$,$\{$+,*,(,),cislo$\}$,$P$,E$)$, kde $P$ je množina nasledujúcich pravidiel:
| ${}$ |
|---|
E $\to$ E + T | T |
T $\to$ T * F | F |
F $\to$ cislo | ( E ) |
Riešenie
Aby sme odpovedali na vyššie uvedenú otázku potrebujeme zostrojiť rozkladovú tabuľku gramatiky $G$. To si v prvom kroku vyžaduje konštrukciu množín $\mathit{FIRST}(A)$ pre každý neterminál $A\in N$.
Konštrukcia množiny $\mathit{FIRST}($E$)$:
| Úroveň vnorenia | Vstupná vetná forma $\alpha$ | $\beta$ | $\mathit{FST}_A\phantom{halo}$ | Iterácia cyklu$\phantom{halohalohaloha}$ | $\gamma$ | Opis |
|---|---|---|---|---|---|---|
| 1. | E |
$\varepsilon$ | $\emptyset$ | 1. | E + T |
Vstupná vetná forma $\alpha$ sa začína neterminálom prvé 2 kroky preskočíme. Keďže E je prefixom E + T postúpime na ďalšiu alternatívu pravej strany pravidla pre neterminál E. |
| ${}$ | ${}$ | ${}$ | $\emptyset$ | 2. | T |
Keďže E nie je prefixom T vykonáme rekurzívne volanie $\mathit{FIRST}($T$)$. |
| 2. | T |
$\varepsilon$ | $\emptyset$ | 1. | T * F |
Vstupná vetná forma $\alpha$ sa začína neterminálom prvé 2 kroky preskočíme. Keďže T je prefixom T * F postúpime na ďalšiu alternatívu pravej strany pravidla pre neterminál T. |
| ${}$ | ${}$ | ${}$ | $\emptyset$ | 2. | F |
Keďže T nie je prefixom F vykonáme rekurzívne volanie $\mathit{FIRST}($F$)$. |
| 3. | F |
$\varepsilon$ | $\emptyset$ | 1. | cislo |
Vstupná vetná forma $\alpha$ sa začína neterminálom prvé 2 kroky teda preskočíme. Keďže F nie je prefixom cislo vykonáme rekurzívne volanie $\mathit{FIRST}($cislo$)$. |
| 4. | cislo |
$\varepsilon$ | ${}$ | vráti $\{$cislo$\}$ |
${}$ | Keďže cislo je neterminál volanie vracia množinu $\{$cislo$\}$. |
| 3. | F |
$\varepsilon$ | $\{$cislo$\}$ |
2. | (E) |
Návrat z rekurzívneho volania. Keďže F nie je prefixom (E) vykonáme rekurzívne volanie $\mathit{FIRST}($(E)$)$. |
| 4. | (E) |
E) |
${}$ | vráti $\{$($\}$ |
${}$ | Keďže ( je neterminál volanie vracia množinu $\{$($\}$. |
| 3. | F |
$\varepsilon$ | $\{$cislo,($\}$ |
vráti $\{$cislo, ($\}$ |
${}$ | Návrat z rekurzívneho volania. |
| 2. | T |
$\varepsilon$ | $\{$cislo,($\}$ |
vráti $\{$cislo, ($\}$ |
${}$ | Návrat z rekurzívneho volania. |
| 1. | E |
$\varepsilon$ | $\{$cislo,($\}$ |
vráti $\{$cislo, ($\}$ |
${}$ | Návrat z rekurzívneho volania a poskytnutie výsledku. |
Na základe vyššie uvedeného výpočtu by malo byť zrejmé, že:
- $\mathit{FIRST}($
E$)=\{$cislo,($\}$, - $\mathit{FIRST}($
T$)=\{$cislo,($\}$ a - $\mathit{FIRST}($
F$)=\{$cislo,($\}$.
Následne pristúpime ku konštrukcii množín $\mathit{FOLLOW}(A)$ pre každý neterminál $A\in N$.
Konštrukcia množiny $\mathit{FOLLOW}($E$)$:
| Úroveň vnorenia | Vstupný neterminál $A$ | $\mathit{FLW}_A\phantom{a}$ | Iterácia cyklu | $B$ | $\beta\phantom{ha}$ | $\mathit{FIRST}(\beta)$ | Opis |
|---|---|---|---|---|---|---|---|
| 1. | E |
$\{$$,+$\}$ | 1. | E |
+ T |
$\{$+$\}$ |
${}$ |
| ${}$ | ${}$ | $\{$$,+,)$\}$ |
2. | F |
) |
$\{$)$\}$ |
${}$ |
Konštrukcia množiny $\mathit{FOLLOW}($T$)$:
| Úroveň vnorenia | Vstupný neterminál $A$ | $\mathit{FLW}_A\phantom{halo}$ | Iterácia cyklu | $B$ | $\beta\phantom{ha}$ | $\mathit{FIRST}(\beta)$ | Opis |
|---|---|---|---|---|---|---|---|
| 1. | T |
$\emptyset$ | 1. | E |
$\varepsilon$ | $\{\varepsilon\}$ | ${}$ |
| 2. | E |
vráti$\{$$,+,)$\}$ |
${}$ | ${}$ | ${}$ | ${}$ | Rekurzívne volanie $\mathit{FOLLOW}($E$)$ |
| 1. | T |
$\{$$,+,)$\}$ |
1. | E |
$\varepsilon$ | $\{\varepsilon\}$ | Návrat z rekurzívneho volania. |
| ${}$ | ${}$ | $\{$$,+,)$\}$ |
2. | E |
$\varepsilon$ | $\{\varepsilon\}$ | ${}$ |
| 2. | E |
vráti$\{$$,+,)$\}$ |
${}$ | ${}$ | ${}$ | ${}$ | Rekurzívne volanie $\mathit{FOLLOW}($E$)$ |
| 1. | T |
$\{$$,+,)$\}$ |
2. | E |
$\varepsilon$ | $\{\varepsilon\}$ | Návrat z rekurzívneho volania. |
| ${}$ | ${}$ | $\{$$,+,),*$\}$ |
3. | T |
* F |
$\{$*$\}$ |
${}$ |
Konštrukcia množiny $\mathit{FOLLOW}($F$)$:
| Úroveň vnorenia | Vstupný neterminál $A$ | $\mathit{FLW}_A\phantom{haloha}$ | Iterácia cyklu | $B$ | $\beta\phantom{ha}$ | $\mathit{FIRST}(\beta)$ | Opis |
|---|---|---|---|---|---|---|---|
| 1. | F |
$\emptyset$ | 1. | T |
$\varepsilon$ | $\{\varepsilon\}$ | ${}$ |
| 2. | T |
vráti $\{$$,+,),*$\}$ |
${}$ | ${}$ | ${}$ | ${}$ | Rekurzívne volanie $\mathit{FOLLOW}($T$)$ |
| 1. | F |
$\{$$,+,),*$\}$ |
1. | T |
$\varepsilon$ | $\{\varepsilon\}$ | Návrat z rekurzívneho volania. |
| ${}$ | ${}$ | $\{$$,+,),*$\}$ |
2. | T |
$\varepsilon$ | $\{\varepsilon\}$ | ${}$ |
| 2. | T |
vráti $\{$$,+,),*$\}$ |
${}$ | ${}$ | ${}$ | ${}$ | Rekurzívne volanie $\mathit{FOLLOW}($T$)$ |
| 1. | F |
$\{$$,+,),*$\}$ |
2. | T |
$\varepsilon$ | $\{\varepsilon\}$ | Návrat z rekurzívneho volania. |
Následne pristúpime ku konštrukcii množín $\mathit{PREDICT}(A\to\alpha)$ pre každé pravidlo $A\to\alpha\in P$.
- $\mathit{PREDICT}($
E$\to$E + T$)$
$=\mathit{FIRST}($
E + T$)=\{$cislo,($\}$, keďže $\mathit{FIRST}($E + T$)$ neobsahuje $\varepsilon$.
- $\mathit{PREDICT}($
E$\to$T$)$
$=\mathit{FIRST}($
T$)=\{$cislo,($\}$, keďže $\mathit{FIRST}($T$)$ neobsahuje $\varepsilon$.
- $\mathit{PREDICT}($
T$\to$T * F$)$
$=\mathit{FIRST}($
T * F$)=\{$cislo,($\}$, keďže $\mathit{FIRST}($T * F$)$ neobsahuje $\varepsilon$.
- $\mathit{PREDICT}($
T$\to$F$)$
$=\mathit{FIRST}($
F$)=\{$cislo,($\}$, keďže $\mathit{FIRST}($F$)$ neobsahuje $\varepsilon$.
- $\mathit{PREDICT}($
cislo$)$
$=\mathit{FIRST}($
cislo$)=\{$cislo$\}$, keďže $\mathit{FIRST}($cislo$)$ neobsahuje $\varepsilon$.
- $\mathit{PREDICT}($
( E )$)$
$=\mathit{FIRST}($
( E )$)=\{$($\}$, keďže $\mathit{FIRST}($( E )$)$ neobsahuje $\varepsilon$.
Na základe vyššie uvedeného teraz možno pristúpiť k zostrojeniu rozkladovej nasledujúcej tabuľky.
| $RT$ | + |
* |
( |
) |
cislo |
$ |
|---|---|---|---|---|---|---|
E |
${}$ | ${}$ | $\textcolor{red}{1,2}$ | ${}$ | $\textcolor{red}{1,2}$ | |
T |
${}$ | ${}$ | $\textcolor{red}{3,4}$ | ${}$ | $\textcolor{red}{3,4}$ | |
F |
${}$ | ${}$ | $\textcolor{green}{6}$ | ${}$ | $\textcolor{green}{5}$ |
Keďže rozkladová tabuľa obsahuje konflikty (zvýraznené červenou farbou) daná gramatika nie je $LL(1)$ gramatikou.
Ako si je možné všimúť, 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álmi preto nikdy nebude $LL(1)$ gramatikou.
Úloha 2.1
Daná je nasledujúca gramatika:
| ${}$ |
|---|
$(1)$ S $\to$ A |
$(2)$ A $\to$ xAx |
$(3)$ A $\to$ C |
$(4)$ B $\to$ yBy |
$(5)$ B $\to$ C |
$(6)$ C $\to$ zBz |
$(7)$ C $\to$ wAw |
$(8)$ C $\to$ $\varepsilon$ |
a) Určte množiny $N$, $T$.
b) Skonštruujte deriváciu reťazca xzzx začínajúc v S. Vyznačte, ktoré odvodzovacie pravidlá ste použili a nakreslite odvodzovací strom podľa Vašej derivácie.
c) Nájdite množiny $\mathit{FIRST}$ a $\mathit{FOLLOW}$ pre každý neterminálny symbol gramatiky.
d) Pre každé pravidlo gramatiky skonštruujte množinu $\mathit{PREDICT}$.
e) Zostavte rozkladovú tabuľku pre danú gramatiku. Zistite, či daná gramatika je $LL(1)$ gramatikou. Svoju odpoveď odôvodnite.
f) Ukážte kroky, ktoré by váš analyzátor realizoval na analýzu vstupu xzyyzx.
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.
Úloha 2.2
Daná je nasledujúca gramatika:
| ${}$ |
|---|
$(1)$ S $\to$ AB |
$(2)$ A $\to$ xA |
$(3)$ A $\to$ B |
$(4)$ B $\to$ yzB |
$(5)$ B $\to$ z |
a) Určte množiny $N$, $T$.
b) Skonštruujte strom odvodenia pre vstupný reťazec xyzzz
c) Nájdite množiny $\mathit{FIRST}$ a $\mathit{FOLLOW}$ pre každý neterminálny symbol gramatiky.
d) Pre každé pravidlo gramatiky skonštruujte množinu $\mathit{PREDICT}$.
e) Zostavte rozkladovú tabuľku pre danú gramatiku. Zistite, či daná gramatika je $LL(1)$ gramatikou. Svoju odpoveď odôvodnite.
f) Ak do danej gramatiky pridáme pravidlo A $\to$ $\varepsilon$, zmení sa jej klasifikácia? Svoju odpoveď odôvodnite.
Riešenie
a) $T = \{$ x, y, z, $\}$, $N=\{$ S, A, B $\}$.
b)
xyzzz
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
V predchádzajúcom príklade sme identifikovali jeden zo zdrojov nedeterminizmu v gramatike, a to ľavú rekuziu, princíp odstránenia ktorej sme si ukázali na predchádzajúcom cvičení. Ďalším zdrojom nedeterminizmu je existencia viacerých pravidiel pre neterminálny symbol $A$, ktorých pravé strany začínajú rovnakou vetnou formou $\alpha$. Riešením tohto problému je vyčlenenie spoločných symbolov zľava tzv. ľavá faktorizácia, ktorá predstavuje nasledujúci princíp. 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$
Príklad
Transformujte gramatiku jazyka aritmetických výrazov z 2. príkladu na $LL(1)$ gramatiku. Využite pritom poznatky z predchádzajúceho cvičenia (odstránenie ľavej rekurzie) a vyššie uvedený princíp ľavej faktorizácie.
Riešenie
V prvom, kroku musíme pristúpiť, k odstráneniu ľavej rekurzie z prepisovacích pravidiel gramatiky a to nasledovne. Pravidlá
| ${}$ | ${}$ | ${}$ |
|---|---|---|
E $\to$ E + T | T |
$\phantom{halohalohalo}$ | T $\to$ T * F | F |
nahradíme dvojicami pravidiel:
| ${}$ | ${}$ | ${}$ |
|---|---|---|
E $\to$ T E'$\;\;$| T |
$\phantom{halohalohalo}$ | T $\to$ F T'$\;\;$| F |
E' $\to$ + T E'$\;\;$| + T |
${}$ | T' $\to$ * F T'$\;\;$| * F |
na základe čoho získame gramatiku $G'=(\{$E,E',T,T',F$\}$,$\{$+,*,(,)$\}$,$P'$,E$)$, kde $P'$ je množina nasledujúcich pravidiel:
| ${}$ |
|---|
E $\to$ T E'$\;\;$| T |
E' $\to$ + T E'$\;\;$| + T |
T $\to$ F T'$\;\;$| F |
T' $\to$ * F T'$\;\;$| * F |
F $\to$ cislo | ( E ) |
Táto gramatika je však jednoznačne nedeterministická. Tento nedeterminizmus možno odstrániť metódou ľavej faktorizácie (vyčlenením spoločných symbolov z ľava), čím vznikne gramatika $G''=(\{$E,E',E'',T,T',T'',F$\}$,$\{$+,*,(,)$\}$,$P''$,E$)$, kde možina pravidiel $P''$ pozostáva z nasledujúcich pravidiel:
| ${}$ |
|---|
E $\to$ T E'' |
E'' $\to$ E'$\;\;$|$\;\;\varepsilon$ |
E' $\to$ + T E'' |
T $\to$ F T'' |
T'' $\to$ T'$\;\;$|$\;\;\varepsilon$ |
T' $\to$ * F T'' |
F $\to$ cislo | ( E ) |
Túto gramatiku ešte možno zjednodušiť, nasledovne. Keďže pre neterminál E' existuje len jediné prepisovacie pravidlo, všetky výskyty tohto neterminálu na pravej strane pravidiel možno nahradiť pravou stranou tohto pravidla teda vetnou formou + T E'' (obdobne postupujeme pri netreminálnom symbole T'). Výsledkom je gramatika $G^F=(\{$E,E'',T,T'',F$\}$,$\{$+,*,(,)$\}$,$P^F$,E$)$, kde $P^F$ je množina nasledujúcich pravidiel:
| ${}$ |
|---|
E $\to$ T E'' |
E'' $\to$ + T E''$\;\;$|$\;\;\varepsilon$ |
T $\to$ F T'' |
T'' $\to$ * F T''$\;\;$|$\;\;\varepsilon$ |
F $\to$ cislo | ( E ) |
Následne overme, či výsledná gramtika $G^F$ je $LL(1)$ gramatikou. Zostavme teda množiny $\mathit{FIRST}(A)$ a $\mathit{FOLLOW}(A)$, pre všetky neterminály $A \in N^F$ a množiny $\mathit{PREDICT}(A\to\alpha)$ pre všetky pravidlá $A\to\alpha \in P^F$.
| ${}$ | ${}$ | ${}$ |
|---|---|---|
$\mathit{FIRST}($E$)=\{$cislo,($\}$ |
${}$ | $\mathit{FOLLOW}($E$)=\{$$,)$\}$ |
$\mathit{FIRST}($E''$)=\{$+,$\varepsilon\}$ |
${}$ | $\mathit{FOLLOW}($E''$)=\{$$, )$\}$ |
$\mathit{FIRST}($T$)=\{$cislo,($\}$ |
${}$ | $\mathit{FOLLOW}($T$)=\{$$,),+$\}$ |
$\mathit{FIRST}($T''$)=\{$*,$\varepsilon\}$ |
${}$ | $\mathit{FOLLOW}($T''$)=\{$$,),+$\}$ |
$\mathit{FIRST}($F$)=\{$cislo,($\}$ |
${}$ | $\mathit{FOLLOW}($F$)=\{$$,),*,+$\}$ |
| ${}$ |
|---|
$\mathit{PREDICT}($E$\to$ T E''$)=\{$cislo,($\}$ |
$\mathit{PREDICT}($E''$\to$ + T E''$)=\{$+$\}$ |
$\mathit{PREDICT}($E''$\to \varepsilon)=\{$$,)$\}$ |
$\mathit{PREDICT}($T$\to$ F T''$)=\{$cislo,($\}$ |
$\mathit{PREDICT}($T''$\to$ * F T''$)=\{$*$\}$ |
$\mathit{PREDICT}($T''$\to \varepsilon)=\{$$,),+$\}$ |
$\mathit{PREDICT}($F$\to$ cislo$)=\{$cislo$\}$ |
$\mathit{PREDICT}($F$\to$ ( E )$)=\{$($\}$ |
Následne možno zostaviť rozkladovú tabuľku.
| $RT$ | + |
* |
( |
) |
cislo |
$ |
|---|---|---|---|---|---|---|
E |
${}$ | ${}$ | $\textcolor{green}{1}$ | ${}$ | $\textcolor{green}{1}$ | ${}$ |
E'' |
$\textcolor{green}{2}$ | ${}$ | ${}$ | $\textcolor{green}{3}$ | ${}$ | $\textcolor{green}{3}$ |
T |
${}$ | ${}$ | $\textcolor{green}{4}$ | ${}$ | $\textcolor{green}{4}$ | ${}$ |
T'' |
$\textcolor{green}{6}$ | $\textcolor{green}{5}$ | ${}$ | $\textcolor{green}{6}$ | ${}$ | $\textcolor{green}{6}$ |
F |
${}$ | ${}$ | $\textcolor{green}{8}$ | ${}$ | $\textcolor{green}{7}$ | ${}$ |
Transformovaná gramatika $G^F$ je $LL(1)$ gramatikou, to znamená, že na základe danej gramatiky možno zostaviť jednoduchý prediktívny nerekurzívny syntaktický analyzátor.
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, presnejšie, pre vetné formy 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. 4, z ktorého vidno, že 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 v 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 oznam o chybe.
- $\mathit{PUSH}(S)$;
- $t\leftarrow$ prvý symbol $w$;
- pokiaľ zásobnik nie je prázdny vykonaj
- $X\leftarrow \mathit{POP}()$;
- ak $X\in N\;\land\;RT[X,t]=X\to\alpha$ potom
- $\mathit{PUSH}(\alpha^R)$;
- výstup $X\to\alpha$;
- v opačnom prípade
- ak $X\in T\cup\{$$$\}\;\land\;X=t$ potom
- $t\leftarrow$ nasledujúci symbol $w$;
- v opačnom prípade
- výstup $\mathit{ERROR}$;
- koniec ak
- koniec ak
- koniec pokiaľ
Príklad
Vykonajte nerekurzívnu syntaktickú analýzu jazykového výrazu 3 * ( 2 + 1 ) na báze gramatiky $G^F$ konštruovanej v predchádzajúcom príklade.
Riešenie
| Iterácia | Vstup | Zásobník $\phantom{aaaaa}$ | Výstup |
|---|---|---|---|
| 1. | 3 * ( 2 + 1 ) |
E $ |
$(1)$ |
| 2. | 3 * ( 2 + 1 ) |
T E'' $ |
$(4)$ |
| 3. | 3 * ( 2 + 1 ) |
F T'' E'' $ |
$(7)$ |
| 4. | 3 * ( 2 + 1 ) |
3 T'' E'' $ |
|
| 5. | * ( 2 + 1 ) |
T'' E'' $ |
$(5)$ |
| 6. | * ( 2 + 1 ) |
* F T'' E'' $ |
|
| 7. | ( 2 + 1 ) |
F T'' E'' $ |
$(8)$ |
| 8. | ( 2 + 1 ) |
( E ) T'' E'' $ |
|
| 9. | 2 + 1 ) |
E ) T'' E'' $ |
$(1)$ |
| 10. | 2 + 1 ) |
T E'' ) T'' E'' $ |
$(4)$ |
| 11. | 2 + 1 ) |
F T'' E'' ) T'' E'' $ |
$(7)$ |
| 12. | 2 + 1 ) |
2 T'' E'' ) T'' E'' $ |
|
| 13. | + 1 ) |
T'' E'' ) T'' E'' $ |
$(6)$ |
| 14. | + 1 ) |
E'' ) T'' E'' $ |
$(2)$ |
| 15. | + 1 ) |
+ T E'' ) T'' E'' $ |
|
| 16. | 1 ) |
T E'' ) T'' E'' $ |
$(4)$ |
| 17. | 1 ) |
F T'' E'' ) T'' E'' $ |
$(7)$ |
| 18. | 1 ) |
1 T'' E'' ) T'' E'' $ |
|
| 19. | ) |
T'' E'' ) T'' E'' $ |
$(6)$ |
| 20. | ) |
E'' ) T'' E'' $ |
$(3)$ |
| 21. | ) |
) T'' E'' $ |
|
| 22. | $ |
T'' E'' $ |
$(6)$ |
| 23. | $ |
E'' $ |
$(3)$ |
| 24. | $ |
$ |
Úloha 3.1
Zakreslite diagram ZA z predchádzajúceho príkladu. Z koľkých stavov a koľkých prechodov bude pozostávať?
Krok 4
Úloha 4.1
Na báze vyššie uvedeného algoritmu implementujte nerekurzívny prediktívny syntaktický analyzátor výslednej transformovanej gramatiky $G^F$. Ako lexikálny analyzátor môžete znova použiť triedu Lexer zo 6. cvičenia.
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