9. gyakorlat

A gyakorlat anyaga

Az eddigi "kifejezés"-parserünk áttekintése, eggyel karbantarthatóbb struktúrába refaktorálása és a JFlex + CUPS használata.

A múlt heti parserünk

A shunting yard algoritmus múlt heti implementációjában a kulcsosztályok a ShuntingYardParser, a Token és az ExpressionTree voltak. Utóbbi kettő csak egy-egy interfész: a Token teljesen üres, az ExpressionTree pedig egy kifejezést reprezentálna fában, egy darab double evaluate(); metódust deklaráltunk neki. Ameddig eljutottunk, az a Main file-ból elolvasható, a kézzel írt parserünk ezt tudja:

String input = "10+21*3+1*3*2+5";                      //az inputot stringben kapjuk
ShuntingYardParser parser = new ShuntingYardParser();  //konstruálunk egy Parser objektumot
ExpressionTree tree = parser.parse(input);             //a bejövő stringből a Parser épít egy fát
System.out.println( tree.evaluate() );                 //amit akár ki is értékelhetünk, erre épp kiírja, hogy 84.0

A parser parse(String input) függvénye követi a shunting yard algoritmust:

output = new Stack<ExpressionTree>();       //van két member fieldünk, egy verem az outputnak, ExpressionTree-kből
tokens = new Stack<Token>();                //és egy verem az operátor tokeneknek ill. az épp építés alatt álló számnak

for(int i = 0; i < input.length(); i++ ) {  //végégmegyünk az input stringen és
  char c = input.charAt(i);                 //minden karakterét
  parseChar(c);                             //felparsoljuk
}
while( !tokens.empty() ) {                  //ha ez kész, de még van jel a műveleti veremben,
  applyOp();                                //akkor azt alkalmazzuk
}
return output.pop();                        //és elvileg az output veremben ekkor pontosan egy fa kell legyen, az eredmény

Eddig jó.

A yard lelke az applyOp() metódus, ami

• popol a token veremből egy elemet
• ha ez a token egy szám token, azt egy (egypontú) faként átrakja az output verembe
• ha műveleti jel, akkor az output verem tetejéről levesz még annyi fát, ahány változós az adott műveleti jel, és ezekből az operátor tokennel épít egy (nagyobb) expression tree-t, majd ezt lerakja az output verembe:

Ezt konkrétan így írtuk meg:

public void applyOp(){
  Token topToken = tokens.pop();                                  //kivesszük a token verem felső elemét
  if( topToken instanceof OperatorToken ) {                       //ha operátor token van a verem tetején
    OperatorToken opToken = (OperatorToken) topToken;             //azzá castoljuk -- ez egy enum osztály
    ExpressionTree right = output.pop();                          //kivesszük az output verem felső
    ExpressionTree left = output.pop();                           //két elemét, mert bináris 
    ExpressionTree newExp = null;                                 //létrehozzuk az eredmény expressiont, mert látni akarjuk a switch után is
    switch (opToken) {                                            //enum mentén lehet switchelni
      case PLUS: newExp = new AddExpression(left, right);  break; //ha PLUS token, akkor összeadást építünk belőlük
      case STAR: newExp = new MultExpression(left, right); break; //ha STAR token, akkor szorzást
      //TODO hibakezelés nem ártana
    }
    output.push(newExp);                                          //az elkészített új fát berakjuk az output verembe
  }else if( topToken instanceof NumberExpression ){               //ha nem operátor token van, hanem szám
    output.push( (NumberExpression) topToken );                   //akkor a számot berakjuk az output verembe. A NumberExpression Token is és TreeExpression is
  }
}

A fenti kódból PLUS és STAR fix tokenek, amik az OperatorToken enum osztály egy-egy példánya:

public enum OperatorToken implements Token {
    PLUS(2, true),
    STAR(1, true);

    public final int priority;                        //az enum értékek mindegyikének lesz egy saját prioritása, kisebb erősebb
    public final boolean isLeftAssoc;                 //és egy bit, hogy bal- vagy jobbasszociatív: pl az összeadás bal, mert az a+b+c-t (a+b)+c-ként értékeljük ki
    OperatorToken(int priority, boolean isLeftAssoc){ //a konstruktorban beállítjuk a mezőket a kapott értékekre
        this.priority = priority;
        this.isLeftAssoc = isLeftAssoc;
    }
}

