Compilerbau Bücher?

Enno

Hi Leute,
ich bräuchte mal Buch Tipps, da ich ein Compiler bauen soll.
Oder vielleicht ein Link zu ein Thread wo es um das Thema geht. Hab in der SuFu nichts gefunden.
Danke.

Xin

Enno schrieb:

Hi Leute,
ich bräuchte mal Buch Tipps, da ich ein Compiler bauen soll.

Üblich ist das Drachenbuch. Eine Empfehlung ist das nicht unbedingt, mehr ein Hinweis, was eben so üblich ist.

Gute Bücher zum Thema sind mir nicht bekannt, die semantische Analyse - also das, was einen Compiler interessant macht - findet meist eine eher kurze Beschreibung.

"ein Compiler" kann viel sein.
Was für einen Compiler, was soll er können, was geht rein - was geht raus?

Enno

Er soll con c++ auf Javascript umbauen.

EDIT: hab jetzt das hier im netz gefunden: http://vhb.fh-regensburg.de/co/

Da sollte man denke ich ein gutes Verständnis bekommen vor allem weil für mich das einlesen erstmal jetzt das wichtigste wohl ist richtig?

Xin

Enno schrieb:

Er soll con c++ auf Javascript umbauen.

Okay... C++ ist jetzt schon etwas aufwendiger. ^^
Daher stelle ich vorsichtshalber die Frage nach der Motivation und der Notwendigkeit.

Ich gehe mal von einer Untermenge von C++ aus?

Möchtest Du C++ selbst parsen oder Yacc oder Bison verwenden? Die Enhanced Backus Naur Form wäre vermutlich hier Dein Einstieg (EBNF), wo Du Dich z.B. in Wikipedia einlesen kannst.

Enno schrieb:

EDIT: hab jetzt das hier im netz gefunden: http://vhb.fh-regensburg.de/co/

Da sollte man denke ich ein gutes Verständnis bekommen vor allem weil für mich das einlesen erstmal jetzt das wichtigste wohl ist richtig?

Es gibt hier im Magazin einen Artikel zum Thema: http://magazin.c-plusplus.net/artikel/Compilerbau

Ob der gut ist, kann ich Dir allerdings auch nicht sagen, da ich noch nicht gelesen habe.

Wo bist Du gerade, also was ist Dein nächster Schritt?

Enno

Xin schrieb:

Wo bist Du gerade, also was ist Dein nächster Schritt?

Ich bin ganz am Anfang. Parsen werde ich selbst machen müssen.
Ich bin Motiviert weiß das es aufwändig ist allerdings ist fürs nächste halbe Jahr meine Aufgabe in meiner Ausbildung FiAe. Schon mal vielen dank für deinen ganzen Tipps.

Xin

Enno schrieb:

Xin schrieb:

Wo bist Du gerade, also was ist Dein nächster Schritt?

Ich bin ganz am Anfang. Parsen werde ich selbst machen müssen.

Herzlich willkommen in der Compilerbau Phase 1: Lexikalische Analyse.

Definiere für jedes Schlüsselwort ein Token, z.B. ein integer und schreibe einen Parser, der Dir ein Text wie "int var;" in die Token 'int', 'Identififier' (var) und 'Semikolon' übersetzt.

Alles was überflüssig ist, wirfst Du weg: Leerzeichen, Anführungszeichen ("Hi" => String mit H, i, Nullbyte), Newlines, Tabs, Kommentare. Der Rest ist Dein Programm in leicht lesbaren Elementen.

Anschließend kommt die Syntaktische Analyse:

Die Token der Reihe nach analysieren und in einen abstrakten Syntaxbaum überführen. Dafür gilt es die Operatorprioritäten zu berücksichtigen. Schreib vielleicht vorsichtshalber mal einen Taschenrechner, der "1+2*3" sauber übersetzt, damit Du mit der notwendigen "Erfahrung" in den Compiler kommst.

Hier solltest Du die semantische Analyse bereits im Hinterkopf haben. Du brauchst eine Repräsentation für Datentypen und deren Attribute. Const-Methoden solltest du vielleicht auch als methode_const() gestalten, da JS kein Const-Correctness unterstützt. Trotzdem musst Du wissen, wer was ruft. Du brauchst also erstens eine Repräsentation aller Basistypen, anschließend eine Repräsentation von zusätzlichen Informationen (Zeiger? Array und wenn ja wie groß? Referenz?) und abschließend eine Repräsentation von Strukturen.

