Ahogy nemrég mondtam, CF nyelvtant akarunk parsolni, lehetőleg gyorsan. Van viszont egy 2002-es tétel, ami azt mondja, hogy egy $O(|G|n^{3-\epsilon})$ időigényű CF parser algoritmust mindig át lehet konvertálni $O(n^{3-\epsilon/3})$ időigényű Boolean mátrixszorzó algoritmussá. Namost mivel ha lineárist szeretnénk, ezek szerint abból lesz egy $O(n^{2.33})$ időigényű mátrixszorzás, ami ugyan elvileg lehetségesnek látszik, a ma ismert legjobb algoritmus $n\times n$-es mátrixok szorzására $O(n^{2.37})$ körül van. De ez az az eset, amikor szép jószág az ordó, de nem valami hasznos: itt a konstans szorzó valami olyan orbitálisan hatalmas, hogy még akkora mátrixokra is jobb a sima $n^3$-ös naiv algoritmus, amiknél $n$ az atomok száma az ismert univerzumban. Az ilyen algoritmusokat Lipton prof galaktikus algoritmusnak hívja, szerintem jó név.
Mindenesetre az egy elég kivitelezhetetlen tasknak tűnik, hogy bármilyen nyelvtant lineáris időben parsoljunk. Szerencsére nem akármilyen nyelvtant szeretnénk: egyrészt egyértelmű, avagy unambiguous nyelvtant elemzünk akkor, ha valami strukturált módon kimentett anyagunk van, egyetlen szemantikával, pl. xml file, forráskód egy kulturált programozási nyelven, matematikai értelemben vett formula, ilyesmik. (Ha természetes nyelvi szöveget elemzünk, akkor nagyobb a gond, a természetes nyelvek nyelvtanai nem ilyenek. Akkor CYK + Viterbi, valószínűség-maximalizálással.) Egy nyelvtan egyértelmű, ha minden stringhez legfeljebb egy parse tree tartozik. (Egy akkor, ha benne van a generált nyelvben, nulla akkor, ha nincs, ofc.)
Ha egyértelmű a nyelvtanunk, akkor pl. már az általános Earley algoritmus alapból csak négyzetes ideig fut, de ennél többet szeretnénk.
Elöljáróban mindenesetre azt elmondanám, hogy azt a nyelvtan tervezőjének a dolga biztosítani, hogy a nyelvtana "jó" formájú legyen - ugyanis az, hogy egy input CF nyelvtan egyértelmű-e vagy sem, az egy eldönthetetlen probléma. Miért? Vegyük a Post Megfelelkezési Probléma, PCP egy példányát. (A wiki ad egy elég jó példát, ha valaki nem emlékszik, mi is ez.) Tehát legyenek a dominóink az $(u_1,v_1)$, $(u_2,v_2)$, $\ldots$, $(u_n,v_n)$, ahol az $u_i$-k és $v_i$-k mondjuk az $\{a,b\}$ ábécé fölötti nemüres szavak. Készítünk egy nyelvtant, a $\Sigma=\{1,2,\ldots,n,a,b\}$ ábécé fölött:
$S\to A\ |\ B$
$A\to 1Au_1\ |\ 2Au_2\ |\ \ldots\ |\ nAu_n\ |\ 1u_1$
$B\to 1Bv_1\ |\ 2Bv_2\ |\ \ldots\ |\ nBv_n\ |\ 1v_1$
Ekkor $A$-ból levezethetőek az $i_1i_2\ldots i_k1u_1u_{i_k}\ldots u_2u_1$ alakú szavak (kezd az indexsorozattal, ami $1$-re végződik, majd fordított sorrendben az $u$-szavak konkatenációja), $B$-ből meg ugyanezek a $v_i$-s szavak. Ha az $1,i_1,i_2,\ldots,i_k$ sorozat megoldás, akkor az $i_ki_{k-1}\ldots i_11u_{i_1}u_{i_2}\ldots u_{i_{k-1}}$ szó $A$-ból is meg $B$-ből is levezethető lesz, tehát $S$-ből kétféleképp, vagyis ekkor (és pont ekkor) a nyelvtanunk nem egyértelmű. Mivel a Postnak ez a változata (hogy az első dominót kikötjük, hogy az $1$. indexű legyen) is eldönthetetlen, ezért a nyelvtan egyértelműsége is az.
Ennyi kitérő után, egy shift-reduce parser bottom-up építi fel az input stringet karakterenként beolvasva a parse treet. Kicsit konkrétabban:
- Egyszer olvassa végig az input stringet, balról jobbra.
- Nem backtrackel közben.
- Van egy verem adatszerkezete, ebbe parse treeket pusholhat.
- Kétféle műveletet hajthat végre: a shiftet és a reduce-et (redukálást).
- Egy shift lépés: az input következő betűjét feldolgozzuk: mint egy egyetlen csúcsú parse treet, betesszük a verembe.
- Egy reduce lépés: ha van egy $A\to X_1X_2\ldots X_k$ szabály a nyelvtanban, és verem tetején az utolsó $k$ darab parse tree, legyenek ők $t_1,\ldots,t_k$, gyökerei éppen $X_1,\ldots,X_k$ (sorrend persze számít, az $X_k$ gyökerű van a verem tetején), akkor popolhatjuk a veremből ezt a $k$ darab fát és lenyomhatjuk helyettük az összevont, $A(t_1,\ldots,t_k)$ fát. (Tehát egy szabályt alkalmaztunk lentről felfelé.)
- shift-reduce conflict: ha shiftelni és redukálni is tud a parser (azaz mindig, ha tud redukálni, és még nem fogyott el az input), akkor melyiket válassza?
- reduce-reduce conflict: ha többféleképp is tudna redukálni a parser, akkor melyiket válassza?
- először üres a parse tree stack, shift. Bekerül az $a$ a verembe, az input maradék része $b$-vel kezdődik.
- ekkor viszont lehet redukálni: van $A\to a$ szabályunk és a verem tetején pont $a$ a gyökércímke. Tehát valid lépés az, hogy a verem tetejéről popoljuk az $a$-t és helyette $A(a)$-t teszünk be. De valid lépés békén hagyni a stacket és inkább shiftelni. (shift-reduce kérdés)
- Mondjuk shiftelünk, akkor a veremben lesz egy $a$, fölötte egy $b$ (ezt úgy írom most, hogy ($a$, $b$) a vermünk tartalma.) Ekkor van reduce-reduce gondunk is: van $B\to b$ szabály is, tehát a veremből ($a$, $B(b)$)-t is készíthetünk, de van $B\to ab$ szabály is, tehát ($B(a,b)$)-t is.
- a parsernek egy belső állapota is van (egy véges állapothalmazból) és
- a parser előre tudja nézni a következő $k$ karaktert.
Azért egyébként, hogy ne kelljen minden egyes lépésben megnézni a parse tree stack fölső elemeinek gyökércímkéjét, lényegében ez az infó el van kódolva a parser belső állapotában is (és azért, hogy pop után is tudjuk az újonnan fölül lévő elemek gyökércímkéit, ezt a belső állapotot is nyomja lefele a verembe a parser, ahányszor csak pushol egy új fát) - de ezt nem kell tudnunk. Akit a gyakorlatban leginkább használt shift-reduce parserek, az LR(1) parserek belső működése érdekel, nézzen wikit, jó a leírás róluk (a zárójelben az $1$ a $k=1$-nek a jele, miszerint a parser egy karaktert néz előre az inputból). Egy ilyen "parser" egyébként az aritmetikai kifejezésekre fát építő (OK, nem fát épít, csak postfix jelölésre átírja az infix kifejezést, kezelve a műveleti jelek precedenciáját) shunting yard algoritmus. Maga az algoritmus nagyon egyszerű: kezel egy operátor-vermet, ahova lenyomja a még nem kiértékelt műveleteket, ez alapból üres.
- ha szám jön az inputon, azt teszi is ki outputra.
- ha operátor, akkor amíg a verem tetején erősebb operátorok vannak, azokat popolja a veremből és tegye outputra, majd nyomja le az érkezett operátort.
- a folyamat végén popolja az egész operátor-vermet.
Az egyforma precedenciánál a műveleti szimbólumok asszociativitása is szerepet játszik, bal-asszociatív a művelet, ha az $a+b+c$ zárójel nélkül $(a+b)+c$ formában kell kiértékelődjön (pl az összeadás ilyen szokott lenni), és jobb-asszociatív, ha $a+(b+c)$ formában (ilyen pl. az értékadó egyenlőség). Balasszociatív műveleteknél először pop, aztán push, jobbnál pedig push, majd a végén lesz pop. A nyitó-csukójelek a leggyengébbnek számítanak, tehát ha nyitójel jön, azt mindig push, ha meg csukójel, akkor popoljunk a veremből mindent és tegyük outputra, míg meg nem találjuk a nyitójelet, azt töröljük (ne tegyük outputra).
A shunting yard elég spécinek néz ki, de gyors, táblázat se kell hozzá a belső állapotról, sem a derivációs fák gyökerei, amikről az előbb volt szó, csak a next token és a top operátor a veremből. Ezért más bottom-up parserekbe bele szokták kódolni kézzel azokra a helyekre, ahol aritmetikai kifejezés-like részfát várnak, például a GCC magjában is (ami egyébként pont hogy egy top-down parser, nem bottom-up, amit eddig néztünk) ha a top-down rész egy aritmetikai kifejezéshez ér, átadja a vezérlést egy shunting yardos kódrésznek. (Matematikailag amit most "shunting yardos"-nak hívok, azt kb operátor precedencia nyelvtannak nevezik, ha valakit érdekel, nézzen rá.) Van egy olyan tétel is, ami azt mondja, hogy ha a CF nyelvtanunk jobb oldalai nemüresek és nincs bennük szomszédos nemterminális (Chomsky normálforma kilőve, bocs :P ), és a terminálisok közt van precedencia, akkor működik rá a shunting yard (akárhány változósra módosított változata).
Szerencsére nem kell feltétlenül kézzel írnunk nyelvtanhoz parsert (bár van, aki erre esküszik, ez ízlés dolga lehet, a GCC is egy kézzel írt parsert tartalmaz), vannak generátorok, amik egy input nyelvtanból generálnak nekünk egy (vagy több) C/C++/Java/egyéb célnyelvi parsert, ami egy stringből nekünk elkészít egy parse treet (is). Legközelebb ezek közül nézzük meg, hogy használjuk a CUPot (ami előtt a JFlexet futtatjuk, hogy legyenek tokenjeink, de ez egy másik történet lesz).
folytköv
No comments:
Post a Comment