Láthatjuk, hogy Javában az enum értékek nem puszta int-ek, mint C-ben voltak: itt az OperatorToken enum típusnak két értéke lehet, a PLUS és a STAR, előbbi tkp az összeadásjel lesz, utóbbi pedig a szorzásjel. A yardnak a tokenek kezelésekor szüksége van az egyes tokenek prioritására és asszociativitására is, ezt úgy oldottuk meg, hogy ebben az enum osztályban mezőként tároljuk el, lásd a konstruktort. Az enum osztályt az értékek felsorolásával kezdjük, pontosvessző zárja az enum utolsó lehetséges értékét, mindnek deklaráljuk a neki szükséges konstruktorhívás módját, így lesz a PLUS token prioritása 2 és bal-asszociatív, a STAR tokené pedig 1 és jobb-asszociatív.

Ez eddig nem rossz megközelítés, de ha már egyszer az OperatorToken osztályunk tud valamit az általa reprezentált műveleti jelek szemantikájáról (prioritás, asszociativitás), akkor az már nem hangzik olyan jól, hogy a Parser osztály applyOp metódusába is jut a szemantikából. Szerencsésebb lenne, ha minden egy helyen lenne és valahogy pl. ide az OperatorToken enumba tudnánk rakni azt a részletet is, hogy a PLUS token egy AddExpression-t kéne építsen, a STAR token pedig egy MultExpression-t.

Amik egyébként, AddExpression és MultExpression ilyenek:

public class AddExpression implements ExpressionTree{
    public final ExpressionTree left;
    public final ExpressionTree right;

    public AddExpression(ExpressionTree left, ExpressionTree right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public double evaluate() {
        return left.evaluate() + right.evaluate();
    }
}

public class MultExpression implements ExpressionTree {
    public final ExpressionTree left;
    public final ExpressionTree right;

