CF parsing: top-down, LL(k), recursive descent, predictive

Mondom a szitut. Megkapod melóban a taskot, hogy kéne írni mondjuk Java-hoz egy interface extractort, ami egy Java forrásfile-hoz elkészít az abban levő osztályhoz egy interface-et, ha az osztály neve ClassName, akkor az interface neve legyen IClassName, az összes metódust, amit az osztályban deklaráltunk, kapja meg az interface (konstruktort ofc nem), ha ClassName implementál valami interface-et, akkor azt extendelje IClassName,

ezt reflectionnel meg lehet csinálni

a metódus argumentumok neve legyen az interface-ben ugyanaz, mint az osztályban volt,

wat.. ok, akkor javac -parameters, aztán reflection

és a metódus deklarációjában levő kommentek is maradjanak.

hell no

Tehát ha van egy input file, hogy

class Schanyi<T> implements ITuroRudiListener<T> {

  Schanyi( String paramparam ){...}

  int getTomegAram( String kiszerint /* sokan kerdezik */ ) {

    return 42;

  }

  void setTomegAram( String ki /* ohaten */, int newValue ){

    /* TODO do something, srsly */

  }

}

akkor ebből legyen az az output, hogy

interface ISchanyi<T> extends ITuroRudiListener<T> {

  int getTomegAram( String kiszerint /* sokan kerdezik */ );

  void setTomegAram( String ki /* ohaten */, int newValue );

}

ok, challenge accepted.

A persze az lenne, ha minél több részt garantáltan működő 3rdparty toolok csinálnának és csak keveset kéne kódolni hozzá. A Java nyelv is szintaktikailag egy CF nyelvtannal leírható (azon a szinten, ahogy most szükség van erre), és ha építenénk egy parse treet a forráskódhoz, akkor abban már "csak" DOM-barangolással ki tudunk szedni minden információt. Ezúttal nem a bottom-up JFlex+CUP megoldásunkat fogjuk használni, hanem a top-down ANTLR-t izzítjuk be, hogy lássunk ilyet is.

Egy egész kis elmélet: a top-down azt jelenti, hogy a parser kiindul a nyelvtan kezdőszimbólumából, aztán minden egyes lépésben alkalmaz egy szabályt, és ezzel direktben megpróbálja levezetni a stringet, közben ha olyan, akkor backtrackelhet is. Megint megkülönböztetünk olyan parsereket, amik az input soron következő $k$ tokenjét előrenézve hoznak döntést (ahogy az LR($k$) parserek előrenéztek $k$ karaktert és ebből, meg a parser állapotából döntöttek, hogy shift legyen vagy reduce; ott a gyakorlatban $k=1$ szokott lenni), és ennek, meg az aktuális átírandó nemterminálisnak (baloldali levezetést csinálunk, vagyis mindig az első nemterminálist írjuk át - az LR($k$) parserek egyébként egy jobboldali levezetést csinálnak meg visszafele) meg esetleg a belső állapotuknak függvényében döntik el, hogy melyik szabályt hajtsák végre. Ha ezt determinisztikusan tudják csinálni, és nem kell backtrack, akkor LL($k$) parsernek hívjuk.

Nézzünk egy példát: a "végezzünk bitműveleteket" történet,

A $\to$ Conj | Conj 'V' A 

Conj $\to$ Neg | Neg '&' Conj

Neg $\to$ Atom | '-' Atom

Atom $\to$ '0' | '1' | (A)

