Ich schreibe gerade einen C-Compiler, um zu lernen, wie ein Compiler funktioniert.

Ein C-Compiler übersetzt Quellcode (Strings) in Assembler.

Dieser Compiler zerlegt die Strings zunächst in Tokens, parst sie dann mithilfe der Tokens zu Knoten und erzeugt schließlich den Assembler-Code.

  • Tokenizer
  • Parser
  • Codegenerator

Tokenizer

Der Tokenizer läuft über die Strings und erzeugt eine verkettete Liste von Tokens.

Parser

Der Parser parst die Strings zu Knoten.

Um den Parser zu implementieren, braucht es einen Entwurf des Compilers. Üblicherweise verwendet man dafür die BNF-Notation (Backus-Naur-Form).

Die BNF-Notation sieht so aus:

expr = num ("+" num | "-" num)*

Das ist ein einfaches Beispiel für Addition und Subtraktion. Dieser Ausdruck nimmt eine Zahl entgegen und addiert oder subtrahiert eine weitere Zahl, falls eine folgt (* bedeutet null oder mehr Wiederholungen).

Codegenerator

Der Codegenerator erzeugt den Assembler-Code.

Das BNF-Beispiel von oben wird etwa in folgenden Assembler übersetzt:

.intel_syntax noprefix
.globl main
main:
    push 2
    push 3
    pop rdi
    pop rax
    add rax, rdi
    push rax
    pop rax
    ret

Das entspricht 2 + 3 und ist als Stack-Maschine umgesetzt.

Zuerst werden die beiden Zahlen 2 und 3 auf den Stack gelegt, dann wird 3 dem Register rdi und 2 dem Register rax zugewiesen. Zum Schluss wird 2 + 3 berechnet und das Ergebnis in rax abgelegt. Die nächsten beiden Anweisungen kann man in diesem Beispiel ignorieren, denn sie machen effektiv nur rax = rax. ret liefert das Ergebnis zurück, also 5.

Fortschritt

Bisher habe ich die mathematischen Berechnungen implementiert.

Mein Quellcode liegt auf github.