    public MultExpression(ExpressionTree left, ExpressionTree right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public double evaluate() {
        return left.evaluate() * right.evaluate();
    }
}

Lényegében egy nagy copy az egész, csak az evaluate metódusban különböznek, ez is refactorért kiált, de legalább persze működik. A kifejezés fa lehet pl. egy összeadás vagy egy szorzás, amit úgy értékelünk ki, hogy rekurzívan kiértékeljük mindkét részfáját, majd az eredményeken elvégezzük az adott műveletet.

Már csak a ShuntingYardParser.parseChar(char c) függvényt nem láttuk, hogy mindent értsünk:

public void parseChar(char c) {
  if( c >= '0' && c <= '9' ) {  //jött egy számjegy. Ha Number van a tokens tetején => hozzáforrasztjuk, ha nem, pusholunk új Numbert
    if(!tokens.empty() && tokens.peek() instanceof NumberExpression ) {
      double originalTokenValue = ((NumberExpression)tokens.pop()).value;
      tokens.push( new NumberExpression(originalTokenValue * 10 + c - '0'));
    } else {
      tokens.push( new NumberExpression( c - '0' ));
    }
  }else if( c == '+' || c == '*' ) { //ha műveleti jel érkezett:
    if( !tokens.empty() && tokens.peek() instanceof NumberExpression ) {  //ha szám volt a token verem tetején
      applyOp(); //a számot a tokens verem tetejéről átrakjuk az output verem tetejére
    }
    OperatorToken currentToken = null;
    switch(c){
      case '+' : currentToken = OperatorToken.PLUS; break;
      case '*' : currentToken = OperatorToken.STAR; break;
      default: //TODO HIBAKEZELÉS
      break;
    }
    while( !tokens.empty() ) {
      Token top = tokens.peek();
      if(! (top instanceof OperatorToken) ) break;
      OperatorToken topOperator = (OperatorToken) top;
      if(topOperator.priority > currentToken.priority ) break;
      if(topOperator.priority == currentToken.priority && !topOperator.isLeftAssoc ) break;
      applyOp();
    }
    tokens.push(currentToken);
  }
}

Világos: ha jön egy számjegy, akkor megnézzük, hogy Number van-e a verem tetején, ha igen, akkor még azt a számot folytatjuk, különben pedig egy új NumberExpressiont hozunk létre ezzel a számjeggyel. Btw a NumberExpression.java is csak egy adatosztály:

public class NumberExpression implements ExpressionTree, Token {
  public final double value;
  @Override
  public double evaluate() {
    return value;
  }
  public NumberExpression(double value) {
    this.value = value;
  }
}

Ha pedig egy összeadás vagy egy szorzás jel érkezik, akkor az algoritmusnak megfelelően, először is ha eddig számépítésben voltunk, akkor az elkészített számot átrakjuk az applyOp() metódussal az output verembe. Ezt itt nem vesszük még ki, ezért peek() és nem pop(), amit hívunk. Eztán a karakterből (a switchben) elkészítjük a megfelelő tokent, majd a token veremben amíg erősebb prioritású, vagy azonos prioritású jobb-asszoc műveleti token van, azt kivesszük (a while ciklussal) és alkalmazzuk az output verem felső két fáján (hogy pont kettőn, azt az applyOp fogja tudni), végül lenyomjuk a token verembe az újonnan jött tokenünket.

Az algoritmus bővítése

Szeretnénk támogatni a két fenti alapműveleten kívül kivonást, osztást, hatványozást (ez jobb-asszoc, pl. 2^3^4 az nem 8^4, hanem 2^81), és zárójelezést is. Ha ez megvan, akkor jó lenne még negatív számokat, tizedespontokat, meg néhány neves függvényt, mint a sin, ami unáris, vagy akár a pow, ami bináris -- akkor az argumentumai közé vesszőt kérjünk. Whitespace-t is kezelnünk kéne.

Ha ez is megvan, tehetnénk bele változókat, melyeknek lehetne értéket is adni, és pontosvesszőkkel elválasztani az egyes utasításokat, pl. x=3;x+2;x+1 kiírhatná eredményképpen, hogy 3;5;4.

Ezeket épp a shunting yard algoritmus megfelelő kibővítésével is el tudjuk érni, de nézzünk erre inkább egy szoftvercsomagot, amivel az efféle CF parsing taskokat, amikor is egy parse treet akarunk építeni egy input stringből, gyorsabban és hibamentesebben meg lehet ennél oldani.

Lexer és Parser

Láthattuk, hogy a folyamatban, amit implementáltunk, három lényegi elem volt: először is kaptunk egy karakterekből álló stringet, aztán ezekből a karakterekből tokeneket építettünk, amik sok esetben egy-egy karakter (mint pl. egy összeadás, szorzás stb. operátor), de sok esetben nem:

• a Java/C-like ||, && operátorokat egy tokennek kéne kezelni;
• általában egy számból, konstansból egy darab tokent jó építeni, melynek van egy mezője, ami a szám értékét tárolja (ez történt a NumberExpression osztályunkban is);
• ha programozási nyelv forráskódját parsoljuk, akkor stringből ugyanez: egy string literálból is jobb, ha egy token készül;
• egy azonosítóból (függvény, osztály implementált interface neve) pl. egy Identifier token készülhet, aminek egy string mezőjében tárolhatjuk magát a stringet;
• ha programnyelvünk van, akkor a beépített kulcsszavakból is egy-egy token készül.

Mindez azért, hogy így, az input karaktersorozatból előálló tokensorozatot aztán hatékonyabban tudjuk kezelni szemantikailag. Ezt a folyamatot a legtöbb nyelvi elemzőben egy külön motor végzi, melyet lexernek neveznek.

Eztán a lexer által előállított tokensorozatot megkapja egy parser, ami ezeket a tokeneket tkp. mint egy CF nyelvtan terminálisait veszi, és a tokensorozathoz megpróbál építeni egy CF nyelvtannak megfelelő parse tree-t, melynek pont ez a tokensorozat a határa.

Persze mivel a lexer által generált tokeneket a parser meg kell kapja, ezért kell legyen valami token interface, amiben megállapodik lexer és parser - ezért általában egy csomag részeként tudjuk megszerezni a lexert és a parsert. Pontosabban, a lexer és parser generátorokat -- olyan toolokat, amik arra képesek, hogy a megadott nyelvtani szabályok alapján kigeneráljanak egy-egy Java forráskódot, egyet a Lexernek, egyet a Parsernek, melyeknek aztán a megfelelő metódusai hívogatásával az input stringünkből meg tudunk kapni egy parse treet.

JFlex és CUP

Ha már Javában vagyunk, az első lexer-parser generátor párunk, amit megnézünk, hogy hogy lehet használni, és amivel szintén megoldjuk ezt a kifejezés-parsoló modult, a JFlex + CUP páros lesz. A JFlex generálja nekünk a Lexert, a CUP pedig a Parsert.

Szerezzük be a két libet innen és innen. Amit én használni fogok: a jflex-1.8.2.tar.gz és a java-cup-bin-11b-20160615.tar.gz. A JFlex-et kicsomagoljuk valahova, én mondjuk a dev mappámba, amin belül van az idea projektem egy mappában, ez létrehozza a jflex-1.8.2 könyvtárat. Mellé kicsomagolom a cup tar gézában lévő két jart is, a java-cup-11b.jar és a java-cup-11b-runtime.jar jarokat.

A JFlex Maven plugin

Alapvetően a JFlex egy jflex fileból, melyben specifikáljuk, hogy milyen módon készítsen tokeneket az input stringből, készít egy Java lexer osztályt, ők Scannernek hívják. Többféle módon lehet használni (a JFlex weblapon ott a manuál), egyebek közt:

• parancssorból, kiadva a java -jar jflex-1.8.2.jar <opciók> <inputfile> parancsot
• Maven pluginként ideából gombokkal

Az utóbbit fogjuk tenni, mert kényelmes, de persze konzolból is lehet parancssorból fordíttatni a scanner javát, ha valaki ezt preferálja.

Ha esetleg úgy hoztuk létre Ideában a projektet, hogy nem Maven projektként, nem baj: a Project tool ablakban jobb klikk a project rooton, Add Framework Support és a legördülőből kiválasztjuk a Mavent. Létrejön egy pom.xml, amit innentől szerkeszthetünk, hogy miféle fileokat hogyan szeretnénk kezelni, ha megváltoznak. A jflex fileokat pl. le akarjuk fordíttatni majd a JFlexszel. Érdemes lehet adni egy groupId-t a pom.xmlben, én most ezt parsers-re raktam.

A Maven 1.5-re akarja alapból állítani a language levelt, ezt felülírjuk 1.8-ra, a pom.xml-ben, és be kell húznunk a megfelelő verziójú maven-compiler-plugint is:

<properties>
  <maven.compiler.source>11</maven.compiler.source>
  <maven.compiler.target>11</maven.compiler.target>
</properties>

majd egy jobb klikk a projekten, Maven, reload project és már le is fog fordulni az eredeti kódunk.

A JFlex főoldaláról van egy link a Maven plugin oldalára. Ahogy a Usage és a Plugin Documentation lap írja, kibővítjük a pom.xmlt:

   <build>
        <!-- To define the plugin version in your parent POM -->
        <pluginManagement>
            <plugins>
                <plugin>
                    <groupId>de.jflex</groupId>
                    <artifactId>jflex-maven-plugin</artifactId>
                    <version>1.8.2</version>
                </plugin>
            </plugins>
        </pluginManagement>
        <!-- To use the plugin goals in your POM or parent POM -->
        <plugins>
            <plugin>
                <groupId>de.jflex</groupId>
                <artifactId>jflex-maven-plugin</artifactId>
                <version>1.8.2</version>
            </plugin>
        </plugins>
    </build>

Világos, hogy mi történik, megkérjök rá, hogy használja a jflex-maven-plugint. Jobb klikk, reload és máris van egy működő JFlex pluginunk, a mavenes doksija szerint a src/main/jflex könyvtáron belül ha talál jflex filét, akkor abból generál scannert és a generált forráskódot berakja a target/generated-source/jflex könyvtárba.

Írjunk egy JFlex filet

Hozzuk létre tehát a src/main/jflex könyvtárat, majd benne mondjuk egy Expression.jflex file-t.

Egy jflex file három nagyobb részből áll, köztük egy-egy %% sorral szeparátorként.

• Az első részt változtatás nélkül be fogja másolni a generált lexer file elejére. Tipikusan ide kerül a package deklaráció, importok, ilyesmik, hogy a lexer leforduljon.

• A második részben opciókat tudunk megadni a generálással kapcsolatban. Minden opció % jellel kezdődik. Néhány példa:

