Kapitola 6 LL gramatiky 6.1 Definice LL(k) gramatik Definice 6.1. Nechť G = (N, E, P, S) je CFG, k > 1 je celé číslo. Definujme funkci FIRSTS : (JV U £)+ -»• P({w G S* | |w| < fc}) předpisem FIRSTS (a) = {w G S* | (a =^* w A \w\ < k) V (a =^* wx A |w| = k A x G £*)} a funkci FOLLOW^ : iV -»• P({w G S* | \w\ < k}) předpisem FOLLOW%(A) = {wgS*|5^* 7Aa, w G FIRST^(a)}. Nechť dále w = aia2 ■ ■ ■ an je libovolný řetěz. Pak klademe Íai ... cik k < n iw k > n Poznámka 6.2. Nechť relace =^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álních řetězů, tj. například platí: FOLLOW^ (A) = {«jgE*|5^ xAa, w G FIRST^(a)}. K tomu stačí indukcí ověřit následující dvě tvrzení (při obvyklém značení a X, Y G (NUT.) *): (1) {w G S* | 7 =^2 to} = {to G S* | 7 =^n u>} a (2) je-li Y =^n • resp. =$■*, pokud nebude řečeno jinak. Definice 6.3. Nechť G = (N, E, P, S) je CFG, fc > 1 je celé číslo. Řekneme, že G je LL(k) gramatika, právě když pro libovolné dvě nejlevější derivace (w G E *) (1) S =^* wAa => wßa =^* wx (6.1) (2) S =^* 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é fc G N, jazyk L je LL(k) právě když existuje LL(k) gramatika G taková, že L = L(GÍ). 152 KAPITOLA 6. LL GRAMATIKY 6.2 Vlastnosti LL gramatik Věta 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 E 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 k : 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, S, 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 7^* e, nechť« =^* v,v E £+, a A =^+/3 =^* w, kde /3 7^* Aa (použití pravidla, které již nevede k levé rekurzi A =>• * Aa). Pak existují levé derivace: (1) 5 =>*iüAa' =^* wAe/c/ =^+ wßotoL =^* wuvka' (2) 5 =^*wAc/ =^* wiafca' =^+ wiafc+1a' =^* urn^+V . 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 =>• +/3, použito nějakého pravidlapi, 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 jiného pravidla p2, které k levé rekuzi vede. Tedy pí / p-2 a G není LL(fc). D Věta 6.6. Nechť G = (N, T,, P, S) je CFG. Pak G je LL(k) právě když platí podmínka: Jsou-li A —► ß a A —► 7 í/vé libovolná různá pravidla v P, pak pro všechny nejlevější větné formy wAa platí: FIRSTk(ßa) n FIRSTk(ia) = 0. Důkaz: Předpokládejme, že existují w, A, a, ß, 7 tak, j ak uvedeno výše, ale FIRST k (/3a) n FIRST k(ja) / 0. Nechť x e FIRST k(ßa) n FIRST k(ja). Odtud (a z předpokladu o wAa a z definice funkce FIRST) plyne existence dvou derivací S =^*wAa =>- to/?« =^* u>:ry S1 =^*u>Aoí =>- wja =^* wxz a současně k : xy = k : xz, protože x E FIRST k(ßa) n FIRST'^(70) (je-li |x| < fc, pak y = e = z). Jelikož máme ß / 7, pak G není LL(k). Naopak, předpokládejme, že G není LL(k). To jest, existují dvě různé derivace S =^*wAa =>- tľ/3a =^* tra S =^*wAa =>- 107« =^* toy takové, že fc : x = fc : y, ale ß / 7. Tedy A —► /3 a A —► 7 jsou dvě různá pravidla, ale množiny FIRST k(ßa) a FIRSTk ('jot) nejsou disjunktní - obě obsahují řetěz fc : x. D 6.3. SYNTAKTICKÁ ANALÝZA LL(1) GRAMATIK 153 Důsledek 6.7. Necht G = (N, S, P, S) je CFG bez e-pravidel. Pak G je LL(1) právě když \/A E N a pro každá dvě různá A-pravidla A —► ß, A —► 7 z P platí FIRSTS) n FIRSTS) = 0. Důkaz: Jelikož ß 7^* e a 7 7^* e, pak Va. FZRSTi (/3a) n F/ß5Ti (7a) = FIRST\ (ß) n FližSTi (7). D Věta 6.8. Necht'G = (N, E, P, 5) je CFG. G je LL(1) gramatika právě když M A E N a pro každá dvě různá A-pravidla A —► ß, A —► 7 z P platí FIRST\(ßFOLLOW\(A)) n FIRST^FOLLOW^Ä)) = 0 (6.5) Důkaz: Pro ß / 7 provedeme rozbor po případech: • je-li /3 =^* 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 FOLLOW 1 (A). • je-li /3 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\{ß) n FIRST\{a) / 0, právě kdyzFIRST1(ßFOLLOW1(A))nFIRST1('yFOLLOW1(A)) = 0,protože FIRSTS) C FOZPCWi(A). Identicky pro případ ß ^* eaj^* 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, E, P, S), kde pravidla z P jsou očíslována i = 1,..., card(P). Je-li w E 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 S$, 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 1 typu M:(iVUEU{$})x(EUe)^ { | A -► a je i-té pravidlo v P} U {odstraň, prijmi, 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. Je-li A —► a i-té pravidlo, klademe M (A, a) = pro všechna a G FIRST x (a). Je-li též e e FIRST! (a), pak M (A, b) = pro všechna b e FOLLOW! (A). V obou případech: je-li 2. M(a, a) = odstraň, pro všechna a G S . 3. M($, e) = prijmi. Automat vymaže ze zásobníku symbol $ a akceptuje. 4. M(x, a) = chyba, pro x G S, x / 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(1) 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, i > a<ß,j> pro nějaká AeJV,aeEU {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 vstupu je 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 definuj eme jako(iVUEU{$})* 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 (S$, w, e). Na K definujeme binární relaci (krok výpočtu) h takto: 1. (ax, Aj, tt) \- (ax,aj,TTÍ) jestliže M(A, a) =. 2. (ax, ďy, tt) h (x, 7, tt) (pozn.: v tomto případě je M (a, a) = odtraň). 3. (e, $,7t) h (e, £,7t) , kde (e,e,7r) je akceptující konfigurace a tt 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, tt) \- chyba Tvrzení obsažené v bodě 3 je třeba dokázat: Věta 6.9. Nechť G = (N, T,, 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, tt) <í=^ w G L(G) a tt je levý rozbor w. Důkaz: Idea důkazu: nechť M 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 M 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ů M a A). Jelikož nahrazování neterminálů na vrcholu zásobníku odpovídá levé derivaci, je tt 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. Věta 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í: VA e N. VA -»■ ß I 7. /5 # 7 : FIRSTk(ßFOLLOWk(Ä)) n FIRST k(i FOLLOW k(A)) = 0 Pro libovolné dvě levé derivace (1) 5 =^* -uMa =>- to/3a =^* tra (2) 5 =^* w'Act' => w'ia! =^* w'y (3) podmínka k : x = k : y implikuje rovnost ß = 7. Důkaz: Negace tvrzení (6.6) je ekvivaletní s tvrzením: 3A G N. 3A -»■ /3 I 7. /5 # 7 : 3y G FIRST k{ß FOLLOW k{A)) n FIRST ^FOLLOW k(A)), které je ekvivaletní tvrzení: 3AeN. 3A -»• /3 I 7 : S =>£ tu A5i, y G FIRST k (ßSi). S^w'ASa, yeFIRSTk(j52) a/5#7j 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, E, 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 E *) (1) S =^* wAa =>- wßa =^* wx (2) S =^* w'Aa' =$■ w'^a! =^* 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 G 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. LL GRAMATIKY 6.5 Příloha: algoritmy pro výpočet funkcí FIRST a FOLLOW Nechť S je abeceda, Lu L2 C S*, k > 1. Definujeme funkci 0fc : S* x S* —► S* takto: Li ©fc L2 = {to | w = k : xy pro nějaká x E L\,y E L2}. Je dána gramatika G = (N, S, P, 5) a řetězec a = Yi • Y2.....Yu kde Yx = N U S. 1) FIk(x) = {x} pro x G S 2) Výpočet FIk (x) pro x G iV: Nechť iV = {Xx,X2,... ,Xn}. Budeme počítat hodnotu FIk(Xí) současně pro všechny neterminály (i = 1,..., n). Nechť všechna pravidla pro neterminál X í jsou tato: Xi^Y?...YŽ1\Y?...Y*2\...\Y>...Y>i Potom FIk(Xi) = [ FIk{Y?) (Bk FIk(YÍ) 0fc ... 0fc FIk{Yk\) ] U ... U [ FIk(Yl) ®k FIk(YÍ) efc ... 0fc FIk(Yk\) ]. Hodnoty FIk (Xi) jsou pevnými body uvedené soustavy rekurzivních rovnic. Počáteční hodnoty j sou FIk(Xi) = 0. 3) FIRSTk(a) = F4(Yi) (Bk FIk(Y2) 0fc • • • 0fc FIk(Y) Je dána gramatika G = (N, Y*, P, S). Funkce -FO je definována pro A E N. Postupně počítáme hodnoty: FOi(A) pro všechny A E N, F02 (A) pro všechny A E N FOk(A) pravš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 ß / e FOt(A) ■= FOt(A) U [(FIi(ß) - {e}) ©, FO^B)] 3) OPAKUJ Pro každé pravidlo tvaru: B —► «A/3 G P, kde /3 = e nebo e G FYi (/3) FO,(A):=FO,(A)UFO,(P) Tak dlouho, dokud se nedosáhne pevného bodu. 6.6. TRANSFORMACE GRAMATIK DO LL(1) TVARU 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