Einfacher Compiler in C++: Rekursive-Abstieg-Parser Tutorial (CSE340)

Einführung in den Compilerbau – Dein erstes Projekt für CSE340

Das Erstellen eines Compilers klingt komplex – und das ist es auch. Aber mit einem strukturierten Ansatz und den richtigen Werkzeugen wird es machbar. Im CSE340 Fall 2025 Project 1 implementierst du einen einfachen Compiler für eine eigene kleine Sprache. Du wirst einen rekursiven Abstiegsparser schreiben und Datenstrukturen für die semantische Analyse und Ausführung nutzen. Dieses Tutorial führt dich Schritt für Schritt durch die Grundlagen – von der Grammatik über den Parser bis zur Fehlerbehandlung.

Stell dir vor, dein Compiler ist wie ein KI-Assistent, der eine Anweisung wie „F = x^2 + 1“ versteht und daraus eine Berechnung macht. Genau das wirst du umsetzen.

Was ist ein Compiler und warum ist dieses Projekt relevant?

Ein Compiler übersetzt Quellcode in ausführbaren Code. In deinem Projekt geht es um einen Compiler, der eine einfache Programmiersprache mit Polynom-Definitionen, INPUT- und OUTPUT-Anweisungen verarbeitet. Die Eingabe besteht aus vier Teilen: TASKS, POLY, EXECUTE und INPUTS. Dein Parser prüft die Syntax, dann die Semantik und führt schließlich den Code aus.

Das Projekt ist größer als andere, aber nicht schwer – es erfordert nur eine gute Planung. Lies die Aufgabenstellung mehrmals, erstelle einen Implementierungsplan und beginne dann mit dem Codieren. Die bereitgestellten Dateien (lexer.h, inputbuf.h) dürfen nicht verändert werden.

Die lexikalische Analyse: Token für Token

Bevor der Parser arbeitet, muss der Lexer den Quelltext in Tokens zerlegen. Die Klasse LexicalAnalyzer stellt Methoden wie GetToken() und peek() bereit. Du instanziierst genau ein Lexer-Objekt und rufst diese Methoden auf. Die Token-Definitionen sind vorgegeben – du musst sie nur nutzen.

Ein Beispiel: Aus F = x^2 + 1; werden Tokens wie ID, ASSIGN, NUM, PLUS. Der Parser erwartet eine bestimmte Reihenfolge. Weicht die Eingabe ab, gibt es einen Syntaxfehler.

Rekursiver Abstiegsparser: Schritt für Schritt

Der rekursive Abstiegsparser ist eine Technik, bei der jede Grammatikregel eine Funktion ist. Du beginnst mit dem Startsymbol und rufst rekursiv Funktionen für Teilausdrücke auf. Für die gegebene Grammatik schreibst du Funktionen wie parseProgram(), parsePolySection(), parseExecuteSection().

Wichtig: Verwende expect(), um ein bestimmtes Token zu erwarten. Wenn das Token nicht kommt, melde einen Syntaxfehler. Der Parser stoppt dann.

Beispielhafte Grammatik (vereinfacht):

program ::= TASKS tasks_section POLY poly_section EXECUTE execute_section INPUTS inputs_section
poly_section ::= poly_decl_list
poly_decl ::= ID '=' poly_body ';'
poly_body ::= term { '+' term }
term ::= factor { '*' factor }
factor ::= ID | NUM | '(' poly_body ')'

Dein Parser ruft für poly_section eine Funktion auf, die wiederum poly_decl aufruft, und so weiter.

Semantische Analyse: Fehler finden, die kein Parser sieht

Nach der Syntaxprüfung folgt die semantische Analyse. Hier prüfst du, ob die Verwendung von Variablen und Polynomen korrekt ist. Typische Fehler:

Semantischer Fehler Code 1: Ein Polynom wird verwendet, aber nicht deklariert.
Semantischer Fehler Code 2: Im Polynomkörper taucht eine Variable auf, die nicht in der Parameterliste steht (z.B. G(X,Y) = X Y^2 + X Z; – Z ist nicht deklariert).
Weitere Fehler: Doppelte Deklarationen, falsche Argumentanzahl.

Dein Compiler muss diese Fehler erkennen und eine Meldung wie Semantic Error Code 2: 5 ausgeben (die Zahl ist die Zeilennummer).

