Automaadid, keeled ja translaatorid

Genereeritud parseri kasutamine parse-puu saamiseks

Teemat tutvustav video: ANTLRi parsepuu.

ANTLRi pluginaga saab asju katsetada, aga nüüd kasutame ANTLRi loodud koodi parsepuu läbimiseks. Kui Gradle'i käsk generateGrammarSource õnnestus, siis tekitatakse failid kataloogi src/gen/java/. Nüüd saame neid kasutama hakkata. Plaan on teha üks abimeetod, mis võtab argumendiks sõnena antud keele programmi, parsib selle ja tagastab parse-puu -- selle andmestruktuuri, mida ANTLR-i IntelliJ plugin sulle grammatikate testimisel graafiliselt näitas.

Kuna siin tuleb lihtsalt teada, kuidas ANTLR-i parserit käivitatakse, siis anname kogu vajamineva koodi ette:

    private static ParseTree createParseTree(String program) {
        ArithLexer lexer = new ArithLexer(CharStreams.fromString(program));
        ArithParser parser = new ArithParser(new CommonTokenStream(lexer));
        ParseTree tree = parser.expr();
        System.out.println(tree.toStringTree(parser));
        return tree;
    }

Tegelikku parsimisprotsessi alustab parser.expr(), kõik muu on ettevalmistus. Kui sa oletad, et see expr viitab samanimelisele reeglile Arith grammatikas, siis on sul täiesti õigus. Tuleb välja, et ANTLR-i poolt genereeritud parseril on iga grammatika reegli kohta üks meetod, mõningaid kutsub välja parseri klient, mõnda kasutab parser ise teiste reeglite juures. Üldstruktuur on tal nagu meie käsitsi kirjutatud parseril!

Tagastatud puud hoiame ParseTree tüüpi muutujas. ParseTree on konkreetsest grammatikast sõltumatu liides, millel on palju eeldefineeritud operatsioone. Näiteks puu struktuuri suluesituse nägemiseks on toodud koodis kasutatud meetodit toStringTree. See vajab argumendina ka parserit, sest grammatikas kasutatud nimed on muidu puus asendatud täisarvuliste indeksitega.

Parsepuuga töötamine

Vaatame, kuidas nüüd defineerida meile tuttav väärtustamise funktsioon eval sissejuhatuses toodud avaldisgrammatika Arith põhjal.

expr : expr '+' term | expr '-' term | term ; term : term '*' factor | term '/' factor | factor ; factor : '(' expr ')' | Variable | Literal ;

Siin on avaldise 5 + 2 *4 parse-puu graafiline esitus. Kui me käivitame eelpool antud funktsiooni selle programmiga (st. createParseTree("5 + 2 *4")), siis me saame sama kujuga andmestruktuuri. See on puu, mille kõik tipud implementeerivad ülalmainitud liidest ParseTree. Puu läbimiseks on liidesel muuhulgas järgmised meetodid:

• int getChildCount()
• ParseTree getChild(int childIndex)

Nendest isegi piisaks puu läbimiseks, aga neid on ebamugav kasutada, kui tahame erinevat tüüpi tippude juures erinevalt käituda.

Programmi struktuuri täpsemaks esitamiseks genereeris ANTLR koos parseriga ka meie grammatikale spetsiifilised klassid. Meie grammatikal oli kolm mitte-terminali: expr, term ja factor. Igaühele neile vastab siis enda klass: ExprContext, TermContext ja FactorContext. Nende kaudu saame natuke personaalsemalt läheneda sellele puule. Näiteks, igal ExprContext isendil on lisaks üldisele getChild meetodile ka expr ja term meetodid, mis tagastavad sellele mitte-terminalile vastava alampuu.

Parse-puu läbimine Visitoriga

ANTLR genereerib soovi korral koos parseriga veel ühe liidese ja ühe klassi, mis realiseerivad varemnähtud visitor mustrit meie grammatika parsepuu peal. Arith grammatika puhul on nendeks ArithVisitor ja ArithBaseVisitor. Nende genereerimiseks on juba build.gradle faili lisatud generateGrammarSource reegli juurde vastav käsureaparameeter.