hát még erre sincs LL($k$) parser. Miért? Mert mondjuk rögzítsünk egy $k$-t. Akkor az is egy valid kifejezés ebben a nyelvtanban, hogy ((..(0)..), meg az is, hogy ((..(0)..)V1, ahol $k$ darab nyitócsukójel van. A parser első körben azt látja mindkét esetben, hogy jön $k$ darab nyitójel, ő valami kezdőállapotban van, és az A nemterminálisból kéne elindulni, de nyilván nem tudja ebből kitalálni, hogy az A $\to$ Conj (első esetben) vagy az A $\to$ Conj 'V' A (másodikban) szabályt aktiválja. 

Persze egy LR($1$) parser simán megeszi ezt, láttuk, hogy az egész shunting yardolható operátor precedencia nyelvtanos történetek mind shift-reduce parsolhatóak. Redukálni kell, ha a parse tree stack tetején '0', '1', (A), Atom, '-' Atom, Neg '&' Conj vagy Conj 'V' A áll, meg akkor, ha Neg és a következő token nem egy '&', meg akkor is, ha Conj és a következő token nem egy 'V'. Egyébként meg shiftelni, clear.

Ha még egy kicsit tudni akarunk az LL($k$) és az LR parsolható nyelvekről, hát, az összes LL($k$) parsolható nyelv LR($1$) (bár magát a nyelvtant lehet, hogy fésülni kell hozzá egy kicsit). Tehát egy determinisztikus, konstans sok szimbólumot előrenéző top-down parsolható nyelv mindig parsolható bottom-up, egy szimbólum előrenézésével.

Persze felmerül a kérdés, hogy akkor minek foglalkozik bárki top-down parserekkel? Nos, a top-down nem szinonimája az LL($k$)-nak. A fenti nyelvre egy teljesen jó leszálló parser az, hogy

parseA(){

  ret = parseConj();

  if( peek() == 'V' ) { getch(); return A( ret, parseA() ); }

  return A( ret );

}

parseConj(){

  ret = parseNeg();

  if( peek() == '&' ) { getch(); return Conj(ret, parseConj() ); }

  return Conj( ret );

}

parseNeg(){

  if( peek() == '-' ) { getch(); return Neg('-', parseAtom() ); }

  return parseAtom();

}

parseAtom(){

  c = getch();

  switch( c ){

    case '0':

    case '1': return Atom( c );

    case '(': ret = parseA();

              if( peek() == ')' ) {

               getch(); 

               return Atom( '(', ret, ')' );

             }

    default: throw "helpful message: undefined is not a function"

  }

}

és ha megnézzük, ez a parser egyrészt determinisztikus, másrészt csak egy karaktert néz mindig előre az inputban. Az igaz, hogy a szabály illesztésének az elején még nem tudja, hogy mit kellene tegyen az alternatívák közül, de közben eldől. És ami pozitívum: mindenképp sokkal olvashatóbb ennek a parsernek a kódja, és világosabb, hogy mi miért történik (debugkor etc), mint a fentebbi shift-reduce algoritmusnál.
Tippre ez a kód a következő, ekvivalens nyelvtannak megfelelően parsol:
A $\to$ Conj ConjTail
ConjTail $\to\ \varepsilon$ | 'V' A
Conj $\to$ Neg NegTail
NegTail $\to\ \varepsilon$ | '&' Conj
Neg $\to$ '-' Atom | Atom
Atom $\to$ '0' | '1' | '(' A ')'

ami viszont már egyébként LL($1$)-nek is látszik.

A fenti parser kódot, amikor is minden nemterminálisnak kb megfelel egy metódus, ami belül eldönti, hogy melyik szabályt alkalmazzuk, és ezen metódusok a szabályoknak megfelelően kölcsönösen rekurzívan hívják egymást, recursive descent parsernek hívják. Ha ezt még ráadásul úgy is teszi, hogy backtrackre nincs szükség (mint fent), akkor pedig predictive parsernek.
Ökölszabály, hogy ha a nyelvtanunkban van $A\to A\alpha$ ún. balrekurzív szabály (vagy nemterminális), akkor azt nem lehet top-down parsolni (mert akkor a metódus olvasás nélkül végtelen ciklusban hívná magát). 

Ez OK, így van, viszont van balrekurzió-mentesítés, ami ekvivalens, balrekurzió-mentes nyelvtant ad, amire még talán lehet is top-down parsert írni. Írnék én a balrekurzió-mentesítésről is szívesen, DE most nem fogok!

Mert van az ANTLR nevű parser generátor, ami az input nyelvtanunkhoz készít egy recursive descent (egyébként egész olvasható) parsert, a legújabb változatába bele van égetve már a közvetlen balrekurzió-mentesítés is (azért az $A\to B\alpha$, $B\to A\beta$ szabályok kifognak rajta :P ), és megpróbál prediktív parsert építeni, de ha nem sikerül, akkor backtrackelő recursive descent lesz belőle.

A következő postban ANTLR-rel fogjuk megoldani a post elején feldobott kérdést és írunk egy java forrásból interface extractor kódot, amiből tényleges kódot írnunk csak pár tucat sort kell, tops. Jó lesz.

folytköv

CF parsing: nahát, egy sarokcsiszoló

avagy jé, flex.

Folytatva az előzőt, a CUP file akkor megvan.

A JFlex pedig egy lexer file-ból fog készíteni nekünk egy Lexert, ami az input Stringet, CharSequencet vagy akármit tokenekre bontja. Emlékszünk, a tokeneket Symbol példányok fogják reprezentálni, amiknek a sym mezőjükben lesz az az int, ami azonosítja a típusukat és amit a Lexer a generált symbol fileból szed ki.

Ebből ugye az is következik, hogy a Lexer forrásfile-ból látni kell a generált symbol file-t, másrészt az, hogy előbb kell futtatni a CUPot (aki megcsinálja a symbol java filet) és utána a JFlexet (aki használni fogja).

A lexer file három részből áll, amiket %% sorok választanak el egymástól. A JFlex ugyanúgy, mint a CUP, ebből a bemeneti fileból egy java forrást fog generálni, annak az elején meg jellemzően szoktak lenni importok, packagek stb, ezeket az első részbe beírjuk, a JFLex az egész részt változtatás nélkül beemeli a generált java elejére. A példában ez egy import és egy package infó.

A második részben a generálandó osztállyal kapcsolatban adhatunk meg Java-specifikus opciókat, és magának a lexernek is van néhány konfigolható opciója, ezek kerülnek ide. Minden utasítás ebben a részben egy %-kal kezdődő sorba kerül. Nem adok ebben a postban egy teljes leírást a JFLexről, csak amennyi épp ehhez a feladathoz kell, az opciók egy teljes listáját lásd a doksiban; amit most használtam:

• %class FormulaLexer - legyen ez a generált Lexer osztály neve. (enélkül a default Yylex lesz)
• %cup - a lexer osztály a CUP (amit használtunk az előző postban) által várt Lexer interface-t implementálja
• %line és %column - lexelés közben elérjük az yyline és yycolumn változókban, hogy az input hanyadik sorában és oszlopában tartunk - ez mindenképp kell a Symbol konstruktorában
• %unicode - a lexer unicodeban várja az inputot
• %public - a lexer osztály public class lesz (alapból package private)
• ami %{ ... %} sorok közé kerül, azt a JFlex a generált osztály belsejébe fogja bemásolni változtatás nélkül. Ide beírtam két Symbol konstruktort, az első value nélküli (az adattagot nem hordozó tokeneknek), a második meg kap egy value paramétert is (ez meg a VARIABLE tokennek lesz). Erre ugyan technikailag semmi szükség nem volt, de átláthatóbb kódot tudtam írni alul a harmadik rész akciókódjaiban.

A harmadik részbe kerülnek a Lexer szabályai, amik (dobpergés) reguláris kifejezések hozzájuk kapcsolt akciókódokkal. Egy sor tartalma jellemzően regex { akciókód } alakúak, ahol regex egy reguláris kifejezés, az akciókód pedig tetszőleges Java kód. Megszokhattuk már, hogy nincs Egy Mindenhol Használható Standard regex jelölés, a JFlexét nézzétek meg a doksijában. Stringeket "" közt vár és az előre definiált karakterosztályai közt szerepel pl. a [:jletter:] és a [:jletterdigit:], előbbi Java betűre, utóbbi alfanumerikusra illeszkedik. Ami a lexer file regexei közül említésre méltó még, az a [^] mint regex: ez egy negált karakterosztály, negálja a semmit, tehát bármire illeszkedik (máshol . jelölné).

A lexer motor (így ebben az egyszerű formában) a következőképp működik: az input még feldolgozatlan részének az elejére megpróbálja illeszteni az összes reguláris kifejezést (nemürest illeszt, üres token nincs) a felsoroltak közül. A leghosszabban illeszkedő regexek közül a felsorolásban legelsőt adja be találatnak és annak az akciókódját végrehajtja.

Ez például azt jelenti, hogy a file legvégén szereplő [^] regex mikor lesz találat? Egyrészt az "egy bármilyen karakter" biztos illeszkedni fog az inputra (ha még van benne betű - de ha nincs, akkor meg a Lexer egy EOF tokent ad vissza és leáll), tehát ez a regex egy hosszan illeszkedik. Ha bármelyik másik regex illeszkedik, az is legalább egy hosszan, és előbb is van felsorolva, ezért

a file végén szereplő [^] regex akciókódja pontosan akkor hajtódik végre, ha semelyik másik regex nem illeszkedik,

ezért Lexer errort visszaadni tökéletes. Ez is történik, dobok egy új Errort. Benne az yytext() függvény visszaadja azt a substringjét az inputnak, amire a találat regex illeszkedett (ebben az esetben az egy renitens karaktert). Az akciókódról egyébként azt kell tudni, hogy ha nincs benne return, akkor nem is adunk még vissza tokent: ekkor az input maradék részére megint megkeresi a leghosszabban illeszkedő, azok közül legelső regexet a motor, majd megint, egész addig, míg nem returnol valamit (praktice egy Symbol példányt) az akciókód, ekkor ez lesz a visszaadott token.

Például, az utolsó előtti sor azt mondja, hogy skippeljük a whitespacet: [ \t]+ a space vagy tab sorozat, a hozzájuk tartozó akciókód üres, tehát a Lexer ha ilyet lát, lenyeli és illeszt tovább.

Ami még nemtriviális, az ezt megelőző kód: alfával kezdődő, majd alfanumerikus szekvencia (mint pl sanyi007), ha ilyennel kezd az input, akkor hozzon létre egy VARIABLE típusú szimbólumot, aminek a value tagja legyen az yytext(), vagyis maga a string, amire illeszkedett. (Ez OK, a VARIABLE token adattagja a CUP file szerint String, tehát oké lesz minden.) Amit érdemes végiggondolni, hogy ez a sor direkt van a fölötte levő pl. "V" sor után: ha ezzel kezdenénk, akkor egy whitespace-ek közt levő V betűt is változóvá lexelnénk, mert mindkét regex illeszkedik rá egy hosszan, az győz, aki előbb szerepel a szabályok közt. Tehát a sorrend számíthat, átfedő regexek esetében ebből hosszas debugolás sülhet ki, ha az ember nem számít rá.

Ettől eltekintve a többi regex-akció pár egyértelmű: a regex egy "védett" "kulcsszó" idézőjelek közt, az akció rész pedig az adott kulcsszónak megfelelő tokent készít és ad vissza. Itt persze használjuk a generált symbol file-beli kulcsszavakat, amiket azért fogunk látni, mert ugyanabba a csomagba generáljuk e Lexert, mint a Parser Symbol osztályát.

A Lexer ennél sokrétűbben konfigolható, pl. deklarálhatunk Lexer állapotokat, és állapotonként megszabhatjuk, hogy melyik regex-akciókód párokat próbálja illeszteni lexeléskor, ha az adott állapotban van. Ez a lehetőség pl. olyankor hasznos, ha van egy lexered egy nyelvhez (pl a C-hez), de akarsz támogatni mondjuk beágyazott assembly kódot. Ekkor az alap állapotban a lexer C kódnak megfelelő tokeneket kezd feldobálni, amíg egy __asm__ tokenhez nem ér, ekkor állapotot várt, innen asm tokeneket gyárt le a másik állapotban, mígnem egy __endasm__ tokent nem lát, amikor visszavált C-be és így tovább. Erre most nincs szükségünk.
Futtassuk a JFlexet: letöltjük a weblapról éés

A generált lexer itt.

és akkor egy main kód:
FileReader reader = new FileReader( "formula.txt");
FormulaLexer lexer = new FormulaLexer( reader );
FormulaParser parser = new FormulaParser( lexer );
Symbol parsedSymbol = parser.parse();
System.out.println( parsedSymbol.value );
simán kiírja, hogy (((peti -> sanyi) & gejza0) V sanyi), ha a formula.txt tartalma (peti->sanyi)& gejza0 V sanyi (mert a Formula implementációmnak meg van csinálva a toString()-je). Tehát szépen felépíti a parse treet és a value adattagba bele is kerül a konstruált Formula objektum, ahogy képzeltük.

jó ez.

legközelebb LL(k) parserekről lesz szó és az ANTLR-ben oldunk meg egy másik taskot.

folytköv

CF parsing: LR(1), JFlex és Cup 1: CUP

Az előző postból megismert bottom-up (avagy shift-reduce) parsereket persze lehet kézzel is drótozni, és van, mikor az egy gyors megoldás.

Mármost volt olyan élményem, mikor kiadtam valakinek szakdolgozatkészítésre valamit (nálunk valami furcsa okból két féléves a szakdolgozatkészítés), valami formulás dolgot kellett (volna) csinálnia, hogy Hilbert-kalkulust, rezolúciót vagy mit, én már arra nem emlékszem, és az első félév végén azzal jött, hogy van valami adatszerkezete a formulának és már majdnem írt hozzá parsert, de bugos, meg zárójelek így meg precedencia úgy.

néztem, hogy

wtf?

mert persze lehet kézzel is írni gyorsan egy formula parsert, és ha az embernek van rutinja benne, pl. első félév elején már látott kifejezés-kiértékelő kódot (nem tudom, azt tanítjuk-e), akkor az elég gyorsan megy, meg fel lehet találni a shunting yard megfelelőjét is formula parsingra, kézzel megírni, tesztelni, etc, egész gyorsan megy biztos. (Most mondjuk ítéletkalkulus-beli formulákról legyen szó.)

De ha az ember valami strukturált dolgot akar beolvasni, amire ráadásul van némi esély, hogy a specifikáció idővel változhat (támogassa már a függvényeket / elsőrendű logikát / legyen már egy pötty operátor is etc etc), akkor érdemes lehet elgondolkodni egy parser generátor használatában, aminek az ember lényegében inputként megad egy CF nyelvtant, outputként meg kap egy Java / C++ / akármilyen kulturált forráskódot, ami elvégzi neki a parsolást.

Bottom-up generátorok régóta léteznek, és általában párban járnak: egy Lexer és egy Parser együtt. A Lexernek az a feladata, hogy az input karaktersorozatból token-szekvenciákat gyártson. Egy token egy, mondjuk úgy, szintaktikai atom, pl. lehet "szám" (amit a [\d]+(.[\d]+)? regex írhat le), vagy "azonosító" (amit meg \b\w+\b, például)), így lehet, hogy ami karaktersorozatként System.out.println(6); volt, az token szekvenciaként IDENTIFIER, DOT, IDENTIFIER, DOT, IDENTIFIER, LPAREN, NUMBER, RPAREN, SEMICOLON lesz (attól függően, hogy a Lexer milyen karakterszekvenciákból milyen tokeneket készít, de ez egy elég védhető tokenekre bontásnak látszik). Persze adat nem vész el, a tokeneknek a Lexer eltárolja leggyakrabban a kezdő- és zárópozícióját az eredeti stringben, vagy magát a substringet, amiből készült, így persze visszakaphatjuk egy alkalmas metódussal, hogy pl. a második IDENTIFIER az az "out" string volt.

Amikor a Lexer előállította a tokensorozatot, jöhet a Parser, aki számára a tokenek lesznek a terminális szimbólumok, és Parser a Lexer által szolgáltatott tokensorozatra próbál illeszteni egy parse treet.

Történetileg tán az egyik legelső Lexer-Parser pár a lex-yacc volt (yacc: Yet Another Compiler Compiler, tehát tuti nem az első :D ), őket már nagyjából leváltotta a flex-bison kombó, ezek C++ eszközök. Tavaly a flexről és a bisonról beszéltem, idén az egészen hasonló szintaktikájú, de Java alapú JFlex és CUP került elő Lexer-Parser párosnak. Ezek szépen együtt is működnek egymással, kompatibilis formátumot generálnak, ezért emlegetem őket párban.

Az érdeklődés felkeltésére azt elmondom, hogy miután megcsináltam a Formula interface-t implementáló osztályokat (az tűnt kényelmesnek, hogy legyen egy-egy osztályom minden operátorra, tehát lett egy Disjunction, egy Conjunction, egy Implication meg egy Equivalence osztály, akik konstruktorban két formulát várnak; egy Negation, aki egyet; egy True és egy False, akik singletonok, a static getInstance() metódusuk adja vissza a példányt; végül egy Variable, aki egy Stringet vár konstruktorban), a Lexer forrása ennyi, a Parser forrása pedig ennyi lett.

Kezdjük a Parser forrásával, abból több mindent értünk meg elsőre. A file elején látunk a Java-ból ismerős package, import sorokat és egy class sort is. Ahogy mondtam, a CUP egy parser generátor, tehát ebből a file-ből egy Parser osztályt fog készíteni, egy Java forrásfile-ban; ha ebben a bemeneti .cup file-ban egy import sorral találkozik, azt változtatás nélkül beemeli a generált forrásfile-ba. Ha package sorral találkozik, azt is. Alapértelmezésként egy parser.java nevű file-ba generálja a parser nevű osztályt, ha ez nem tetszik, mint ahogy nekem se tetszett, egy class sorral (class FormulaParser;) megadható a generálandó osztály neve (így FormulaParser lesz). Generálódik emellé egy szimbólum osztály is egy másik file-ba; ez alapértelmezetten sym.java lesz, ha viszont megadjuk a class nevét explicite, akkor amögé rakja, hogy "Sym" (most FormulaParserSym.java lesz a szimbólumfile is).

Ezek után megadtam a nyelvtan terminálisait és nemterminálisait. Azt már az eddigiek alapján sejtjük, hogy a terminálisok tokenek nevei lesznek, amiket a Lexer fog nekünk adni. A CUP (és a JFlex) úgy működik, hogy minden terminálist és nemterminálist egy-egy Symbol objektummal (teljes nevén java_cup.runtime.Symbol - ezért importoljuk a file elején a java_cup.runtime csomagot) reprezentál, aminek az egyes tokenek nem leszármazottai lesznek, hanem: minden egyes token típus, mint fentebb az LPAREN, RPAREN, IDENTIFIER etc kapnak egy-egy unique int ID-t (és ez kerül tulajdonképpen bele a generált FormulaParserSym.java file-ba), a Symbol osztálynak pedig van egy int sym; mezeje, ennek az értéke mondja meg az adott token / szimbólum típusát.

Továbbá, egy Symbol objektumnak egy Object value; mezeje is van, amibe tetszőleges adatot rakhatunk. Hogy ez a mező valójában milyen típusú legyen, azt a terminálisok-nemterminálisok felsorolásánál mondjuk meg: a 

8. terminal VEE, WEDGE, IMPLIES, IFF, LPAREN, RPAREN, UP, DOWN, NEGATION;
sor azt mondja, hogy ezek a tokenek nem hordoznak adatot (a típusukon kívül egyéb infót tényleg nem nagyon van mit hozzájuk csatolni), a 

9. terminal String VARIABLE;

sor pedig azt, hogy a VARIABLE tokenek adattagja egy String objektum lesz (konkrétan a változó neve, de ezt majd a Lexer megoldja). A

11. non terminal Formula formula;

sor pedig azt, hogy a "formula" egy nemterminális ebben a nyelvtanban, az adattagja pedig Formula (konkrétan formula.data.Formula) típusú, ezért kellett a file elejére az az import.

Ugorjunk egyet. Egy formula lehet változó, zárójelbe rakott formula, vagy a szokásos logikai jelekkel összekötött egyéb formulák. Erre egy CF nyelvtan:

formula $\to$ UP $|$ DOWN $|$ VARIABLE $|$ LPAREN formula RPAREN $|$ NEGATION formula $|$

         formula VEE formula $|$ formula WEDGE formula $|$

         formula IMPLIES formula $|$ formula IFF formula

ez mind szép és jó. Ezt a nyelvtant így adjuk be a CUP-nak, azaz egy $S\to\alpha | \beta$ szabályt $S::=\alpha|\beta$ formában kér, itt a "formula" a nemterminálisunk.

Formális nyelvi szempontból igazunk is lehet, hogy ez egy jó nyelvtan és pontosan a szintaktikailag oké formulákat generálja, de az a gond van vele, hogy ez a nyelvtan nem egyértelmű, pl. a $p\vee q\wedge r$-nek két parse treeje is van: az egyikben a vagyolás, a másikban az éselés a külső művelet.

Ennek megfelelően nem lehet rá determinisztikus shift/reduce parser (ami ambiguous nyelvtanokra sosincs). És tényleg: ha megpróbálunk ebből a file-ből generáltatni egy java parsert, el fog szállni. Maga a generálás kényelmes: csak letöltjük a tar.gz-zett jarokat (kettő darab jar), és a szokásos

java -jar java-cup-11b.jar nyelvtanfileneve.cup

parancsot kiadva máris kapjuk, hogy

aminek azért nem örülünk. Az előző post alapján persze teljesen világos, mi a gondja a CUP-nak: pl. az utolsó esetben ha lát egy NEGATION formula IFF alakú inputkezdeményt (ekkor a negálás és a formula a parse stack tetején vannak, az IFF pedig a következő token, amit lát), akkor ezen a ponton redukálhatna is (és a NEGATION formula-t kicserélné formula-ra), vagy shiftelhetne is (és az IFF bekerülhetne a parse stackbe), aminek azért lenne értelme, mert akkor a $\neg p \leftrightarrow q$ alakú inputot $\neg(p\leftrightarrow q)$-nak parsolná fel (shift $\leftrightarrow$, shift $q$, reduce, reduce), ha meg a redukálást preferálná, akkor $(\neg p)\leftrightarrow q$-nak (reduce, shift $\leftrightarrow$, shift $q$, reduce). Azt látjuk, hogy ha rábíznánk a konfliktus-feloldást, itt (a másik húsz shift/reduce konfliktussal egyetemben) a shiftelést preferálná. Azért dob egy errort, mert nem mondtuk neki expliciten meg, hogy jogában áll megpróbálni feloldani a konfliktusokat.

Az is világos, hogy azért vagyunk gondban, mert nincs meg a precedencia-sorrendünk (és a bal- vagy jobbasszociativitásunk) a műveletekre. Ha erre odafigyelnénk, mégpedig oly módon, hogy NEGATION > WEDGE > VEE > IMPLIES > IFF (ez a szokásos erősorrend), és úgy terveznénk meg a nyelvtanunkat, akkor precedencia-szintenként kellene bevezetnünk egy nemterminálist, a gyengébbtől az erősebb felé haladva, ahogy pl. aritmetikai kifejezésekre is szokták tanítani:

Formula       $\to$ IFF_Part $|$ IFF_Part IFF Formula

IFF_Part      $\to$ IMPLIES_Part $|$ IMPLIES_Part IMPLIES IFF_Part

IMPLIES_Part  $\to$ VEE_Part $|$ IMPLIES_Part VEE VEE_Part

VEE_Part      $\to$ WEDGE_Part $|$ VEE_Part WEDGE WEDGE_Part

WEDGE_Part    $\to$ NEGATION_Part $|$ NEGATION WEDGE_Part

NEGATION_Part $\to$ VARIABLE $|$ LPAREN Formula RPAREN

és ennyi.  Ha ezt a módszert választjuk (why not), akkor pl. azt érdemes végiggondolnunk, hogy az IFF_Part a fenti leirattal az implikációt jobbasszociatívra veszi (mert az $F\to G\to H$ inputot $F\to( G\to H)$-ként parsolja fel), a VEE_Part a konjunkciót pedig balasszociatívra, $F\wedge G\wedge H \equiv (F\wedge G)\wedge H$. Tehát attól lesz balasszociatív a műveleti jel, ha a szabály jobb oldala "szint művelet következőszint" alakú, és attól jobbasszociatív, ha "következőszint művelet szint" alakú.

Szerencsére ezt nem kell begépelnünk a CUP input file-ba, ha csak precedenciát és asszociativitást akarunk beállítani, akkor erre van parancs: a végleges változat 13. sorától kezdődő

precedence left IFF;

precedence right IMPLIES;

precedence left VEE;

precedence left WEDGE;

precedence left NEGATION;

sorok pontosan ezt adják meg: a "precedence assoc operator" alakú sorok, ahol assoc left vagy right, operator pedig egy terminális, megadják, hogy az adott terminális mint operátor milyen asszociativitású, a precedence sorok sorrendje pedig az erőviszonyukat adja meg (a legutolsóként deklarált precedencia a "legerősebben kötő", most a negálás). Ezek a sorok kicsit konkrétabban az első futtatásnál jelentkező húsz shift/reduce konfliktusra határozzák meg, hogy melyiket szeretnénk, hogy válassza a parser az adott helyen, a shiftet vagy a redukálást.

És tényleg, ez a precedencia-szabályokkal kiegészített változat már fordul. Generál is két file-t, a szimbólum és a parser java file-okat. Ha belekukkantunk a parser file-ba, látjuk, hogy ott tényleg egy mezei shift-reduce üzemel, pl. a 190. sorban láthatjuk, hogy az ÉS szabály redukálásakor egy új szimbólumot (formula nemterminálist) létrehoz, aminek a gyerekei a parse stack felső három fája lesz stb.

Ha ehhez a nyelvtanfile-hoz elkészítenénk még a jflex lexerfile-ját is, akkor amit saját kézzel írt kódból tennünk kéne, ha a user ad egy stringet azzal, hogy ez egy formula:

1. létrehozunk egy Lexer példányt, konstruktorban megkapja a paraméter stringet;
2. létrehozunk egy Parser példányt, konstruktorban megkapja a Lexert;
3. meghívjuk a Parser példány parse metódusát.

Ekkor kapunk egy Symbolt visszatérési értékként, ami az input string parse treejének gyökérszimbóluma.

No de nekünk most nem pont ez kéne: ugyan ezután bejárhatnánk a parse treet, hogy fabejárással könnyen építsünk egy neki megfelelő Formula példányt, de ezt parsolás közben kényelmesebb megcsinálni: az aktuális részfának megfelelő Formula példányt eltesszük a részfa gyökerének value tagjába. Ez eddig nem történt meg, a parsolás végén van egy derivációs fánk, aminek minden csomópontjában egy null az adattag. Az adattag beállítása a következőképp történik:

1. Minden egyes jobboldal után (de még az elválasztó | előtt) {: ... :} tagek közé írhatunk "szemantikus akciót", lényegében tetszőleges Java kódot, amit a parser akkor fog lefuttatni, ha ennek a szabálynak megfelelő redukálást hajt végre.
2. Az akció blokkján belül egy RESULT nevű változónak kell értékül adjuk, amit az épp létrehozott csúcs value-jaként látni akarunk. (A típusa persze legyen az, amit a CUP file elején az adott nemterminális adattag-típusaként megadtunk, jelen esetben mivel non terminal Formula formula volt a sor, a RESULT változónak egy Formula objektumot adhatunk értékül.)
3. Az adattag létrehozásához általában szükségünk van a közvetlen gyerekek adattagjaira. Ezeket úgy érhetjük el, hogy a jobb oldal azon szimbólumaihoz, amiknek az adatára szükségünk van, létrehozunk kettősponttal egy aliast, amit mint Java változót használunk az akció kódrészleten belül, aminek értéke az adott szimbólum adattagjának értéke lesz. Vagyis a CUP file 22. sora:
   
   formula ::= formula:f WEDGE formula:g {: RESULT = new Conjunction(f,g); :}
   

   azt mondja, hogy ez egy formula $\to$ formula $\wedge$ formula szabály, ha pedig aktiváljuk, akkor a bal oldali formula adattagja kerüljön az f, a jobb oldalié a g változóba (ezt a formula:f és formula:g részek mondják a szabály belsejében), aztán a most létrehozott nemterminális adattagja legyen egy new Conjunction(f,g) objektum (van egy formula.data.Conjunction osztályom, ami implementálja a formula.data.Formula interfészt és aminek van olyan konstruktora, ami két Formula objektumot vár).

Egyébként fordítóprogram zsargonban ha egy csúcspontnak egy attribútuma a gyerekek egyes attribútumaiból számítható (mint most a value), azt az attribútumot szintetizált attribútumnak nevezzük. (Ha meg az ős tolja lefele, akkor örökölt attribútumnak). Amikor egyébként egy CF nyelvtant csomópontonkénti adattagokkal támogatunk meg, mint ahogy CUP-ban minden csúcs kap egy value membert, akkor attribútumnyelvtanról beszélünk. A shift/reduce parserek bottom-up parsolása nem nagyon támogatja az örökölt attribútumokat (mert az őst később fogjuk létrehozni, mint a gyerekeket) parsolás közben (bár a szemantikus akciókba tetszőleges Java kódot írhatunk, tehát globális változókon keresztül a fának nem csak lentebb, de "balra" levő csúcsaiból is szerezhetünk infót), csak a szintetizáltakat, az ilyen attribútumnyelvtant pedig S-attribútumnyelvtannak hívjuk.

Futtatva megint a CUP-ot, ebből a nyelvtanfile-ból generálja ezt a parsert. Belekukkantva látjuk, hogy pl. az ÉS szabály alkalmazásakor (198-210. sor) pontosan az történik, amire számítunk: lekéri a parse tree stack top és a fentről harmadik parse tree gyökércsúcsának adattagját, elteszi az f és g változókba, létrehozza a megfelelő Conjunction objektumot (207. sor, ez az a kódrész, amit mi írtunk akció kódba), és odaadja az új node value tagjának (a 208. sor konstruktorhívásának utolsó paraméterében).

Na nem mintha bele kéne kukkantanunk bármikor is ebbe a generált file-ba. Csak annyi dolgunk van ezzel, hogy beemeljük a projectbe forrásfile-ként, példányosítsuk egy Lexerrel, hívjuk meg a parse() metódusát és az eredmény value adattagjában ott lesz a Formula objektumunk, amit az input stringből varázsolt.

Hogy ne legyen túl hosszú a blogpost, a lexert legközelebb írjuk meg és példakódot is látunk a használatukra.

folytköv

CF parsing: shift, reduce és ambiguity

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é.)

