Compiler Entwicklung mit Coco/R

Category: 

Coco/R ist ein Compiler Generator, welcher eine attributierte Grammatik als Eingabe erhält und daraus einen Scanner und Parser erzeugt. Der Scanner arbeitet als deterministischer, endlicher Automat und zerlegt die Eingabe in Tokens. Der Parser ist ein sogenannter recursive descent parser. In diesem Tutorial werde ich anhand kleiner Beispiele auf die Verwendung von Coco/R eingehen.

Falls man sich bisher noch nie mit Compilern beschäftigt hat, so sollte man sich ggf. dieses kleine Tutorial angucken: Compiler Grundlagen

Coco/R herunterladen

Zuerst sollte man sich Coco/R von der offiziellen Seite herunterladen. Coco gibt es für verschiedene Programmiersprachen, hier werden wir erst einmal nur auf die Java Version eingehen. Ladet euch dazu die folgenden Dateien herunter:

  • Coco.jar - Beinhaltet den Coco/R Compiler generator
  • Scanner.frame - Beinhaltet den Rahmencode des Scanners
  • Parser.frame - Beinhaltet den Rahmencode des Parsers

Aufbau einer Compiler Spezifikation

Eine Compiler Spezifikation besteht aus mehreren Sektionen:

COMPILER CompilerName
CHARACTERS
  cr  = '\r'.
  lf  = '\n'.
  tab = '\t'.
  ...
TOKENS
  ...

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

IGNORE cr + lf + tab

PRODUCTIONS
  ...
END CompilerName.

Grundlegend wird die Spezifikation durch COMPILER CompilerName und END CompilerName eingeschlossen. Alles dazwischen gehört zur Definition des Compilers. Optional kann (und sollte) man am Anfang angeben, ob der erzeugte Code eine package Deklaration hat: $package=packagename
Am Anfang muss man definieren was für Zeichen benutzt werden können und welche Tokens es gibt. Durch die COMMENTS Befehle, kann man angeben wie Kommentare aussehen sollen. Der IGNORE Befehl sagt aus, welche Zeichen man ignorieren möchte. Zum Schluss folgt noch der wichtigste Teil, die Produktionen. Diese geben die eigentliche Grammatik an.

Praktisches Beispiel

Oft lernt man durch Beispiele besser als durch reine Theorie, daher schauen wir uns nun ein kleines Beispiel an. Wir möchten einen Compiler bauen, welcher einfache Arithmetische Ausdrücke berechnen kann. Gültiger Programmcode dieser Sprache soll z.B. so aussehen:

calc 1+2+3
calc 40+2

Die zugehörige Spezifikation sieht so aus:

$package=com.infectedbytes.tutorials.compiler.math
COMPILER Math
CHARACTERS
  digit = "0123456789".
  cr  = '\r'.
  lf  = '\n'.
  tab = '\t'.

TOKENS
  number = digit {digit}.

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

IGNORE cr + lf + tab

PRODUCTIONS
  Math = {"calc" Expr}.
  Expr = Term {'+' Term}.
  Term = number.
END Math.

Diese speicher ich nun direkt im passenden Package meines Projekts unter dem Namen Math.jatg.

Wenn man ganz ohne package arbeiten möchte, kann man einfach die erste Zeile weglassen.

Als erstes definieren wir uns Zeichen und Tokens die wir benutzen möchten. Da wir uns nur um Zahlen kümmern wollen, definieren wir nur ein Token namens number. Jede Zahl besteht aus mindestens einer Ziffer, in der Ausdrucksnotation sieht das dann so aus: number = digit {digit}.
Die geschweiften Klammern sagen, dass der Inhalt beliebig oft auftreten darf. digit{digit} erzeugt somit beliebig lange Zahlen, die mindestens eine Ziffer enthalten. Am Ende der Definition muss ein Punkt stehen.

Wie bereits erwähnt wird durch die Produktionen eine KFG definiert. Das Startsymbol ist immer der Name des Compilers. In unserem Beispiel ist dies Math. Wir möchten nun beliebig viele calc Ausdrücke erlauben, dazu nutzen wir wieder die geschweiften Klammern: Math = {"calc" Expr}
Expr besteht aus mindestens einem Term und kann durch + mit weiteren Termen verknüpft sein. Term selbst wird dann durch eine number ersetzt.

