FANDOM


36TPR, přednáší Prof. Ing. Bořivoj Melichar, DrSc.

Následující text slouží jako shrnutí látky probírané na ČVUT-FEL 36TPR (2006/07) a vznikl jako příprava ke zkoušce z dostupných materiálů (skripta Melichar: Tvorba překladačů 1996, skripta Melichar: Tvorba překladačů cvičení 2001, zápisky ze cvičení u L. Vágnera a z konzultace u L. Vágnera).

Poděkování L. Vágnerovi za jedny z nejkvalitnějších cvičení za dobu mého studia.

--Wictor 17:01, 14. 2. 2007 (UTC)


Přehled LR gramatik Editovat

LR algoritmy syntaktické analýzy jsou typu bottom-up. Čtou vstupní řetězec zleva doprava a vytvářejí pravý rozklad. LR(k) používají informaci o nejbližších k symbolech (tzv. lookahead, LA) ještě nepřečtené části vstupního řetězce.
Gramatika G = (N,T,P,S), jednoznačná, bezkontextová.

Pro všechny LR je společný postup vytváření tzv. LR položek, z kterých se pak vytváří tzv. tabulka akcí. V této tabulce nesmí být v jedné buňce více akcí (např. přesun a redukce nebo dvě různé redukce) – to je indikace nedeterminismu a je třeba buď upravit gramatiku nebo sáhnout po silnějším nástroji.

Trocha terminologie

  • Redukční část (handle): část zásobníku, která se zredukuje na nový symbol.
  • Perspektivní předpona (viable prefix): FIXME
  • Úplná perspektivní předpona (complete viable prefix): FIXME


Silné LR(k) gramatiky (Strong LR(k)) Editovat

K jejich deterministické analýze stačí znát k dopředu prohlížených (nepřečtených) symbolů a symbol na vrcholu zásobníku. Není třeba znát historii (tj. v LR položkách nebudou indexované množiny).

Silná LR(0) gramatika Editovat

K její deterministické analýze stačí informace o hodnotě na vrcholu zásobníku. Taková gramatika musí mít vzájemné rozdílné konce pravých stran pravidel a symbol, nacházející se na konci pravé strany pravidla, se nesmí vyskytovat na pravé straně žádného jiného pravidla. Tzn. gramatika nemůže obsahovat ε-pravidla a startovací symbol S se nevyskytuje na pravé straně žádného pravidla. Symboly na konci pravých stran identifikují redukce pro dané pravidlo.

Tabulka akcí (Action table / Parsing table) má jeden sloupec (resp. ve všech sloupcích v daném řádku je jen jedna možná akce). Kam jít se rozlišuje jen podle vrcholu zásobníku.


Slabé LR(k) gramatiky (Weak LR(k)) Editovat

K jejich deterministické analýze potřebujeme symbol na vrcholu zásobníku, k dopředu prohlížených symbolů (k lookahedů) a ještě navíc historii (indexované množiny LR položek).

Přívlastek Slabé se zde explicitně dále nepoužívá. Tedy, co není silné, je slabé.

LR(0) gramatiky Editovat

Deterministický analyzátor potřebuje znát jen historii. Oproti Silné LR(0) musíme někde rozlišovat více stavů stejných symbolů (podle historie), což se rozlišuje pomocí indexů. Stále však platí, že pro aktuální stav může nastat jen 1 redukce nebo jen přesuny.

Tabulka akcí (Action table / Parsing table) má tedy jeden sloupec. Kam jít se rozlišuje jen podle vrcholu zásobníku. Oproti Silné LR(0) se zde vyskytují indexované symboly (podle historie).

Simple LR(k) gramatiky (SLR(k)) Editovat

V jedné množině LR položek se může vyskytovat přesun i redukce.

Tabulka akcí (Action table / Parsing table) tak má počet sloupců jako symbolů vstupní abecedy + ε. Přesun je jen pro symboly, kterých se přesun týká (před kterými je v pravidlech tečka) a redukce jen pro ty symboly, které se nacházejí v množině FOLLOW symbolu na levé straně příslušného pravidla.

Pozn.: Prakticky se setkáváme jen se SLR(1). Pro k>1 je spíše sahá po LR(k) nebo se snažíme gramatiku převést na jednodušší.

LALR(k) Editovat