Shiftelni mindig lehet persze, amíg az input el nem fogyott. Kétféle döntéshelyzet van, amit a parsernek meg kéne oldania:

• 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?

Például ha a nyelvtanunk $A\to a$, $B\to b\ |\ ab$ (és esetleg négyezer másik szabály), és az input $ab$-vel kezdődik, akkor...

• 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 jó shift-reduce parser az ilyen felmerülő problémák esetén valami alapján sokszor el tudja dönteni, hogy merre kell menjen tovább. Amivel leggyakrabban lehet operálni:

• 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 állapotból, a következő $k$ karakterből és a parse tree stack fölső korlátos sok fájának gyökércímkéje alapján már elég sok esetben ki lehet találni, hogy mit kell csinálni és feloldani a shift-reduce vagy reduce-reduce konfliktust (de persze pl. ha a nyelvtan nem egyértelmű, akkor nem lehet, hiszen akkor van, amihez több fa is létezik, eleve feloldhatatlan a konfliktus). A gyakorlatban $k=1$ szokott lenni, csak az input soron következő karakterét látjuk, többet nem (már ASCII kódolás esetén is kezelhetetlen méretűre szorozná fel az akciótábla méretét a két karakterre előrenézés).

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.

Így például a $3+4*6-5$ kifejezésből output 3, push(+), output 4, push(*) (mert a veremben levő + gyengébb, mint az érkezett *), output 6, output * (mert a verem tetején levő * erősebb, mint az érkezett -), output + (egyforma erős, ld lentebb), push(-), output 5, pop(-) (mert már csak ez van a veremben) és kapjuk a $3 4 6 * + 5-$ stringet, vagy épp fát, ha úgy építettük.

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

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.

