CF parsing módosított CYK-val

Emlékszünk, volt a Chomsky-normálforma, amiről már ranteltem egyet, hogy hogy kéne csinálni rendesen. Csak azt nem meséltem el, hogy mire jó, vagy miért.

A felállás most az, hogy szeretnénk CF nyelvet parsolni, vagyis ha van egy CF nyelvtanunk, és egy input stringünk, akkor egy derivációs fát akarunk építeni, aminek a határa épp ez az input string. Ezt pl. ha a nyelvtan Chomsky-normálformában van, akkor a Cocke-Younger-Kasami algoritmussal, avagy CYK, meg lehet tenni. Ha a nyelvtanunkban $R$ a szabályok halmaza és $n$ hosszú az input string, mondjuk $w=a_1a_2\ldots a_n$, akkor mindezt $O(|R|n^3)$ időben elvégzi, mégpedig dinamikus programozással:

• kitölt egy $T[i][j]$ táblázatot, ahol $1\leq i\leq j\leq n$;
• a táblázat egy cellába a nemterminálisok $V$ halmazának részhalmazai kerülnek;
• az $A$ nemterminális pontosan akkor kerül $T[i][j]$-be, ha $A\Rightarrow^*a_ia_{i+1}\ldots a_j$.

Nyilván akkor vezethető le a string, ha $S\in T[1][n]$. A táblázat kitöltésére pedig:

• alapeset: $T[i][i]=\{A\in V:\ A\to a_i\in R\}$, tehát ha az $i$. betű $a$, akkor minden $A\to a$ szabály bal oldalát felvesszük.
• indukció: $T[i][j]$-be akkor kerül be $A$, ha $i<j$, ha van olyan $i\leq k\leq j$ index és $A\to BC$ szabály, melyre $B\in T[i][k]$ és $C\in T[k+1][j]$. Ehhez végig kell pörgetni a lehetséges $k$-kat és $R$-eket, tehát egy cella kitöltése $(j-i)|R|$, ezt szummázva az összes cellára kapunk egy $O(|R|n^3)$ időigényt.

Persze ettől még csak az eldöntési problémát oldjuk meg, hogy a string benne van-e a nyelvben, nekünk viszont jó lenne egy parse tree is, ha igen. Ez nem baj, annyit kell csak tennünk, hogy letároljuk minden $A\in T[i][j]$ esetén a $k$-t és az $r\in R$ szabályt is, aki alapján bekerült az $A$ ebbe a cellába (ha több ilyen $A$ is van, az egyrészt baj, mert a nyelvtan nem egyértelmű, lásd később, másrészt válassz ki egyet), és az alapján visszaépíthető lesz a szokásos módon a fa is.

Remek, mondhatnánk, van egy elemző algoritmusunk, polinomidejű, mi kell még

hát például használható időigény

mert a köbös az nem az, bárki bármit mond.

Miről van szó, mikor akarunk elemezni? Mondjuk ha van egy fordítóprogramunk, akkor az benyeli a forráskódot tartalmazó file-t mint egy stringet és izzításképp felépíti belőle a kódhoz tartozó AST-t. De azért gondoljuk már végig, hogy ha pl a gcc köbös időben menne, egy ~10kbyte-os forrásfile-nál is cca $10^{12}$ ideig kéne várnunk, mire végez? Ez testvérek közt (egy ciklusban egy lépés, pár gigahertzes gépen) félóra minimum. File-onként. Indítasz egy buildet, másnapig be se jössz, vagy hogy? :D

Szóval, hatékonyabb elemzési módszer kell.

Ha visszagondolunk a rantemre a Chomsky normálformáról, akkor ott láttuk, hogy a balettlépések közül a darabolás és az ezUTÁN elvégzett $\varepsilon$-mentesítés lineáris időben, konstansszor nagyobb nyelvtant ad vissza, a szűk keresztmetszet a láncszabály-mentesítés volt, ami négyzetes.

öm...

de mégis kit zavarnak a láncszabályok?

csak jól kéne velük bánni.

Nézzünk már magunkba, ezzel a láncszabály-mentesítéssel csinálunk egy tök redundáns nagy nyelvtant. Kb annyi értelme, mint NFA-t $\varepsilon$-mentesíteni. Ott is csak az $\varepsilon$-lezárton kéne operálni on-the-fly, legalábbis az esetek túlnyomó részében, cachelve az elérhetőséget, még úgy is kevesebb tárat eszünk, mintha végrehajtanánk az $\varepsilon$-mentesítő algoritmust..