Pro deterministické rozhodnutí, kde všude redukovat je třeba ještě znát lookahead (LA). Redukce je pak vykonávána jen pro ty symboly, které jsou v množině LA daného pravidla (ještě méně než v množině FOLLOW, proto se můžeme vyvarovat některých konfliktů v tabulce akcí).

Tabulka akcí (Action table / Parsing table) je tak podobná jako u SLR, jen redukce jsou více upřesněné (je jich méně).

Obecné LR(k) Editovat

Nejsilnější nástroj. Avšak pro k>1 se dramaticky zvyšuje obtížnost (rozuměj délka) výpočtu. Postup je stejný jako u LALR, jen LR položky je možné slučovat při stejném nejenom jádře, ale i lookaheadu. Položek je tak mnohem více.

Tabulka akcí (Action table / Parsing table) má tak více řádků než u LALR (je zde více indexů množin).


Formální překlad řízený LR analyzátorem Editovat

Překladovka je slabším z obou nástrojů, zase se nemusíte zabejvat sémantikou atributů. Pokud vám ale zadání řiká něco o překladu z ucv na vRvu, pak rovnou sáhněte po atributovce.


Atributový překlad řízený LR analyzátorem Editovat

Atributovka je to nejlepší, co vám Melichar na překlad nabízí. Na druhou stranu ty atributy můžou pěkně potrápit, zvlášť když si u LR zavedete dědičný (u jiného než výstupního symbolu se důrazně nedoporučuje).

Příklad 1 Editovat

Přeložte ucv na vRvu, kde u,v \in \left\{a,b\right\}^+

Řešení

1.  S \to A^1 c A^2 \underline o \underline o.cout = Rev(A^2.str) + A^2.str + A^1.str
2.  A^0 \to A^1 a A^0.str = A^1.str + 'a'
3.  A^0 \to A^1 b A^0.str = A^1.str + 'b'
4.  A \to \varepsilon A.str = \varepsilon

Atributy:

symbolsyntetizovanýdědičný
Astr-
o-cout

Dál se dodělaj LR položky, tabulka akcí, brejle a úsměv...

Paralelní analýza Editovat

Předem jedna špatná zpráva: ke zkoušce je třeba umět LR i LL, bo se v zadáních vyskytuje ta či ona rekurze. A některé zadání dokonce nevyřešíte ani jedním způsobem, prostě pro takovou gramatiku neexistuje deterministickej paralelní analyzátor.

V každym pádě, jakmile se v LR či LL položkách objevěj neslučitelný indexovaný množiny (tj. nejedná se o silnou gramatiku) je to tu. Buď je tam rekurze a je třeba sáhnout po to druhym (LR nezvládne pravou a LL levou rekurzi) nebo se jedná o ten nedeterministickej prevít:-). V takovym případě se nezapomeňte s touto skutečností v řešení pochlubit, nebo dostanete tak jako já 0% za příklad.

Paralelní LR analýza Editovat

Vytvoření paralelního LR syntaktického analyzátoru se sestává ze 2 částí:

Nejdříve se vytvoří LR položky a tabulka akcí silného LR(k) (prakticky SLR(1)) – pro paralelní výpočet nelze využít historii analýzy, proto jakékoliv neslučitelné indexované množiny indikují nedeterminismus paralelního výpočtu. Z tohoto důvodu nelze také vycházet z gramatiky s pravou rekurzí. Pro takovou gramatiku neexistuje deterministický paralelní LR analyzátor a je třeba (ač jakkoliv bolestivě) sáhnout po paralelním LL analyzátoru.

V druhé části se již odkloníme od podobnosti se sekvenčním výpočtem. Z tabulky akcí sestavíme tzv. přípustné páry (možné dvojice), což je dvojice terminálních symbolů označujících řádek a sloupec, pro které existuje v tabulce nějaká akce. Pro každý tento pár pak vypočteme tzv. triplet, což není nic jiného, než předpočítaný mezivýsledek z určité fáze do další. Každý procesor v paralelním výpočtu tak zjistí svůj výchozí bod, najde příslušný triplet a dle něho zjistí svůj mezivýsledek. Následnou paralelní redukcí získáme finální výsledek.

Triplet se skládá z (1) předpokládaného stavu (části) zásobníku (výchozí bod), (2) cílového stavu (části) zásobníku a (3) části pravého rozkladu, který se k tomu použil.

Např.:

a b ...
... ... ... ...
a p R3
... ... ... ...

Část přípustných párů tedy bude:

  • (a,a)
  • (a,b)