Input rezolváljuk szét a mobot középen

Tegnapelőtt egy fb poszt alatt volt egy agymenés arról, hogy hogyan lehetne valamelyik részéből a logika kurzusnak játékot csinálni (mert akkor aztán megtanulnák :P ), aminek folyományaképp tegnap estére összedrótoztam ezt. Röviden:

• a legkisebb objektumok a játékban színes körök, vagy üresek, vagy telik;
• a pálya közepén lévő mob ilyeneknek egy (bekarikázott) halmaza;
• a pálya alján lévő fegyvereink szintén ilyeneknek egy-egy (bekarikázott) halmaza;
• egy lépésben valamelyik fegyverünkkel rálövünk a mobra;
• alapból ha odaér a lövedékünk, akkor azt a mob lenyeli és az összes színes bigyula halmaza fogja alkotni az új mobot, aki meg is növekszik ettől, de
• halmazról van szó, ha a mobban is és a lövedékben is volt pl piros teli karika, akkor az új mobban is csak egy piros teli karika marad;
• ha két azonos színű teli és üres  karika lenne az új mobban, azok kiütik egymást;
• viszont ha több, mint egy ilyen pár van, akkor azonnal elvesztjük a játékot.
• a játék célja pedig, hogy teljesen kiürítsük a mobot, még mielőtt túlnövi a játékteret.

