3. Mini-Compiler in C++ (Lexer,Parser,....)

Mini-Compiler in C++ (Lexer,Parser,....)

  • ?

    Hallo,
    Ich suche nach einem Beispielcode für einen Compiler in C++. Ich habe nähmlich keinen Schimmer wie das geht. Ich habe zwar schon einen einfachen Interpreter für eine kleine Programmiersprache geschafft, aber keinen Compiler. Kennt jemand einen Beispielcode oder eine deutsche genauere Beschreibung von dem was ein Compiler macht als in der Wikipedia. Darf auch eine andere Programmiersprache sein(soweit trotzdem lesbar).
    Danke schonmal im Vorraus

    0
  • ?

    http://compilers.iecc.com/crenshaw/

    schon älter, aber imho hervorragend geschrieben und leicht zu verstehen.

    0
  • B

    http://magazin.c-plusplus.net/artikel/Compilerbau

    0
  • C

    Naja ein Interpreter ist nix anderes als ein Compiler. Du solltest dich erstmal vor allem mit Parsing-Techniken auseinandersetzen, denn letztenendes ist da nicht viel Unterschied zwischen Compiler und Interpreter.

    Ein kleines Beispiel für einen "Mini-Compiler" findest du z.B. in meinem Projekt JS/CC (ein Parser-Generator für JavaScript), die "Skriptsprache XPL". Hier kannst du unter http://jscc.jmksf.com/jscc/jscc.html einen Mini-Compiler mit virtueller Maschine direkt im Webbrowser generieren und ausführen.

    Ich empfehle dir zudem, dich mit ausreichend Manuals zu bestücken. Sehr empfehlenswert ist das von Crenshaw (siehe oben), nur leider ist dieses Buch niemals zuende geschrieben worden.

    Ansonsten kann ich wärmsten Empfehlen: "Compiler-Design in C" von Allen I. Holub und zum Einstieg Niklaus Wirth's "Compilerbau".

    Bist du eher ein Pragmatiker (so wie ich?) oder ein Theoretiker?

    Gruß
    ~cp

    0
  • B

    code_pilot schrieb:

    Naja ein Interpreter ist nix anderes als ein Compiler.

    Starke Aussage. Was ist mit Optimierung und Codeerzeugung, das macht man wohl mal so nebenher, wenn der Parser erstmal läuft?

    0
  • C

    Bashar schrieb:

    code_pilot schrieb:

    Naja ein Interpreter ist nix anderes als ein Compiler.

    Starke Aussage. Was ist mit Optimierung und Codeerzeugung, das macht man wohl mal so nebenher, wenn der Parser erstmal läuft?

    Welch freundliche Aussage, wenn du es ja anscheinend so gut besser weist; Dann schreibe auch etwas Sinnvolleres zu deiner Aussage, und nicht nur einen Satz.

    Der Parser ist quasi Kernelement eines jeden Compilers UND Interpreters. Codeerzeugung/-optimierung ist mehr Part des Backends, keine Frage, aber das Frontend ist in beiden Fällen sehr ähnlich, wenn sogar identisch, und man bezeichnet das Parsing ebenfalls schon als Compilierungsphase.
    Ein Compiler muß zudem nicht immer Code Ausgeben oder Optimieren, und ist dennoch ein Compiler.

    @Ich=Ich
    Hier ist übrigens mal ein von mir geschriebener Ausdrucksparser, der mit Hilfe der Technik des rekursiven Abstiegs implementiert ist, und einen Parsebaum "pseudo-graphisch" darstellt. Habe den Code mal geschrieben um das Thema einem Arbeitskollegen etwas näher zu bringen.

    #define NODETYP_OPERATOR		0
#define NODETYP_ZAHL			1

#define OPERATOR_PLUS			0
#define OPERATOR_MAL			1
#define OPERATOR_GLEICH			2
#define OPERATOR_UNGLEICH		3

typedef struct _node NODE;

struct  _node
{
	int		typ;
	int		wert;
	NODE*	next;
	NODE*	child;
};

char*		source;

#define TOKEN_WEISS_NICHT		-1
#define TOKEN_ENDE			0
#define TOKEN_ZAHL			1
#define TOKEN_PLUS			2
#define TOKEN_MAL			3
#define TOKEN_GLEICH			4
#define TOKEN_UNGLEICH			5
#define TOKEN_KLAMMER_AUF		6
#define TOKEN_KLAMMER_ZU		7

void ausdruck( NODE** start );
void faktor( NODE** start );
void mal( NODE** start );
void plus( NODE** start );
void bedingung( NODE** start );

/* ~~~~~~~~~~~~~~~~~~SCANNER & PARSER~~~~~~~~~~~~~~~~~~ */
int		lookahead		= TOKEN_WEISS_NICHT;
int		att;

NODE* getnode( int typ, int wert )
{
	NODE* n;

	n = (NODE*)malloc( sizeof( NODE ) );
	memset( n, 0, sizeof( NODE ) );

	n->typ = typ;
	n->wert = wert;

	return n;
}

int get_token( int* val )
{
	char	buf [ 10 + 1 ];
	char*	start = source;

	printf( "source = >%s<\n", source );

	if( *start == '+' )
	{
		source++;
		return TOKEN_PLUS;
	}
	else if( *start == '*' )
	{
		source++;
		return TOKEN_MAL;
	}
	else if( *start == '(' )
	{
		source++;
		return TOKEN_KLAMMER_AUF;
	}
	else if( *start == ')' )
	{
		source++;
		return TOKEN_KLAMMER_ZU;
	}
	else if( *start == '=' )
	{
		source++;
		return TOKEN_GLEICH;
	}
	else if( *start == '!' )
	{
		source++;
		return TOKEN_UNGLEICH;
	}
	else if( *start == '\0' )
	{
		return TOKEN_ENDE;
	}
	else if( *start >= '0' && *start <= '9' )
	{
		while( *source >= '0' && *source <= '9' )
		{
			source++;
		}

		sprintf( buf, "%.*s", source - start, start );
		*val = atoi( buf );
		return TOKEN_ZAHL;
	}

	return TOKEN_WEISS_NICHT;
}

void bedingung( NODE** start )
{
	NODE*	op;

	plus( start );

	if( lookahead == TOKEN_GLEICH )
	{
		op = getnode( NODETYP_OPERATOR, OPERATOR_GLEICH );
		op->child = *start;

		lookahead = get_token( &att );
		bedingung( &( op->child->next ) );

		*start = op;
	}
	else if( lookahead == TOKEN_UNGLEICH )
	{
		op = getnode( NODETYP_OPERATOR, OPERATOR_UNGLEICH );
		op->child = *start;

		lookahead = get_token( &att );
		bedingung( &( op->child->next ) );

		*start = op;
	}
}

void plus( NODE** start )
{
	NODE*	op;

	mal( start );

	if( lookahead == TOKEN_PLUS )
	{
		op = getnode( NODETYP_OPERATOR, OPERATOR_PLUS );
		op->child = *start;

		lookahead = get_token( &att );
		plus( &( op->child->next ) );

		*start = op;
	}
}

void mal( NODE** start )
{
	NODE*	op;

	faktor( start );

	if( lookahead == TOKEN_MAL )
	{
		op = getnode( NODETYP_OPERATOR, OPERATOR_MAL );
		op->child = *start;

		lookahead = get_token( &att );
		mal( &( op->child->next ) );

		*start = op;
	}
}

void faktor( NODE** start )
{
	if( lookahead == TOKEN_ZAHL )
	{
		*start = getnode( NODETYP_ZAHL, att );
		lookahead = get_token( &att );
	}
	else if( lookahead == TOKEN_KLAMMER_AUF )
	{
		lookahead = get_token( &att );
		bedingung( start );

		if( lookahead != TOKEN_KLAMMER_ZU )
		{
			printf( "PARSE ERROR at >%s<\n", source );
			exit( 0 );
		}

		lookahead = get_token( &att );
	}
	else
	{
		printf( "PARSE ERROR at >%s<\n", source );
		exit( 0 );
	}
}

void ausdruck( NODE** start )
{
	lookahead = get_token( &att );
	bedingung( start );

	if( lookahead != TOKEN_ENDE )
	{
		printf( "PARSE ERROR at >%s<\n", source );
		exit( 0 );
	}
}

/* ~~~~~~~~~~~~~~~~~~TREEVIEW~~~~~~~~~~~~~~~~~~ */
int draw( NODE* s )
{
	static int i	= 0;
	int y;

	for( ; s; s = s->next )
	{
		for( y = 0; y < i; y++ )
			printf( "\t" );

		if( s->typ == NODETYP_ZAHL )
		{
			printf( "ZAHL %d\n", s->wert );
		}
		else if( s->typ == NODETYP_OPERATOR )
		{
			printf( "OPERATOR " );

			switch( s->wert )
			{
				case  OPERATOR_PLUS:
					printf( "PLUS" );
					break;
				case  OPERATOR_MAL:
					printf( "MAL" );
					break;
				case  OPERATOR_GLEICH:
					printf( "GLEICH" );
					break;
				case  OPERATOR_UNGLEICH:
					printf( "UNGLEICH" );
					break;				
			}

			printf( "\n" );

			i++;
			draw( s->child );
			i--;
		}
	}
}

int main( int argc, char** argv )
{
	char	s	[ 80 + 1 ];
	NODE*	startpunkt;

	while( 1 )
	{

		printf( "Was soll ich denn parsen? ");
		gets( s );
		if( *s )
		{	
			source = s;
			ausdruck( &startpunkt );

			printf( "ok\n" );

			draw( startpunkt );
		}
		else
		{
			printf( "bye!" ); 
			return 1;
		}
	}
	return 0;	
}

    Auch wenn dieser von Hand geschrieben ist, würde ich dir empfehlen, auf einen Parser Generator zurückzugreifen. Am besten vor allem für rekursiv-descent finde ich persönlich Coco/R, der auch für C/C++ verfügbar und angenehm zu benutzen ist.

    ~cp

    0
  • ?

    Danke für eure zahlreichen Antworten.
    erklärbär: Spitze Tut, genau sowas hab ich gesucht. Des einzig "blöde" daran ist dass des alles in englisch ist(bin in englisch nicht so gut), aber man kann es verstehen. 🙂
    Bashar: Genau das war es was ich nicht hinbekommen habe, das code erzeugen(kann mich nicht wirklich als asm-Programmierer bezeichnen)
    Nochmal danke

    0
  • B

    Ich=Ich schrieb:

    Bashar: Genau das war es was ich nicht hinbekommen habe, das code erzeugen(kann mich nicht wirklich als asm-Programmierer bezeichnen)

    Du kannst auch eine höhere Zielsprache verwenden, z.B. C, und dann einen C-Compiler als Backend benutzen. Das wird relativ häufig gemacht, besonders wenn Sprachen noch im Anfangsstadium ihrer Entwicklung sind.

    Andererseits ist Kein-Assembler-Können kein Schicksal, Assembler ist ziemlich leicht zu verstehen, es ist nur etwas schwerer, damit größere Probleme zu lösen, ohne dass einem die Übersicht verloren geht. Das ist aber für die Codeerzeugung nicht wichtig, da hast du mit ganz anderen Problemen zu tun.

    0
  • .

    Wenn's C++ sein soll, dann könntest du für die Codeerzeugung vielleicht LLVM benutzen. Damit bekommst du viele Optimierungen quasi umsonst mit und hast auch eine ganze Menge an Ausgabeformaten (außer „normalen“ Binärdateien z.B. auch MSIL (.NET), LLVM-Bytecode) und JIT-Kompilierung. Der einzige Nachteil ist das relativ hässliche Design (nix mit RAII, ständig werden Zeiger rumgeschoben).

    Wenn du in C++ sehr fit bist kannst du für den Parser Spirit aus Boost verwenden.

    Damit hättest du quasi den Blick frei für Wesentliches.

    0
  • C

    .filmor schrieb:

    Wenn's C++ sein soll, dann könntest du für die Codeerzeugung vielleicht LLVM benutzen. Damit bekommst du viele Optimierungen quasi umsonst mit und hast auch eine ganze Menge an Ausgabeformaten (außer „normalen“ Binärdateien z.B. auch MSIL (.NET), LLVM-Bytecode) und JIT-Kompilierung. Der einzige Nachteil ist das relativ hässliche Design (nix mit RAII, ständig werden Zeiger rumgeschoben).

    Hallo .filmor,

    Sag mal kennst du dich ein wenig mit solchen Libs wie LLVM aus? Gibt es da auch etwas für ANSI C, was du mir in dieser Art empfehlen könntest?

    Gruß
    ~cp

    0
  • .

    Von „Auskennen“ kann nicht die Rede sein, ich hab mich nur mal mit solchem modernen Compilerbaufirlefanz beschäftigt 😉

    Das einzige, was ich sonst noch dazu (Codegenerierung) kenne ist PyPy. Du könntest einfach LLVM benutzen und dir einen C-Wrapper dafür schreiben.

    0
Anmelden zum Antworten