Speichere die Polynome in einer geeigneten Datenstruktur, z.B. einer Map von Polynomnamen zu einer Struktur mit Parameterliste und Ausdrucksbaum. So kannst du bei der Ausführung die Polynome mit konkreten Werten auswerten.

Ausführung: Von der Eingabe zur Ausgabe

Wenn keine Fehler vorliegen, führt der Compiler den EXECUTE-Block aus. INPUT-Anweisungen lesen Werte aus der INPUTS-Liste, OUTPUT gibt Ergebnisse aus. Die Polynome werden mit den übergebenen Argumenten berechnet.

Beispiel aus der Aufgabenstellung:

TASKS
1 2
POLY
F = x^2 + 1;
G = x + 1;
EXECUTE
INPUT X;
INPUT Y;
X = F(X);
Y = G(Y);
OUTPUT X;
INPUTS
1 2 3 18 19

Die Ausgabe ist 2 (da X=1 -> F(1)=2, Y=2 -> G(2)=3, aber nur X wird ausgegeben).

Trends und Analogien: Wie ein Compiler den Alltag erleichtert

Denk an einen KI-Chatbot, der deine Anfrage parsen muss – ähnlich wie dein Compiler den Code. Oder an eine Finanz-App, die Formeln wie Zins = Kapital * Rate ^ Jahre auswertet. Dein Compiler macht genau das: Er liest eine Formel, prüft sie auf Korrektheit und berechnet das Ergebnis. In der Spieleentwicklung werden oft eigene Skriptsprachen mit Compilern übersetzt, um Spielelogik flexibel zu halten.

Ein weiteres Beispiel aus dem E-Sport: Ein Turnierplaner könnte eine kleine Sprache verwenden, um Match-Ergebnisse zu berechnen. Dein Compiler könnte die Regeln parsen und die Rangliste aktualisieren.

Implementierungsplan für dein Projekt

Grammatik verstehen: Lies die Grammatik in der Aufgabenstellung. Markiere, welche Teile optional oder wiederholbar sind.
Parser-Grundgerüst: Schreibe die Hauptfunktion parseProgram(), die die vier Abschnitte nacheinander aufruft.
Syntaxfehler behandeln: Verwende expect() und gib bei Fehlern SYNTAX ERROR !!!!!&%!! aus.
Datenstrukturen für Polynome: Erstelle eine Klasse Poly mit Name, Parameterliste und Ausdrucksbaum (z.B. als ExprNode).
Semantische Prüfung: Nach dem Parsen durchlaufe die Polynome und prüfe auf Fehler wie undeklarierte Variablen.
Ausführung: Implementiere einen Interpreter, der die Polynome mit gegebenen Werten auswertet.
Testen: Nutze die Beispiele aus der Aufgabenstellung, um deinen Compiler zu testen.

Häufige Fehler und wie du sie vermeidest

Mehrere Lexer-Instanzen: Erstelle nur ein Lexer-Objekt. Sonst gibt es Fehler.
Vergessene Semikolons: Die Grammatik verlangt Semikolons nach Polynom-Deklarationen und Anweisungen. Fehlende Semikolons führen zu Syntaxfehlern.
Falsche Variablen in Polynomen: Wenn ein Polynom mit Parametern deklariert wird, darf der Körper nur diese Parameter und Zahlen enthalten. Sonst gibt es einen semantischen Fehler.
Kein peek() vor expect(): Nutze peek(), um das nächste Token zu prüfen, bevor du es konsumierst.

Fazit: Dein erster Compiler – ein Meilenstein

Mit diesem Tutorial hast du die Grundlagen für dein CSE340-Projekt gelegt. Du kennst jetzt die Struktur eines einfachen Compilers, die Rolle des Lexers, den Aufbau eines rekursiven Abstiegsparsers und die semantische Analyse. Setze die Schritte um, teste mit den Beispielen und erweitere deinen Compiler Schritt für Schritt. Viel Erfolg!

Wenn du Hilfe brauchst, denk daran: Assignment Chef bietet Unterstützung bei Programmierprojekten – aber versuche zuerst, selbst eine Lösung zu erarbeiten. Das Verständnis, das du dabei gewinnst, ist unbezahlbar.