A játékban egyébként ha $n$-féle szín van (a színek száma egytől nyolcig állítható), akkor $n$ fegyvert kapunk és $2n$ lövésből kellene leszedjük a mobot. Hogy a mob meg a fegyverek merre és milyen gyorsan forognak, semmi szerepe nincs, azért van, hogy könnyebb legyen elrontani és elveszíteni a játékot, mert több párt alakítunk ki egyszerre.

Ha valaki már megcsinálta a logika kurzust, akkor felismerheti, hogy ez nagyon hasonlít a rezolúció nevű módszerre, amivel input konjunktív normálformákról (CNF) tudjuk megmutatni, hogy kielégíthetetlenek. Aki hiányzott: vannak 0/1 értékű logikai változók, ezek a pozitív, negáltjaik a negatív literálok, literálokat vagyolva kapunk klózokat, amiket éselve pedig a CNF-et. Például

$(p\vee\neg q)\ \wedge\ (\neg p\vee\neg q)\ \wedge\ q$

egy CNF, a változók $p$ és $q$, a literálok $p,\neg p,q,\neg q$ és a három klóz: $(p\vee\neg q)$, $(\neg p\vee\neg q)$ és $q$, a harmadik egy egyelemű, avagy unit clause.

Mivel a vagyolás és az éselés is kommutatív, asszociatív és idempotens művelet, a sorrend nem számít, és egy klózon belül hogy egy előforduló literál hányszor szerepel, az se számít. Emiatt reprezentálhatunk egy klózt mint literálok egy halmazát, egy CNF-et meg mint klózok halmazát. A fenti pl

