HaDes XP - HaCom

HaCom steht für "HaDes Compiler" - seine Aufgabe ist es, Quellcode in der Programmiersprache HL (HaDes Language) in Objektcode (HO) zu übersetzen, der dann vom Linker weiterverarbeitet werden kann.

Wieso nur...

haben wir eine eigene Programmiersprache erfunden und einen eigenen Compiler programmiert? Inzwischen habe auch ich mich das öfter gefragt, aber eigentlich war der Compiler als Übung zur Vorlesung Compilerbau gedacht, und noch einen Compiler für eine Sprache, die es schon gibt, zu entwickeln ist ja langweilig... Außerdem scheint es mir auch nicht gerade einfach zu sein, gcc zu portieren.

Implementierung von HaCom

Wie allgemein üblich, besteht der HaDes Compiler HaCom aus mehreren Übersetzungsphasen:

• Lexikalische Analyse. Die lexikalische Analyse wird durch einen mit Hilfe des Lexergenerators flex erzeugten Lexers durchgeführt. Die Klasse HLLexer kapselt diesen und implementiert außerdem einen einfachen Präprozessor.
• Syntaktische und semantische Analyse. Die syntaktische Analyse erfolgt mit einem von Hand geschriebenen rekursiven Abstiegsparser, der in der Klasse HLParser implementiert ist und bereits beim Einlesen semantische Bedingungen überprüft.
• Optimierung. Codeoptimierungen, unter Anderem die Vorab-Berechnung von Konstanten sowie Inlining von Funktionen werden auf der Zwischenstufe des in C++-Objekten abgelegten Codes von der Klasse HLOptimizer durchgeführt.
• Code-Generierung. Zum Schluss wird der Code durchlaufen, Variablen werden an Register gebunden und HaDes XP-Maschinencode wird generiert. Dies geschieht im HLCodeGenerator.

Die Sprache HL

HL ist eine imperative Programmiersprache, deren Syntax sich grob an C anlehnt. Der Funktionsumfang von C ist allerdings nicht vollständig vorhanden, da HL quasi typenlos ist (alles ist ein 32-Bit-Wort) und die HL-records nur mit Mühe C-structs ersetzen können. Gegenüber Assembler ist es aber dennoch ein Riesen-Fortschritt und ermöglichte uns die zügige Entwicklung unserer Spiele. 

HL-Grundlagen

Anstelle einer formalen, langweiligen Syntaxdefinition möchte ich versuchen, HL anhand eines kleinen Beispielprogramms zu erklären. 

/* *************************************
   Jede HL-Programmdatei besteht aus drei Abschnitten.
   Sie beginnt mit den Importen, durch die Deklarationen aus
   anderen Dateien verfügbar gemacht werden.
   Dies funktioniert ähnlich wie in Java. */
import hal;
// Als Verzeichnistrenner wird ein Punkt verwendet.
import images.green;

/* *************************************
   Im zweiten Abschnitt werden Konstanten, Variablen und
   Record-Typen deklariert. */

const null = 0x0; // Konstante ohne Typ, d.h. 32-bit-Wort.
var glob_n = 10; // Globale Variable ohne Typ, wird beim Laden des
// Programms vorinitialisiert.
// Array-Konstanten (aus 32-bit-Worten) können durch Strings initialisiert
// werden und werden dann automatisch null-terminiert.
// Array-Konstanten oder -Variablen werden bei Verwendung im Programm
// stets automatisch als Pointer interpretiert (wie in C).
const hallo[] = "Hallo!\n";
// Compact Strings sind ein Spezialfall, hier werden bis zu vier
// Zeichen in ein 32-bit-Wort gepackt.
const hallo_c[] = C"Hallo!\n";
// Array-Variable (aus 32-bit-Worten). Zur Initialisierung können Literale,
// Konstanten und Funktionspointer verwendet werden.
var arr[] = { 1, null, addressof lowercase };
// Record-Typen entsprechen ungefähr C-Structs.
record Id {
 value;
}
// Sie können untypisierte 32-Bit-Werte, Arrays
// und Mitglieds-Records bzw. Zeiger auf Records (Referenzen)
// enthalten.
record Player {
 name[10];
 score;
 record Id id;
 ref Player next_player;
}
// Es können globale Records angelegt werden (braucht ordentlich Platz)
var record Player plyr;
// und auch globale Zeiger auf Records (das ist nur ein 32-bit-Wort)
var ref Player first_player;

/* *************************************
   Im dritten Abschnitt werden Funktionen implementiert. */

// Zur Einstimmung eine Implementierung von lowercase eines
// nicht kompakt gespeicherten Strings. Der String wird in-place bearbeitet,
// beachte dass jeder untypisierte Wert als Pointer verwendet werden kann
// und diese mit dem @-Operator dereferenziert werden. Ausdrücke werden wie
// in C von links nach rechts abgearbeitet.
function lowercase(str) returns()
vars(str_ptr) // Alle lokalen Variablen werden in vars aufgezählt.
{
  for(str_ptr = str; @str_ptr != 0; str_ptr++)
    if(@str_ptr >= 'A' && @str_ptr <= 'Z')
      @str_ptr += 32;
}
// Zählt die Anzahl der Vorkommen von char in str und gibt einen
// Zeiger auf das letzte Vorkommen zurück.
// Funktionen können beliebig viele Parameter und Rückgabewerte besitzen.
// Ein Rückgabewert kann wie eine lokale Variable verwendet werden.
function count(str, char) returns(count, ptr)
attribs(inline) // Das inline-Attribut weist den Compiler zum Inlinen an.
vars()
{
  count = 0;
  forever { // Endlosschleife
    if(@str == 0)
      leave; // ... die beim Auffinden eines 0-Characters abgebrochen wird
    if(@str == char) {
      count++;
      ptr = str;
      // Nur zur Demo: gehe mit next sofort weiter zum nächsten Durchlauf
      str++;
      next;
    }
    str++;
  }
}