Und bevor Du das machst - erkundige Dich, ob Du das in dem halben Jahr schreiben sollst...

Syntaktische und semantische Analyse kann man in der Regel in einem Aufwasch erledigen.
Die syntaxtische Analyse klärt, dass kein break am Funktionsanfang steht oder puts nur 1 Argument bekommt. Die sementische, dass puts einen Parameter bekommt, der zu seinem gewünschten Typ passt: (char*).

Du bekommst einen Syntaxbaum:

funktion "main" (void -> int )
+- funccall "puts" (char * -> int)
|  +- "Hello World" (char *)
|- return ( -> int)
   +- 0 (int)

Nun hast Du also einen Baum, denn Du wieder abrufen kannst. Letzte Phase hier: Codegenerierung.
Oben steht ein Knoten mit "Function"-Token, das heißt "main" und es gibt eine Liste ohne Parameter und eine Rückgabe int. Die Rückgabe spielt bei JS keine Rolle:

function main()
{

Es folgen Befehle. Funccall "puts". Der Generator könnte das jetzt abfangen und als document.write ersetzen und die Parameter einfügen:

document.write( "Hello World" );

Selbiges mit dem Knoten 'return'.

return 0;

Anschließend kommen keine Knoten mehr im Baum.

Eine Klasse ist lediglich ein größerer Syntaxbaum.

Enno schrieb:

Ich bin Motiviert weiß das es aufwändig ist allerdings ist fürs nächste halbe Jahr meine Aufgabe in meiner Ausbildung FiAe. Schon mal vielen dank für deinen ganzen Tipps.

Kläre die Teilmenge ab. Vermutlich wird man Dir die semantische Analyse auch abnehmen. Die semantische Analyse in C++ ist, was die Sprache stark macht... das programmiert man nicht in der Ausbildung mal eben so nach...

Enno

Hey wow,
danke das hilft mir wirklich gut. Auch wenn ich mir sicher bin ich muss alles schreiben. Die Anforderung sind hier ziemlich groß. Naja dann werde ich mich mal an mein Werk machen.

P.S.: Ich mag deine Seite.

Xin

Enno schrieb:

Hey wow,
danke das hilft mir wirklich gut.

Wenn's ein Thema gibt, zu dem ich was sagen kann, dann dieses.

Enno schrieb:

Auch wenn ich mir sicher bin ich muss alles schreiben. Die Anforderung sind hier ziemlich groß. Naja dann werde ich mich mal an mein Werk machen.

Erkundige Dich... hier sind noch keine Templates, noch keine virtuellen Funktionen, keine Mehrfachableitungen. C++ ist keine Sache, die man in einem halben Jahr abarbeitet... schon gar nicht als Anfänger.

Enno schrieb:

P.S.: Ich mag deine Seite.

Ich auch

Danke

Enno

Dann werde ich mich immer an dich wenden können bei Problem.
Ich soll dadran halt c++ üben damit ich fit bin. Werde hier ja auch unterstüzt. Mein Ausbilder sagt so kannst das auf jeden Fall lernen. Durch beißen

Kellerautomat

Damit lernst du vielleicht die Syntax von C++, aber anwenden kannst du dann noch nichts. Halte ich nicht fuer sinnvoll.

Xin

Kellerautomat schrieb:

Damit lernst du vielleicht die Syntax von C++, aber anwenden kannst du dann noch nichts. Halte ich nicht fuer sinnvoll.

Er soll es programmieren... in C++... schönes Projekt, vor allem, wenn er es nach Hause mitnehmen kann.

Enno

Hey Xin,

wenn das ok ist hab ich mal deine Anleitung ohne Erklärung sozusagen als Plan aufgebaut. Wäre nett wenn du noch einmal drüber liest und mir sagst ob das so ok ist? Das ist sehr vereinfacht allerdings weiß ich ja auch wo ich nachlesen kann.
Danke

Compilerbau Phase 1: Lexikalische Analyse.

Definiere Schlüsselwort Token, Parser

überflüssig: Leerzeichen, Anführungszeichen ("Hi" => String mit H, i, Nullbyte), Newlines, Tabs, Kommentare.

die Syntaktische Analyse:
Token analysieren und in einen abstrakten Syntaxbaum überführen. Operatorprioritäten berücksichtigen.

die semantische Analyse im Hinterkopf.
Repräsentation für Datentypen und deren Attribute.
Const-Methoden als methode_const(), da JS kein Const-Correctness unterstützt.
Repräsentation aller Basistypen
Repräsentation von zusätzlichen Informationen (Zeiger? Array und wenn ja wie groß? Referenz?)
Repräsentation von Strukturen.

Die syntaxtische Analyse
kein break am Funktionsanfang oder puts nur 1 Argument

Die sementische
puts einen Parameter bekommt, gewünschten Typ passt: (char*).

Syntaxbaum:

Code:
funktion "main" (void -> int )
+- funccall "puts" (char * -> int)
| +- "Hello World" (char
|- return ( -> int)
+- 0 (int)
Code:
funktion "main" (void -> int )
+- funccall "puts" (char * -> int)
| +- "Hello World" (char
|- return ( -> int)
+- 0 (int)

Codegenerierung.
Knoten mit "Function"-Token "main"
Liste ohne Parameter Rückgabe int

Code:
function main()
{
Code:
function main()
{

Funccall "puts"
Generator abfangen als document.write ersetzen und die Parameter einfügen:
Code:
document.write( "Hello World" );
Code:
document.write( "Hello World" );

Selbiges mit dem Knoten 'return'.
Code:
return 0;
Code:
return 0;

keine Knoten mehr im Baum.
Code:
}
Code:
}

In der Ausbildung, in einem halben Jahr, einer C++ zu JS Compiler bauen? Komplett von Hand?

Mein Beleid. Daran würden die meisten Uni-Absolventen und langjährigen Programmierer scheitern. Ich habe etwas erfahrung im Lexer-/Parserbau und Compilertheorie und hätte Respekt vor der Aufgabe.

Die Aufgabe ist absurd komplex und ein Interpreter für einen Taschenrechner, vielleicht sogar eine kleine Sprache mit Schleifen und Funktionen, wäre im Rahmen einer Ausbildung vielleicht gerade noch machbar.

Enno

µ schrieb:

In der Ausbildung, in einem halben Jahr, einer C++ zu JS Compiler bauen? Komplett von Hand?

Mein Beleid. Daran würden die meisten Uni-Absolventen und langjährigen Programmierer scheitern. Ich habe etwas erfahrung im Lexer-/Parserbau und Compilertheorie und hätte Respekt vor der Aufgabe.

Die Aufgabe ist absurd komplex und ein Interpreter für einen Taschenrechner, vielleicht sogar eine kleine Sprache mit Schleifen und Funktionen, wäre im Rahmen einer Ausbildung vielleicht gerade noch machbar.

Ja ich weiß. Ich werde hier hart ran genommen.
Allerdings bin ich der Meinung das ich wohl einfach mich da mal rein fummeln soll, so dass ich dadran lernen kann. Ich mein die machen hier eh krassen kram und irgendwie muss ich da ja rein kommen.

Xin

Enno schrieb:

Hey Xin,

wenn das ok ist hab ich mal deine Anleitung ohne Erklärung sozusagen als Plan aufgebaut. Wäre nett wenn du noch einmal drüber liest und mir sagst ob das so ok ist? Das ist sehr vereinfacht allerdings weiß ich ja auch wo ich nachlesen kann.
Danke

Aus dem gequoteten lese ich nur, was ich schon schrieb!?

Du brauchst einen Plan, wie Du einen Compiler aufbaust und möglichst wenig Zeit in Features steckst, die Du vielleicht nicht mehr erreichst.

Wie gesagt: Fang an die lexikalische Analyse zu schreiben. Das sollte Dich nicht mehr als einen Tag kosten, wenn Du es brutal in eine Schleife packst reden wir eher von einer oder zwei Stunden.

Datei öffnen und laden und z.B.

#include "stdio.h"

int main( void )
{
  printf( "Hello World\n" );
  return 0;
}

liefert

Token: "#include"
Token: String "stdio.h"
Token: int
Token: Identifier "main"
Token: (
Token: void
Token: )
Token: {
Token: (
Token: Identifier "printf"
Token: String "Hello World
"
Token: )
Token: ;
Token: return
Token: IntValue 0
Token: ;
Token: )

Fertig. Das Anführungszeichen in der nächsten Zeile nach "Hello World" ist Absicht!

Danach überlegst Du Dir, wie Du Datentypen darstellen möchtest. Die Darstellung ist essenziell für die semantische Analyse. In meinem Compiler werkelt jetzt Version 3, Version 1 waren 2 Monate Arbeit - Vollzeit - die durch nach einer zweistündigen Trauerfeiner von mir gelöscht wurden, weil sie nicht gut genug war.
Version 3 wird nicht die letzte sein, das steht jetzt schon fest.
KLÄRE AB, OB DU DIE MACHEN MUSST!

µ schrieb:

Mein Beleid. Daran würden die meisten Uni-Absolventen und langjährigen Programmierer scheitern. Ich habe etwas erfahrung im Lexer-/Parserbau und Compilertheorie und hätte Respekt vor der Aufgabe.

Komplett C++ ist nicht machbar. Schon alleine, weil die Sprachen nicht 1:1 austauschbar sind, geht technisch einfach nicht.

Aber wenn man nicht zuviele Fehler macht, ist einiges machbar.

µ schrieb:

Die Aufgabe ist absurd komplex und ein Interpreter für einen Taschenrechner, vielleicht sogar eine kleine Sprache mit Schleifen und Funktionen, wäre im Rahmen einer Ausbildung vielleicht gerade noch machbar.

Kommt drauf an, was er sonst noch macht. Der Compilerbau ist eigentlich gar nicht sooo schwer, wenn man ein paar Grundlagen kennt. Und wenn er sich nicht an die Fachbücher hält, sondern seinen Verstand benutzt, kann man viele Funktionen in einen 15 Zeiler unterbringen.

Xin schrieb:

Kommt drauf an, was er sonst noch macht. Der Compilerbau ist eigentlich gar nicht sooo schwer, wenn man ein paar Grundlagen kennt. Und wenn er sich nicht an die Fachbücher hält, sondern seinen Verstand benutzt, kann man viele Funktionen in einen 15 Zeiler unterbringen.

Das birgt aber erhebliche Fickelgefahr. Und sowas wie einen Bottom-Up-Parser überlegt man sich nicht mal nebenher. Auf so etwas kommt man von alleine, mit an Sicherheit grenzende Wahrscheinlichkeit, garnicht. Um diese Themen zu verstehen ist also erstmal Grundwissen gefragt: Grammatiken, Automaten und dergleichen. Alleine dafür geht schon ein halbes Jahr drauf.
Wenn er Lexer- und Parsergeneratoren verwenden darf, ist schon enorm viel gewonnen und er kann das Zeug einfach als Black-Box betrachten. Das müsste zu erstmal geklärt werden.

maximAL

Große Firmen brauchen Jahre, um einen halbwegs standardkonformen C++ Compiler zu schreiben, sowas als Ausbildungsprojekt zu machen ist totaler Irrsinn. Für eine kleine, klar definierte Teilmenge von C++ meinetwegen. Aber selbst dann hat man noch das Problem, dass man erstmal eine EBNF für diese Teilmenge auftreiben (oder wahrscheinlich eher selbst definieren) muss.

@Topic: Das Drachenbuch ist wirklich nicht übermäßig gut, ich glaube kaum, dass das viel bringt. Zum Einstieg ist "Grundlagen und Techniken des Compilerbaus" von Niklaus Wirth zu empfehlen. Das ist recht schlank, setzt aber eine niedrige Einstiegshürde. An "Übersetzerbau" von Güting und Erwig habe ich auch noch ganz gute Erinnerungen.
Letztendlich ist das auch ein extrem gut erforschter und relativ alter Zweig der Informatik, da steht in den meisten Büchern eh dasselbe.

PS: Ich habe eine Diplomarbeit in dem Gebiet geschrieben. Allerdings für eine weit besser dokumentierte und klarer strukturierte Sprache als C++ und mit Verwendung eines Parsergenerators

Enno

Xin schrieb:

Aus dem gequoteten lese ich nur, was ich schon schrieb!?

Ja meinte ich ja. Hab deinen Text mal vereinfacht.^^

Xin schrieb:

Kommt drauf an, was er sonst noch macht. Der Compilerbau ist eigentlich gar nicht sooo schwer, wenn man ein paar Grundlagen kennt. Und wenn er sich nicht an die Fachbücher hält, sondern seinen Verstand benutzt, kann man viele Funktionen in einen 15 Zeiler unterbringen.

Hmm ... ich sollte vielleicht sagen das ich ziemlicher Anfänger bin.

Xin

maximAL schrieb:

PS: Ich habe eine Diplomarbeit in dem Gebiet geschrieben. Allerdings für eine weit besser dokumentierte und klarer strukturierte Sprache als C++ und mit Verwendung eines Parsergenerators

Dito. Hattest Du etwas Akzeptables zum Thema 'Semantische Analyse' gefunden? Sämtliche Bücher, die ich seinerzeit zu dem Thema in der Hand hatte, blieben da... sagen wir mal... sehr theoretisch und wortkarg. Wenn eine Seite in einem Buch das Thema abhandelt, dann verläuft das eher nach dem Motto "sowas gibt's auch" und fertig. Fand ich recht enttäuschend.
Ich wollte dazu selbst mal ein Buch schreiben, aber schlussendlich... das Drachenbuch ist allgegenwärtig und das Thema garantiert nicht gerade nennenswerte Verkaufszahlen

µ schrieb:

Xin schrieb:

Kommt drauf an, was er sonst noch macht. Der Compilerbau ist eigentlich gar nicht sooo schwer, wenn man ein paar Grundlagen kennt. Und wenn er sich nicht an die Fachbücher hält, sondern seinen Verstand benutzt, kann man viele Funktionen in einen 15 Zeiler unterbringen.

Das birgt aber erhebliche Fickelgefahr.

Für die 15 Zeilen habe ich drei Tage gebraucht, sie regeln den Ordnung des Parserbaums anhand der Operatorpriorität. Das üblicherweise an der Stelle beschriebene Verfahren ist eine kleine Redundanzkatastrophe und da ich mich bzgl. der Prioritäten sowieso nicht endgültig festlegen wollte, wäre das frickelig bis zum geht nicht mehr geworden. Prinzipiell kann ich zur Compile-Laufzeit die Operatorprioritäten ändern, aber das muss man ja nicht. Wichtig ist, dass nur eine Stelle gibt, die entscheidet, wie der Baum aufgebaut wird.

µ schrieb:

Und sowas wie einen Bottom-Up-Parser überlegt man sich nicht mal nebenher. Auf so etwas kommt man von alleine, mit an Sicherheit grenzende Wahrscheinlichkeit, garnicht. Um diese Themen zu verstehen ist also erstmal Grundwissen gefragt: Grammatiken, Automaten und dergleichen. Alleine dafür geht schon ein halbes Jahr drauf.

In einer Hochschule schon. Wenn er nicht ganz blöd ist, kann er sich das auch in 2 Tagen aneignen.

Enno schrieb:

Ja meinte ich ja. Hab deinen Text mal vereinfacht.^^

Sah mir eher nach einer 1:1 Kopie mit kaputten Code-Tags aus

Enno schrieb:

Hmm ... ich sollte vielleicht sagen das ich ziemlicher Anfänger bin.

Wir sind alle Anfänger... mehr oder weniger.

Beschreib mal, was Du kannst, damit ich abschätzen kann, wieviel Erklärung Du brauchst.
Ich darf mal davon ausgehen, dass Du C++ und JavaScript zumindest akzeptabel kannst?

Xin schrieb:

In einer Hochschule schon. Wenn er nicht ganz blöd ist, kann er sich das auch in 2 Tagen aneignen.

Ich schätze Du bist schon so lange in dem Thema drinnen, dass Du Dir nicht mehr vorstellen kannst, welche Anlaufschwierigkeiten man bei sowas haben kann. Er ist Azubi, ohne Grundlagenvorlesungen in Logik oder Mathematik! Den Leuten im ersten Semester brennt gerne mal der Schädel durch bis sie geschluckt haben was eine Grammatik ist. Alles schon vergessen?

Die Aufgabe ist, wenn sie nicht ganz erheblich eingeschränkt wird, nicht zu bewältigen. Punkt.

Aber gut, ich sollte mal ein wenig arbeiten und nicht nur im Forum rumhängen