SimpleVM #9 Bonus: Assembler

Category: 

Unsere SimpleVM ist zwar vollständig, allerdings ist es recht aufwendig und fehleranfällig den Bytecode mit einem HexEditor zu schreiben. Daher werden wir in diesem Artikel einen Assembler entwickeln der den Bytecode aus einem für Menschen lesbaren Assemblercode erzeugt.

Dieser Artikel ist Teil der Serie: Simple Virtual Machine
#1 Einstieg
#2 Prototyp
#3 Bedingte Sprünge
#4 Funktionen
#5 OOP
#6 Globale Variablen und Java Funktionen
#7 Operator overloading
#8 Details & Loading from File
#9 Bonus: Assemblercode

Zielsetzung

Um die Erstellung des Bytecode zu vereinfachen, wollen wir einen Assembler entwickeln, der Programme in einer Assemblersyntax einliest und in Bytecode kompiliert. Ein einfaches Assemblerprogramm soll dann so aussehen:

.function
getglobal "print"
push "Hello World"
call 1
.end

Hier sieht man auch eine Stärke des Assemblers, anstatt uns mit den String indizes rumzuärgern, schreiben wir den String einfach direkt nach dem push-Befehl. Der Assembler fügt den String beim kompilieren in das Array ein und fügt den push_string Befehl mit passendem Index dem Code hinzu. Ebenso können wir beliebige Zahlen mitgeben und der Assembler wählt je nach Größe der Zahl den passenden push_* Befehl ein.

Umsetzung

Einen Assembler kann man relativ leicht auch direkt in Java programmieren, allerdings kann dies auch schnell unübersichtlich werden. Daher werde ich den Assembler mit dem Compiler Generator Coco/R entwickeln.
Als erstes erstelle ich ein neues Package namens "assembler" und erstelle dort die Dateien "Assembler.java" und "Assembler.jatg". Letztere füllen wir vorerst mit diesem Code:

$package=com.infectedbytes.tutorials.simplevm.assembler
COMPILER Assembler
 
CHARACTERS
  letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".
  digit = "0123456789".
  cr  = '\r'.
  lf  = '\n'.
  tab = '\t'.
  notQuote = ANY - '"' - '\\' - "\r\n".

TOKENS
 

COMMENTS FROM "/*" TO "*/" NESTED
COMMENTS FROM "//" TO lf

IGNORE tab

PRODUCTIONS
 
END Assembler.

Nun müssen wir uns überlegen was wir für Tokens und Produktionen benötigen. Dazu überlegen wir uns erst einmal einen komplexeren Beispielcode, welcher alle wichtigen Fälle betrachtet.

.function main
getglobal "print"
push "Hello World"
call 1

getglobal "print"
push @max
push 42
push 3.141
call 2 // call function max with 42 and 3.141
call 1 // call print with result of max
.end
.function max
.limit 2 2 // 2 params 2 locals
.local a 0
load $a // instead of using the index directly, we could use an alias for it
load 1
ifge greater // if local 0 is greater or equal to local 1, goto label "greater"
load 1
return
greater:
load 0
return
.end

Hier sieht man eine weitere Vereinfachung. Anstatt den Index der Funktion auf den Stack zu legen, wollen wir einen Namen verwenden können. Der Assembler soll sich dann darum kümmern, diesen Namen durch einen passenden Index zu ersetzen. Außerdem wollen wir bei Sprüngen keine relativen Offsets angeben, sondern einfach nur ein Ziellabel. Meistens wird es reichen, die Indizes der lokalen Variablen direkt zu benutzen, aber bei sehr großen Funktionen kann es sehr hilfreich sein, den Variablen einen Namen zu geben, daher kann man einen Alias für einen Index verwenden.

Tokens

Was für Tokens benötigen wir? Durch den obigen Beispielcode sehen wir, dass wir allein für den push Befehl bereits vier Tokens benötigen: intNumber, floatNumber , string und functionId. Zusätzlich brauchen wir noch ein Token für die Labels und für die Aliase. Nun erweitern wir den CHARACTERS und TOKENS Abschnitt der jatg Datei:

CHARACTERS
  letter = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_".
  digit = "0123456789".
  cr  = '\r'.
  lf  = '\n'.
  tab = '\t'.
  notQuote = ANY - '"' - '\\' - "\r\n".

TOKENS
  ident  = letter {letter | digit}.
  intNumber = ['-']digit {digit}.
  floatNumber = ['-']digit {digit} '.' digit {digit}.
  string = '"' {notQuote | "\\\""} '"'.
  functionId = '@' letter {letter | digit}.
  aliasName = '$' letter {letter | digit}.
  eol = (cr lf) | lf.

Wie man sieht, habe ich noch ein weiteres Token namens "eol" eingeführt. Dieses dient nur dazu, ein Windows/Linux Zeilenende zu erkennen. Das benötigen wir, da der Assemblercode immer nur einen Befehl pro Zeile erlauben soll.

Produktionen

Eine Assemblerdatei besteht aus einer Folge von Funktionen, diese wiederum bestehen aus mehreren Befehlen. Der Code für die Produktionen sieht so aus:

PRODUCTIONS
  Ident<out String value> = ident (. value = t.val; .) .
  IntExpr<out int value> = intNumber (. value = parseInt(t.val); .) .
  FloatExpr<out float value> = floatNumber (. value = parseFloat(t.val); .) .
  FunctionId<out String id> = functionId (. id = t.val.substring(1); .) .
  AliasName<out String id> = aliasName (. id = t.val.substring(1); .) .
  IndexOrAlias<out int index> = (. index = 0; String name; .)
    ( IntExpr<out index> | AliasName<out name> (. index = currentProto.indexOfAlias(name); if(index<0) SemErr(name + " is not defined"); .) ) .
  StringExpr<out String string> = string (. string = parseString(t.val); .) .
  Label<out String name> = ident (. name = t.val; .) ":".
  EOL = eol {eol}.
 
  Assembler =
    Function (. add(currentProto); .)
    { Function (. add(currentProto); .) }
    (. resolveFunctionNames(); .) .
  Function = (. String name; int count = 0; Instruction instr = null; .)
    ".function" Ident<out name> EOL (. currentProto = new Prototype(name); .)
    [ ".limit" IntExpr<out count> (. currentProto.params = count; .) IntExpr<out count> (. currentProto.locals = count; .) EOL ]
    { LocalDef EOL }
    { Expr<out instr> EOL (. currentProto.addInstruction(instr); .) }
    ".end" EOL
    (. resolveLabels(currentProto); .) .
  LocalDef = (. String alias; int index; .)
    ".local" Ident<out alias> IntExpr<out index>
    (.
      if(currentProto.containsAlias(alias)) SemErr(alias + " already defined");
      else currentProto.addAlias(alias, (short)index);
    .) .
  Expr<out Instruction instr> = (. instr = null; .)
    ( LabelDef<out instr> | NoArgsExpr<out instr> | MoveExpr<out instr> | CallExpr<out instr> | Self<out instr> | Push<out instr> | Locals<out instr> | Globals<out instr> | JumpExpr<out instr>) .
  LabelDef<out Instruction instr> = (. String name; .)
    Label<out name> (. instr = new Instruction.Label(name, t.line); .) .
  NoArgsExpr<out Instruction instr> = (. instr = null; .)
    ( "swap" (. instr = new Instruction.NoArgs(SWAP); .)
    | "dup" (. instr = new Instruction.NoArgs(DUP); .)
    | "pop" (. instr = new Instruction.NoArgs(POP); .)
    | "add" (. instr = new Instruction.NoArgs(ADD); .)
    | "sub" (. instr = new Instruction.NoArgs(SUB); .)
    | "mul" (. instr = new Instruction.NoArgs(MUL); .)
    | "div" (. instr = new Instruction.NoArgs(DIV); .)
    | "mod" (. instr = new Instruction.NoArgs(MOD); .)
    | "unary" (. instr = new Instruction.NoArgs(UNARY); .)
    | "and" (. instr = new Instruction.NoArgs(AND); .)
    | "or" (. instr = new Instruction.NoArgs(OR); .)
    | "xor" (. instr = new Instruction.NoArgs(XOR); .)
    | "not" (. instr = new Instruction.NoArgs(NOT); .)
    | "return" (. instr = new Instruction.NoArgs(RETURN); .)
    | "new" (. instr = new Instruction.NoArgs(NEW); .)
    | "get" (. instr = new Instruction.NoArgs(GET); .)
    | "set" (. instr = new Instruction.NoArgs(SET); .)
    ).
  MoveExpr<out Instruction instr> = (. int a, b; .)
    "move" IndexOrAlias<out a> IndexOrAlias<out b> (. instr = new Instruction.Args(MOVE, new byte[] {(byte)a, (byte)b} ); .) .
  CallExpr<out Instruction instr> = (. int args; .)
    "call" IntExpr<out args> (. if(args<0 || args>127) SemErr("Invalid index"); instr = new Instruction.Args(CALL, byteToByteArray(args)); .) .
  Self<out Instruction instr> = (. String string; .)
    "self" StringExpr<out string> (. instr = new Instruction.Args(SELF, shortToByteArray(currentProto.indexOfString(string))); .) .
  Push<out Instruction instr> = "push" (. instr = null; String sval; int ival; float fval; .)
    ( "null" (. instr = new Instruction.NoArgs(PUSH_NULL); .)
    | "globals" (. instr = new Instruction.NoArgs(PUSH_GLOBALS); .)
    | StringExpr<out sval> (. instr = new Instruction.Args(PUSH_STRING, shortToByteArray(currentProto.indexOfString(sval))); .)
    | FunctionId<out sval> (. instr = new Instruction.PushFunction(sval, t.line); .)
    | FloatExpr<out fval> (. instr = new Instruction.Args(PUSH_FLOAT, floatToByteArray(fval)); .)
    | IntExpr<out ival> (. instr = smallestPush(ival); .)
    ).
  Locals<out Instruction instr> = (. byte op = 0; int index; .)
    ( "load" (. op = LOAD; .) | "store" (. op = STORE; .) )
    IndexOrAlias<out index>
    (. instr = new Instruction.Args(op, byteToByteArray(index)); .) .
  Globals<out Instruction instr> = (. byte op = 0; String string; .)
    ( "getglobal" (. op = GET_GLOBAL; .) | "setglobal" (. op = SET_GLOBAL; .) )
    StringExpr<out string> (. instr = new Instruction.Args(op, shortToByteArray(currentProto.indexOfString(string))); .) .
  JumpExpr<out Instruction instr> = (. byte op = 0; String label; .)
    ( "ifeq" (. op = IF_EQ; .)
    | "ifne" (. op = IF_NE; .)
    | "ifge" (. op = IF_GE; .)
    | "ifgt" (. op = IF_GT; .)
    | "ifle" (. op = IF_LE; .)
    | "iflt" (. op = IF_LT; .)
    | "jump" (. op = JUMP; .)
    ) Ident<out label> (. instr = new Instruction.Jump(op, label, t.line); .)
    .

