Obsah

Zadání
Vypracování
Předměty
Použitá literatura
Vypracoval

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 $X \rightarrow w$ , kde $X$ je libovolný neterminál a $w$ 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)

Definice

Nechť $G = (N, \Sigma, P, S)$ je CFG, $k \geq 1, k \in \mathbb{Z}$ . Definujeme nasledovné funkce:

$FIRST_k^G: (N \cup \Sigma)^+ \rightarrow \mathcal{P}(\{w \in \Sigma^* |\ |w| \leq k \})$
$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^*)\}$

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

A dále pro $w = a_1 a_2 ... a_n$ :
$k:w = a_1 ... a_k$ pro $k < n$
$k:w = w$ pro $k \geq n$

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

$S \Rightarrow^* wA\alpha \Rightarrow w\beta\alpha \Rightarrow^* wx$
$S \Rightarrow^* wA\alpha \Rightarrow w\gamma\alpha \Rightarrow^* wy$

podmínka $k:x = k:y$ implikuje $\beta = \gamma$ .

Vlastnosti

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

LR(k)

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

Gramatika $G = (N, \Sigma, P, S)$ je $LR(k)$ pro $k \geq 0$ , pokud pro všechny pravé větné formy z podmínek:

$S \Rightarrow_R^* \alpha A w \Rightarrow \alpha \beta w$
$S \Rightarrow_R^* \gamma B x \Rightarrow \alpha \beta y$
$FIRST_k(w) = FIRST_k(y)$ , resp. $k:w = k:x$

vyplývá, že $\alpha A y = \gamma B x$ .

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

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

Speciálně pro $LR(0)$ platí, že:

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

Parsing $LR(k)$ gramatik

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

Vztahy mezi DCFL, LL a LR

Platí: $LL \subseteq LR \subseteq DCFL$ .

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

Předměty

FI:IA006 Vybrané kapitoly z teorie automatů (podzim 2010), prof. RNDr. Mojmír Křetínský, CSc.

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 %