Compilerdesign in C

Ethon

Hoi!
Wir müssen für die Uni einen self-hosting Compiler schreiben. Da C recht trivial ist, habe ich beschlossen, einen C-Compilier in C zu schreiben, mit ein paar Extras und abzüglich schwer zu implementierender Subsets. (Auch wenn ich mir noch nicht klar bin welche)

Jetzt scheitere ich gerade etwas daran, mir ein Vernünftiges Design für Lexer und Parser einfallen zu lassen. Ich habe bei meinen Versuchen in der Vergangenheit auch in C++ gestrauchelt, den Lexer schön zu bekommen. In der C Version sieht es nocht schlimmer aus, im Prinzip ist es aktuell so:

#include <alles was ich brauche>

/*** Implementation details ***/
typedef struct LexerTag
{
	FILE* file;
	unsigned line, pos;
	int currentChar;
    jmp_buf jumpEof, jumpError;
} Lexer;

static int Lexer_currentChar(Lexer* lexer)
{
    /* Gibt das aktuelle Zeichen zurück */
}

static int Lexer_nextChar(Lexer* lexer)
{
    /* Holt das nächste Zeichen aus dem Stream, bricht im Fehlerfall mit longjmp ab */
    /* Passt dabei line/pos an */
}

static void Lexer_skipUntilString(Lexer* lexer, char const* end)
{
    /* Liest und verwirft solange Zeichen, bis ein String gefunden wurde */
}

static void Lexer_skipUntilChar(Lexer* lexer, char end)
{
    /* Liest und verwirft solange Zeichen, bis ein Zeichen gefunden wurde */
}

static int Lexer_skipSpaces(Lexer* lexer)
{
    /* Verwirft Whitespaces */
}

static int Lexer_skipComment(Lexer* lexer)
{
    /* Überspringt Kommentare */
}

static void Lexer_getWord(Lexer* lexer, char* dest, unsigned len)
{
    /* Liest das aktuelle (alphanumerische) Wort vom Stream */)
}

static int Lexer_processSpecial(Lexer* lexer, Token* out)
{
    /* Behandelt das aktuelle Zeichen falls es ein Interpunktionszeichen ist,
     * zb Operatoren, Klammern etc. True, wenn etwas verarbeitet wurde. */
}

static int Lexer_processKeyword(Token* out)
{
    /* Behandelt das aktuelle Wort, wenn es ein Keyword ist, zb "return".
     * True, wenn etwas verarbeitet wurde. */
}

static int Lexer_processIdentifier(Lexer* lexer, Token* out)
{
    /* Verarbeitet den aktuellen Wert, falls er ein Identifdier ist .
     * True, wenn etwas verarbeitet wurde. */
}

static int Lexer_processLiteral(Lexer* lexer, Token* out)
{
    /* Verarbeitet den aktuellen Wert, falls er ein Literal ist, also zb ein
     * String/Int/Char/Float Literal. True, wenn etwas verarbeitet wurde. */
}

/*** Public API ***/

Lexer* Lexer_createFromFile(char const* filename)
{
    /* Erzeugt einen Lexer, null im Fehlerfall */
}

void Lexer_destroy(Lexer* lexer)
{
    /* Zerstört einen Lexer */
}

void Lexer_nextToken(Lexer* lexer, Token* out)
{
    assert(lexer && out);

    // Handle eof.
    if(setjmp(lexer->jumpEof))
    {
        out->line = lexer->line;
        out->pos = lexer->pos;
        out->type = TOK_EOF;
        out->value[0] = 0;
        return;
    }

    // Handle I/O errors.
    if(setjmp(lexer->jumpError))
    {
        perror("I/O Error");
        exit(-1);
    }

    // Skip Whitespaces and comments.
    while(Lexer_skipSpaces(lexer) || Lexer_skipComment(lexer))
    { }

    // Prepare the token object.
    out->line = lexer->line;
    out->pos = lexer->pos;
    out->type = TOK_UNK;
    out->value[0] = '\0';

    // Extract the token.
    if(Lexer_processSpecial(lexer, out))
        return;

    if(Lexer_processIdentifier(lexer, out))
        return;

    if(Lexer_processLiteral(lexer, out))
        return;
}