  • %class ExpressionLexer - így tudjuk megadni a generált Lexer osztály nevét. (Enélkül Yylex lesz)
  • %cup - ezzel adjuk meg, hogy a generált osztályunk implementálni fogja a CUP által várt Lexer interfacet, így tudnak majd együttműködni
  • %line, %column - lexelés közben el fogjuk érni, az yyline és az yycolumn változkban, hogy az inputnak hanyadik sorában és azon belül hanyadik karakteren tartunk. Ha CUP-pal együtt akarjuk használni a lexert, akkor erre is szükség van, mert a CUP által várt tokenek a CUP esetében Symbol példányok lesznek, amiknek a konstruktora várja ezeket az értékeket.
  • %unicode - a lexer unicode karakterkódolásban kapja meg az inputot
  • %public - a lexer osztály public class legyen (alapból package privát)
  • ami %{ .. %} sorok közé kerül, azt pedig a JFlex be fogja másolni változtatás nélkül a generált osztály belsejébe.

• Végül, a harmadik részbe kerülnek a Lexer szabályai, melyek reguláris kifejezések a hozzájuk tartozó akciókkal. A legegyszerűbb esetben egy sorban regex { akciókód }-ként adjuk meg, ahol regex egy itteni nyelvi dialektusnak megfelelő reguláris kifejezés, az akciókód pedig egy tetszőleges Java kód.

A Lexer motor a következőképp működik: az input még feldolgozatlan részének az elejére megpróbálja szép sorban illeszteni a megadott reguláris kifejezéseket. Mindegyiket illeszti, némelyik illeszkedni fog, némelyik nem, ezek közül a leghosszabban illeszkedők közül a legelsőt adja be találatnak, és annak hajtja végre az akciókódját.

A legegyszerűbb esetben mindegyik akciókódban készítünk egy új tokent, ha CUPpal akarunk együtt dolgozni, akkor egy Symbolt konstruálunk és returnöljük. Ekkor a lexer ezt a tokent fel is dobja és majd a CUP ezzel dolgozni fog tovább. Ha nem returnölünk semmit, az nem baj; ekkor a motor csak végrehajtja az akciókódban szereplő utasításokat, és folytatja az input feldolgozását.

Az Expression.jflex file elég rövid, ha csak azt akarjuk támogatni, amit a korábbi változatban is tettünk:

package szamtud.week11;
import java_cup.runtime.*;

%%

%class ExpressionLexer
%unicode
%cup
%line
%column
%public
%{
  private Symbol symbol( int type ){ return new Symbol(type, yyline, yycolumn); }
  private Symbol symbol( int type, Object value ){ return new Symbol(type, yyline, yycolumn, value); }
%}

%%

"+"   { return symbol( ExpressionParserSym.PLUS ); }
"*"   { return symbol( ExpressionParserSym.STAR ); }
"("   { return symbol( ExpressionParserSym.LPAREN ); }
")"   { return symbol( ExpressionParserSym.RPAREN ); }
[\d]+ { return symbol( ExpressionParserSym.NUMBER, Double.parseDouble( yytext() )); }
[ \t]+ {}
[^]    { throw new Error("Illegal character <"+yytext()+">"); }

Az utolsó két akciókód érdekes lehet, kezdjük azokkal, mielőtt rátérünk ezekre az ExpressionParserSym dolgokra. Mivel a [ \t]+ regexre nem teszünk semmit, effektíve ezzel lenyeljük a whitespace-t. Az utolsó, a [^] avagy "negált semmi" karakterosztály, pontosan egy karakterre fog illeszkedni. Mivel a lexer soha nem dob fel találatnak üres stringet (hiszen akkor végtelen ciklusba esne), a találat mindig legalább egykarakteres lesz. Ha pedig ez az utolsó szabályunk, akkor ez egy "default" regexként fog működni: akkor hajtódik végre az akciókódja, ha semmire nem illeszkedett fentebb a string még feldolgozatlan részének az eleje. Ez tipikusan hibajelzésre használható kód, én is dobok itt egy Errort.

Ami még említésre méltó: az yytext() metódussal érjük el magát a stringet, melyre illeszkedett a regex, ezt használjuk a szám mint string kinyerésére a NUMBER token akciójában, meg a hibaüzi visszaadásában az utolsó pozin. Ezen kívül látjuk, hogy használjuk az yyline és yycolumn értékeket a Symbol konstruálásakor. Ez azért van, mert egy CUP-beli Symbolt akarunk létrehozni, annak a konstruktora pedig azt mindenképpen vár. Ezen kívül egy intet is vár, ami megadja a Symbol típusát: ez pontosan az az eset, amikor is korábban mi is egy enumba tettük az összeadás és kivonás jeleket, azzal, hogy itt minden egyes token típusnak kell deklarálnunk egy-egy int értéket - lényegében fel kell soroljuk az összes tokent és mindhez egy intet rendelni. (Ha a token ezen kívül rendelkezik egyéb értékekkel, akkor a symbol konstruktora a típus, sor, oszlop után még pluszban kaphat egy objektumot is, melyben adatot tudunk neki odaadni, az ilyet egyébként "szintetizált attribútum"nak hívják), ez történik a szám létrehozásakor, hiszen ott nem lesz elég csak annyit tudnunk, hogy egy számot kapunk, hanem magának a számnak az értékére is szükségünk lesz.

Ha most generálunk ebből a fileből a maven lapon (jobb oldalt) egy lexert, akkor kapunk is a target/generated-sources/jflex/szamtud.week11/ExpressionLexer.java fileba egy Java filet. Elég komplex és nem fordul, ennek két oka van:

• a lexerünk implementálja a java_cup.runtime.Scanner interfészt, amire megkértük a %cup direktívával, de nem tudja, mi az, mert a cup csomagot még nem emeltük be. A Symbol osztállyal ugyanez a helyzet.
• mik azok az ExpressionParserSym.PLUS és társai intek?

Ezeknek a problémáknak a feloldásához be kell izzítsuk a CUPot is.

CUP

Először is, az látszik, hogy a lexernek látnia kéne egy java_cup.runtime csomagot. Adjuk hozzá a projekthez external libraryként a korábban kicsomagolt CUP jarok közül a runtime-ot. (Project structure, Settings, Libraries, add, jar-t kiválaszt) Ezen a ponton az ExpressionLexer generált java file-ban hirtelen sok minden lefordul (persze, elkezdi érteni a CUPos dolgokat), már csak az alján nem tudja hova tenni az ExpressionParserSym osztály (ezek szerint) int mezőit. Azért nem, mert a token típusok neveit, ezeket az enumokat, a CUP fogja nekünk generálni - ők lesznek annak a CF nyelvtannak, amit a CUP parsol, a terminálisai.

Ehhez első körben meg kell írjuk a nyelvtan filet is, első közelítésből legyen ennyi:

package szamtud.week11;

import java_cup.runtime.*;

class ExpressionParser;

terminal PLUS, STAR, LPAREN, RPAREN;
terminal Double NUMBER;

non terminal ExpressionTree Tree;

Tree ::= NUMBER |
         Tree PLUS Tree |
         Tree STAR Tree |
         LPAREN Tree RPAREN
         ;

Ebből már valamennyire sejthetjük a CUP file szintaxisát: ennek is az elején lévő sorok (package, import) változtatás nélkül beemelődnek, a generált Parser osztály neve ExpressionParser lesz, felsoroltuk a nyelvtanunk terminálisait: pluszjel, szorzásjel, nyitójel, csukójel és egy külön sorba a számot is. Ennek itt még specifikáltuk azt is, hogy az adattagja (ez az, amit a lexer feltöltött pl. a számnál) típusa egy Double.

Eztán felsoroltuk a nyelvtanunk nemterminálisait is, most egy van: a Tree, ennek a nemterminálisnak ez a neve, és ExpressionTree lesz a típusa Javaban a belőle készített objektumnak majd.

A maradék részben pedig egy CF nyelvtan négy szabályát adtuk meg: a Tree az lehet egy szám, vagy két fa összege, vagy két fa szorzata, vagy zárójelek közt egy fa.

Szintaktikailag ez is egy helyes CUP nyelvtan file, ebből is generálunk egy Java osztályt. Ehhez most nem használunk Mavent (tbh nem néztem utána, hogy tud-e olyat), hanem parancssorból fordítunk: ehhez kell a nem-runtime jar.

$ java -jar java-cup-11b.jar ./zumi-szamtud/src/main/cup/ExpressionParser.cup

Warning : *** Shift/Reduce conflict found in state #8
  between Tree ::= Tree STAR Tree (*) 
  and     Tree ::= Tree (*) PLUS Tree 
  under symbol PLUS
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #8
  between Tree ::= Tree STAR Tree (*) 
  and     Tree ::= Tree (*) STAR Tree 
  under symbol STAR
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #7
  between Tree ::= Tree PLUS Tree (*) 
  and     Tree ::= Tree (*) PLUS Tree 
  under symbol PLUS
  Resolved in favor of shifting.

Warning : *** Shift/Reduce conflict found in state #7
  between Tree ::= Tree PLUS Tree (*) 
  and     Tree ::= Tree (*) STAR Tree 
  under symbol STAR
  Resolved in favor of shifting.

Error : *** More conflicts encountered than expected -- parser generation aborted
------- CUP v0.11b 20160615 (GIT 4ac7450) Parser Generation Summary -------
  1 error and 4 warnings
  7 terminals, 1 non-terminal, and 5 productions declared, 
  producing 11 unique parse states.
  0 terminals declared but not used.
  0 non-terminals declared but not used.
  0 productions never reduced.
  4 conflicts detected (0 expected).
  No code produced.
---------------------------------------------------- (CUP v0.11b 20160615 (GIT 4ac7450))

Bizony, hibát kaptunk, mert a nyelvtan nem egyértelmű (erről volt szó korábban), ezért nem tudott hozzá LALR(1) parsert generálni a CUP, nincs mese, azzá kell tennünk. A második megközelítésben már a "szokásos" módon, újabb nemterminálisok bevezetésével bevezetjük az operátorok precedencia-szintjeit és hogy balosak:

package szamtud.week11;

import java_cup.runtime.*;

class ExpressionParser;

terminal PLUS, STAR, LPAREN, RPAREN;
terminal Double NUMBER;

non terminal ExpressionTree AddExp, MultExp, NumberExp;

AddExp ::= MultExp |
           AddExp PLUS MultExp
           ;
MultExp ::= NumberExp |
            MultExp STAR NumberExp
            ;
NumberExp ::= NUMBER |
            LPAREN AddExp RPAREN
            ;

na és akkor

$ java -jar java-cup-11b.jar ./zumi-szamtud/src/main/cup/ExpressionParser.cup 
------- CUP v0.11b 20160615 (GIT 4ac7450) Parser Generation Summary -------
  0 errors and 0 warnings
  7 terminals, 3 non-terminals, and 7 productions declared, 
  producing 13 unique parse states.
  0 terminals declared but not used.
  0 non-terminals declared but not used.
  0 productions never reduced.
  0 conflicts detected (0 expected).
  Code written to "ExpressionParser.java", and "ExpressionParserSym.java".
---------------------------------------------------- (CUP v0.11b 20160615 (GIT 4ac7450))

Sounds good, generált valamit, két filet is: ExpressionParser.java és ExpressionParserSym.java (utóbbinak a nevét már hallottuk). Mivel ezt okosan sikerült kint generálni, bemásoljuk a src/main/java/szamtud/week11-be (vagy ahova a package infó mutat), és

• az ExpressionParserSym file lefordul, mondjuk ez lényegében egy enum-like statikus adatot tartalmazó osztály, itt láthatjuk, hogy a CUP nyelvtan file-beli nevek mind kaptak egy számot. Van köztük EOF is, ez persze az end of file, ez mindig generálódik pluszban, ahogy az error is.
• a JFlex által generált Lexer file-ban hirtelen már csak egy fordítási hiba lesz: nem találja a sym.EOF mezőt. Persze pont ezt keresi, ami az ExpressionParserSym fileban van, de valamiért ezen az egy helyen nem írja át ExpressionParserSym.EOF-ra, mint lentebb mindenhol. A megoldás semmiképp nem az, hogy kézzel hegesztünk bele generált file-ba! Hanem: írjuk be a %cupsym ExpressionParserSym sort a jflex file-ba, még a %cup direktíva előtt. Érdekes módon a többi szimbólumot eltalálja, csak az EOF kód generálásakor zavarodik össze.

Ezen a ponton már az újragenerált lexerünk, az ExpressionLexer is le fog fordulni. A generált parser még nem. Ha belenézünk, láthatjuk, hogy miért: megadtuk, hogy ExpressionTree lesz majd a kifejezés típusa, amit nem lát (egy import szamtud.week10.*; segít az ügyön, a CUP file import szekciójába).

Most minden fordul, próbáljuk ki, mit alkottunk eddig!

A generált lexer és parser osztályok használata

Egy Main osztály main metódusában:

ExpressionLexer lexer = new ExpressionLexer(new StringReader("3+4*5+6"));
ExpressionParser parser = new ExpressionParser(lexer);
Symbol topSymbol = parser.parse();
System.out.println( topSymbol.value );

Lefordul, kiírja, hogy null. Persze, a value mező az az adattag, melyet a parse tree node-jai adatként vihetnek felfelé és ilyet nem is adtunk meg, hogy hogy kéne kiszámítani, csak a terminális leveleknél! Ott is csak a Numbernek.

Faépítéskor hogy vigyük is "felfelé" a készített fát, ahogy pl. a shunting yard kézi implementációnkkor is csináltuk, akciókódot kell megadjunk a CUP nyelvtan file szabályai mellé is, hasonló szintaxissal, mint a jflex fileban tettük:

package szamtud.week11;

import java_cup.runtime.*;
import szamtud.week10.*;

class ExpressionParser;

terminal PLUS, STAR, LPAREN, RPAREN;
terminal Double NUMBER;

non terminal ExpressionTree AddExp, MultExp, NumberExp;

AddExp ::= MultExp:e {: RESULT = e; :} |
           AddExp:e1 PLUS MultExp:e2 {: RESULT = new AddExpression(e1,e2); :}
           ;
MultExp ::= NumberExp:e {: RESULT = e; :} |
            MultExp:e1 STAR NumberExp:e2 {: RESULT = new MultExpression(e1,e2); :}
            ;
NumberExp ::= NUMBER:n {: RESULT = new NumberExpression(n); :} |
            LPAREN AddExp:e RPAREN {: RESULT = e; :}
            ;

Mi is történik itt? A {: és :} jelek közt adhatunk meg akciókat, amik akkor sülnek el, ha a parser ezt a szabályt alkalmazza. Bottom-up parserről lévén szó, lentről felfelé fogja alkalmazni a szabályokat. Az akció részben a védett RESULT szó az újonnan létrehozott parse tree fapont adattagját jelöli, ha pedig a szabály részen a terminálisok vagy nemterminálisok jobb oldalára kettősponttal írunk egy változónevet, akkor az akciókódban ennek a szimbólumnak az adat mezőjére ezen a néven hivatkozhatunk.

Újra cupolás, file bemásolás és a Main:

ExpressionLexer lexer = new ExpressionLexer(new StringReader("3+4*5+6"));
ExpressionParser parser = new ExpressionParser(lexer);
Symbol topSymbol = parser.parse();
System.out.println( ((ExpressionTree)topSymbol.value).evaluate() );

ki is írja, hogy 29.0. És támogat zárójelezést is. Nice.

---

Utolsó frissítés: 2021-11-07 19:55:30