Kapitola 6 LL gramatiky 6.1 Definice LL(k) gramatik Definice 6.1. Nechf G = (N, S, P, S) je CFG, k > 1 je celé číslo. Definujme funkci FIRSTfr : (N U £)+ ^({w G S* | M < &}) předpisem FIRST^(a) = {m £ S* | (a =>* w A |w| < V (a m A |w| = k A x G £*)} a funkci FOLLCWjľ : N ->• T({w e S* | \w\ < k}) předpisem Poznámka 6.2. Nechf relace =>£ značí levou derivaci, jako obvykle její transitivní a reflexivní uzávěr. Není těžké ukázat, že pokud bychom v definicích funkcí FIRST a FOLL O W použili namísto =>*, obdržíme tytéž množiny terminálních řetězů, tj. například platí: FOLLOW^(A) = {w e S* | S xAa, w e FIRST^(a)}. K tomu stačí indukcí ověřit následující dvě tvrzení (při obvyklém značení a X, Y E (N U S)*): (1) {w e S* | 7 w} = {w e S* | 7 =ž>" w} a (2) je-li Y =>n ^X(3 A 7 =>* x A [3 =>* y, pak 1" xla 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. Nechf G = (N, S, P, S) je CFG, k > 1 je celé číslo. Řekneme, že G je LL(k) gramatika, právě když pro libovolné dvě nejlevější derivace (w E £*) FOLLOW%(A) = {w e E* | S =>* 7,4a, w e FIRST):(a)}. Nechf dále w = a\a,2 ■ ■ ■ an je libovolný řetěz. Pak klademe k : w (1) S =>* wAa =>• w/3qí =>* (2) S =>* juia => wja =>* wy , podmínka (3) k : x = k : y (6.1) (6.2) (6.3) implikuje rovnost /3 = 7. (6.4) 151 152 KAPITOLA 6. LL GRAMATIKY Řekneme, že gramatika G je LL právě když je LL(k) pro nějaké k E N, jazyk L je LL(k) právě když existuje LL(k) gramatika G taková, že L = L (G). 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(3a =>* wx = u (2) S =>*wAa =>• wja =>* wy = u kde A —> (3 | 7 jsou dvě různá pravidla. Pak k : x = k : y =, ale (3 7^ 7, a tedy G není LL(k). □ Věta 6.5. Je-li G levorekurzivní, pak neníLL(k) pro žádné k. Důkaz. Nechf 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, nechf a v, v E S+, a A =^+/3 u, kde (3 7^* Aa (použití pravidla, které již nevede k levé rekurzi A =>* Aa). Pak existují levé derivace: (1) S ^*wAa' wAaka' w{3aka' wuvka' (2) S =>*wAa' ^* wAaka wAak+1a ^* wuvk+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 =5>+/3, použito nějakého pravidla pi, které již nemůže vést na levou rekurzi; v odpovídajícím kroku derivace (2), konkrétně v části A =>+J4a, ale bylo použito jiného pravidla P2, které k levé rekuzi vede. Tedypí 7^ P2 aGneníLL(/j). □ Věta 6.6. Nectí G = (N, S, P, S) je CFG. Pak G je LL(k) právě když platí podmínka: Jsou-li A —> (3 a A —> 7 dvě libovolná různá pravidla v P, pak pro všechny nejlevější větné formy wAa platí: FIRSTk(f3a) n FIRSTk(-ya) = 0. Důkaz. Předpokládejme, že existují w, A, a, (3,7 tak, jak uvedeno výše, ale FIRST'k(f3a)C\ FIRSTk^a) ^ 0. Nechf x E FIRSTk{(3a) n FIRSTk(-/a). Odtud (a z předpokladu o wAa a z definice funkce FIRST) plyne existence dvou derivací S =>*wAa =>• wf3a =>* wxy S =>*wAa =>• wja =>* wxz a současně k : xy = k : x z, protože x E FIRST k(f3a) n FIRST k{la) (je-li \x\ < k, pak y = e = z). Jelikož máme (3 7^ 7, pak G není LL(k). Naopak, předpokládejme, že G není LL(k). To jest, existují dvě různé derivace 6.3. SYNTAKTICKÁ ANALÝZA LL(1) GRAMATIK 153 S =>*wAa =>• w/3a =>* wx S =>*wAa =>• wja =>* wy takové, že k : x = k : y, ale (3 ^ 7. Tedy A —> /3 a A —> 7 jsou dvě různá pravidla, ale množiny FIRST ^(Pa) a FIRSTk{la) nejsou disjunktní - obě obsahují řetěz k : x. □ Důsledek 6.7. NectíG = (N", S, P, S) je CFG bez e-pravidel. Pak G je LL(1) právě když V A E N a pro každá dvě různá A-pravidla A—yfl^—y'yzP platí FIRSTn FIRST^-y) = 0. Důkaz. Jelikož (3 e a 7 e, pak Ma. FIRST\((3a) n FIRST^a) = FIRST^(3) n FIRSTi^). D Věta 6.8. Nectí G = (N, S, P, S) je CFG. G je LL(1) gramatika právě když MA E N a pro každá dvě různá A-pravidla A—yfl^—y'yzP platí FIRST\{(3•FOLLOWí{A)) n FIRST ^FOLLOW^A)) = 0 (6.5) Důkaz. Pro (3 7^ 7 provedeme rozbor po případech: • je-li (3 =5>* e a 7 =>* e, pak G není jednoznačná. Tedy G není ĽL(k) a současně průnik (6.5) je neprázdny: je roven FOLLOW\ (A). • je-li (3 e a 7 ^4>* e, pak tvrzení platí díky důsledku 6.7. • je-li (3 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\((3) n FIRST1(a) ^ 0, pvávěkdyžFIRST^FOLLOW^A^nFIRST^FOLLOW^A)) ^ 0,protože FIRSTi(u) C FOLLOW\{A). Identicky pro případ (3 e a 7 e. □ 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 0 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 1 = 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. 154 KAPITOLA 6. LL GRAMATIKY 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 funkci1 typu M:(ÍVUSU {$}) x(SUe)^ { \ A ->• a je i-té pravidlo v P} U {odstraň, přijmi, chyba}, a je definována takto: 1. Je-li A —ya í-té pravidlo, klademe M (A, a) = pro všechna a E FIRSTi (a). Je-li též s E FIRST1 (a), pak M (A, b)= pro všechna b E FOLLOW1 (A). V obou případech: je-li 2. M(a, a) = odstraň, pro všechna a E 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(Í) 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(Í); v opačném případě by M (A, a) obsahovala dvě různé položky < a, í > a < (3, j > pro nějaká A E N, a E S U {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 podpřípadech) udělat krok dle bodu 1 definice funkce M. Nechf 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 definu-jemejako (]VUEU{$})* 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 Jí definujeme binární relaci (krok výpočtu) h takto: 1. (si, Aj, 7r) h (ax, «7, ttí) jestliže M (A, a) =< a, i >. 2. (ax, ď-f, 7r) h (x, 7,7r) (pozn.: v tomto případě je M(a, a) = odtraň). 3. (e, $, 7r) h (e, e, ir) , kde (e, e, ir) je akceptující konfigurace a ir je levý rozbor w E 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, X'j, -k) h chyba Tvrzení obsažené v bodě 3 je třeba dokázat: 1. Protože automat má jen jeden stav, v definci přechodové funkce ho neuvádíme. 6.4. SLL(K) GRAMATIKY A JEJICH ANAL ÝZA 155 Věta 6.9. Nechi G = (N, S, P, S) je LL(1) gramatika, jejíž pravidla jsou očíslována i = í,..., card(P) a nechi A s přechodovou funkcí M jsou takové, jak deňnováno výše. Pak platí: (S§,w,e) h* (e, e,ir) <í==> w E L (G) a ir je levý rozbor w. Důkaz. Idea důkazu: nechť J\í 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 J\í 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 JV (po případech dle definice přechodových funkcí automatů JV a A). Jelikož nahrazování neterminálů na vrcholu zásobníku odpovídá levé derivaci, je ir je levým rozborem w. □ 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í: M A e N. M A ß I 7. ß ŕ 7 : FIRSTk{ßFOLLOWk{A)) n FIRSTk(-yFOLLOWk(A)) = (6.6) Pro libovolné dvě levé derivace (1) S =>* wAa => w[3a =>* wx (2) S ^* w'Aa' => w'-ju1 ^* w'y (3) podmínka k : x = k : y implikuje rovnost P = 7. Důkaz. Negace tvrzení (6.6) je ekvivaletní s tvrzením: 3A e N. 3A 13 I 7. /3^7: 3y e FIRSTk{l3FOLLOWk{A)) n FIRSTk(^FOLLOWk(A)), které je ekvivaletní tvrzení: 3A e N. 3A (3 I 7 : S wASu y e FIRSTk((35i), S w'AS2, y e FIRSTkfrh) a/3 ^ 7, (6.7) což je ekvivalentní negaci trvrzení (6.7) - viz definice FIRST, FOLLOW a poznámka 6.2. □ 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: 156 KAPITOLA 6. LL GRAMATIKY 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 E £*) (1) S =>* wAa =>• wf3a =>* wx (2) S w'Aa' => w'ja' w'y , podmínka (3) k : x = k : y implikuje rovnost (3 = 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. 6.5 Příloha: algoritmy pro výpočet funkcí FIRST a FOLLOW Nechť S je abeceda, L\, L2 C T,*, k > 1. Definujeme funkci ®fe : S* x S* —> S* takto: Li ffifc L2 = {w I w = k : xy pro nějaká x E Li,y E L2}- Je dána gramatika G = (N, S, P, S) a řetězec a = Y1-Y2.....Yu kde Yx = N U S. 1) FIk(x) = {x}prox E S 2) Výpočet FIk(x) pro x E N: Nechť N = {Xi, X2, ■ ■ ■, Xn}. Budeme počítat hodnotu FI]„(Xi) současně pro všechny neterminály (í = 1,..., n). Nechť všechna pravidla pro neterminál Xi jsou tato: •\ >i!... U' ... ){...);: Potom FIk(Xi) = [ FIk(y?) ®fe FIk(Yj) @k ... ®fe FIk{Yk\) } U ... U [ FhW) ®fe FIk(Yj) ffife ... ®fe FIk(Yk\) }. Hodnoty FIk(Xi) jsou pevnými body uvedené soustavy rekurzivních rovnic. Počáteční hodnoty jsou FIk(Xi) = 0. 3) FIRSTk(a) = FIk(Y{) ®fe FIk{Y2) ®fe • • • ffife FIk(Yi) Je dána gramatika G = (N, S, P, S). Funkce FO je definována pro A e N. Postupně počítáme hodnoty: FO\ (Ä) pro všechny A e N, F02(Ä) pro všechny AeN FOk(Ä) pro všechny Ae N Při výpočtu FOi(Ä) postupujeme následovně: 6.6. TRANSFORMACE GRAMATIK DO LL(1) TVARU 157 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 —> aAf3 E P, kde (3 ^ e FOi(A) := FO^Ä) U [(F 1^/3) - {e}) ®, FO^B)] 3) OPAKUJ Pro každé pravidlo tvaru: B —> aAf3 E P, kde (3 = e nebo e e F/! FOi(A) := FOl(A) U FOl(B) Tak dlouho, dokud se nedosáhne pevného bodu. 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