Intuice pro analýzu zdola nahoru IB102 Automaty, gramatiky a složitost, 3.11.2014 1/27 Intuice pro analýzu zdola nahoru S ^ XY X ab Y c IB102 Automaty, gramatiky a složitost, 3.11.2014 2/27 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, 3.11.2014 3/27 Nechť G = (N, e, P, S). Položme 72. = ({q, r}, z, a/ u e U {_L}, 5, q, _L, {r}), kde _L je nově přidaný symbol a kde S je definována takto: D <5(<7, a, e) = {(q, a)} pro všechna a g e Q je-li -A ->• a pravidlo v P, pak 8(q, e, a) obsahuje (q, A) B ô{q,e,±S) = {(r,e)} IB102 Automaty, gramatiky a složitost, 3.11.2014 4/27 krok výpočtu odpovídající pravidlo z Q {q, / + /*/, _L) ^ (q, +i * i, F -w 1 £ (q, +i * /, T ^ F (q, +i * /, ^) E-f T + (q, i*/, / J-E + /) F / ±E + F) T ^ F ±E+ 7) * (<7, /, ±E+ 7*) / ±E + 7 * /') F ^ i £ _LE + 7 * F) 7^7 £ (q, e, ±E+ 7) E -f E £ £ IB102 Automaty, gramatiky a složitost, 3.11.2014 5/27 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, 3.11.2014 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, 3.11.2014 7/27 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, 3.11.2014 8/27 Sjednocení /-i je generován CFG Q\ = (A^, , PA, Si) a /-2 je generován CFG £2 = (A/2, ^2, p2, S2). Bez újmy na obecnosti můžeme předpokládat ^ n A/2 = 0. Definujeme Q = (A^ u A/2 u {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 ^ S-i nebo S S2. Podmínka A/i 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 = L| u Z_2 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 n Z-2 = {anbnď | a? > 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: Z_-i n Z-2 = ^-(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, 3.11.2014 13/27 Průnik s regulárním jazykem L = L{V), kde V je PDA V = (Q\, Z, l~,S-\,q-\,Z0, F|) fř = /.(.A), kde .4 je deterministický FA .4 = (Q2,51,52, c/2, F2) Sestrojíme PDA V' takový, že L(P') = LnR. V = (Q,T,r,S,q0,Z0,F), kde ■ Q = Q1 x Q2 ■ y) | (p,,7)^1(p,a)Z)aí2(q,a) = £/} Zřejmě platí w e L(V) ^ we L(V) n L(A). IB102 Automaty, gramatiky a složitost, 3.11.2014 14/27 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, 3.11.2014 15/27 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 uv1 i/i/x'y, je tedy nekonečný. IB102 Automaty, gramatiky a složitost, 3.11.2014 16/27 (=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, | vwx\ < q a uvlwxly e /.((?) pro všechna / > 0. Pro / = 0 dostáváme, že uwy e L{Q) a současně \uwy\ < \uvwxy Z nerovností |i/iwxy| > p + q a |iwx| < q plyne, že uwy\ > (p + q) - q = p. Tedy i/wy e M, což je spor s volbou z jako slova z M s minimální délkou. Celkem tedy musí být |z| < p + q. □ IB102 Automaty, gramatiky a složitost, 3.11.2014 17/27 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 /A i//4v. 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, 3.11.2014 18/27 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, 3.11.2014 19/27 Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q, Z, r, 5, gb, Z0, F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky: D pro všechna q e Q a Z g r platí: kdykoliv 5(qr, e, Z) ^ 0, pak 5(qr, a, Z) = 0 pro všechna a e Z Q pro žádné q e Q, ZeVaaeTu{e} neobsahuje 5(q, a, Z) více než jeden prvek Řekneme, že Z. je deterministický bezkontextový jazyk (DCFL), právě když existuje DPDA M takový, že L = L(M). IB102 Automaty, gramatiky a složitost, 3.11.2014 20/27 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, 3.11.2014 21/27 Komplikace 2: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí e-kroky pod kterýmy zásobník neomezeně roste. Řešení: s = |Q|, t = |l~| r = max{|7| | (p',7) e 5(p,e,Z), p,pf e Q, Z e I"} zásobník neomezeně roste při ^-krocích během posloupnosti e-kroWů jeho délka vzroste o více než r • s • t IB102 Automaty, gramatiky a složitost, 3.11.2014 22/27 Komplikace 3: DPDA nemusí dočíst vstupní slovo do konce, protože přestane číst vstup a neustále provádí e-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 = r = max{|7| | (p',7) e 8(p, e, Z), p,p' e Q, Z e V} IB102 Automaty, gramatiky a složitost, 3.11.2014 23/27 Komplikace 4: DPDA dočte slovo, ale pak pod e-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, 3.11.2014 24/27 o ■ a sjednocení Věta. Třída DCFL není uzavřena na průnik. Důkaz. LÁ = {anbncm | m,n > 1} a L2 = {ambncm {m^n^-i} jsou DCFL, ale L| n L2 = {anbncn | a? > 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: Z_-i n Z-2 = co-(co-Li u co-L2) (Z uzavřenosti na sjednocení by plynula uzavřenost na průnik.) IB102 Automaty, gramatiky a složitost, 3.11.2014 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, 3.11.2014 26/27 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, 3.11.2014 27/27