Compilerbau: Beispiel

Als Beispiel wird ein kleiner Taschenrechner herangezogen. Er zeigt die Arbeitsweise eines Compilers an einem wenig komplexen Beispiel.

Kontextfreie Grammatik

expression -> expression + term expression -> expression - term expression -> term term -> term * primary term -> term / primary term -> primery primary -> NUMBER primary -> -primary primary -> ( expression )

Diese Grammatik enthält bereits die Regeln der Priorität der Operatoren. Da vor der Auflösung der Expression mit seiner "Strichrechnung" der Term mit seiner "Punktrechnung" ausgeführt wird, gilt Punktrechnung vor Strichrechnung.

Rekursiver Abstieg

Handelt es sich um eine NUMBER, ist Primary beendet und kehrt zu Term zurück. Findet sich hier ein * oder ein /, wird erneut Primary gerufen. Andernfalls wird zu Expression, das wiederum auf + oder - prüft.

Findet Primary aber eine linke Klammer ruft es (rekursiv!) Expression auf, das wieder den ganzen Stapel durchläuft. Kehrt Expression wieder zurück, prüft Primary an der korrekten Stelle, ob die Klammer wieder geschlossen wird.

Listing des Parsers

double Expression() { double Value; Value = Term(); while (CurrentToken==PLUS || CurrentToken==MINUS) { if (CurrentToken==PLUS) { GetToken(); Value += Term(); } else if (CurrentToken==MINUS) { GetToken(); Value -= Term(); } } return Value; }

Wie in der Grammatik beschrieben, wird zunächst zu Term hinabgestiegen. Ist Term ausgewertet, prüft die Funktion auf die Tokens PLUS und MINUS. In diesem Fall ist die Expression noch nicht abgearbeitet, sondern ruft erneut Term. Durch die while-Schleife kann dies beliebig oft passieren. Erst wenn ein Zeichen erscheint, das weder PLUS noch MINUS ist, endet die Funktion und kehrt zurück.

double Term() { double Value; Value = Primary(); while (CurrentToken==MUL || CurrentToken==DIV) { if (CurrentToken==MUL) { GetToken(); Value *= Primary(); } else if (CurrentToken==DIV) { GetToken(); Value /= Primary(); } } return Value; }

In Term passiert im Grunde das gleiche wie in Expression. Hier wird allerdings MUL und DIV abgearbeitet.

double Primary() { double Value; switch(CurrentToken) { case NUMBER: GetToken(); return TokenNumberValue; case MINUS: GetToken(); return -Primary(); case LPAR: GetToken(); Value = Expression(); if (CurrentToken != RPAR) return Error(") expected"); GetToken(); return Value; case END: return 1; } return Error("primary expected"); }

Primary liefert im einfachsten Fall eine Zahl, wenn das erste Zeichen eine Ziffer ist. Ist es ein Minuszeichen, wird die Zahl negiert. Das "Negier-Minus" unterscheidet sich durch seine Position von dem Operatoren Minus.

Listing des Scanners

enum tToken { PLUS, MINUS, MUL, DIV, LPAR, RPAR, NUMBER, END, ERROR };

Die lexikalische Analyse ist aus Anschaulichkeitsgründen extrem knapp ausgefallen. Es fehlt das Übergehen von Leerzeichen und Leerzeilen. Auch die Auswertung der Zahl ist auf ganzzahlige Werte beschränkt. Aber zum Testen der Funktion ist er ausreichend.

tToken CurrentToken; double TokenNumberValue; char *pSource; char *PP; void SetSource(char *s) { pSource = s; PP = pSource; GetToken(); // bestimme schon einmal das erste Token vorweg } tToken GetToken() { CurrentToken = ERROR; if (*PP==0) { CurrentToken = END; } else { switch (*PP) { case '(': CurrentToken=LPAR; break; case ')': CurrentToken=RPAR; break; case '*': CurrentToken=MUL; break; case '/': CurrentToken=DIV; break; case '+': CurrentToken=PLUS; break; case '-': CurrentToken=MINUS; break; } if (*PP>='0' && *PP<='9') { CurrentToken=NUMBER; TokenNumberValue = 0.0; } while (*PP>='0' && *PP=<'9') { TokenNumberValue *= 10; TokenNumberValue += *PP-'0'; PP++; } if (CurrentToken != NUMBER) PP++; } return CurrentToken; } Error(char *s) { return puts(s); }

Aufruf

#include "parser.h" #include "lex.h" int main(int argc, char* argv[]) { double Wert; SetSource(argv[1]); Wert = Expression(); printf("%f\n", Wert); return 0; }