Automata, Languages and Compilers

Eksami lõviosa

Eksami lõviosas genereerime CMa baitkoodi sellesama ASTi põhjal, mille jaoks oleme interpretaatori juba kirjutanud. Idee poolest peaksid nad andma sama tulemuse! Kui õpid ära, kuidas see kompileerimine käib, siis on ta peaaegu sama lihtne kui väärtustamine. Selleks peab kõigepealt meie Vam osaga tutvuma (ja tutvuda CMa käsustikuga).

Demo: KalaCompiler

Praktikumides proovime Imp keele lõviosa lahendada, aga selleks, et siin lehel oleks väike näide koodi genereerimise skeemist vaatame ka Kala tippude kompileerimist. See on tegelikult listide keel ja selle AST'il on meetod sum, mis liidab tema kõik komponendid kokku. Argumendiks võtab ta keskkonna, mis seab muutujatele oma väärtusi, näiteks võisime kirjutada:

        KalaNode kalaAst = makeKalaAst("(kala, (x,y , null, (), (kala,()) ))");
        Map<String, Integer> env = Map.of("kala", 1, "x", 2, "y", 3);
        System.out.println(kalaAst.sum(env));  // 7

Kui me tahaks kompileerida seda programmiks, mis jookseb CMa peal, siis peame kuidagi ka seda keskkonda argumendina talle andma. CMa sisendiks on ainult magasin ja me saame selle kaudu vastavate muutujate väärtused ette anda. Antud näites käivitame CMa magasiniga [1, 2, 3], aga me peame kuidagi kokku leppima, kuidas etteantud magasin on seotud muutujate nimedega. Üks lihtne variant, mida me tihti kasutame on see, et fikseerime muutujate nimed ära ja kõik programmid kasutavad samu nimesid sisendiks. Meil on seega globaalne list argumentide nimedest:

   public static final List<String> ARGS = List.of("kala", "x", "y");

Ja nüüd kävitame kompileeritud programmi järgmiselt:

   public static void main(String[] args) {
        KalaNode kalaAst = makeKalaAst("(kala, (x,y , null, (), (kala,()) ))");
        CMaProgram program = compile(kalaAst);
        CMaStack initialStack = new CMaStack(1, 2, 3);
        System.out.println(CMaInterpreter.run(program, initialStack));
   }

Meie koodi genereerimise skeem on siis järgmine. Muutujate juures me vaatame lihtsalt muutujate nimede listis mitmes ta peaks olema.

    public static CMaProgram compile(KalaNode expr) {
        CMaProgramWriter pw = new CMaProgramWriter();
        new KalaAstVisitor<Void>() {
            @Override
            protected Void visit(KalaNull nullnode) {
                pw.visit(LOADC, 0);
                return null;
            }

            @Override
            protected Void visit(KalaList list) {
                pw.visit(LOADC, 0);
                for (KalaNode arg : list.getArgs()) {
                    visit(arg);
                    pw.visit(ADD);
                }
                return null;
            }

            @Override
            protected Void visit(KalaIdent ident) {
                pw.visit(LOADA, ARGS.indexOf(ident.getName()));
                return null;
            }
        }.visit(expr);
        return pw.toProgram();
    }

Eksami ülesannete lahendamine

Nüüd saab meie eksami näidiste lõviosasid lahendada. Kui saad nendega hakkama, siis oled eksamiks valmis.