Výpočet tripletů:

  • (a,a,\varepsilon) \vdash (aa,\varepsilon,\varepsilon) \longrightarrow (a,aa,\varepsilon)
  • (a,b,\varepsilon) \vdash (\alpha,b,3) \vdash ... \vdash (\gamma b,\varepsilon,3...) \longrightarrow (a,\gamma b,3...)

Někdy se ovšem stane, že potřebujeme dle tabulky akcí redukovat podle pravidla, které má např. tvar A \to A x A y, ale na našem parciálním zásobníku toho tolik není. V takovém případě si tzv. půjčíme, resp. triplet bude indikovat, co vše na zásobníku budeme potřebovat:

  • (y,z,\varepsilon) \vdash ^{AxA}(A,z,2) \vdash (AB,z,25) \vdash (ABz,\varepsilon,25) \longrightarrow (AxAy,ABz,25)

Po vypočtení všech tripletů je vše připraveno ke spuštění analýzy. Pro každý symbol vstupu najdeme patřičný triplet, tedy ten, který má na konci předpokládaného zásobníku předcházející symbol a na konci koncového zásobníku současný symbol:

řetězec a b ...
1.předpokládaný stav části zásobníku ... ..a ...
2.cílový stav části zásobníku ..a ..b ...
část pravého rozkladu ... ... ...

Jen pro první symbol použijeme sekvenční triplet, nejčastěji (\varepsilon,\vdash,\varepsilon).

Následná paralelní redukce se sestává z „lepení“ tripletů. Vytvoříme dvojice vedlejších tripletů a sloučíme je do jednoho:

  1. koncový zásobník prvního je stejný jako počáteční druhého
    • (\alpha,\beta,r_1) + (\beta,\gamma,r_2) = (\alpha,\gamma,r_1 r_2)
  2. pravá část zásobníku koncového prvního je stejná jako počáteční druhého
    • (\alpha,\beta\gamma,r_1) + (\gamma,\delta,r_2) = (\alpha,\beta\delta,r_1 r_2)
  3. koncový zásobník prvního je stejný jako pravá část počátečního druhého
    • (\alpha,\beta,r_1) + (\gamma\beta,\delta,r_2) = (\gamma\alpha,\delta,r_1 r_2)

(Tohle je fakt dobrý si radši nakreslit;-)

Příklad 1 Editovat

č.pravidlafirstfollow
1. S \to \vdash A B \dashv \vdash\varepsilon
2. A \to A x A y xx,y,z,\dashv
3. A \to \varepsilon \varepsilon
4. B \to B z zz,\dashv
5. B \to \varepsilon \varepsilon

Řešení - při pohledu na pravidlo 2. a 4. (levá rekurze) je jasné, že LR je správná volba. Jedině by nás moh ještě vyšplouchnout ten nedeterminista (objevily by se neslučitelný indexovaný množiny), ale to tady nebude.

SLR(1) položky

\# = \{ S \to .{\vdash}AB\dashv \}
\vdash = \{ S \to {\vdash}.AB\dashv
'"`UNIQ6e3d4aa7668b0eb4-math-00000023-QINU`"' A \to .AxAy
A \to . \}
A_1 = \{ S \to {\vdash}A.B\dashv
A \to A.xAy
B \to .Bz
B \to . \}
B = \{ S \to {\vdash}AB.\dashv
B \to B.z \}
x = \{ A \to Ax.Ay
A \to .AxAy
A \to . \}
\dashv = \{ S \to {\vdash}AB{\dashv}. \}
z = \{ B \to Bz. \}
A_2 = \{ A \to AxA.y
A \to A.xAy \}
y = \{ A \to AxAy. \}

Tabulka akcí

x y z \vdash \dashv \varepsilon
\# P
\vdash R3 R3 R3 R3
\dashv A
A_1 P R5 R5
A_2 P P
B P P
x R3 R3 R3 R3
y R2 R2 R2 R2
z R4 R4

Množiny A_1 a A_2 můžeme (a musíme) sjednotit:


x y z \vdash \dashv \varepsilon
\# P
\vdash R3 R3 R3 R3
\dashv A
A P P R5 R5
B P P
x R3 R3 R3 R3
y R2 R2 R2 R2
z R4 R4

Triplety