Erst einmal habe ich ein paar Hilfproduktionen definiert, um Zahlen, Funktions IDs und ähnliches zu parsen. Außerdem habe ich die EOL-Produktion definiert, welche nichts weiter macht, als mindestens eine neue Zeile zu erzwingen. Das eigentliche Programm besteht dann, wie bereits erwähnt, aus mindestens einer Funktion. Eine Funktion beginnt mit .function, sowie einem Identifier und endet mit .end. Dazwischen dürfen beliebig viele Instruktionen stehen.
Am Anfang einer Funktion kann man festlegen, wieviele Parameter und lokale Variablen unterstützt werden. Außerdem kann man Aliase definieren, welche später dann durch Indizes ersetzt werden.
Doch bevor wir weiter ins Detail gehen, müssen wir uns überlegen wie wir das Programm im Speicher darstellen. Da wir die verschiedenen Labels und Funktions IDs erst noch korrekt auflösen müssen, können wir nicht direkt Bytecode oder gar korrekte VMFunctions erzeugen. Dementsprechend müssen wir Funktionen und Instruktionen erst abstrakt im Speicher ablegen.

Den kompletten Code der jatg-Datei findet ihr im Quellcode Archiv.

Instruktionen

Für die Instruktionen erzeuge ich eine neue, abstrakte Klasse namens "Instruction". Diese dient als Basis für alle Instruktionen, selbst für die Label-Instruktion, welche nicht im Bytecode existieren wird.