$\{p,\neg q\},\{\neg p,\neg q\},\{q\}$

alakba kerül.

A rezolúciós algoritmusban egy ilyen alakú CNF az input és listát írunk klózokról. Egy klózt kétféle okból vehetünk fel:

• ha szerepel az input klózok közt, vagy
• ha előáll két korábban felírt klóz rezolvenseként.

Ebből a rezolvens a következőt jelenti: ha van két klózom, mondjuk $C$ és $D$, és egy olyan $p$ változóm, amire $p\in C$ és $\neg p\in D$ (akkor a két klóz $p$-n ütközik, say), akkor rezolvensük a $(C-\{p\})\cup(D-\{\neg p\})$ klóz (az ütköző literálpárokat kidobjuk, a maradékot uniózzuk).
Például $\{p,\neg q\}$ és $\{\neg p,\neg q\}$ a $p$-n ütközik, rezolvensük $\{\neg q\}$, aminek $\{q\}$-val a rezolvense a $\Box$ jelű üres klóz. Tehát a példa CNF-ünkből levezethető az üres klóz; a rezolúció helyességi és teljességi tétele azt mondja ki, hogy ez pont akkor történik, ha az input CNF kielégíthetetlen.

So far so good.

A játékban persze a színek megfelelnek egy-egy változónak, a teli karika mondjuk a pozitív literál, az üres karika a negatív literál. Ha a mobba belelövünk és lesz ütköző változó, az kiüti egymást, ez pont egy rezolvensképzés. Ha nincs, akkor simán beleolvad - hát ez ugyan nem volt a rezolúciós szabálykönyvben, de math says ha bevennénk ezt is valid szabálynak, akkor az így kapott rezolúciós variáns is helyes és teljes, szóval miért ne. Ha levezettük az üres klózt, azaz ha kiürül a mob, akkor bizonyítjuk, hogy az input kielégíthetetlen, ez OK.

Volt még az a furán hangzó kitétel, hogy egyszerre két ütköző szín game overt ad; ezt azért kellett bevenni, mert ez annak felelne meg, mintha két változó mentén "egyszerre" rezolválnánk, amit viszont a rezolúciós algoritmus nem enged és okkal nem enged: ha tehetnénk ilyet, akkor olyan esetekben is kijönne az üres klóz, mikor a formula kielégíthető. Pl. a $\{p,q\},\{\neg p,\neg q\}$ input kielégíthető, pl. $p=1,q=0$, de ha szabad lenne két változó mentén egyszerre rezolválni, akkor kijönne belőlük az $\Box$.