x y z \vdash \dashv
\vdash (\vdash, {\vdash}Ax, 3) (\vdash, {\vdash}Ay, 3) (\vdash, {\vdash}ABz, 35) (\vdash, {\vdash}AB\dashv, 35)
x (x, xAx, 3) (x, xAy, 3) (x, xABz, 35) (x, xAB\dashv, 35)
y (AxAy, Ax, 2) (AxAy, Ay, 2) (AxAy, ABz, 25) (AxAy, AB\dashv, 25)
z (Bz, Bz, 4) (Bz, B\dashv, 4)

Pokud by nebylo někomu jasné, jak vznikly jednotlivé triplety, zde jsou dva příklady pro buňky (\vdash, x) a (y, z):

  • (\vdash, x, \varepsilon) \vdash ({\vdash}A, x, 3) \vdash ({\vdash}Ax, \varepsilon, 3) \to (\vdash, {\vdash}Ax, 3)
  • (y, z, \varepsilon) \vdash^{AxA} (A, z, 2) \vdash (AB, z, 25) \vdash (ABz, \varepsilon, 25) \to (AxAy, ABz, 25)

Ověření na řetězci

FIXME

Paralelní LL analýza Editovat

Pokud dané zadání skrývá radost pravé rekurze, musíme zkusit zvolit opožiční LL analýzu. Vtip je v tom, že nejenom že se všechno dělá opačně (tečku posouváme zprava do leva), ale navíc je tam ještě pár zpestřujících fíčurek - lookahead a obsah zásobníku.

  • Lookahead se počítá jako FIRST1 ze symbolu vlevo před tečkou ztřetězenym s obsahu zásobníku (z pravidla, ze kterého jsme vyšli).
  • Obsah zásobníku se složí (zřetězí) z tečkou přeskočeného symbolu a předcházejícího obsahu zásobníku. Následně se zkrátí na minimální možnou délku (zprava) tak, aby z něho stále šlo vygenerovat (FIRST1) aktuální lookahead.

Jak přesně poznat nedeterminismus u LLP? FIXME


Příklad 1 Editovat

č.pravidlafirstfollow
1. S \to \vdash A B \dashv \vdash\varepsilon
2. A \to x A y xy,z,\dashv
3. A \to \varepsilon \varepsilon
4. B \to z B z\dashv
5. B \to \varepsilon \varepsilon

Řešení - při pohledu na pravidlo 4. (pravá rekurze) je jasné, že LL je správná volba

LL položky

Položky jsou ve tvaru: pravidlo s tečkou z prava, lookahead, zásobník.

\sharp = \{ S \to \vdash A B \dashv . , \varepsilon, \varepsilon \}

\begin{array}{lcl}
\dashv = \{ & S \to & \vdash A B . \dashv, \dashv, \dashv \\
            & B \to & z B . , \dashv, \dashv \\
            & B \to & . , \dashv, \dashv \}
\end{array}

\begin{array}{lcl}
B = \{ & S \to & \vdash A . B \dashv, \begin{smallmatrix}z \\ \dashv \end{smallmatrix},
\begin{smallmatrix}B \\ B\dashv \end{smallmatrix} \\
            & B \to & z . B , \begin{smallmatrix}z \\ \dashv \end{smallmatrix},
\begin{smallmatrix}B \\ B\dashv \end{smallmatrix} \\
            & A \to & x A y . , \begin{smallmatrix}z \\ \dashv \end{smallmatrix},
\begin{smallmatrix}B \\ B\dashv \end{smallmatrix} \\
            & A \to & . , \begin{smallmatrix}z \\ \dashv \end{smallmatrix},
\begin{smallmatrix}B \\ B\dashv \end{smallmatrix} \}
\end{array}

(...) FIXME


PSLS tabulka

Pro všechny položky, kde je tečka vpravo od terminálního symbolu zapíšeme do tabulky její obsah zásobníku. Sloupce tabulky odpovídají LA (lookaheadu) a řádky LB (lookbacku) (tedy onomu terminálnímu symbolu u tečky).

LLP tabulka

Vychází z PSLS, obsahuje už celé triplety: (1) původní obsah zásobníku (jako v PSLS), (2) koncový obsah zásobníku (po přijetí daného LA), (3) použité pravidla.

FIXME

Ověření na řetězci

Slučování (lepení/paralelní redukce) tripletů se řídí trochu jinými pravidly než u LR, prakticky to co jde otočit, tak otočit (místo suffixů prefixy). Jako příklad stačí to, co je ve skriptech.

FIXME

Literatura Editovat

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

V síti Wikia

Náhodná Wiki