public abstract class Instruction {
  public int size() {
    return 0;
  }
  public void writeOut(ByteArrayOutputStream out) {}
}

Von dieser Klasse leite ich dann die "einfachen" Instruktionen ab:

public class NoArgs extends Instruction {
  public final byte opCode;
  public NoArgs(byte opCode) {
    this.opCode = opCode;
  }

  @Override
  public int size() {
    return 1;
  }

  @Override
  public void writeOut(ByteArrayOutputStream out) {
    out.write(opCode);
  }
}

public class Args extends NoArgs {
  public byte[] args;

  public Args(byte opCode, byte[] args) {
    super(opCode);
    this.args = args;
  }

  @Override
  public int size() {
    return 1 + args.length;
  }

  @Override
  public void writeOut(ByteArrayOutputStream out) {
    out.write(opCode);
    try {
      out.write(args);
    } catch(IOException e) {
      e.printStackTrace();
    }
  }
}

Die NoArgs Klasse wird für die OpCodes benutzt, welche keine Argumente besitzen. Die Args Klasse wird für alle OpCodes benutzt, welche mindestens ein Argument haben. Allerdings gibt es dort eine Ausnahme. Für die verschiedenen Jump Befehle, erzeuge ich eine weitere Klasse, da das Sprungziel erst noch ermittelt werden muss:

public class Jump extends Args {
  public final String label;
  public final int line;

  public Jump(byte opCode, String label, int line) {
    super(opCode, null);
    this.label = label;
    this.line = line;
  }

  @Override
  public int size() {
    return 3;
  }
}

public class Label extends Instruction {
  public final String name;
    public final int line;

  public Label(String name, int line) {
    this.name = name;
    this.line = line;
  }
}

public class PushFunction extends Args {
  public final String name;
  public final int line;

  public PushFunction(String name, int line) {
    super(OpCode.PUSH_FUNCTION, null);
    this.name = name;
    this.line = line;
  }

  @Override
  public int size() {
    return 3;
  }
}

Die Zeile in der der jeweilige Befehl auftritt, muss jeweils dem Konstruktor übergeben werden, da wir erst später auf Fehler prüfen können und für die Fehlermeldung auch die Zeile kennen sollten.

Funktionsprototypen

Neben den Instruktionsklassen brauchen wir auch noch eine Klasse für die Funktionsprototypen. Diese speichern die Strings, lokalen Variablen und vor allem die ganzen Instruktionen. Für die Strings und Aliase benötigen wir natürlich auch noch Hilfsmethoden, um neue Einträge hinzuzufügen.

public class Prototype {
  public final String name;
  public short index;
  public final ArrayList<Instruction> code = new ArrayList<Instruction>();
  private final ArrayList<String> strings = new ArrayList<String>();
  private HashMap<String, Short> aliases = new HashMap<String, Short>();
  public int params;
  public int locals;

  public Prototype(String name) {
    this.name = name;
  }

  public short indexOfString(String string) {
    if (!strings.contains(string))
      strings.add(string);
    return (short)strings.indexOf(string);
  }

  public boolean containsAlias(String alias) {
    return aliases.containsKey(alias);
  }

  public void addAlias(String alias, short index) {
    aliases.put(alias, index);
  }