Liides ArithVisitor sarnaneb väga varemnähtud visitor liidestele. Meetod saab argumendiks vastava tüübiga parse-puu tipu ning peab ka midagi tagastama, sõltuvalt visitori enda tagastustüübist. ANTLRi visitor liides nõuab aga mõnede üldiste meetodite realiseerimist, näiteks visitErrorNode, mille vaikeimplementatsioon meile väga hästi sobib. Seega kasutame ArithBaseVisitor ja implementeerime ainult visitExpr, visitTerm ja visitFactor.

Proovime selle liidese abil nüüd lahendada avaldise väärtustamise ülesanne (klassis ArithAst). See ei ole aga kõige mugavam, sest grammatika reeglite järgi on expr alluvateks, kas lihtsalt term või expr plus/miinus term. Me peame seega kontrollima, kas expr on olemas või mitte:

private static int eval(ParseTree tree, Map<String, Integer> env) {
    ArithVisitor<Integer> visitor = new ArithBaseVisitor<Integer>() {

        @Override
        public Integer visitExpr(ExprContext ctx) {
            Integer termValue = visit(ctx.term());
            if (ctx.expr() == null) return termValue;
            // Kui siia jõuame, siis expr -> expr +/- term
            Integer exprValue = visit(ctx.expr());
            String op = ctx.getChild(1).getText();
            if (op.equals("+")) return exprValue + termValue;
            ...
        }

        @Override
        public Integer visitTerm(TermContext ctx) {
            ...
        }

        @Override
        public Integer visitFactor(FactorContext ctx) {
            ...
        }
    };
    return visitor.visit(tree);
}

Nimetame asju õigete nimedega

Ülal oleva koodi probleemiks on see, et erinevad produktsioonid on siin võetud ühtekokku samasse konteksti, et peab muudkui uurima, kas tipul on vastav väli olemas või mitte. ANTLR võimaldab olukorra päästmiseks erinevatele alternatiividele nimesid anda. Me saame ka lausevormi osadele nimesid anda. Selleks, et tehe oleks kergesti kättesaadav, paneme sellele nimeks op. Järgmises näites on nimede kasutamise võimalusi kasutatud.

expr : expr op='+' term #BinaryExpr | expr op='-' term #BinaryExpr | term #SimpleExpr ; term : term op='*' factor #BinaryTerm | term op='/' factor #BinaryTerm | factor #SimpleTerm ; factor : '(' expr ')' #Paren | Variable #Variable | Literal #Literal ;

Nende alternatiivide nimede järgi luuakse uusi parsepuu alamklasse. Meil tekib seega järgmine hierarhia, mida on kasulik teada, kui läbida puud ilma visitorita (intanceof kontrollidega):

• ParserRuleContext (üldine ParseTree liidese implementatsioon)
  • ExprContext
    • BinaryExprContext
    • SimpleExprContext
  • TermContext
    • BinaryTermContext
    • SimpleTermContext
  • FactorContext
    • ParenContext
    • VariableContext
    • LiteralContext