Kompilieren

Nun haben wir ein kleines Beispiel und müssen dieses nur noch kompilieren.
Dazu öffnen wir ein Terminal und navigieren zu Coco.jar. Der Einfachheit halber habe ich diese, zusammen mit den frame Dateien, im gleichen Verzeichnis liegen wie unsere Math.jatg Datei.
In der Konsole geben wir nun einfach folgendes ein: java -jar Coco.jar Math.jatg
Falls wir irgendwelche Fehler in der Spezifikation haben, werden sie uns nun angezeigt:

Coco/R (Apr 15, 2013)
checking
  Math deletable
parser + scanner generated
0 errors detected

Fehler wurden keine gefunden, jedoch hat Coco festgestellt, dass man die Grammatik noch vereinfachen könnte. Diese Tatsache ignorieren wir jedoch und machen weiter.

Nun wollen wir die Sprache natürlich testen. Dazu erstellen wir uns eine passende Java Datei und führen diese aus:

package com.infectedbytes.tutorials.compiler.math;

public class Test {
        public static void main(String[] args) {
                compile("..."); // hier den passenden Pfad zur Testdatei angeben
        }

        private static void compile(String file) {
                System.out.println("Compiling " + file);
                Scanner scanner = new Scanner(file);
                Parser parser = new Parser(scanner);
                parser.Parse();
                System.out.println(parser.errors.count + " errors detected");
        }
}

Eine passende Testdatei könnte so aussehen:

calc 1+2+3
calc 40+2

Sematik

Soweit so gut, aber bisher wird nur geprüft, ob die Syntax korrekt ist. Die eigentliche Berechnung des Ausdrucks fehlt noch.
Um dies zu implementieren, müssen wir die Grammatik um Attribute erweitern. Dazu fügen wir an geeigneten Stellen Java Code ein.

...
PRODUCTIONS
  Math = {            (. int result = 0; .)
    "calc"
    Expr<out result>  (. System.out.println(result); .)
  }.
  Expr<out int n> =  
    Term<out n>
    {'+'              (. int tmp; .)
    Term<out tmp>     (. n += tmp; .)
    }.
  Term<out int n> =
    number            (. n = Integer.parseInt(t.val); .)
    .
END Math.

Jede einzelne Produktion wird von Coco in eine Methode umgewandelt. Dabei können wir sowohl den Rückgabetyp, als auch die Parameter angeben.
Dazu müssen wir die gewünschte Signatur in spitzen Klammern schreiben, z.B. <out int n>. Falls wir einen Rückgabetyp wollen, so muss dies der erste Parameter sein und mit einem out gekennzeichnet sein.
Zum besseren Verständnis hier noch ein paar Beispiele:
Test<int x, int y> erzeugt folgende Methode: void Test(int x, int y){ ... }
Test<out int x, int y> erzeugt folgende Methode: int Test(int y) { int x; ... return x; }
Test<int x, out int y> wirft einen Fehler, da out nur am ersten Parameter erlaubt ist.

Wenn wir die Signatur entsprechend angepasst haben, können wir noch Java Code innerhalb der Methode hinzufügen. Dazu müssen wir den Code mit (. und .) einschließen.
Die Expr Produktion wird von Coco in folgende Methode übersetzt:

int  Expr() {
  int  n;
  n = Term();
  while (la.kind == 3) {
    Get();
    int tmp;
    tmp = Term();
    n += tmp;
  }
  return n;
}

Wie man sieht, wurde Term<out n> in n = Term() übersetzt. Der von uns definierte Java Code wird genau an der Stelle eingefügt, wie wir ihn definiert haben. Die lokale Variable tmp wird Beispielweise direkt nach dem holen des Plus Zeichens deklariert.
Wenn wir nun diese neue Version starten, erhalten wir auf der Konsole die korrekten Ergebnisse ausgegeben.

Abschluss

Wir haben nun gelernt, wie wir mit Coco/R einen einfachen Compiler erzeugen können. Natürlich war das Beispiel noch recht simpel, daher werde ich bald ein etwas komplexeres Beispiel veröffentlichen.
Bei Fragen und Anmerkungen könnt ihr gerne einen Kommentar hinterlassen.