Konstrukce LR analyzátorů je v matematické informatice automatizovaný proces konstrukce LR syntaktických analyzátorů (). Pro jejich složitost je obtížné naprogramovat LR parsery ručně. Proto byly vytvořeny generátory analyzátorů. LR parsery jsou obvykle implementované jako analyzátory řízené tabulkou analyzátoru – jednotlivé typy se liší hlavně metodou konstrukce této tabulky.
Konstrukce tabulky pro LR(0) analýzu
Jako příklad použijeme následující gramatiku:
(1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1
Položky
Konstrukce tabulky analýzy vychází z konceptu LR(0) položek (). Tyto položky vzniknou z pravidel formální gramatiky doplněním tečky na libovolné místo na pravé straně pravidla. LR(0) položka má obecně tvar [A→β1•β2] kde (A→β1β2) je pravidlo gramatiky. Například k pravidlu (E → E + B) existují 4 položky:
E → • E + B E → E • + B E → E + • B E → E + B •
K pravidlům tvaru A → ε existuje jen jedna položka A → •. Položky slouží k vyznačení stavu syntaktického analyzátoru. Například položka [E → E • + B] znamená, že analyzátor rozpoznal ve vstupním proudu řetězec odpovídající neterminálu E (vygenerovaný z tohoto neterminálu) a nyní očekává na vstupu symbol '+', za kterým se nachází řetězec odpovídající neterminálu B.
Množiny položek
Stav analyzátoru obvykle není možné popsat jedinou položkou, protože analyzátor zpravidla neví předem, které pravidlo použije pro redukci. Pokud například existuje také pravidlo (E → E * B) pak po načtení řetězce odpovídajícího neterminálu E budou použité obě položky, které mají tečku za E: [E → E • + B] a [E → E • * B]. Proto je stav analyzátoru určen množinou položek, v našem případě množinou { E → E • + B, E → E • * B }.
Uzávěr množiny položek
Položka s tečkou před neterminálním symbolem, jako E → E + • B, označuje, že parser má zpracovat B jako následující neterminální symbol. Množina položek musí obsahovat všechny položky popisující stav konečného automatu, v němž začíná zpracování symbolu B. To znamená, že pokud existují taková pravidla jako B → 1 a B → 0, pak množina položek musí obsahovat také B → • 1 a B → • 0. Toto pravidlo funguje rekurentně: pokud položka, kterou přidáváme, obsahuje tečku (bezprostředně) před neterminálním symbolem, je třeba doplnit položky pro tento symbol. Obecně je to možné zformulovat takto:
Každá množina položek může být tímto způsobem rozšířena tím, že opakovaně doplňujeme další položky, ve kterých je neterminální symbol předcházený tečkou, dokud je možné další přidávat. Toto rozšiřování množiny položek nazýváme vytvořením uzávěru () množiny položek a uzávěr množiny položek S označujeme Closure(S). Každá množina položek, které jsou dosažitelné z počátečního stavu, bude tvořit stav analyzátoru.
Algoritmus konstrukce uzávěru Closure(S) vypadá takto: opakuj pro každou položku [A → α•Bβ] ∈ S pro každé pravidlo (B → η) přidej do množiny S položku [B → •η] dokud bylo něco přidáno do množiny S.
Zúplněná gramatika
Než začneme popisovat přechody mezi stavy analyzátoru, je třeba rozšířit gramatiku o dodatečné pravidlo:
(0) Z → E
Kde Z je nový počáteční symbol. Analyzátor použije toto pravidlo pro redukci pouze v okamžiku, kdy bude přijat celý vstupní text. Zúplnění gramatika je nutné, pokud se počáteční symbol objevuje v pravidlech gramatiky více než jednou.
Gramatika dostane tvar:
(0) Z → E (1) E → E * B (2) E → E + B (3) E → B (4) B → 0 (5) B → 1
Pro tuto gramatiku rozšířenou o první pravidlo definujeme množiny položek a přechody mezi nimi.
Konstrukce tabulky
Nalezení dosažitelných množin položek a přechodů mezi nimi
První krok konstrukce tabulek spočívá v popsání přechodů mezi zúplněnými množinami položek. Přechody jsou definovány tak, jako bychom měli konečný automat, který čte jak terminální tak neterminální. Počátečním stavem tohoto automatu je uzávěr první položky přidaného pravidla: Z → • E:
Množina položek 0 Z → • E + E → • E * B + E → • E + B + E → • B + B → • 0 + B → • 1
Symbol "+" před položkou označuje, že byla přidaná do množiny při konstrukci uzávěru. Původní položky, před kterými není "+", se nazývají báze množiny položek.
Vytváříme množinu J všech stavů automatu, kde každý stav je definován nějakým uzávěrem množiny položek. Na počátku je J tvořena pouze počátečním stavem S0. Začneme od S0 a postupně definujeme stavy, které jsou dosažitelné z S0. Přechody mezi množinami položek jsou tvořeny symboly (terminálními nebo neterminálními), které se objevují po tečce. V případě množiny položek s číslem 0 máme terminální symboly '0' a '1' a neterminální E a B. Nalezení množiny položek, do které lze přejít pomocí symbolu X, provádíme následujícím postupem:
Goto(Sa,X) na počátku je výsledná množina S prázdná pro každou položku tvaru [A → α•Xβ] ∈ Sa přidáme do výsledné množiny [A → αX•β], neboli pro každou položku v množině Sa, v níž je tečka před X, do množiny přidáme položku, ve které tečku přesuneme za symbol X pokud výsledná množina S není prázdná, nahradíme ji jejím uzávěrem S = Closure(S), a máme dvě možnosti: nalezli jsme v J množinu Sj, která má stejnou množinu položek; pak odstraníme S a přidáme přechod Goto(Sa,X)=Sj taková množina položek v J zatím není; pak přiřadíme nové množině další volný index k, a přidáme přechod Goto(Sa,X)=Sk.
Pro terminální symbol '0' bude výsledkem:
Množina položek 1 B → 0 •
pro terminální symbol '1':
Množina položek 2 B → 1 •
pro neterminální symbol E:
Množina položek 3 Z → E • E → E • * B E → E • + B
a pro neterminální symbol B:
Množina položek 4 E → B •
Je třeba poznamenat, že provedení uzávěru nepřidalo v žádném z těchto případů žádnou novou položku. Postup opakujeme tak dlouho, dokud nacházíme nové množiny. Pro množin položek s čísly 1, 2 a 4 neexistují žádné přechody, protože se tečka nenachází před žádným symbolem. Pro množinu položek číslo 3 vidíme, že tečka je před terminálními symboly ' *' a '+'. Pro '*' přechod povede do:
Množina položek 5 E → E * • B + B → • 0 + B → • 1
a pro '+':
Množina položek 6 E → E + • B + B → • 0 + B → • 1
Pro množinu položek číslo 5 musíme probrat terminální symboly '0' a '1' a neterminální symbol B. V případě obou terminálních symbolů vidíme, že výsledné množiny jsou stejné, jako již nalezené množiny 1 a 2. Pro symbol B přechod povede do:
Množina položek 7 E → E * B •
Pro množinu položek číslo 6 musíme také probrat terminální symboly '0' a '1' a neterminální symbol B. Stejně jako v předchozím případě, jsou výsledné množiny položek pro terminální symboly stejné jako množiny 1 a 2. Pro symbol B přechod povede do:
Množina položek 8 E → E + B •
Ostatní dvě množiny položek nemají tečky před symbolem, takže přidávání nových množin ukončíme. Výsledná tabulka přechodů automatu vypadá takto:
Množina položek * + 0 1 E B012341235645127612878
Konstrukce tabulek action a goto
Na základě této tabulky a nalezených množin položek zkonstruujeme tabulky action a goto takto: sloupce pro neterminální symboly se zkopírují do tabulky goto sloupce pro terminální symboly se zkopírují do tabulky action jako akce přesunu () do tabulky action přidáme dodatečný sloupec pro '$' (konec vstupního proudu); sloupec bude obsahovat acc (přijmout) pro množiny položek obsahujícího položku Z → E •. pokud množina položek i obsahuje položku tvaru A → α • nebo A → α je pravidlem m pro m > 0, pak řádek pro stav i v tabulce action bude celý vyplněn akcí redukce rm.
Výsledkem jsou tabulky
action goto stav * + 0 1 $ E B 0 s1 s2 3 4 1 r4 r4 r4 r4 r4 2 r5 r5 r5 r5 r5 3 s5 s6 acc 4 r3 r3 r3 r3 r3 5 s1 s2 7 6 s1 s2 8 7 r1 r1 r1 r1 r1 8 r2 r2 r2 r2 r2
Poznámka o rozdílech mezi LR(0) a SLR a LALR
Všimněte si, že pouze krok 4 výše uvedené procedury vytváří akce redukce, a že všechny akce redukce musí zabírat celý řádek tabulky, což způsobuje, že redukce se provede nezávisle na dalším symbolu ve vstupním proudu. Díky tomu se jedná o tabulky LR(0): před rozhodnutím, jakou redukci použít, není třeba prohlížet další symboly na vstupu. Gramatika, která potřebuje prohlížet zatím nezpracované symboly, aby vybrala správnou redukci, bude potřebovala tabulky analýzy, jejichž řádky budou obsahovat v různých sloupcích různé akce redukce; pro konstrukci takových tabulek není výše uvedená procedura vhodná.
Procedury konstruující SLR nebo LALR analyzátor mohou vytvářet tabulky, ve kterých akce redukce nezabírá celé řádky. Tyto analyzátory proto mohou analyzovat větší množství gramatik než LR(0) analyzátory.
Konflikty při konstrukci tabulek
Automat musí být konstruovaný takovým způsobem, který zaručuje determinismus. Jednak když akce redukce jsou přidávané do tabulky action, může se stát, že ta samá buňka je vyplněná jak akcí redukce tak akcí přesun (to je konflikt přesun-redukce) nebo dvěma různými akcemi redukce (konflikt redukce-redukce). Když to se stane, znamená to, že gramatika není LR(0).
Malý příklad gramatiky, která není LR(0), s konfliktem přesun-redukce:
(1) E → 1 E (2) E → 1
Jednou z množin položek, které nacházíme, je:
Množina položek 1 E → 1 • E E → 1 • + E → • 1 E + E → • 1
a obsahuje konflikt přesun-redukce, protože v buňce tabulky action pro tento stav a symbol '1' je současně přesun do stavu 1 a redukce pravidlem 2.
Malý příklad gramatiky, která není LR(0), s konfliktem redukce-redukce:
(1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1
V tomto případě dostáváme následující množinu položek:
Množina položek 1 A → 1 • B → 1 •
Což je konflikt redukce-redukce, protože v buňkách tabulky action pro tento stav bude současně redukce pravidlem 3 a pravidlem 4.
Oba výše uvedené příklady mohou být vyřešené tak, že dovolíme, aby analyzátor používal množiny Follow pro neterminální symbol A pro rozhodnutí, zda použít jedno z pravidel A pro redukci; použijeme pravidlo A → α pro redukci, pokud následující symbol ve vstupním proudu patří do množiny Follow pro A. Takové řešení se nazývá SLR (Simple LR parser, jednoduchý LR analyzátor).
SLR tabulky
Uvažujme nevelkou gramatiku, která při vytváření LR(0) tabulek dávala konflikt redukce-redukce; gramatika po doplnění nového počátečního symbolu bude mít tvar: (0) Z → E (1) E → A 1 (2) E → B 2 (3) A → 1 (4) B → 1
Množiny First a Follow pro tuto gramatiku budou vypadat takto:
Symbol First FollowZ1$E1$A11B12
Množiny položek vypadají takto:
S0 Z → • E + E → • A 1 + E → • B 2 + A → • 1 + B → • 1
S1 = Goto(S0, E) Z → E •
S2 = Goto(S0, A) E → A • 1
S3 = Goto(S0, B) E → B • 2
S4 = Goto(S0, 1) A → 1 • B → 1 •
S5 = Goto(S2, 1) E → A 1 •
S6 = Goto(S3, 2) E → B 2 •
Při konstrukci tabulek zapisujeme přesuny do sloupců pro neterminální symboly v tabulce goto a pro terminální symboly v tabulce action jako při konstrukci LR(0) tabulky, stejně jako akceptace pro množinu položek, kde vystupuje Z → E •. Rozdíl bude při vpisování redukce, která bude vepsána pouze do těch sloupců tabulky, které odpovídají terminálním symbolům nacházejícím se v množině Follow pro symbol na levé straně pravidla, který vznikne při redukci.
Konkrétně v množině položek číslo 4 A → 1 • B → 1 • máme dvě položky s tečkou na konci, které se vztahují k pravidlu 3 (A → 1) i 4 (B → 1). Pravidlo 3 má na levé straně symbol A, pro který Follow(A) = {1} a pravidlo 4 má symbol B, pro který Follow(B) = {2}. Proto vpisujeme redukci podle pravidla 3 do sloupce terminálního symbolu 1 a redukci podle pravidla 4 do sloupce odpovídajícího symbolu 2. V množinách položek vztahujících se ke stavům 5 a 6 automatu máme redukci podle pravidel 1 a 2, které mají na levé straně symbol E, jehož množina Follow(E) = { $ }
Výsledkem jsou tabulky:
action goto stav 1 2 $ E A B 0 s4 1 2 3 1 acc 2 s5 3 s6 4 r3 r4 5 r1 6 r2
Kanonický LR(1) analyzátor