Compilerbau Bücher?

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

Enno

Xin schrieb:

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?

Hmm... ich denke eher nicht. Ich kann nicht viel aber Parser hab ich schon z.B. geschrieben. Also wirklich nicht so viel erwarten.

So ich hab nochmal eben mit meinem Aufgabensteller gesprochen. Er sagte es so:

Schreibe ein Compiler für unser Javascript Code der OOP enthält und es wieder in JS umwandelt, so das der Browser das verstehen kann.

Ich hab hier eine test Datei die ich einlesen kann um zu probieren ob mein Compiler funktioniert. Vielleicht hilft das.

class a {
public:
   function hello(){
    console.log("hello");
  }
};

class b {
public:
  function bye(){
     console.log("Bye");
  }
};

class c : public a,b{
public:
  function greet(){
    console.log("greeting");
  }
}

maximAL

Xin schrieb:

Dito. Hattest Du etwas Akzeptables zum Thema 'Semantische Analyse' gefunden?

Nein, das war für meine Aufgabe auch nicht nötig.
Eigentlich wäre für das, was praktisch rauskommen sollte gar kein tiefergehendes Wissen über Compilerbau nötig gewesen, da dass meisste eh vom Parsergenerator übernommen wurde. Aber das musste ja voll wissenschaftlich sein ( )und ich hab meine Zeit damit vertrödelt die LL(k) Eigentschaft für die Grammatik zu bestimmen. Und LL Parser sind, sobald es über LL1 hinausgeht, wiederum unglaublich schlecht dokumentiert.

Xin

µ schrieb:

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?

Nein, überhaupt nicht.

Ich erinnere mich sehr gut daran, wie man jeden Furz so verklausuliert hatte, dass möglichst niemand verstand, worum es geht, oftmals in einer hochtheoretischen Betrachtung, ohne praktischen Bezug, reichlich griechischen Buchstaben und so weiter.
Es ist wie alles, was ich bisher in der Wissenschaft kennengelernt habe. Aufwendige Arbeiten an mit CAD, wissenschaftliche Publikationen und die Realisation sieht dann so aus, dass man einen Milchaufschäumer und Powertape kauft und als Kontrastmittel Tinte und Wasser mischt. Sowas basteln auch Grundschüler, aber die Papers hätten sie nicht schreiben können...
Gibt's Fischertechnik eigentlich noch für Kinder oder wird das heute nur noch an Wissenschaftler verkauft... ich hab's die letzten Jahren nämlich nur noch in Laboren gesehen.

Deterministische Automaten sind nun wirklich kein Zauberwerk und die Tatsache, dass man 90 oder 180 Minuten pro Woche damit verbrachte, führt nunmal dazu, dass man das ganze - insbesondere den Part, den er braucht - zeitlich wunderbar reduzieren kann.
Zumal er das perfekte Beispiel hat und kennt, um sich einen Automaten und Grammatiken praktisch vorzustellen. Lässt man die Verklausulierung weg, ist das nicht mehr als ein Knobelspiel.

µ schrieb:

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

Unbestritten, zumal er die komplette Standard-Lib abbilden müsste, Templates, nicht den Hauch einer Chance...

Aber Algorithmen von C++ nach JS zu überführen, könnte er schaffen, wenn er sich tief reinkniet, und wenn er es schafft, dann hat er sehr viel gelernt. Darum geht's für ihn in der Ausbildung.

maximAL schrieb:

Xin schrieb:

Dito. Hattest Du etwas Akzeptables zum Thema 'Semantische Analyse' gefunden?

Nein, das war für meine Aufgabe auch nicht nötig.
Eigentlich wäre für das, was praktisch rauskommen sollte gar kein tiefergehendes Wissen über Compilerbau nötig gewesen, da dass meisste eh vom Parsergenerator übernommen wurde. Aber das musste ja voll wissenschaftlich sein ( )und ich hab meine Zeit damit vertrödelt die LL(k) Eigentschaft für die Grammatik zu bestimmen. Und LL Parser sind, sobald es über LL1 hinausgeht, wiederum unglaublich schlecht dokumentiert.

Jow... das mit dem wissenschaftlich kenne ich... ich habe auch nicht wissenschaftlich genug gearbeitet... mein Prof wollte, dass ich gewisse Dinge aus dem Informatikduden zitiere... blöderweise stand da genau das Gegenteil von dem drin, was an der Hochschule gelehrt und ich angewandt habe. Kurz: Da stand Quatsch drin. Nun war die Quelle aber nunmal da und das Zitat vom Prof verlangt. Freundlicherweise fand ich im Informatikduden auch gleich die Stellen, um den Informatikduden zu widerlegen... ich musste mich also nicht nur auf die Vorlesungen meiner eigenen Hochschule verlassen. Aber das war natürlich viel Text, eigentlich vollkommen ohne größeren Sinn, nur um das geforderte Zitat zu bringen und es dann anschließend gleich wieder zu widerlegen.

