Intuice pro analýzu zdola nahoru IB102 Automaty, gramatiky a složitost, 7.11.2016 1/28 Intuice pro analýzu zdola nahoru s XY X ->• ab Y ->• c IB102 Automaty, gramatiky a složitost, 7.11.2016 2/28 Nedeterministická syntaktická analýza zdola nahoru Věta 3.55. Nechť Q je libovolná CFG, pak lze zkonstruovat rozšířený PDA takový, že L(G) = L(1Z). Důkaz. Vrchol zásobníku píšeme vpravo. Konstruujeme rozšířený PDA 1Z, který simuluje pravou derivaci v Q v obráceném pořadí. PDA 1Z má kroky dvojího typu: □ může kdykoli načíst do zásobníku symbol ze vstupu H (redukce) je-li na vrcholu zásobníku řetězec tvořící pravou stranu nějakého pravidla v g, může ho nahradit odpovídajícím levostranným neterminálem (a ze vstupu nic nečte) IB102 Automaty, gramatiky a složitost, 7.11.2016 3/28 Nechť G = (N, e, P, s). Položme 72. = ({q, r}, z, A/ u e U {_L}, 5, q, _L, {r}), kde ± je nově přidaný symbol a kde S je definována takto: D 5(q, a, e) = {(q, a)} pro všechna a e Y. Q je-li A -> a pravidlo v P, pak S(q, e, a) obsahuje (q, A) m S(q,s,±S) = {(r,e)} IB102 Automaty, gramatiky a složitost, 7.11.2016 4/28 krok výpočtu odpovídající pravidlo z Q (q7 1 + 1*1, ±) i (g, +i * i, -L0 F ^ i 1 6 T ^ F e E-f T £ (q, +i * i, + {q, i * i, / ±E + /) F ^ i £ (q, *i, ±E+F) T ^ F £ (q, *i, ±E+T) * (q, i, ±E+ T*) / (q, e> ±E+T* /') F ^ i £ (q, £, ±E+T*F) r r * f £ (q, e> ±E+T) E^ E+T £ (q, e> £ e) IB102 Automaty, gramatiky a složitost, 7.11.2016 5/28 Korektnost aAyAxy ^ (q,xy,±)^-(q,y,±aA), n kde S =4>* aAy =4> xy je pravá derivace a A je nejpravější neterminál (=4>) indukcí k délce odvození (<==) indukcí k délce výpočtu Pro A = S aa,y = e dostáváme: x ^ (q,x,±)\^(q,e,±S) "Výstupem" je pravá derivace v obráceném pořadí. IB102 Automaty, gramatiky a složitost, 7.11.2016 Efektivnost syntaktické analýzy Nederministický PDA =4> nedeterministický algoritmus =4> exponenciální deterministický algoritmus Řešení: deterministický algoritmus složitosti 0(n3), kde n = \ w (algoritmus Cocke - Younger - Kasami) deterministické zásobníkové automaty a deterministické bezkontextové jazyky lineární algoritmy pro speciální třídy deterministických bezkontextových jazyků IB102 Automaty, gramatiky a složitost, 7.11.2016 7/28 Vlastnosti bezkontextových jazyků Věta 3.58. (a 3.61.) Třída bezkontextových jazyků (£2) je uzavřena vzhledem k operacím: D sjednocení B zřetězení B iterace □ pozitivní iterace B průnik s regulárním jazykem Věta 3.60. Třída bezkontextových jazyků (£2) není uzavřena vzhledem k operacím: □ průnik B doplněk IB102 Automaty, gramatiky a složitost, 7.11.2016 8/28 Sjednocení /-i je generován CFG Q\ = (A^, , PA, Si) a /_2 je generován CFG £2 = (W2, ^2, P2, S2). Bez újmy na obecnosti můžeme předpokládat A/-| n A/2 = 0. Definujeme 5 = (A/1uA/2u {S}, Z1 u Z2, P, S), kde S je nový symbol a p = p1 u P2 u {S -> Si, S -> S2}. Každá derivace v £ začne použitím buď S ^ nebo S S2. Podmínka A/-| n A/2 = 0 zaručí, že při použití S -> S-i (resp. S S2) lze v dalším derivování používat jen pravidla z Pí (resp. P2). Jazyk L = Li u L2 je generován gramatikou 1} /_2 = {ambncm \ m, n > 1} Oba tyto jazyky jsou CFL. Kbyby C2 byla uzavřena vzhledem k operaci průniku, pak by i L| n L2 = {anbncn | n > 1} musel být bez kontextový, což však není. Neuzavřenost £2 vůči doplňku plyne z její uzavřenosti na sjednocení, neuzavřenosti na průnik a z De Morganových pravidel: L-| n L2 = co-(co-/_-| u co-L2), tj., kdyby £2 byla uzavřena na doplněk, musela by být uzavřena i na průnik, což však není. IB102 Automaty, gramatiky a složitost, 7.11.2016 13/28 Protipříklad k uzavřenosti na doplněk L = {ww | w g {a, by} není CFL. co-L je CFL. IB102 Automaty, gramatiky a složitost, 7.11.2016 14/28 Průnik s regulárním jazykem L=L(V), kde V je PDAV = V,5i,qi,Z0, Fi) R = L(A), kde A je deterministický FA A = (Q2,51, S2, cfe, ^2) Sestrojíme PDA V takový, že L(P') = LnR. V = (Q7ZJ75,q0,Z0,F), kde ■ Q = Q1 x Q2 ■ q0 = (<7i, Q2> ■ f = f) x f2 ■ 5 : pro každé peQ1,qe02,aelu {e}, Zel" platí: 5((p,(?),a,Z) = {((p',c7/),7) I (p/,7)e51(p,a,Z)a<52((7,a) = qf'} Zřejmě platí iv e L(V) ^we L(P) n L(^). IB102 Automaty, gramatiky a složitost, 7.11.2016 15/28 Rozhodnutelné problémy pro bezkontextové jazyky Problém příslušnosti Existuje algoritmus, který pro libovolnou danou CFG Q a slovo w rozhoduje, zda w e L(Q) či nikoliv. Problém prázdnosti Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) = 0 či nikoliv. Problém konečnosti Existuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) je konečný či nikoliv. IB102 Automaty, gramatiky a složitost, 7.11.2016 16/28 Konečnost Věta 3.68. Ke každé CFG Q lze sestrojit čísla m, n taková, že L{Q) je nekonečný právě když existuje slovo z e L(Q) takové, že m < \z\ < n. Důkaz. Předpokládejme, že Q je v CNF. Nechť p, q jsou čísla s vlastnostmi popsanými v Lemmatu o vkládání. Položme m = pa n = p + q. (<==) Jestliže z g L(Q) je takové slovo, že |z| > p, pak existuje rozdělení z = uvwxy splňující vx ^ e a uv'wx'y e L(Q) pro všechna / > 0. Tedy jazyk L(Q) obsahuje nekonečně mnoho slov tvaru uv'wx'y, je tedy nekonečný. IB102 Automaty, gramatiky a složitost, 7.11.2016 17/28 (=4>) Nechť L(Q) je nekonečný. Pak obsahuje i nekonečně mnoho slov délky větší než p - tuto množinu slov označme M. Zvolme z M libovolné takové slovo z, které má minimální délku a ukažme, že musí platit p < \z\ < p + q. Kdyby \z\> p + g, pak (opět dle Pumping lemmatu pro CFL) lze z psát ve tvaru z = uvwxy, kde vx ^ e, |iwx| < q a uv'wx'y e L(Q) pro všechna / > 0. Pro / = 0 dostáváme, že uwy e L{Q) a současně \uwy\ < \uvwxy Z nerovností |L/vwxy| > p + q a |iwx| < q plyne, že UWYI > (P + Q) - Q = P- Tec|y uwy e M, což je spor s volbou z jako slova zMs minimální délkou. Celkem tedy musí být \z\ < p + q. □ IB102 Automaty, gramatiky a složitost, 7.11.2016 18/28 Vlastnost sebevložení Definice 3.70. Nechť Q = (A/, Z, P, S) je CFG. Řekneme, že Q má vlastnost sebevložení, jestliže existují A e N a u, v e Z+ taková, že CFL L má vlastnost sebevložení, jestliže každá bezkontextová gramatika, která jej generuje, má vlastnost sebevložení. Věta 3.71. CFL L má vlastnost sebevložení, právě když L není regulární. Důkaz. Viz skripta. IB102 Automaty, gramatiky a složitost, 7.11.2016 19/28 Nerozhodnutelné problémy pro bezkontextové jazyky Problém regularity Neexistuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L(Q) je regulární či nikoliv. (Tedy není rozhodnutelné, zda L(Q) má vlastnost sebevložení či nikoliv.) Problém univerzality Neexistuje algoritmus, který pro libovolnou danou CFG Q rozhoduje, zda L{Q) = Z* či nikoliv. Problémy ekvivalence a inkluze také nejsou rozhodnutelné (plyne z nerozhodnutelnosti problému univerzality). IB102 Automaty, gramatiky a složitost, 7.11.2016 20/28 Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q, z, r, 5, q0, -2b, F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky: D pro všechna q g q a z g ľ platí: kdykoliv 5(q, e, z) ^ 0, pak a, z) = 0 pro všechna a e z Q pro žádné qeQ, ZeVaaeTu{e} neobsahuje 5(q, a, z) více než jeden prvek Řekneme, že L je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA M takový, že L = L(M). IB102 Automaty, gramatiky a složitost, 7.11.2016 21/28 Vlastnosti deterministických bezkontextových jazyků Věta 3.82. Třída DCFL je uzavřena na doplněk. Intuice: DPDA má nad každým slovem právě jeden výpočet. Pro doplněk stačí zaměnit koncové a nekoncové stavy. Komplikace 1: DPDA nemusí dočíst vstupní slovo do konce, protože se vyprázdní zásobník nebo přechod není definován. Řešení: IB102 Automaty, gramatiky a složitost, 7.11.2016 22/28 Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí č-kroky pod kterýmy zásobník neomezeně roste. Řešení: s = |Q|, t = r = max{|7| | (p1',7) e 5(p,e,Z), p,p' e Q, Z e r} zásobník neomezeně roste při ^-krocích během posloupnosti e-kroků jeho délka vzroste o více než r • s • t IB102 Automaty, gramatiky a složitost, 7.11.2016 23/28 Komplikace 3: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí č-kroky pod kterýmy zásobník neroste neomezeně, tj. po jistém počtu kroků se jeho obsah opakuje. Řešení: s = |Q|, t = |l~| r = max{|7| | (p',7) e 8{p,e,Z), p,pf e Q, Z e I"} IB102 Automaty, gramatiky a složitost, 7.11.2016 24/28 Komplikace 4: DPDA dočte slovo, ale pak pod č-kroky prochází koncové i nekoncové stavy (tj. některá slova jsou akceptována původním DPDA i DPDA se zaměněnými koncovými stavy). Řešení: IB102 Automaty, gramatiky a složitost, 7.11.2016 25/28 o ■ a sjednocení Věta. Třída DCFL není uzavřena na průnik. Důkaz. = {anbncm |m,n>1}aL2 = {ambncm {m^n^-i}jsou DCFL, ale L1 n L2 = {anbncn | n > 1} není ani bezkontextový. Věta. Třída DCFL je uzavřena na průnik s regulárním jazykem. Věta. Třída DCFL není uzavřena na sjednocení. Důkaz. Plyne z uzavřenosti na doplněk, neuzavřenosti na průnik a z De Morganových pravidel: L| n Z-2 = co-(co-Li u C0-/-2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.) IB102 Automaty, gramatiky a složitost, 7.11.2016 Vztah deterministických a nedeterministických CFL Věta. Třída DCFL tvoří vlastní podtřídu třídy bezkontextových jazyků. Zejména existují bezkontextové jazyky, které nejsou DCFL. Příklad. Jazyk co-{ww \ w e {a, £>}*} je CFL, ale není DCFL. IB102 Automaty, gramatiky a složitost, 7.11.2016 27/28 Aplikace (deterministických) bezkontextových jazyků ■ syntaxe programovacích jazyků je definována pomocí CFG (dobře uzávorkované výrazy, if-then-else konstrukty) ■ DTD (Document Type definition) umožňuje definovat bezkontexové jazyky - využití ve značkovacích jazycích (HTML, XML,...) ■ nástroje pro tvorbu parserů/překladačů využívají různé algoritmy pro lineární deterministickou syntaktickou analýzu: LALR(1) - Yacc, Bison, javacup LL(k) - JavaCC, ANTLR IB102 Automaty, gramatiky a složitost, 7.11.2016 28/28