Bezkontextové gramatiky, zásobníkové automaty, LL(1) parsovanie

Prekontrolujte a prediskutujte riešenia úloh z cvičenia 7.

Navrhnite zásobníkový automat pre jazyk $L(M) = \left\{ a^{n}b^{2n}~|~n \geq 1\right\}$, $n \in \mathbb{N}$.

Daná je nasledujúca gramatika:

$$\begin{array}{ll} (1) & S \rightarrow A\# \\ (2) & A \rightarrow xAx \\ (3) & A \rightarrow C \\ (4) & B \rightarrow yBy \\ (5) & B \rightarrow C \\ (6) & C \rightarrow zBz \\ (7) & C \rightarrow wAw \\ (8) & C \rightarrow \varepsilon \\ \end{array}$$

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

Daná je nasledujúca gramatika:

$$\begin{array}{ll} (1) & S \rightarrow AB\# \\ (2) & A \rightarrow xA \\ (3) & A \rightarrow B \\ (4) & B \rightarrow yzB \\ (5) & B \rightarrow z \\ \end{array}$$

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 \rightarrow \varepsilon$, zmení sa jej klasifikácia? Svoju odpoveď odôvodnite.