Ich komme einfach nicht darauf, was ich sinnvoll aufsplitten könnte, die Sourcedatei ist schon weit über 1000 LOC groß und ich kann lange noch nicht jeden C-Source lexen.
Desweiteren scheint meine Schleife zum Entfernen von Comments/Spaces nicht zu funktionieren, zb soetwas

int /* Hier kommt die Main funktion */ /*Ich meine 'main' */   main()

verursacht Garbage, obwohl die Funktionen selbst eigentlich beide optimal funktionieren, wo liegt mein Denkfehler?

Und was wären ein paar grobe Designideen zum Design des Parsers? Ich wollte C++-Style einen AST mit nachgebauter Polymorphie, also Funktionszeigern aufbauen, gute Idee? Den Codegenerator analog (Ich baue mir eine VM, um bei der Codegenerierung Schmalz zu sparen, dh. da muss kein x86 raus)

Würde mich über jede sinnvolle Anregung freuen.
Danke und Grüße,
Ethon

Mechanics

An der Uni müsst ihr doch bestimmt einen Parser Generator benutzen und die Grammatik in EBNF definieren. Das von Hand zu schreiben find ich reichlich sinnlos.

gigg

Hallo, ich kann leider nicht helfen, dafür reicht mein C nicht.
Mir ist nur aufgefallen, dass in der Code-Zeile

int /* Hier kommt die Main funktion */ */Ich meine 'main' */   main()

das Kommentarzeichen vor "Ich" verkehrt rum ist.

knivil

Meine Standardantwort: Schon mal Flex und Bison angeschaut?

Bashar

Das Benutzen von generiertem Code oder von Libraries hat eventuell das Problem, dass man den dazu benötigten Sprachumfang für ein Uni-Projekt von der Zeit her nicht implementiert kriegt.

Ethon

Das ist mit Flex und Bison ist ne tolle Idee, danke.
Ich arbeite mich da mal ein, gibt es ein brauchbares Einsteigertutorial? Habe da nichts wirklich Freundliches gefunden, sonst muss ich halt aus der Manpage lernen.

Gibt es bei euch keine Vorlseung "Compilerbau"? Oder gab es eine?
Da sollte es doch irgendwo ein paar Skripte geben.

Ethon

Die Sache ist dass ich den Kurs erst nächstes Sommersemester besuche, da habe ich allerdings so viel zu tun, dass ich Vorhinein Arbeit abbauen möchte.
Die Vorlesung selbst soll aber in etwa 1:1 Compiler Construction von Niklaus Wirth wiedergeben, einfach nur ohne Snippets in Oberon sondern in C.

Mechanics

Ich würde sagen, das macht ohne Theorie wenig Sinn. Mach lieber was für andere Vorlesungen im Voraus. Compilerbau ist eines der wichtigsten Themas, damit hat man immer wieder zu tun.

*Q* 1

Mechanics schrieb:

Compilerbau ist eines der wichtigsten Themas, damit hat man immer wieder zu tun.

Wo braucht man das denn z.B.?

Meinst du jetzt, wenn man irgendwas parsen will oder so, oder meinst du bezogen aufs Studium, oder was meinst du?

Mechanics

Ja, wenn man irgendwas parsen will. Und das kommt ständig vor. Es muss ja nichts kompliziertes wie eine Programmiersprache sein, reicht ja irgendeine ASCII basiertes Dateiformat, oder Strings, die nach einem bestimmten Muster aufgebaut sind, oder Formeln, Regeln usw... Und dann seh ich oft die abenteurlichsten Konstrukte mit String Operationen (indexOf & Co), anstatt einen einfachen Scanner und Parser zu schreiben.

ja klar, es gibt typ a, der haut einen url validator mit ner regex platt und typ b, der schreibt dafür nen parser und scanner. ich bin dann typ c und verwurste so ne scheiße in drei funktionen