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