Wissenschaftliches Arbeiten würde ich nicht als Blödsinn bezeichnen, die Diskussion hatte ich allerdings auch schon mit meinem Prof. Er meinte, ich müsse belegen, dass meine Gedankengänge richtig sind, in dem ich meine Annahmen über andere Bücher belege. Ich fragte ihn, wie ich davon ausgehen kann, dass in dem Buch etwas sinnvolles steht, ob es nicht sinnvoller wäre, meinen Verstand zu benutzen und statt irgendwelcher fraglicher Belege meine eigene Begründung zu geben, die auch beschreibt, warum ich diese Arbeit mache. Meine Begründungen könnten ja falsch sein - er meinte, dass es in jedem Fachbuch Quellenangaben gibt, womit der Autor des Fachbuchs seine Annahmen belegt und meine Arbeit nur so als richtig belegt sein könnte. So muss ich auch arbeiten. Die Frage, wie das erste Fachbuch entstanden ist und wie Fachbücher etwas belegen, wenn sie sich auf Fachbücher ohne Belege stützen, schien ihn zu überraschen, jedenfalls gab es eine längere Denkpause und eine Antwort bekam ich auch nicht.

Ich habe aber von einem anderen Prof schriftlich bestätigt bekommen, dass ich ein kritischer Geist wäre, der zielsicher Schwachpunkte thematisiert... kommt in der akademischen Welt gar nicht gut an... wenn's gedruckt wurde, muss es wahr sein.

Xin

Enno schrieb:

Xin schrieb:

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?

Hmm... ich denke eher nicht. Ich kann nicht viel aber Parser hab ich schon z.B. geschrieben. Also wirklich nicht so viel erwarten.

Verstehst Du den Code, den Du kompilieren sollst?

Enno schrieb:

Schreibe ein Compiler für unser Javascript Code der OOP enthält und es wieder in JS umwandelt, so das der Browser das verstehen kann.

für unseren C++-Code?

Enno schrieb:

Ich hab hier eine test Datei die ich einlesen kann um zu probieren ob mein Compiler funktioniert. Vielleicht hilft das.
class a {
public:
   function hello(){
    console.log("hello");
  }
};

class b {
public:
  function bye(){
     console.log("Bye");
  }
};

class c : public a,b{
public:
  function greet(){
    console.log("greeting");
  }
}

Mehrfachvererbung... sieh an... daher weht also der Wind... ^^

Weiß Dein Aufgabensteller, dass JavaScript keine Mehrfachvererbung unterstützt? Das ist umsetzbar, aber wie ich schon sagte: Beide Sprachen lassen sich nicht 1:1 umsetzen, das ist technisch nicht möglich. Diesen Code nach JS zu bringen, ist aber möglich, wenn Du verstehst, was genau dieser Code hier tut.

Enno

Ich glaube ich hatte die Aufgabe am Anfang falsch verstanden. Der drückt sich auch immer aus, versteht ja auch kein Mensch.(Ausbilder)
Don't kill me.

Xin

Enno schrieb:

Ich glaube ich hatte die Aufgabe am Anfang falsch verstanden. Der drückt sich auch immer aus, versteht ja auch kein Mensch.(Ausbilder)
Don't kill me.

Heißt?

Wie lautet Deine Aufgabe nun?

Enno

Xin schrieb:

[
Diesen Code nach JS zu bringen, ist aber möglich, wenn Du verstehst, was genau dieser Code hier tut.

Das soll ich auch machen.
Ich hab mri den ehrlich gesagt noch garnicht richtig angeguckt.

Xin

Enno schrieb:

Xin schrieb:

[
Diesen Code nach JS zu bringen, ist aber möglich, wenn Du verstehst, was genau dieser Code hier tut.

Das soll ich auch machen.
Ich hab mri den ehrlich gesagt noch garnicht richtig angeguckt.

Dafür musst Du ein Programm schreiben, was den Code versteht und das, was es verstanden hat, als JavaScript wieder wegschreibt... einen Compiler.

Enno

Xin schrieb:

class a {
public:
   function hello(){
    console.log("hello");
  }
};

class b {
public:
  function bye(){
     console.log("Bye");
  }
};

class c : public a,b{
public:
  function greet(){
    console.log("greeting");
  }
}
Mehrfachvererbung... sieh an... daher weht also der Wind... ^^

wenn Du verstehst, was genau dieser Code hier tut.

Öhm ... hier erbt die class c von a und b alle public Funktionen?

Xin schrieb:

Weiß Dein Aufgabensteller, dass JavaScript keine Mehrfachvererbung unterstützt?

Ja das ist doch grade der sinn meines Compilers oder? Es ist umsetzbar allerdings nicht in JS vorgesehen, d.h. mein Compiler übersetzt das dann wieder?

pumuckl

Was als Einstieg recht gut ist imo, ist Language Implementation Patterns | ISBN: 193435645X, damit kann man schon einiges anfangen. Allerdings empfehle ich trotzdem die Kenntnis von gewissen Interna von C und/oder C++, damit man ne Idee hat, wie verschiedene Dinge umgesetzt werden könnten.

Kellerautomat

Ich wuerde die Aufgabe ja mit Regex loesen.

maximAL

Kellerautomat schrieb:

Ich wuerde die Aufgabe ja mit Regex loesen.

Ja, den Lexer.