Visitoriga saame nüüd implementeerida kõige peenemate alamklasside kohta eraldi meetodid. See on palju mugavam! Järgnev kood on peaaegu meie vanade heade AST visitorite moodi:

    ArithVisitor<Integer> visitor = new ArithBaseVisitor<Integer>() {

        // Factori jaoks saame nüüd väga mugavalt:

        @Override
        public Integer visitParen(ParenContext ctx) {
            ...
        }

        @Override
        public Integer visitVariable(VariableContext ctx) {
            ...
        }

        @Override
        public Integer visitLiteral(LiteralContext ctx) {
            ...
        }

        // Defineerime abifunktsiooni, et järgmised koos käsitleda:
        //   expr -> expr '+' term    #BinaryExpr
        //   expr -> expr '-' term    #BinaryExpr
        //   term -> term '*' factor  #BinaryTerm
        //   term -> term '/' factor  #BinaryTerm
        private Integer handleBinop(ParseTree ctx) {
            // Küsime homogeense liidese kaudu tipude alluvad
            ParseTree leftChild  = ctx.getChild(0);
            String operator      = ctx.getChild(1).getText();
            ParseTree rightChild = ctx.getChild(2);
            ...
        }

        @Override
        public Integer visitBinaryExpr(BinaryExprContext ctx) {
            return handleBinop(ctx);
        }

        @Override
        public Integer visitBinaryTerm(BinaryTermContext ctx) {
            return handleBinop(ctx);
        }


        // Aga kus on järgmised reeglid?
        //    expr -> term     #SimpleExpr
        //    term -> factor   #SimpleTerm
        // BaseVisitor hoolitseb nende eest. Kui mõni reegel on defineerimata,
        // siis külastatakse alluvad järjest ja tagastatakse viimase tulemus. '
        // (Seda käitumist saab aggregateResult ja defaultResult kaudu ka muuta.)


    };

Lihtsama parsepuu saamine

Ülalolev kood on see, kuidas me soovitaks seda teha, aga avaldisgrammatikate puhul saab kasutada rohkem ANTLRi kavalusi. Sellega tuleb aga olla ettevaatlik, sest ANTLRi kõikide lisakavaluste koosmõju puhul on raske aru saada, mis seal tegelikult toimub. Kui on aga tegemist üsna standardse avaldise grammatikaga, siis me võime ANTLR'ile anda mitmese grammatika ja lasta tal vasakrekursiooni lahendades ise prioriteetidega arvestada.

ANTLRil on kindlad konventsioonid, kuidas ta mitmesust lahendab. Peamine on see: kui ANTLRi parseril on kahe reegli järgi võimalik derivatsioonis mõnda mitte-terminali (näiteks expr allolevas näites) ümber kirjutada, siis valitakse viimane sobiv alternatiiv. See tähendab, et mida kõrgemal mõni alternatiiv on, seda kõrgema prioriteediga tehe ta defineerib.

expr : expr op=('*'|'/') expr #BinaryExpr | expr op=('+'|'-') expr #BinaryExpr | '(' expr ')' #ParenExpr | Variable #VarExpr | Literal #LitExpr ;

Sellega peab ettevaatlik olema. Ma ise kirjutasin kõigepealt need valepidi siia lehele! See on nüüd parandatud, aga vaatame järgmisena seda vigast versiooni. Kui me vahetame esimese kahe rea järjekorda, siis on tulemuseks ka vale AST:

expr : expr op=('+'|'-') expr #BinaryExpr | expr op=('*'|'/') expr #BinaryExpr | '(' expr ')' #ParenExpr | Variable #VarExpr | Literal #LitExpr ;

Kui proovid seda grammatikat sisendiga 5-3-1, siis ANTLR teeb seda õigesti. Ta teeb vaikimisi kõik operaatorid vasakassotsiatiivseteks. Kui tahaks paremassotsiatiivsust, siis võib seda reeglit annoteerida <assoc=right> abil. See on enam-vähem kõik, mida ma tean ANTLRi kavalustest, aga täpsemalt on see kirjas ANTLRi dokumentatsioonis, kus on ka rohkem näited selle kohta.

Sellise lähenemise suurimaks eeliseks on see, et meil on nüüd ainult neli juhtumit vaja oma visitoris käsitleda. Faktori omad on nagu üleval, aga binaarsete operatsioonide jaoks jääb vaid üks meetod realiseerida:

         
            @Override
            public Integer visitBinaryExpr(BinaryExprContext ctx) {
                Integer leftValue = visit(ctx.expr(0));  // ehk getChild(0)
                Integer rightValue = visit(ctx.expr(1)); // ehk getChild(2)
                switch(ctx.op.getText()) {
                    ...
                }
            }