Automata, Languages and Compilers 2018/19 spring

9. kodutöö: AST koostamine

Selles kodutöös tuleb ANTLR-i kaasabil defineerida meetod createAst, mis annab AKTK programmile vastava abstraktse süntaksipuu:

package week9;
import week9.ast.AstNode;

public class AktkAst {
	public static AstNode createAst(String program) {
		// Erindi viskamine tuleb asendada reaalse implementatsiooniga
		throw new UnsupportedOperationException();
	}
}

Selle saavutamiseks on vaja:

1. genereerida ANTLR-i abil Aktk.g4 grammatikast (võib kasutada meie näidislahendust, aga ka enda lahendust, mida on sobivalt märgendatud) AKTK parser (koos abiklassidega);
2. kirjutada kood, mis genereeritud parseri abil teisendab sõnena esitatud programmi parse-puuks;
3. kirjutada kood, mis teisendab parse-puu abstraktseks süntaksipuuks. Abstraktse süntaksipuu esitamiseks anname ülesandega kaasa klassi AstNode koos alamklassidega. See punkt on selle koduülesande tuum.

Võimaliku lahenduse algus

Toome siinkohal ära kärbitud näite AST koostamisest. NB! Lisaks sellele, et siin on nähtavad lüngad, on neis mõned juhtumid ka täiesti käsitlemata -- need tuleb sul üles leida ja ära realiseerida. Selleks soovitame vaadata läbi grammatika reeglid ja otsustada, milliseid reegleid tuleb eraldi käsitleda ja millised saab jätta vaikeimplementatsiooni hooleks.

Mugavad import'id

import week8.AktkParser.*;
import week9.ast.*;

Lahenduse algus

private static AstNode parseTreeToAst(ParseTree tree) {
    AktkAstStatementVisitor statementVisitor = new AktkAstStatementVisitor();
    return statementVisitor.visit(tree);
}

// Eraldi Expression ja Statement visitoride tegemine võimaldab kasutada eri
// tagastustüüpe, et ei peaks avaldiste AST-i loomisel pidevalt AstNode'sid
// Expression'iteks cast'ima

private static class AktkAstExpressionVisitor extends AktkBaseVisitor<Expression> {
    @Override
    public Expression visitArvuliteraal(ArvuliteraalContext ctx) {
        return new IntegerLiteral(Integer.parseInt(ctx.getText()));
    }

    @Override
    public Expression visitSoneliteraal(SoneliteraalContext ctx) {
        // Arvesta, et sõneliteraalil on ümber jutumärgid, mis ei kuulu sõne sisu hulka
        ...
    }

    @Override
    public Expression visitSuluavaldis(SuluavaldisContext ctx) {
        // Selle tipu alluvad on alustav sulg, avaldis ja lõpetav sulg
        // NB! Alluvate nummerdamine algab 0-st
        // Töötleme rekursiivselt sulgude sees oleva avaldise ja tagastame selle
        return visit(ctx.getChild(1));
    }

    @Override
    public Expression visitFunktsiooniValjakutse(FunktsiooniValjakutseContext ctx) {
        // NB! Siin tuleb kontrollida, kuidas näeb välja
        //   - ilma argumentideta
        //   - ühe argumendiga
        //   - mitme argumendiga
        // funktsiooni väljakutse parse-puu
        ...
    }

    @Override
    public Expression visitKorrutamineJagamine(KorrutamineJagamineContext ctx) {
        return binaarneOperatsioon(ctx);
    }

    @Override
    public Expression visitLiitmineLahutamine(LiitmineLahutamineContext ctx) {
        return binaarneOperatsioon(ctx);
    }

    @Override
    public Expression visitVordlemine(VordlemineContext ctx) {
        return binaarneOperatsioon(ctx);
    }

    private Expression binaarneOperatsioon(ParserRuleContext ctx) {
        // Kõik binaarsed operatsioonid saan käsitleda korraga
        String operaator = ctx.getChild(1).getText();
        Expression vasakArgument = visit(ctx.getChild(0));
        ...

        return new FunctionCall(operaator, Arrays.asList(vasakArgument, ...));
    }
}

private static class AktkAstStatementVisitor extends AktkBaseVisitor<Statement> {
    private final AktkAstExpressionVisitor expressionVisitor = new AktkAstExpressionVisitor();

    @Override
    public Statement visitAvaldis(AvaldisContext ctx) {
        // Kui lause koosneb avaldisest, siis selleks, et temast saaks ikkagi lause,
        // tuleb ta avaldise visitoriga töödelda ja pakendada ExpressionStatement'i sisse
        Expression avaldis = expressionVisitor.visit(ctx.getChild(0));
        return new ExpressionStatement(avaldis);
    }

    @Override
    public Statement visitMuutujaDeklaratsioon(MuutujaDeklaratsioonContext ctx) {
        // Muutuja deklaratsiooni esimene alluv (st. alluv 0) on võtmesõna "var",
        // teine alluv on muutuja nimi

        // Algväärtus võib olla, aga ei pruugi.
        // Kontrolli ANTLRi IntelliJ pluginaga järgi, mitu alluvat
        // on muutuja deklaratsioonil, millel on algväärtus ja mitu
        // alluvat on sellel, millel algväärtust pole.
        ...
    }

    @Override
    public Statement visitLause(LauseContext ctx) {
        // Grammatikast on näha, et lause võib olla ühe alluvaga,
        // (nt. ifLause, whileLause), mis on käsitletud mujal
        if (ctx.getChildCount() == 1) {
            return visit(ctx.getChild(0));
        }
        // ... aga lause võib olla ka loogelistes sulgudes olev lausete jada
        else {
            assert ctx.getChildCount() == 3;
            return visit(ctx.getChild(1));
        }
    }

    @Override
    public Statement visitLauseteJada(LauseteJadaContext ctx) {
        // Siin on tähtis järgi uurida, kuidas näib välja mitme lausega
        // lauseteJada parse-puu.
        ...
    }
}

Huvilistele

• Kui sulle ei meeldi parse-puus liikumine getChild indeksite järgi, siis uuri, milliseid kasulikke meetodeid on konkreetetel Context klassidel ja kuidas alamtippe saab ise nimetada.

Soovitused

• Vaata üle ka AST klasside kirjeldused (dokumentatsiooni leiad klasside ja meetodite päistest). Uuri ka klassihierarhiat (IntelliJ, Eclipse).
• AstNode.toString() näitab puu struktuuri tekstilisel kujul.

Lahenduse esitamine

• Esitada tuleb vähemalt järgmised failid:
  • AktkAst.java
    • klassis AktkAst peab olema meetod signatuuriga public static AstNode createAst(String program)
  • AktkLexer.java
  • AktkParser.java
  • AktkListener.java
  • AktkVisitor.java
  • AktkBaseVisitor.java (kui implementeerid AktkVisitor asemel AktkBaseVisitor-i)
• Kokku võib esitada kuni 9 faili.
• Kõik esitatud failid peavad olema UTF-8 kodeeringus (ANTLR-i poolt genereeritud failide puhul ei pea selle pärast muretsema).
• Esitada ei ole vaja:
  • grammatikat (Aktk.g4)
  • .token ja .interp laiendiga genereeritud faile (Aktk.interp, Aktk.tokens, AktkLexer.interp ja AktkLexer.tokens)