====== Zadání ======

Jazyky: Deterministické bezkontextové jazyky (DCFL). LL(k) a LR(k) gramatiky a jazyky, jejich vlastnosti. Vztahy mezi DCFL, LL a LR.

====== Vypracování ======

===== Deterministické bezkontextové jazyky =====

Deterministické bezkontextové jazyky (DCFL) jsou jazyky, ktoré jsou rozpoznávány deterministickými zásobníkovými automaty. DCFL mají striktně menší vyjadřovací sílu než nedeterministické CFL. DCFL je možné definovat pomocí deterministického zásobníkového automatu (DPDA) nebo deterministické bezkontextové gramatiky (DCFG).

Bezkontextová gramatika je frázová gramatika, která má pravidla tvaru <math>X \rightarrow w</math>, kde <math>X</math> je libovolný neterminál a <math>w</math> je libovolná větná forma.

Pro DCFL neexistuje pumping lemma nebo jiná speciální pomůcka. Je nutno se spolehnout na uzávěrové vlastnosti:
  * uzavřenost na průnik s regulárním jazykem
  * DCFL nejsou uzavřeny na průnik
  * DCFL jsou uzavřeny na doplněk
  * DCFL nejsou uzavřeny na sjednocení

===== LL(k) =====

<box round|Definice>
Nechť <math>G = (N, \Sigma, P, S)</math> je CFG, <math>k \geq 1, k \in \mathbb{Z}</math>. Definujeme nasledovné funkce:

<math>FIRST_k^G: (N \cup \Sigma)^+ \rightarrow \mathcal{P}(\{w \in \Sigma^* |\ |w| \leq k \})</math>\\
<math>FIRST_k^G(\alpha) = \{w \in \Sigma^* | (\alpha \Rightarrow^* w \land |w| \leq k) \lor (\alpha \Rightarrow^* wx \land |w| = k \land x \in \Sigma^*)\}</math>

<math>FOLLOW_k^G: N \rightarrow \mathcal{P}(\{w \in \Sigma^* |\ |w| \leq k\})</math>\\
<math>FOLLOW_k^G(A) = \{w \in \Sigma^* | S \Rightarrow^* \gamma A \alpha, w \in FIRST_k^G(\alpha)\}</math>

A dále pro <math>w = a_1 a_2 ... a_n</math>:\\
<math>k:w = a_1 ... a_k</math> pro <math>k < n</math>\\
<math>k:w = w</math> pro <math>k \geq n</math>
</box>

Nechť <math>G = (N, \Sigma, P, S)</math> je gramatika, <math>k > 1</math> celé číslo. <math>G</math> je <math>LL(k)</math> gramatika, právě když pro každé dvě nejlevější derivace (<math>w \in \Sigma^*</math>)

<math>S \Rightarrow^* wA\alpha \Rightarrow w\beta\alpha \Rightarrow^* wx</math>\\
<math>S \Rightarrow^* wA\alpha \Rightarrow w\gamma\alpha \Rightarrow^* wy</math>

podmínka <math>k:x = k:y</math> implikuje <math>\beta = \gamma</math>.

==== Vlastnosti ====

  * Každá <math>LL(k)</math> gramatika je jednoznačná
  * Je li <math>G</math> levorekurzivní, není <math>LL(k)</math> pro žádné <math>k</math>
  * <math>G</math> je <math>LL(k)</math> pokud platí: Jsou li <math>A \rightarrow \beta</math> a <math>A \rightarrow \gamma</math> dvě různá pravidla v <math>P</math>, pak pro všechny nejlevější větné formy <math>wA\alpha</math> platí: <math>FIRST_k(\beta\alpha) \cap FIRST_k(\gamma\alpha) = \emptyset</math>

===== LR(k) =====

Pro <math>LR(k)</math> gramatiku <math>G</math> definujeme přidruženou gramatiku <math>G' = (N \cup \{S'\}, \Sigma, P' = P \cup \{S' \rightarrow S\bot\}, S')</math>. Přidružená gramatika umožňuje rozeznat konec vstupu.

Gramatika <math>G = (N, \Sigma, P, S)</math> je <math>LR(k)</math> pro <math>k \geq 0</math>, pokud pro všechny pravé větné formy z podmínek:
  * <math>S \Rightarrow_R^* \alpha A w \Rightarrow \alpha \beta w</math>
  * <math>S \Rightarrow_R^* \gamma B x \Rightarrow \alpha \beta y</math>
  * <math>FIRST_k(w) = FIRST_k(y)</math>, resp. <math>k:w = k:x</math>
vyplývá, že <math>\alpha A y = \gamma B x</math>.

Položka gramatiky <math>G</math> je výraz typu <math>X \rightarrow \alpha . \beta</math>, kde <math>X \rightarrow \alpha\beta</math> je pravidlo gramatiky <math>G</math>. Speciálně je <math>X \rightarrow .</math> položkou, pokud <math>X \rightarrow \varepsilon \in P</math>. Pro každé <math>X \rightarrow \gamma \in P</math> nazýváme <math>X \rightarrow \gamma.</math> úplnou položkou.

Položka <math>A \rightarrow \alpha . \beta</math> je platnou položkou pro řetěz <math>w</math>, jestliže existuje pravá větná forma <math>\eta A u</math> (<math>u \in \Sigma^*</math>) taková, že <math>\eta \alpha = w</math>. Množinu všech platných položek pro řetěz <math>\gamma</math> budeme označovat <math>I(\gamma)</math>.

Speciálně pro <math>LR(0)</math> platí, že:
  * počáteční symbol <math>S</math> se nevyskytuje na pravé straně žádného pravidla
  * pro libovolný řetěz <math>\gamma \in (N \cup \Sigma)^*</math> se v množině <math>I(\gamma)</math> vyskytuje nejvýše jedna úplná položka
  * jestliže se v <math>I(\gamma)</math> vyskytuje úplná položka, potom už v <math>I(\gamma)</math> není obsažena žádná položka, v níž je bezprostředně vpravo od tečky terminální symbol

<box round|Parsing <math>LR(k)</math> gramatik>
Gramatika <math>G</math> je <math>LR(k)</math>, pokud existuje deterministický <math>LR(k)</math> zásobníkový automat, který ji rozeznává (parser). <math>LR(k)</math> parser pracuje, narozdíl od <math>LL(k)</math> parserů, s nejpravější derivací. Parser parsuje zespodu, narozdíl od <math>LL</math> parserů, které parsují zeshora. Při parsingu se parser může rozhodovat podle dalších <math>k</math> znaků na vstupu a dle toho parsovat už načtené znaky.
</box>

===== Vztahy mezi DCFL, LL a LR =====

Platí: <math>LL \subseteq LR \subseteq DCFL</math>.

<math>LL</math> nemůže obsahovat rekurzi, <math>LR</math> nezvládá všechny CFG kvůli omezení <math>k</math>.

====== Předměty ======

[[https://is.muni.cz/auth/predmety/predmet.pl?id=585030|FI:IA006]] Vybrané kapitoly z teorie automatů (podzim 2010), prof. RNDr. Mojmír Křetínský, CSc.

[[https://is.muni.cz/auth/predmety/predmet.pl?id=363716|FI:IB005]] Formální jazyky a automaty I (jaro 2007), prof. RNDr. Mojmír Křetínský, CSc.

====== Použitá literatura ======

-

====== Vypracoval ======

DevelX - Martin Jurča

stav - 95 %