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