IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Spezifisches - Compilerbau



Compilerbau

Das Gebiet Compilerbau ist eines der Gebiete, in denen die Forschung der theoretischen Informatik zu den offenkundigsten Ergebnissen geführt hat. Heute ist das Schreiben eines Compilers oder Interpreters keine Hexerei mehr, sondern eine einfache Fingerübung mit klaren Regeln. Dies hat zur Effizienz und Verlässlichkeit heutiger Compiler geführt.


Autor: Arnold Willerner (willemer)
Datum: 23-01-2002, 19:34:48
Referenzen: http://www.willemer.de/informatik/index.htm
Schwierigkeit: Profis
Ansichten: 4478x
Rating: 10 (1x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



Motivation

Die Techniken des Compilerbaus finden nicht nur Anwendung, wenn Programmiersprachen neu erfunden werden, sondern überall da, wo Texte interpretiert werden. Ob man einen mathematischen Ausdruck in der Benutzereingabe oder Konfigurationsdateien mit geschachtelten Daten auswerten will. In all diesen Fällen werkelt ein Interpreter im Hintergrund.

Begriffe wie "rekursiver Abstieg" oder "kontextfreie Grammatik" mögen im ersten Moment abschreckend klingen. Die Einarbeitung lohnt sich aber, da so einfach zu wartende, übersichtliche Programme entstehen. Wer es auf andere Weise versucht, steht meist zum Schluss vor einem zusammengepatchten Monster.

Weitere Informationen

Zum Thema Compilerbau kann man über die Seite www.compilerbau.de einige Informationen, vor allem Links zu relevanten Seiten finden.

Der Clickfish hat eine Informatikseite, auf der weiteres zum Thema Informatik und auch der theoretischen Informatik zu finden ist.

Lohnenswert ist auch der Blick auf die Informatikseiten der verschiedenen Universitäten und Fachhochschulen.

Compilerbau: Struktur

Die Struktur eines Compilers

Lexikalische Analyse (Scanner)
Der Zeichenstrom wird nach Tokens durchsucht und zusammengefasst. Ein Token ist ein Quellzeichen für den Parser. Das sind beispielsweise:
  • Schlüsselworte der Sprache: IF, THEN, GOTO
  • Symbole: <=, -> oder }
  • Identifier: Variablen- oder Funktionsnamen.
  • Konstanten: 23.5 oder "Dies ist ein Text"
Die lexikalische Analyse arbeitet auf der Basis eines endlichen Automaten und erkennt reguläre Sprachen.
Syntaktische Analyse (Parser)
Ordnet die Folge des Tokens und steuert dadurch den Zwischencode-Erzeuger

Ein Parser arbeitet auf der Grundlage einer kontextfreien Grammatik mit der Hilfe eines Kellerautomaten.

Semantische Analyse
Die semantische Analyse prüft beispielsweise die Typgleichheit von Ausdrücken.
Zwischencode-Erzeuger
Erzeugt eine Folge einfacher Anweisungen, beispielsweise Drei-Adress-Code.
Code Optimierung
Optimiert Platz- und Zeitbedarf
Code Erzeugung
Erstellt den Code für die Zielmaschine.

Compilerbau: die lexikalische Analyse

Die lexikalische Analyse kann eine reguläre Sprache erkennen und arbeitet auf der Basis eines deterministischen Automaten. Ein solcher Automat ist ein Modell für einen Programmteil, das durch die Eingabe gesteuert wird. Anhand des ersten Zeichens (oder mehrerer) kann er eindeutig erkennen, was vorliegt.

Um diesem Automaten das Leben leicht zu machen, definieren die meisten Programmiersprachen einen Bezeichner so, dass das erste Zeichen ein Buchstabe sein muss. So weiss der Automat bei Eintreten einer Ziffer, dass es sich um eine Zahl handelt und bei Erscheinen eines Buchstabens, dass es sich um einen Bezeichner handelt.

Die lexikalische Analyse ist für die Bearbeitung der Textvorlage zuständig und hat dem Parser einen Strom von Tokens zu liefern. An dieser Stelle wird die Auswertung der Konstanten und das Überspringen von Leerzeichen und Leerzeilen durchgeführt. Auch das Nachladen weiterer Sourcedateien wie in C bei der #include-Anweisung sind Aufgaben der lexikalischen Analyse.

Compilerbau: Automat

Ein Automat ist eine virtuelles Maschine, das aufgrund externer Ereignisse ihren Zustand ändert. Ein deterministischer (endlicher) Automat ist ein Automat, dessen Übergang von einem Zustand in den anderen eindeutig durch das Ereignis gesteuert wird. Es ist einleuchtend, dass ein deterministischer Automat für die Programmierung bevorzugt wird.

Das folgende Beispiel ist ein Automat, der C-Kommentare aus einem Zeichenstrom ausfiltert. Ein C-Kommentar beginnt mit /* und endet mit */. Der Automat kennt vier Zustände: Start, Slash, InComment und Asterix.

Zustand Zeichen nächster Zustand Aktion
Start alle, außer '/' Start Drucke Zeichen
Start '/' Slash
Slash '/' Slash Drucke '/'
Slash '*' InComment
Slash alle, außer '*' und '/' Start Drucke '/', Drucke Zeichen
InComment '*' Asterix
InComment alle, außer '*' InComment
Asterix '/' Start
Asterix '*' Asterix
Asterix alle außer '/' oder '*' InComment

Die Umsetzung in Programm-Code ist einigermassen trivial.


enum tStatus = {START, SLASH, INCOMMENT, ASTERIX};
tStatus Status = START;

void DeleteComment()
{
char c;

  c = getchar();
  while (c!=0 && c!=EOF) {
    switch(Status) {
    case START:
      if (c=='/') Status = SLASH;
      else putchar(c);
      break;
    case SLASH:
      if (c=='*') Status = INCOMMENT;
      else if (c=='/') putchar(c);
      else { putchar('/'); putchar(c); Status = START; }
      break;
    case INCOMMENT:
      if (c=='*') Status = ASTERIX;
      break;
    case ASTERIX:
      if (c=='/') Status = START;
      else if (c!='*') Status = INCOMMENT;
      break;
    }
    c = getchar();
  }
}

Compilerbau: die syntaktische Analyse

Die syntaktische Analyse kann eine kontextfreie Sprache erkennen und arbeitet auf der Basis eines Kellerautomaten.

Aus dem Strom der Tokens, die der Scanner ihm liefert, bildet der Parser einen Ableitungsbaum. Am Beispiel sieht man, wie aus einem einfachen mathematischen Ausdruck ein Baum entsteht:


6*4+3*5

+
/ \
* *
/ \ / \
6 4 3 5
Da ein Baum eine rekursive Datenstruktur ist, erklärt sich auch, warum ein Kellerautomat, also ein Automat mit einem Stack benötigt wird.

Compilerbau: die lexikalische Analyse

Die lexikalische Analyse kann eine reguläre Sprache erkennen und arbeitet auf der Basis eines deterministischen Automaten. Ein solcher Automat ist ein Modell für einen Programmteil, das durch die Eingabe gesteuert wird. Anhand des ersten Zeichens (oder mehrerer) kann er eindeutig erkennen, was vorliegt.

Um diesem Automaten das Leben leicht zu machen, definieren die meisten Programmiersprachen einen Bezeichner so, dass das erste Zeichen ein Buchstabe sein muss. So weiss der Automat bei Eintreten einer Ziffer, dass es sich um eine Zahl handelt und bei Erscheinen eines Buchstabens, dass es sich um einen Bezeichner handelt.

Die lexikalische Analyse ist für die Bearbeitung der Textvorlage zuständig und hat dem Parser einen Strom von Tokens zu liefern. An dieser Stelle wird die Auswertung der Konstanten und das Überspringen von Leerzeichen und Leerzeilen durchgeführt. Auch das Nachladen weiterer Sourcedateien wie in C bei der #include-Anweisung sind Aufgaben der lexikalischen Analyse.

Compilerbau: Beispiel

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

Kontextfreie Grammatik

Die kontextfreie Grammatik beschreibt die Sprache, die interpretiert werden kann. Eine Grammatik kann direkt in die Programmierung umgesetzt werden.


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

Die Auswertung der Grammatik erfolgt durch den rekursiven Abstieg. Das Programm ruft expression, dies ruft term, welches primary ruft. Hier wird das erste Zeichen gefunden, das mit dem vorliegenden Token verglichen wird.

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

Zugunsten der Übersichtlichkeit wird die Verbindung zur lexikalischen Analyse über globale Variablen erreicht.


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

Das Token ist ein Aufzählungstyp. Ein solcher einfacher Typ ist per case einfacher zu verarbeiten als Strings.


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

Extrem vereinfacht auch der Aufruf. Der erste Parameter ist der zu interpretierende String. Das Ergebnis wird einfach nach per printf ausgegeben.


#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;
}



[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04508
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06246
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1154
Comments: 0