  public short indexOfAlias(String alias) {
    if (aliases.containsKey(alias)) return aliases.get(alias).shortValue();
    return -1;
  }

  public void addInstruction(Instruction instr) {
    code.add(instr);
  }

  public void writeOut(DataOutputStream out) throws IOException {
    out.writeShort(strings.size());
    for (String s : strings) {
      out.writeShort(s.length());
      out.write(s.getBytes());
    }
    out.writeByte(params);
    out.writeByte(locals);
    byte[] code = getBytecode();
    out.writeInt(code.length);
    out.write(code);
  }

  public byte[] getBytecode() {
    ByteArrayOutputStream out = new ByteArrayOutputStream();
    for (Instruction instr : code) {
      instr.writeOut(out);
    }
    return out.toByteArray();
  }

  public String[] getStrings() {
    String[] result = new String[strings.size()];
    strings.toArray(result);
    return result;
  }
}

Assembler

Wenn wir die jatg-Datei kompiliert haben, können wir jetzt die eigentlichen Assemblermethoden zusammenbauen. Diese nutzen den generierten Scanner und Parser um eine Datei einzulesen und zu parsen. Anschließend können wir das Ergebnis mit Hilfe der writeOut-Methoden in eine Datei schreiben oder direkt passende VMFunctions erzeugen.

public class Assembler {
  public static void assemble(String in, String out) throws IOException {
    assemble(new File(in), new File(out));
  }
  public static void assemble(File in, File out) throws IOException {
    Scanner scanner = new Scanner(new FileInputStream(in));
    Parser parser = new Parser(scanner);
    parser.Parse();
    if (parser.errors.count == 0) {
      writeOut(out, parser.getPrototypes());
    } else {
      throw new IOException("Failed to assemble file");
    }
  }

  public static VMFunction[] assemble(VMTable globals, String in) throws IOException {
    return assemble(globals, new File(in));
  }

  public static VMFunction[] assemble(VMTable globals, File in) throws IOException {
    Scanner scanner = new Scanner(new FileInputStream(in));
    Parser parser = new Parser(scanner);
    parser.Parse();
    if (parser.errors.count == 0) {
      Prototype[] protos = parser.getPrototypes();
      VMFunction[] functions = new VMFunction[protos.length];
      for (int i = 0; i < protos.length; i++) {
        Prototype p = protos[i];
        functions[i] = new VMFunction(globals, p.getBytecode(), functions, p.getStrings(), p.locals, p.params);
      }
      return functions;
    } else {
      throw new IOException("Failed to assemble file");
    }
  }

  private static void writeOut(File output, Prototype[] protos) throws IOException {
    DataOutputStream out = new DataOutputStream(new FileOutputStream(output));
    try {
      out.writeInt(Loader.MAGIC_NUMBER);
      out.writeShort(protos.length);
      for (Prototype p : protos)
        p.writeOut(out);
    } finally {
      if (out != null)
        out.close();
    }
  }
}

Um das alles zu testen, schreiben wir uns eine kleine Testdatei:

.function main
push 10
push 10
add
getglobal "print"
swap
call 1
getglobal "print"
push @max
push 10
push 20
call 2
call 1
.end

.function max
.limit 2 2
.local a 0
.local b 1
load $a
load $b
ifge greater
load $b
return
greater:
load $a
return
.end

Das ganze können wir nun wie folgt zusammenbauen:

Assembler.assemble("src/com/infectedbytes/tutorials/simplevm/asm.txt", "src/com/infectedbytes/tutorials/simplevm/out.txt");
Loader.load(globals, "src/com/infectedbytes/tutorials/simplevm/out.txt")[0].call(null);

Assembler.assemble(globals, "src/com/infectedbytes/tutorials/simplevm/asm.txt")[0].call(null);

Abschluss

Damit sind wir auch hier am Ende angelangt. Dank dem Assembler können wir nun auch relativ simpel Programme schreiben und direkt laden.

Quellcode zu diesem Teil der Serie: 09_assembler.zip