Arvutiteaduse instituut
  1. Esileht
  2. Automaadid, keeled ja translaatorid
EN
Logi sisse

Automaadid, keeled ja translaatorid

  • Üldinfo
  • Ajakava
  • Eksami näidised
  • Teemad
    • 1. Soojendus
    • 2. Regulaaravaldised
    • 3. Automaadid
    • 4. Avaldise struktuur
    • 5. Grammatikad ja lekser
    • 6. Käsitsi parsimine
    • 7. ANTLRiga töötamine
    • 8. Interpretaator
    • 9. Kompilaator
      • Vam: CMa simulaator
      • Eksami lõviosa!
      • Kodutöö: Analüüs
      • Kodutöö: Kompilaator
    • 10. Edasi!
  • Süvendus
  • Bitbucket
  • Moodle
  • Zulip
  • Zoom

CMasina simulaator VAM

Teemat tutvustav video: CMa simulaator.

CMasina jaoks on olemas simulaator, Vam. Kõige lihtsam on seda paigaldada, kui tõmmata järgmine jar: vam.jar.

Näide

Selles keskkonnas kahjuks ei saa redigeerida faili, mistõttu tuleks järgmine fail salvestada nime all demo.cma. Sellel programmil on aga väike viga. Kuigi see ei olnud meelega, siis võiksite ikkagi üritada ise välja nuputada, kus viga on:

loadc 5  // 0: n = 5;
loadc 1  // 1: i = 1;
loadc 1  // 2: r = 1;

_while:	// i <= n
  LOADA 1
  LOADA 0
  LEQ
  JUMPZ _end

  // r = r * i;
  LOADA 2
  LOADA 1
  MUL
  STOREA 2
  POP

  // i = i + 1;
  LOADA 1
  LOADC 0
  ADD
  STOREA 1
  POP

  JUMP _while

_end:	
  HALT

Proovige VAMi simulatsiooni abil välja nuputada, mida see funktsioon arvutab ehk mis võrdus kehtib muutujate vahel, kui käivitamine on lõppenud.

Harjutus

Transleerige järgmine koodiosa CMa baitkoodi keskkonnas {n→0, x→1, z→2}:

z = 1;               
while (n > 0) {      // GR
    if (n & 1)       // AND
        z = z * x;   // MUL
    x = x * x;       // MUL
    n = n / 2;       // DIV
}

Selleks, et seda VAMis käivitada tuleb anda muutujatele mingid algväärtused. Kuna n ja x on siin mõeldud sisendiks, siis võib näiteks proovida sisendiga:

LOADC 11 /* n */
LOADC 3  /* x */
LOADC 0  /* z */ 

Muutuja z on koodijuppi väljundiks ja seda algväärtustatakse siin. Kes on laisk võib siin ära optimeerida esimest omistust ja lihtsalt panna "loadc 1". Sisendite 3 ja 11 korral peaks lõpptulemuseks olema magasini tipus 177147.

Mida see koodijupp arvutab?

Meie CMa simulaator

Repos paketis cma on CMa simulaator, mida kasutame teie programmide testimiseks. CMa programmide loomiseks on olemas ka klass CMaProgramWriter, millega saab genereerida CMa masinkoodi analoogiliselt ASM teegiga, mida kasutame Java baitkoodi genereerimiseks. Ülaloleva (vigase) näide loomiseks meie raamistikuga tuleb kirjutada:

import java.io.IOException;

// Impordime vajalike käske. Nad on erinevates klassides, sest nad vajavad
// erinev arv argumente (kompilaator hoiatab kui kasutate valesti).
import static cma.instruction.CMaBasicInstruction.Code.*;
import static cma.instruction.CMaIntInstruction.Code.*;
import static cma.instruction.CMaLabelInstruction.Code.*;

public class CMaDemo {

    public static void main(String[] args) throws IOException {

        // Magasini algväärtustamine: loadc 5; loadc 1; loadc 1
        CMaStack initialStack = new CMaStack(5,1,1);

        // Märgendite jaoks kasutame CMaLabel tüüpi isendid
        CMaLabel _while = new CMaLabel();
        CMaLabel _end = new CMaLabel();

        CMaProgramWriter pw = new CMaProgramWriter();

        // while (i <= n)
        pw.visit(_while);
        pw.visit(LOADA, 1);
        pw.visit(LOADA, 0);
        pw.visit(LEQ);
        pw.visit(JUMPZ, _end);

        // r = r * i;
        pw.visit(LOADA, 2);
        pw.visit(LOADA, 1);
        pw.visit(MUL);
        pw.visit(STOREA, 2);
        pw.visit(POP);

        // i = i + 1;
        pw.visit(LOADA, 1);
        pw.visit(LOADC, 0);
        pw.visit(ADD);
        pw.visit(STOREA, 1);
        pw.visit(POP);

        pw.visit(JUMP, _while);
        pw.visit(_end);

        // Nüüd loome programmi ja kirjutame faili
        CMaProgram program = pw.toProgram();
        program.toFile(Paths.get("cmas", "demo.cma"), initialStack);

        // Võime ka programmi käivitada ja saame tulemuseks uue magasini seisundi
        CMaStack finalStack = CMaInterpreter.run(program, initialStack);
        System.out.println(finalStack);
    }
}

NB! Selles programmis on endiselt viga sees. Seda tuleks parandada, muidu ei saa siin ka oodatud tulemuse.

  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo