Kapitola 6 LL gramatiky 6.1 Definice LL(k) gramatik Definice 6.1. Nechť G = {N, S, P, S) je CFG, k > 1 je celé číslo. Definujme funkci FIRSTS : (N U £)+ -► P({w G S* | |w| < Ä;}) předpisem FIRST f (a) = {w G S* | (a =>* w A \w\ < k) V (a =>* wx A \w\ = k A x G £*)} a funkci FOLLOWf : W -► P({w G S* | \w\ < k}) předpisem FOLLOW^ (A) = {w G S* | S ^>* jAa, w G FIRST^a)}. Nechť dále w = a,ia2 ... an je libovolný řetěz. Pak klademe . .ak k < n k > n Poznámka 6.2. Nechť relace =4>l značí levou derivaci, ^*L jako obvykle její transitivní a reflexivní uzávěr. Není těžké ukázat, že pokud bychom v definicích funkcí FIRST a FOLLOW použili =>*L namísto =>*, obdržíme tytéž množiny terminálni ch řetězů, tj. například platí: FOLLOW f (A) = {toeS*|S^ xAa, w e FIRST%(a)}. K tomu stačí indukcí ověřit následující dvě tvrzení (při obvyklém značení aI,ľe(JVUS)*): (1) {w G S* I 7 =>£ w} = {w G S* | 7 =>n w} a (2) je-li Y =>n jXß A 7 =>* x A ß =>* y, pak Y =>£ ila A a =>* y pro nějaké a. Úmluva: V dalším textu budeme i levé derivace značit symbolem =>• resp. =>• *, pokud nebude řečeno jinak. Definice 6.3. Nechť G = (N, S, P, 5) je CFG, fe > 1 je celé číslo. Řekneme, že G je LL(k) gramatika, právě když pro libovolné dvě nejlevější derivace (w G X *) (1) S =>* w4a => w/3a =>* wx (6.1) (2) 5 =>* wAa => wya =>* wy , podmínka (6.2) (3) k:x = k:y (6.3) implikuje rovnost ß = 7. (6.4) Řekneme, že gramatika G je LL právě když je LL(k) pro nějaké k G N, jazyk L je LL(k) právě když existuje LL(k) gramatika G taková, že L = L(G). 151 152 KAPITOLA 6. LL GRAMATIKY 6.2 Vlastnosti LL gramatik Veta 6.4. Každá LL(k) gramatika je jednoznačná. Důkaz: Předpokládejme, že G není jednoznačná. Pak existuje věta u g L(G), která má alespoň dvě různé levé derivace: (1) S =$~*wAa =>• wßa =>* wx = u (2) S =$~*wAa =>• wja =>* wy = u kde A —> ß | 7 jsou dvě různá pravidla. Pak A; : x = k : y =, ale ß ^ 7, a tedy G není LL(k). D Věta 6.5. Je-li G levorekurzivní, pak není LL(k) pro žádné k. Důkaz: Nechť G = (N, Y,, P, S). Buď A e N levorekursivní neterminál, tj. A =>* Aa pro nějaké a. Jestliže a =>* e, pak G není jednoznačná, a tedy ani LL(k). Jestliže a ^>* e, nechť« =>* v, v G £+, a A =>+/? =>* u, kde ß ^>* Aa (použití pravidla, které již nevede k levé rekurzi A =>• * Aa). Pak existují levé derivace: (1) S =>*wAa' =>* wAaka' =>+ wßaka' =>* wuvka' (2) 5 ^*Wj4a' =>* wia'a' =>+ wAafc+1a' =>* w/+1a' ; kde k : uvk = k : uvk+1. Současně však muselo být (viz kroky =>+) v jistém kroku derivace (1), konkrétně v části A =>• +/?, použito nějakého pravidla p 1, které již nemůže vést na levou rekurzi; v odpovídajícím kroku derivace (2), konkrétně v části A =>• + Aa, ale bylo použito j iného pravidla p 2, které k levé rekuzi vede. Tedy p 1 ^ p2aG není LL(k). D Věta 6.6. Nechť G = (N, S, P, S) je CFG. Pak G je LL(k) právě když platí podmínka: Jsou-li A —> ß a A —> 7 • w/3a =>* wxí/ a současně A; : xy = k : xz, protože x G FIRSTk(ßa) n FIRSTkha) (Íe~n M < &, pak y = e = z). Jelikož máme /? 7^ 7, pak G není LL(k). Naopak, předpokládejme, že G není LL(k). To jest, existují dvě různé derivace S =$~*wAa =>• w/3a =>* wx S* =$~*wAa =>• «rya =>* wí/ takové, že A; : x = k : y, ale ß ^ 7. Tedy A —> /? a A —> 7 jsou dvě různá pravidla, ale množiny FIRSTk(ßa) a FIRSTkha) nejsou disjunktní - obě obsahují řetěz k : x. D 6.3. SYNTAKTICKÁ ANALÝZA LL(1) GRAMATIK 153 Důsledek 6.7. NechťG = (N, Y,,P,S) je CFG bez e-pravidel. Pak G je LL(1) právě když V A G N a pro každá dvě různá A-pravidla A —> ß, A —> 7 z P platí FIRST\(ß) n FIRSTS) = 0. Důkaz: Jelikož /3 ^4>* e a 7 y=>* e, pak Va. PPržSTi (/3a) n FIRST í (7a) = F/RST1 (/?) n FIRST í (7). D Veta 6.8. NechťG = (N, S, P, 5) ;e CFG. G je LL(1) gramatika právě když VA e N a pro každá dvě různá A-pravidla A^ß, A^-fzP platí FIRST\{ßFOLLOWi{A)) n FIRST1(7FOLLOW\(A)) = 0 (6.5) Důkaz: Pro ß ^ 7 provedeme rozbor po případech: • je-li ß =>* e a 7 =>* e, pak G není jednoznačná. Tedy G není LL(fc) a současně průnik (6.5) je neprázdný: je roven FOLL O W1 (A). • je-li ß 7^* e a 7 7^* e, pak tvrzení platí díky důsledku 6.7. • je-li ß 7^* e a 7 =>* e, pak z věty 6.6 pro tento případ plyne, že G není LL(1), právě když existuje levá větná forma wAa tavová, že FIRST 1(ß) n FIRST1(a) ^ 0, právě kás/i FIRST x{ß FOLLOW liA^FIRST^ FOLLOW i{A)) = 0,protože FIRST\{a) C FOLLOW\(A). Identicky pro případß =>* e a7 7^* e. D 6.3 Syntaktická analýza LL(1) gramatik Syntaktickou analýzu LL(k) gramatik lze provádět deterministickým zásobníkovým automatem automatem (DPDA). Požadujeme však, aby v případě, že vstupní slovo patří do jazyka, automat navíc poskytl informaci o struktuře věty (například její levé odvození, či derivační strom, resp. jednoznačné zakódování tohoto stromu). Proto automat rozšíříme o možnost zápisu výstupního symbolu na (přidanou) výstupní pásku Formální definici takového automatu s výstupem ponecháváme čtenáři. Syntaktickou analýzu ukážeme nejprve pro LL(1) gramatiky, přičemž přímo vycházíme z tvrzení věty 6.8. Nechťje dána LL(1) gramatika G = (N, S,P, S), kde pravidla z P jsou očíslována i = 1,..., card(P). Je-li w G L (G), pak levým rozborem w nazveme posloupnost čísel pravidel použitých v levém odvození věty w. DPDA A provádějící LL(1) syntaktickou analýzu vět z L(G) má jeden stav, počáteční obsah zásobníku je 5$, kde S je kořen gramatiky G a $ je symbol nevyskytující se v gramatice. Automat akceptuje prázdným zásobníkem. Označme M přechodovou funkci' typu M:(jVUSU{$})x(EUe)^ { \ A -► a je i-té pravidlo v P} U {odstraň, přijmi, chyba}, a je definována takto: 1. Protože automat má jen jeden stav, v definci přechodové funkce ho neuvádíme. 154 KAPITOLA 6. LL GRAMATIKY 1. le-\iA—>a i-té pravidlo, klademe M {A, a) = pro všechna a eFIRST1(a). Je-li též e G F/ftSTi (a), pak M (A, b) =< a, i > pro všechna b e FOLLOW\ (Ä). V obou případech: je-li 2. M (a, a) = odstraň, pro všechna a G S . 3. M($, e) = přijmi. Automat vymaže ze zásobníku symbol $ a akceptuje. 4. M (x, a) = chyba, pro ieE,i/a. Uvedená přechodová funkce M se též někdy nazývá LL(1) tabulkou pro G, její část zkonstruovaná dle bodu 1 pak redukovanou LL(Í) tabulkou. Díky Větě 6.8 se snadno nahléne, že M je přechodovou funkcí deterministického PDA (s výstupem), a to právě když G je LL(1); v opačném případě by M{ A, a) obsahovala dvě různé položky a < /?, j > pro nějaká 4£JV,aeSU {e}. Činnost automatu lze neformálně popsat takto: 1. Je-li na vrcholu zásobníku neterminál, řekněme A, pak automat má (v obou pod-případech) udělat krok dle bodu 1 definice funkce M. Nechť první symbol ještě nezpracované části vstupuje a: automat provede e-krok, nahradí A na vrcholu zásobníku řetězem a a na výstup zapíše i, tj. číslo použitého pravidla A —> a. 2. Je-li na vrcholu zásobníku terminál, řekněme a a na vstupuje rovněž a, pak (tak jako u nedetermininistické analýzy shora dolů) automat přečte ze vstupu a a z vrcholu zásobníku a odstraní. 3. Je-li na vrcholu zásobníku symbol $ (indikující „prázdný" zásobník) a na vstupuje (již jen) e (indikující eof vstupního souboru), automat akceptuje (vymaže zásobník). 4. ve všech ostatních případech automat ukončí výpočet a neakceptuje. Výše uvedené úvahy lze formalizovat takto: množinu konfigurací K automatu A definujeme jako (JVU£U{$})* x (SUe)* x {1,..., card(P)}* reprezentující obsah zásobníku, dosud nepřečteno část vstupního slova a dosud vyprodukovaný výstup. Počáteční konfigurací pro vstupní slovo w je (5$, w, e). Na K definujeme binární relaci (krok výpočtu) h takto: 1. (ax, Aj, 7t) h (ax, «7, iri) jestliže M (A, a) =< a, i >. 2. (ax, 07, 7t) h (x, 7, 7t) (poza: v tomto případě je M(a, a) = odtraň). 3. (e, $, 7t) h (e, e, it) , kde (e, e, -k) je akceptující konfigurace a n je levý rozbor w G L(G). Pro ostatní konfigurace není krok výpočtu definován. Případně je možné K rozšířit o konfiguraci „chyba" a definovat: 4. (ax, X7, n) V- chyba Tvrzení obsažené v bodě 3 je třeba dokázat: Věta 6.9. Nechť G = (N', S,P, S) je LL(1) gramatika, jejíž pravidla jsou očíslována i = 1,..., card(P) a nechť A s přechodovou funkcí M jsou takové, jak definováno výše. Pak platí: (S$,w,e) h* (e,e,7r) <ŕ=> w G L (G) a n je levý rozbor w. Důkaz: Idea důkazu: nechť N je PDA provádějící nedeterministickou syntaktickou analýzu vět z L(G) zkonstruovaný dle lemmatu o nedeterministické syntaktické analýze shora dolů. Lze ověřit, že každý úspěšný výpočet automatu N lze simulovat výpočtem v A a též i obráceně, že ke každému akceptujícímu výpočtu v A existuje úspěšný výpočet automatu M (po případech dle definice přechodových funkcí automatů N a A). Jelikož nahrazování neterminálů na vrcholu zásobníku odpovídá levé derivaci, je n je levým rozborem w. D 6.4. SLL(K) GRAMATIKY A JEJICH ANALÝZA 155 6.4 SLL(k) gramatiky a jejich analýza Pozorný čtenář si jistě položil otázku, zda tvrzení Věty 6.6 nejde z případu k = 1 zobecnit na k > 1. Ukážeme, že tomu tak není. Nejprve se zabývejme podmínkou (6.5) z Věty 6.6 zobecněnou pro k > 1. Veta 6.10. Pro libovolnou redukovanou CFG G = (N, S, P, S) a libovolné k > 1 celé jsou následující dvě tvrzení (6.6) a (6.7) ekvivalentní: \/AeN. y A -► /? | 7. /? 7^ 7 : FIRST k{ß FOLLOW k{A)) n FIRST k^ FOLLOW k{Ä)) = 0 Pro libovolné dvě levé derivace (1) S* =>* wMa =>• w/3a =>* wa; (2) 5 =>* w'Aa' => w'-ya' =>* w'y (3) podmínka k : x = k : y implikuje rovnost ß = 7. Důkaz: Negace tvrzení (6.6) je ekvivaletnl s tvrzením: 3A e N. 3A -► ß I 7. /? 7^ 7 : 3y G FIRSTk{ßFOLLOWk{A)) n FIRSTk{*yFOLLOWk{A)), které je ekvivaletní tvrzení: 3A e N. 3A -► /3 I 7 : 5 =>£ wA(5i, y G FIRSTkißöi), S^*Lw'Aö.2, yeFIRSTk(>yÖ2) aßrl, což je ekvivalentní negaci trvrzení (6.7) - viz definice FIRST, FOLLOW a poznámka 6.2. D Je tedy vidět, že každá gramatika splňující podmínku (6.7) je LL(k) gramatikou, ale obrácené tvrzení neplatí: lze ukázat (viz níže), že pro každé k > 1 existuje LL(k) gramatika taková, že nesplňuje podmínku (6.7). Má tedy smysl definovat tzv. SLL(k) gramatiky, a to (například) takto: Definice 6.11. NechťG = (N, S, P, S) je redukovaná CFG, k > 1 je celé číslo, řekneme, že G je SLL(k) gramatika, právě když pro libovolné dvě nejlevější derivace (w G S *) (1) S =>* wAq! =>• wßo. =>* wx (2) S =>* w'Aa' => w'ja' =>* w'y , podmínka (3) k : x = k : y implikuje rovnost ß = 7. Řekneme, že gramatika G je SLL právě když je SLL(k) pro nějaké k e N, jazyk L je SLL(k) právě když existuje SLL(k) gramatika G taková, že L = L (G). Je tedy vidět, že syntaktická analýza SLL(k) gramatik je přímočarým rozšírením syntaktické analýzy LL(1) gramatik. Detaily (zatím) ponecháváme čtenáři. 156 KAPITOLA 6. LI GRAMATIKY 6.5 Příloha: algoritmy pro výpočet funkcí FIRST a FOLLOW Nechť S je abeceda, L1, L2 C £*, k > 1. Definujeme funkci ®k : S* x S* —> S* takto: I-i ffifc L2 = {w | w = k : xy pro nejaká x e Li,y e L2}. Je dána gramatika G = (W, S, P, S) a řetězec a = Yx ■ Y2.....Yu kde Yx = N U S. 1) FIk(x) = {x} pro x G E 2) Výpočet FIk(x) pro x e N: Nechť W = {Xi? X2,..., X„}. Budeme počítat hodnotu FIk(Xi) současně pro všechny neterminály (i = 1,..., n). Nechť všechna pravidla pro neterminál X j jsou tato: xi^y11...yfc11|ií...yfc22|...|i?'...^. Potom F4(X) = [ ŕYfcC^1) ©fc FJ^1) ©fc ... ©fc F/fcíy^) ] u ... u [ FIk{Yl) ®k FIk{Y.l) @h...@h FIk(Y^) ]. Hodnoty FIk (X) jsou pevnými body uvedené soustavy rekurzivních rovnic. Počáteční hodnoty jsou FIk(Xi) = 0. 3) FIRSTk(a) = FI^) ®k FIk(Y2) ®k ■ ■ ■ ®k FIk(Yt) Je dána gramatika G = (N, S, P, S). Funkce FO je definována pro A e N. Postupně počítáme hodnoty: FO\{A) pro všechny A e N, F02 (A) pro všechny A e N FOk(A) pro všechny A e N Při výpočtu FOi(A) postupujeme následovně: 1) FOi(S) := {e} pro počáteční neterminál S. FOi(A) := 0 pro ostatní neterminály. 2) Pro každé pravidlo tvaru: B —> aAß e P, kde ß ^ t FOi{A) := FOi{A) U [(FF(ß) - {e}) eť FO^B)] 3) OPAKUJ Pro každé pravidlo tvaru: B —> aAß e P, kde ß = e nebo e e FIľ (/?) Tak dlouho, dokud se nedosáhne pevného bodu. 6.6. TRANSFORMACE GRAMATIK DO LL(1) TVAR U 157 6.6 Transformace gramatik do LL(1) tvaru • odstranění levé rekurze • levá substituce — odstranění konfliktu FIRST-FIRST • pohlcení pravého kontextu — odstranění konfliktu FIRST-FOLLOW