Intuice pro analýzu zdola nahoru IB102 Automaty, gramatiky a složitost, 16.11.2015 1/27 Intuice pro analýzu zdola nahoru S ^ XY X ab Y c IB102 Automaty, gramatiky a složitost, 16.11.2015 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, 16.11.2015 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 5 je definována takto: D S(q, a, e) = {(g, a)} pro všechna a e Y. 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, 16.11.2015 4/27 krok výpočtu odpovídající pravidlo z Q (q, 1 + 1*1, ±) i (9, +/' * /', -L0 F^i 1 6 (Q, +' * T ^ F e (9, +/' * /', E-f T £ (9, +/' * /', + (9, /' * /', / (9, */', ±E + /) F -w £ (9, */', ±E+F) T ^ F £ (9, */', ±E+T) * (Q, i, ±E+ T*) / (9, e, ±E+T* i) F ^ i £ (Q, e, ±E+T*F) £ (Q, e, ±E+T) £ (Q, e, £ (r, e, e) IB102 Automaty, gramatiky a složitost, 16.11.2015 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, 16.11.2015 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, 16.11.2015 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, 16.11.2015 8/27 Sjednocení Li je generován CFG Q\ = (A^, Z-i, PA, Si) a Z-2 je generován CFG £2 = (Afe, 5I2, P2, S2). Bez újmy na obecnosti můžeme předpokládat ^ n A/2 = 0. Definujeme ^ = (A/1uA/2u {S}, Z1 u Z2, P, S), kde S je nový symbol a P=P1uP2u{S^S1,S^ S2}. Každá derivace v Q začne použitím buď S ^ nebo S S2. Podmínka n A/2 = 0 zaručí, že při použití S Si (resp. S S2) lze v dalším derivování používat jen pravidla z P1 (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 L| n Z-2 = {anbnď | 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: Li n Z-2 = co-(co-Li 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, 16.11.2015 13/27 Průnik s regulárním jazykem L = L(V),kdeV\e PDA V = (d, e, r, ^, ^,Z0, F,) Pi = L(.A), kde 4 je deterministický FA A = (O2,51,52, (fe, P2) Sestrojíme PDA V' takový, že L(P') = LnR V = (Q7ZJ75,q0,Z0,F), kde ■ Q = O1 x Q2 ■ qf0 = (qfi, g2) ■ F = F| x F2 ■ 5 : pro každépe O^c/e Q2, aelu{e}, Z e r platí: <5«p,(7>,a,Z) = {((p',qO,7) I (éAt) € MA^z) a 52{q,a) = q1} Zřejmě platí w e L(V) ^ we L(V) n L{A). IB102 Automaty, gramatiky a složitost, 16.11.2015 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(g) = 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, 16.11.2015 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 uv'wx'y, je tedy nekonečný. IB102 Automaty, gramatiky a složitost, 16.11.2015 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, |iwx| < q a uvlwxly e L(Q) 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 UWYI > (p + q) - Q = P- Tec|y t/^y e , 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, 16.11.2015 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, 16.11.2015 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, 16.11.2015 19/27 Deterministické zásobníkové automaty Definice 3.72. Řekneme, že PDA M = (Q, Z, r, 5, q0, Z0, F) je deterministický (DPDA), jestliže jsou splněny tyto podmínky: D pro všechna q e Q a Z e V platí: kdykoliv 5(q, e, Z) 7^ 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, 16.11.2015 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, 16.11.2015 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 r} zásobník neomezeně roste při ^-krocích během posloupnosti č-kroků jeho délka vzroste o více než r • s • t IB102 Automaty, gramatiky a složitost, 16.11.2015 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, 16.11.2015 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, 16.11.2015 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 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: Li 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, 16.11.2015 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, 16.11.2015 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, 16.11.2015 27/27