Tehát ha a nyelvtanunkban csak a hosszú jobboldalakat tördeljük, majd $\varepsilon$-mentesítünk, de a láncszabályokat békén hagyjuk (ha vannak esetleg nem használható nemterminálisok, azokat persze még az elején eldobjuk, amiből meg csak $\varepsilon$ vezethető le, azokat töröljük a jobb oldalakról), akkor kapunk egy ekvivalens nyelvtant, amiben lesznek $A\to BC$, $A\to B$ és $A\to a$ alakú szabályok. Erre az értelemszerűen módosított CYK:

• $T[i][i]$-hez: ciklusban menjünk végig a nemterminálisokon. Ha $A\to a_i\in R$, akkor vegyük be $A$-t $T[i][i]$-be és az összes olyan $B$-t is, melyre $B$-ből $A$ levezethető láncszabályokkal;
• $T[i][j]$, $i<j$ meghatározásához ciklusban menjünk végig a nemterminálisokon. Ha $A$ még nem került bele $T[i][j]$-be, keressünk egy $A\to BC$ szabályt és $i\leq k\leq j$ indexet, amire $B\in T[i][k]$ és $C\in T[k+1][j]$. Ha ilyen van, akkor tegyük bele $A$-t $T[i][j]$-be, és az összes olyan $B$-t is, melyre $B$-ből $A$ levezethető láncszabályokkal.

A "levezethető láncszabályokkal" részt úgy oldjuk meg, hogy még elemzés előtt, a nyelvtannal együtt eltároljuk annak a transzponált láncszabály-gráfját (ne keress rá, most találtam ki ezt a nevet): csúcsok a nemterminálisok, $B\to A$ akkor él, ha $A\to B$ láncszabály a nyelvtanban. Ezután csinálhatunk egy optimalizálást: az erősen összefüggő komponenseket összerántjuk egyetlen nemterminálisba (mert pl. ha $A\to B$ és $B\to A$ is, akkor $A$-ból és $B$-ből teljesen ugyanazok a dolgok vezethetők le, minek nekik külön betű, és a nyelvtanunk is ambiguous lesz, kinek kell az), vagyis ennek a gráfnak a komponensgráfját elkészítjük, a nyelvtanunkban pedig minden nemterminálist átírunk a komponensére. Ettől az egész nyelvtan csak kisebb lehet, a letárolt gráf pedig egy körmentes (irányított ofc) gráf lesz, azaz egy DAG. Eztán ahányszor csak beteszünk valakit egy cellába, még be kell tegyük a belőle elérhetőeket ebben a gráfban, az egy darab mélységi bejárás, azzal a különbséggel, hogy ha egy már betett csúcsot érünk el, akkor annak a részfáját meg se kell nézzük, hiszen annak már minden csúcsát betettük, mikor az épp elért csúcsot is. Emiatt minden egyes nemterminálist csak egyszer járunk be, az időigény marad az $|R|n^3$-ös, csak $R$ lesz jó esetben kisebb. Persze a "nemterminálisokon végigmenni" is fordított toprend szerint érdemes, és akkor minden részfát egyszerre tudunk betenni, nem lesz fölöslegesen megjelölt kis részfa.

és akkor jó ez a módosított CYK, ami láncszabályt is támogat, csók a családnak. 

Miután ezt így kigondoltam, persze találtam egy 2009-es papírt, megjelent az Informatica Didactica c lapban (jé, van ilyen is), akik szintén. Ők ezt 2NF-nek hívják. ez egy ilyen szakma, az ember gondolkodik, aztán ha rájön bármire, rákeres és nahát, mások már megcsinálták :P Aztán rákerestem megint és más is implementálta ezt 2004-ben. Bizonyos dolgokat többször is elfogadnak tudományos helyeken. Nem kéne. Na mindegy..

örülünk, Vincent?

dehogy

hát ez ettől még köbös.

Legközelebb shift-reduce parserekről írok. Azok lineárisak, tehát gyorsak, de "persze" nem minden nyelvtanhoz van ilyen.