Viszont nem szabad, hanem kijönne belőlük rezolvensként vagy a $\{q,\neg q\}$, vagy a $\{p,\neg p\}$. Az ilyeneket (amikben van egy változó is és a negáltja is) triviális klóznak hívják és math says ilyet soha nem érdemes levezetni, ha $\Box$ kijöhet, akkor ilyen nélkül is kijön, legalább ugyanolyan gyorsan. Na ezért tehettem meg, hogy inkább letiltottam azt, hogy egyáltalán próbálkozzanak a userek ilyen esetekben a rezolválással.

Ez a játék viszont egy speciális esete a rezolúciós algoritmusnak, mert

minden lépésben a legutolsóként kapott klózt rezolváljuk egy input klózzal

amit input rezolúciónak hívnak és gyengébb, mint a "rendes" módszer, mert pl. a $\{p,q\},\{\neg p,q\},\{p,\neg q\},\{\neg p,q\}$ inputról nem tudjuk ilyen módon megmutatni, hogy kielégíthetetlen: az elején mondjuk kiválasztjuk a $\{p,q\}$ klózt, aztán mondjuk rálövünk $\{\neg p,q\}$-val, marad $\{q\}$, amire mondjuk $\{p,\neg q\}$-val, marad $\{p\}$, amire mondjuk $\{\neg p,\neg q\}$-val, marad $\{\neg q\}$, amire ha rálőhetnénk a már levezetett $\{q\}$-val, kész lennénk, de nem tehetjük, csak a négy eredeti input klózzal rezolválhatunk.
Úgy egyáltalán, mivel az üres klózhoz az kell, hogy két ellentétes polaritású egységklózt rezolváljunk, eleve csak akkor jöhet ki inputrezolúcióval az üres klóz, ha van az inputban egységklóz is.

Hogy könnyebb legyen a vizualizáció, azt találtam ki, hogy legyen egy inputrezolúciós játék, akkor mindig csak egyetlen klózt kell nyilvántartani a listából (hiszen a lista már elhagyott elemeit nem használjuk fel újra, eldobhatjuk őket), az lesz a mob mindig, és fegyvereink az eredeti input klózok. (Itt nem gondoltam bele pl abba, hogy az eredeti mob is része az inputnak, tehát a mobot ellenségként is és fegyverként is fel kéne venni, hogy teljes legyen a párhuzam az input rezolúció és a játék közt, de ez elmaradt. benéztem, na.)

Már "csak" arra volt szükségem, hogy írjak egy generátort, ami megoldható pályákat (azaz: olyan kielégíthetetlen CNF-eket, melyekre van inputrezolúciós cáfolat) készít. Persze mivel nem tudtam, hogy pontosan miket lehet legyőzni inputrezolúcióval, ezért gondolkodtam gugliztam ezt a survey cikket. Ebben (Thm 3.1) azt látjuk, hogy

ugyanazokból a CNF-ekből lehet inputrezolúcióval kihozni az üres klózt,

mint amikből unit rezolúcióval is ki lehet.

Ez egyszerűsít kicsit, mert az unit (egység) rezolúció annyi, hogy minden rezolválásnál a két klóz legalább egyike egységklóz kell legyen. Pl. a kedvenc példánk esetében, $\{p,\neg q\},\{\neg p,\neg q\},\{q\}$ először üthetjük $\{p,\neg q\}$-t $\{q\}$-val, kapunk $\{p\}$-t, aztán mondjuk $\{\neg p,\neg q\}$-t is $\{q\}$-val (itt ugye nem kell az utolsó klózt is használni mindenképp), kapjuk $\{\neg p\}$-t, ami $\{p\}$-vel együtt kiadja $\Box$-ot.

Úgy általában is igaz, hogy egységrezolúcióra a következő algoritmus működik:

• keresünk egy egységklózt;
• azzal megrezolválunk mindent, amit csak lehet;
• elfelejtjük az egységklózt, meg mindent, amiben csak szerepel ez a változó;
• ezt ismételjük, míg meg nem kapjuk az üres klózt vagy el nem fogynak az egységklózok.

Tkp ezt csináltuk az előbb is, előbb $\{q\}$-val ütöttünk mindent, amit csak lehetett, az eredeti hárommal együtt lett öt klózunk, aztán elfelejtettük közülük azokat, amikben volt $q$ vagy $\neg q$, maradt $\{p\}$ és $\{\neg p\}$, egyikkel végigrezolváltuk a világot, jött is $\Box$, hawaii.

Ha felveszek egy $n\times k$-s $A$ mátrixot, aminek egy sora egy klóz, egy oszlopa egy változó, és $A_{i,j}$ akkor $0$, ha a $j$. változó nem szerepel az $i$. klózban, $1$, ha pozitívan és $-1$, ha negatívan, akkor pl a fenti inputunk mátrixa így néz ki:
$\left(\begin{array}{rr}-1&-1\\1&-1\\0&1\end{array}\right)$, első sor $\{\neg p,\neg q\}$, második $\{p,\neg q\}$, harmadik $\{q\}$. Nyilván sorokat meg oszlopokat csereberélhetek, mert se a klózok sorrendje nem számít, se az, hogy melyik változót hanyadiknak veszem fel. Sőt, egy oszlopban átválthatom az előjeleket is (ha minden $p$-ből $\neg p$-t csinálok és viszont, akkor ugyanazok lesznek a valid rezolválós lépések és minden ugyanúgy marad, az üres klózban meg nincs $p$, az nem változik). Ezért feltehetem, hogy az egységklóz, akivel először irtom a világot, az utolsó sorban van, jobb oldalán van az $1$-es, a többi mező $0$.

Ha ezzel a klózzal rezolválok végig mindent, akkor a fölötte levő $-1$ elemeket $0$-ra állítom. Egyébként math says ha van $C_1\subsetneq C_2$, tehát egy olyan $C_1$ klóz, aminél egy $C_2$ bővebb klóz is van, akkor $C_2$-t el is dobhatom, mert $C_1$-et használni mindig jobb, mint $C_2$-t. Ezért ha van egy $\{p\}$ egységklózom, akkor feltehetem, hogy nincs $\{p,q\}$, $\{p,\neg q,r\}$ etc klózom, vagyis az egységklóz $1$-ese oszlopában nincs több $1$-es.

Ha tehát az egységklózzal végigrezolválok minden mást, akkor rajta kívül kinullázom az oszlopát. Megint átrendezve a sorokat és az oszlopokat meg az oszlopon belül az előjeleket feltehetem, hogy a második ágyúzós egységklóz az utolsó előtti sorban alakul ki, az $1$-es az utolsó előtti cella. Balra tőle nem nullázott az előző egységklóz, tehát ott eleve $0$-k voltak. Jobbra vagy volt $-1$, vagy nem, de most már nincs. Ezzel is végignullázzuk a fölötte levő $-1$-eket, $1$-es továbbra sincs az oszlopban (mert azt a klózt eldobtuk volna), alatta nem lehetett nemnulla (mert akkor az utsó sor nem lett volna egységklóz). A következő egységklóz az előző, stb; azt kapjuk, hogy egy egységrezolúcióval cáfolható "minimális" CNF mátrixa pont így nézhet ki:

$\left(\begin{array}{rrrrrr}\star&\star&\star&\star&\ldots&\star\\ 1&\star&\star&\star&\ldots&\star\\0&1&\star&\star&\ldots&\star\\0&0&1&\star&\ldots&\star\\\ldots\\0&0&0&0&\ldots&1\end{array}\right)$,

ahol $\star$ lehet $0$ vagy $-1$ minden egyes cellában, aztán ennek a sorai meg oszlopai random sorrendet kapnak, és néhány oszlopnak random inkább vesszük az ellentettjét, ennyi. Még azt is látjuk, hogy ez egy $(n+1)\times n$es mátrix kell legyen, ha $n$ változó van. Ezzel a generálást letudtam: csináltam egy ekkora mátrixot, az "átlóját" feltöltöttem $1$-esekkel, alá nulláztam, fölötte random kaptak $0$ vagy $-1$ értéket a cellák. Arra az egyre figyeltem, hogy fölösleges változó ne legyen és minden $1$-es fölött tényleg legyen $-1$ is (különben mit nulláznék).

A fenti tétel szerint tehát ha ilyen mátrixnak sor-oszlop permutálásával és oszlopok mínusz eggyel szorzásával kirakok egy CNF-et, annak lesz inputrezolúciós cáfolata, ami meg nem így néz ki, annak nem lesz (vagy van benne fölösleges klóz/változó, amit nem akartam). Már csak az volt a kérdés, hogy bármelyik elemet kinevezhetem-e mobnak

és hát nem

mert pl. ha az $\{p,\neg q\}$, $\{\neg p,\neg q\}$, $\{q\}$ inputnál épp a $\{q\}$-t nevezem ki mobnak, arra rálövök pl $\{p,\neg q\}$-val, lesz belőle $\{p\}$, amire rálövök a másikkal, lesz belőle $\{\neg q\}$, de attól meg nem szabadulok többet, mert $q$ pozitívan csak a mobban volt, de onnan már eltűnt. (Ez az az eset, ami nem jutott eszembe, hogy a mobot is fel kéne venni fegyvernek: ha $\{q\}$ fegyver is lenne, akkor itt pl megkapnánk az üres klózt.)

Ekkor eszembe jutott a lineáris és az SLD rezolúció tétele. Mind a kettő, bizony.

A lineáris rezolúció annyit jelent, hogy kiindulunk egy input klózból (ez lesz a bázisklóz) és minden egyes lépésben a legutóbb kapott klózt rezolváljuk valamivel. Nem feltétlen input klózzal, lehet a listáról is választani! Pl. a $\{p,q\}$, $\{\neg p,q\}$, $\{\neg p,\neg q\}$, $\{p,\neg q\}$ inputból kiindulunk $\{p,q\}$-ból, rálövünk a másodikkal, lesz $\{q\}$, arra a harmadikkal, lesz $\{\neg p\}$, arra a negyedikkel, lesz $\{\neg q\}$, és erre a lista második elemével, $\{q\}$-val lőve megkapjuk $\Box$-ot. De persze az input rezolúció egy speciális esete a lineárisnak. Gondolom ezért jutott eszembe.

A jó a lineáris rezolúcióban, hogy teljes, vagyis ha az input kielégíthetetlen, akkor ki lehet hozni lineáris rezolúcióval az üres klózt.
Azért nem ezt választottam implementálni, mert úgy voltam vele, hogy akkor az egész listát is tárolni kéne valahol a képernyőn, és egyre több és több fegyverrel kéne tudnunk lőni emiatt, és tartottam tőle, hogy nem fog elférni már kicsi inputokra sem. Ezért az input rezolúciót választottam és nem tartottam nyilván a listát.

Az SLD rezolúció olyan lineáris rezolúció, amiben a bázisklóz negatív (csupa negatív literált tartalmaz). A tétel azt mondja, hogy

ha az input Horn formula (minden klózban legfeljebb egy pozitív literál van),

akkor arra az SLD rezolúció teljes.

Ez azért jó most nekünk, meert

• a mátrixunk minden sorában csak egy $1$-es van, az átlón, minden más $0$ vagy $1$, tehát az input Horn formula, az első sora pedig negatív klóz, jó lesz bázisnak;
• math says, hogy Horn-formulán így indítva a lineáris rezolúciót biztos, hogy input rezolúciót fogunk csinálni. (mert a listán végig csupa negatív klóz lesz, azokat meg nem tudjuk egymással rezolválni.)
• beleértve a bázisklózt is, azt se tudjuk még egyszer felhasználni (tehát a mobot nem kell felvenni a fegyverek közé).

Tehát összesen annyi dolgom volt, hogy az első sort ne cserélgessem el, csak a többit csereberéljem, az oszlopokat tetszés szerint cserélgessem és váltsam át az előjeleiket, majd az első sort nevezzem ki mobnak, a többit fegyvernek. Minden megoldható feladvány így generálható, és tuti megoldhatót generálok.

Hogy lehessen veszíteni a játékban, beletettem lépésszám-korlátot. Fogalmam se volt, hogy hány inputrezolúciós lépésben jöhet ki az üres klóz, de belenézve a fentebb linkelt papírba azt láttam (Thm 3.2/1), hogy $2n+1$ biztos elég, ezért beállítottam a $2n$-t lépésszámnak.

Amit benéztem, az az, hogy a $2n+1$ lépésben az $n$ klóz felvétele is benne van, ami miatt $n+1$ lépés is elég kell legyen...
...sőt, arra jöttem rá ma (illetve mivel éjfél elmúlt, tegnap), hogy ha a mátrixban csináljuk az input rezolúciót úgy, hogy fentről lefelé rezolváljuk a második, harmadik,... végül az $n+1$. sorokkal (tehát az inputtal ebben a sorrendben) az első sort (a mobot), mégpedig úgy, hogy az adott sorral akkor rezolválunk, ha az átlóba eső $1$-es változója ütközik a mobban egy $-1$-gyel, egyébként nem. Akkor így $n$ lövésből megvan az üres klóz, minden fegyverrel max egyszer lövünk.

próbáljátok ki: mindig azzal a még nem használt fegyverrel lőjetek a mobra, amiben van olyan ütköző szín, ami a többi még nem használt fegyverben nincs, mindig lesz ilyen, mindegyik fegyverrel max egyszer lőttök és a végére elfogy a mob... kár.

..tehát, a játék túl könnyű, ha csak inputrezolúcióra szorítkozunk, egyszerűen azért, mert túl könnyen leírható, túl szabályos CNF-eket lehet csak legyőzni vele, amikre van egy faék bonyolultságú algoritmus (ha az input CNF-be nem dobálunk felesleges klózokat elterelés címen. mondjuk ezt még lehetne csinálni.)

A következő task tehát átírni a szabályokat, hogy ne input rezolúciót csináljunk.
hanem mondjuk általános lineárisat. ezzel több gond is lesz, pl hogy kielégíthetetlen CNF-et kell generálni valamilyen módon, minimálisat, és a listát is bele kell mesélni a játékba.. :)