Operatoren

Eine vollständige Aufzählung der HL-Operatoren (darunter sind einige ungewöhnliche enthalten), komplett mit ihrer Präzedenz, findet sich in der folgenden Tabelle.

Fixpunktarithmetik

Genau wie der HaDes XP-Prozessor und -Assembler hat auch HL besondere Unterstützung von Fixpunktzahlen mit je 16 bit Ganzzahl- und Dezimalpräzision. Da HL im Prinzip typenlos ist, wird diese durch spezielle Doppelpunkt-Operatoren bereitgestellt. Die Addition und Subtraktion +: und -: wirken eigentlich genau wie die Ganzzahloperatoren + und -, sollten aber zur Erhöhung der Übersichtlichkeit dennoch verwendet werden. Wesentliche Unterschiede gibt es dagegen bei Multiplikation *: und Division /:. Die Konversion von und zu Ganzzahlen kann mit Hilfe der HAL-Funktionen fp2int() und int2fp() durchgeführt werden. 

Arbeiten mit references und records

Auf die Mitglieder von Datenstrukturen (records) kann, egal ob diese direkt, also als records, oder indirekt durch einen Zeiger, also als references, verfügbar sind, leicht mit dem Punkt-Operator zugegriffen werden. Dabei können globale und lokale (unter vars) definierte refs oder records verwendet werden. Zu beachten ist aber, dass records bei der Parameterübergabe per Referenz übergeben werden, es werden also automatisch Zeiger gebildet. Funktionsparameter und -rückgabwerte können nur 32-bit-Worte sein. HL macht niemals automatisch Kopien von größeren Datenstrukturen, dies muss stets manuell mit mcopy() durchgeführt werden. Auch gibt es in HL keine Casts und keine Typprüfungen. 

// Fügt einen Player vorn an die globale Spielerliste an.
function add_player(ref Player p) returns()
vars(record Id id1, ref Id pid)
{
  p.next_player = first_player;
  first_player = p;
  // Demonstration lokaler Variablen
  pid = p.id; // Zeiger auf p.id wird gebildet
  id1.value = pid.value; // Wert kopiert
}

Builtin-Funktionen

Um hardwarenahe und sonstige Funktionalität zu unterstützen, kennt der Compiler einige Builtin-Funktionen, deren Aufrufe stets durch entsprechenden Inline-Assembler-Code ersetzt werden. Die Parameter dieser Funktionen können meist beliebige Ausdrücke (var) sein, manchmal sind aber Konstanten erforderlich (const). 

Funktionen mit beliebig vielen Rückgabewerten

In HL werden Rückgabewerte innerhalb einer Funktion wie normale lokale Variablen behandelt. Es können auch mehrere davon existieren. Um diese Rückgabewerte aufzufangen ist eine besondere Mehrfach-Zuweisungs-Anweisung nötig:

// Eine Funktion mit mehreren Rückgabewerten.
function returndemo() returns(a, b)
vars()
{
  a = 2; b = 5; // Werte zuweisen.
  return;       // Sofort zurückgehen.
  b = 7;        // Wird nie ausgeführt.
}

// Aufruf einer solchen Funktion. Links können beliebige Ausdrücke stehen.
(glob_n, arr[0]) = returndemo();

Funktionen mit variabler Argumentanzahl ("varargs")

Es sind Funktionen möglich, die zusätzlich zu ihren fest definierten Parametern beliebig viele weitere Parameter annehmen können. Dies wird über das Attribut varargs  mitgeteilt. Solche Funktionen dürfen nicht über Funktionspointer aufgerufen werden. Der Zugriff auf die variablen Parameter innerhalb der Funktion ist durch die Builtin-Funktionen va_start(), va_next() und va_count() möglich.

// Eine Funktion mit beliebiger Argumentanzahl.
function printall() returns() attribs(varargs)
vars(varg, va_count)
{
  varg = va_start();      // Zeiger auf erstes Argument.
  // Alle Argumente durchlaufen.
  for(va_count = va_count(); va_count; va_count--) {
    print(@varg);         // Ausgeben.
    varg = va_next(varg); // Zeiger weiterstellen.
  }
}

// Aufruf einer solchen Funktion.
printall(2, 3, 5, 7, 11, 13, 17, 19); // Alles wird ausgegeben.

Präprozessor

HaCom enthält auch bereits einen sehr einfachen Präprozessor. Dieser versteht nur die Direktiven #define NAME und #undef NAME, um Präprozessor-Bezeichner bekannt zu machen bzw. wieder zu löschen. Mit #ifdef NAME ... #endif bzw. #ifndef NAME ... #endif können die Bezeichner abgefragt werden und ein Teil des Codes bedingt auskommentiert werden. 

Der HL-Präprozessor ist Teil des normalen HL-Lexers. Dies hat einerseits den Vorteil, dass Präprozessor-Direktiven im Gegensatz zu C auch mitten in der Zeile stehen dürfen, andererseits darf aber der durch #ifdef auskommentierte Code nur gültige Tokens enthalten.