Compilerbau

[deejey]

Compilerbau ist eine Wissenschaft für sich, gibt ganze Bücher die nur das behandeln, das kriegt man nicht mal eben hin im Rahmen von "Ich muss einen Compiler für Java schreiben"

[compilerbuilder]

Also mir fällt grad noch ein:

Jede Methode hat return-Statements in jedem Lauf.

Welches Buch empfehlt ihr denn , das mir Fragen wie diese beantworten kann?

[Xin]

compilerbuilder schrieb:

Kann sich jemand vorstellen was eine semantische Analyse von Exceptions oder Generics bedeuten könnte. Also bei Generics muss natürlich der Paramter angegeben werden. Das kann der Parser mit der Grammatik nicht überprüfen.

Warum nicht? Die Parameter sind doch angegeben!? Wenn Du von Java-Generics sprichst, so sind zumindest die notwendigen Interfaces angegeben, der eigentlich Typ ist dabei ja egal.
Gut, die Grammatik selbst kann das nicht prüfen... aber die Grammatik der eingehenden Sprache spielt für die Semantik auch keine tragende Rolle.

compilerbuilder schrieb:

Bei Exeception kann ich mir vorstellen dass die Variable e und keine andere verwendet wird.

try
{

}
catch(Exception e)
{
    f.getMessage(); // falsche Variable f
}

Innerhalb von catch deklarierst Du die Variable e. Ob die jetzt e heißt oder snafu spielt dabei keine Rolle. Sie hat (in Java) innerhalb des darunter liegenden Scopes definiert zu sein.

compilerbuilder schrieb:

Also ich muss einen Compiler für Java schreiben und werde in diesem Thread in nächster Zeit bestimmt öfter mal Fragen stellen. Der Parser braucht doch eigentlich gar keine Baumknoten.

Definiere Parser. Wenn es nur darum geht, eine Abfolge von Token als valide zu bezeichenen, so brauchst Du keinen Abstract Syntax Tree. Der Parser identifiziert Zeichen ja nur als Token und meckert, wenn falsche Token kommen.
Die Aufgabe des Parsers ist aber ja, den AST aufzubauen.

compilerbuilder schrieb:

Die sind doch eigentlich nur für die semantische Phase dann.

Du wirst vermutlich lernen, dass lexikalische Analyse, syntaktische und semantische Analyse die ersten drei Phasen des Compilerbaus darstellen.
Sagen wir mal so... da gibt es die Theorie und die Praxis. Wenn Du wirklich was programmieren möchtest, wirst Du vermutlich die ersten drei Phasen zusammenfassen wollen. Heißt: Du baust den Baum so zusammen, dass er einen Sinn ergibt und wenn nicht wirfst Du mit Fehlermeldungen um Dich.

compilerbuilder schrieb:

Für den Parser selbst verwendet man einfach einen rekursiv absteigenden Parser ? Aber eben für die semantische Phase und später für die Code Erzeugung baut der Parser schon mal den Baum auf ? Für die Überprüfung der Grammatik brauche ich aber definitiv keinen Baum !!! Das ist meine Behauptung

Du willst aber laut eigener Aussage keinen Grammatikbewerter bauen, sondern einen Compiler. "Draußen ist es kälter als nachts." ist ein grammatikalisch korrekter Satz, aber semantisch trotzdem zu nix zu gebrauchen, weil der Vergleichsoperator "kälter als" mit eine Zeitangabe mit einer Ortsangabe vergleicht - und das ganze mit einem impliziten Cast auf Temperatur.

Für den Parser brauchst Du keinen Baum, solltest Du eine Bewertung über die Qualität des geparsten Inhaltes abliefern wollen, hat sich der AST aber als nützlich erwiesen.

compilerbuilder schrieb:

Was gehört denn alles zur semantischen Analyse von Methoden?
Was mir so einfällt:

- besitzt Methode richtige Parameter
- gibt es den Methodennamen
- richtiger Rückgabewert

Was zur semantischen Analyse gehört, ergibt sich durch die Möglichkeiten, die die Sprache Dir zur Verfügung stellt. Java ist halbwegs strikt durchtypisiert, man kann also die korrekte Verwendung von Typen verifizieren. Dass eine Methode einen Namen haben sollte, gehört schon in die Grammatik, die verlangt, dass zu einer Methodendeklaration nunmal auch ein Identifier gehört, mit dem man die Methode identifizieren kann. Bash verlangt das meines Halbwissens nach nicht.

Die semantische Analyse kannst Du im Prinzip mit einer Typanalyse gleichsetzen. Je stärker das Typsystem der Sprache, desto mehr kannst Du die Semantik überprüfen.

Bei den Generics müssen die aufgerufenen Methoden im verlangten Interface vorhanden sein, Identifier, die als final markiert sind dürfen nicht überschrieben werden, Identifier, die als override markiert sind, müssen einen gleichartigen Typen überschreiben (sofern es das in Java gibt - ich ignoriere Java schon wieder ein paar Jahre.) Auch schön ist, wenn Du Methoden rufst, die bisher nicht deklariert sind oder per goto zu einem Identifier springst, der erst hinter dem goto auftaucht (goto ist aber in Java auch nicht so gefragt, oder?). Für die Methoden musst Du jedenfalls beim Parsen grünes Licht geben, obwohl Du sie nicht findest und Dir diese Stellen merken und sie nacharbeiten. Findest Du die Methode dann immernoch nicht, darfst Du motzen.
Das wäre, was mir spontan zu dem Thema einfällt.

compilerbuilder schrieb:

Hallo ?

Hallo.

Ich weiß nicht, weswegen Du gleich einen ganzen Java-Compiler nachschreiben solltest, das geht wohl über eine Hausaufgabe oder großes Projekt hinaus. Ist im überschaubaren Rahmen aber natürlich machbar, wenn man das möchte.

Das sind aber keine Sachen, die hier jeder mal eben so spontan mal als Fingerübung gemacht hat, vermute ich.

Auch die Bücher, die es zu dem Thema gibt, kannst Du eher als nette Einleitung interpretieren, gerade sobald es zur semantischen Analyse geht und wie man das umsetzen soll, wird es doch sehr abhängig von den zu übersetzenden Sprachelementen - anders ausgedrückt, das sind individuelle Arbeiten. Und wer die semantische Analyse in einem Compiler schreibt, dem fehlt üblicherweise die Zeit, das auch noch detailliert zu dokumentieren. Das ganze ist also eher ein Selbsterfahrungskurs.

Ein Java-Compiler ist eine interessante Sache. Gibt's aber schon. Zumal Java in meinen Augen eher ein technischer Rückschritt ist. Sollte das also aus persönlichem Vergnügen entstehen, empfehle ich Dir, Dir zuerst Gedanken darüber zu machen, welches Problem Du lösen möchtest. Eine Lösung, die bereits schlechter ist, als andere Lösungen, nochmal identisch nachzubauen, löst irgendwie mal überhaupt kein Problem.
Trotzdem will ich Dich ermutigen, Dein Projekt weiter zu verfolgen. Es wird sich als extrem lehrreich erweisen - auch wenn Du Dir ein echtes Problem suchst.

compilerbuilder schrieb:

Welches Buch empfehlt ihr denn , das mir Fragen wie diese beantworten kann?

Dir wird das Drachenbuch empfohlen werden. Nicht von mir, aber das wird wohl passieren, einfach weil man es immer empfielt. Es ist ein Standardwerk. Zum Thema Semantik hält es sich aber auch bedeckt.

Ich kann Dir kein Buch empfehlen.

Alle Bücher, die ich zu dem Thema kenne, beschäftigen sich mit der Theorie.
Kauf einfach alles, was Du bekommen kannst, guck rein, ob jemand eine gute Idee hatte, die Dich inspiriert und ansonsten definiere für Dich Dein Problem und finde eine angemessene Lösung. Keine meiner Lösungen habe ich jemals in einem Buch wiedergefunden.

[Mechanics]

Du kannst dir vielleicht das Buch hier mal anschauen:

http://www.amazon.com/Language-Implementation-Patterns-Domain-Specific-Programming/dp/193435645X

Es ist recht praxisnah. Steigt aber nicht ganz so tief in die Theorie ein, wie z.B. das Drachenbuch. Über semantische Analyse steht da auch nicht so viel drin, wie Xin geschrieben hat, wirst du eh nicht viele Bücher finden, die sich darüber auslassen. Hat aber zumindest ein Kapitel "Enforcing static typing rules". Ich weiß jetzt nicht mehr, was da drin steht, mich haben hauptsächlich die Kapitel über Interpreter interessiert.

[hustbaer]

deejey schrieb:

Compilerbau ist eine Wissenschaft für sich, gibt ganze Bücher die nur das behandeln, das kriegt man nicht mal eben hin im Rahmen von "Ich muss einen Compiler für Java schreiben"

Wenn kein wirklich guter Compiler (=schnell, gute Fehlermeldungen etc.) rauskommen soll, und die Sprache einfach genug und einfach genug zu parsen ist (Java sollte dieses Kriterium erfüllen -- wobei ein älterer Java Standard sicher noch einfacher wäre), sehe ich da kein unlösbares Problem. Auch nicht für jemanden der das noch nie gemacht hat und nicht speziell Compilerbau "gelernt" hat. Es ist vermutlich sehr viel Arbeit, aber so wirklich sehr schwer ist glaube ich kein einziger Teil.

Allerdings sollte man sich schon halbwegs gut mit der Sprache auskennen für die man den Compiler schreiben soll, halbwegs gut programmieren können und fähig sein einen Standard zu lesen & entziffern.
Da sehe ich beim OP schon eher ein Problem.

Ich glaube mittlerweile dass dieses "Compilerbau ist eine Wissenschaft für sich" ne urban software developer legend ist.
Compilerbau ist eines von unglaublich vielen nicht-trivialen Themen, das aber mMn. auch nicht signifikant komplizierter ist als alle anderen.
(Also nicht grundsätzlich, nicht für einfache Sprachen. Ein C++ Compiler ist natürlich ein Beast, aber das liegt eher daran dass C++ als Sprache ein Beast ist. Komplizierte Grammatik, komplizierte Sprache => komplizierter Compiler.)

[Xin]

hustbaer schrieb:

Ich glaube mittlerweile dass dieses "Compilerbau ist eine Wissenschaft für sich" ne urban software developer legend ist.

Compilerbau ist eine Wissenschaft für sich. Es ist die Wissenschaft davon, Daten einzulesen, zu verstehen und in einem anderen Format wieder auszugeben. Man kann Compilerbau als Design Pattern von Datenverarbeitung verstehen.

hustbaer schrieb:

Compilerbau ist eines von unglaublich vielen nicht-trivialen Themen, das aber mMn. auch nicht signifikant komplizierter ist als alle anderen.

Ich halte es für universeller, aber eben auch manchmal komplexer, weil es eben nicht von Quelle->Ziel transformiert, sondern von Quelle->AST->Ziel oder auch noch Zwischencodes erzeugt, wie beispielsweise ByteCode.

Hat man die Systematik aber erstmal verstanden, kann man eigentlich nahezu alles in alles andere transformieren.

Es ist richtig, dass man sich in der Quelle gut auskennen sollte - die Zielsprache sollte man aber nicht unterschätzen. Wir programmieren schließlich alle Hochsprachen, weil uns die Zielsprache zu komplex erscheint. ^^
Und während ein Parser beliebige Datenstrukturen zur Verfügung hat, um den AST zu verwalten, sieht das bei z.B. Opcodes schon wieder ganz anders aus.

[hustbaer]

Ich war wohl zu faul das ausreichend weit zu erklären
Klar ist es irgendwie "eine Wissenschaft für sich". Aber das trifft auf viele Dinge zu.

Die Aussage "Compilerbau ist eine Wissenschaft für sich" wird einfach oft in Beiträgen gebracht, wo gleichzeitig behauptet oder zumindest impliziert wird dass es wahnsinnig schwierig ist einen Compiler zu bauen. Und dass jemand der nicht der Superüberdrüberchecker ist das in ein paar Monaten unmöglich hinbekommen kann, sofern er es nicht schonmal gemacht hat.

Und das sehe ich einfach anders.

Es ist schwierig einen Compiler zu bauen...
...für Quellsprachen mit einem extrem umfangreichen und komplexen Sprachstandard,
...für recht komplizierte Zielsprachen,
...der wirklich schnellen Code erzeugt,
...der wirklich schnell läuft,
...der wirklich gute Fehlermeldungen liefert
usw.

Einfach nur einen funktionsfähigen Compiler für z.B. C# 1.0 oder Java 5 zu schreiben ist aber mMn. nicht so schwer. Aber vielleicht ist auch meine Messlatte dafür was ein "halbwegs guter Programmierer" können sollte zu hoch

BTW: Was die Zielsprachen angeht -- die sind doch meist nicht sonderlich komplex. Also x86 Assembler z.B. finde ich überhaupt nicht komplex. Nicht wenn man nur lauffähigen Code haben will - also auf sämtliche Optimierungen mit SSE & Co verzichtet.
AFAIK sind der GNU Zwischencode sowie LLVM ein wenig komplex. Aber man muss ja nicht gleich das schlimmste annehmen.

[deejey]

Der Threaderöffner sprach ja von einen Compiler für java, wenn ich bedenke was da alles hintersteckt, Vererbung, Überladung, Threads und was weiß ich was es da noch für Sachen gibt dann würde ich vom Gefühl her sagen ein erfahrener Programmierer (und der muss excellenter Kenner von Java, SDK-zeugs und Maschinencode bzw. Zwischencode sein) braucht mehrere Monate bis eher Jahre dafür.

Hier was sehr Schönes dazu von der Stanford-Uni, die haben offenbar so ein komplettes Compiler-Projekt letztes Jahr gemacht, sieht sehr Interessant aus. Und hier das Thema was für den TO wichtig ist.

"Ich soll" klingt nach einer begrenzten Projektaufgabe/Hausarbeit (ist nicht abwertend gemeint) oder sowas, da käme aus meiner Sicht höchstens eine Art einfacher Pseudocode-Compiler in Frage.

[maximAL]

compilerbuilder schrieb:

Welches Buch empfehlt ihr denn , das mir Fragen wie diese beantworten kann?

Ich kann dir Grundlagen und Techniken des Compilerbaus von Niklaus Wirth empfehlen. Das ist ein einigermassen einsteigerfreundliches Buch zum Thema - im Gegensatz zum "Drachenbuch". Es bezieht sich aber natuerlich nicht speziell auf Java.

[hustbaer]

deejey schrieb:

Der Threaderöffner sprach ja von einen Compiler für java, wenn ich bedenke was da alles hintersteckt, Vererbung, Überladung, Threads und was weiß ich was es da noch für Sachen gibt dann würde ich vom Gefühl her sagen ein erfahrener Programmierer (und der muss excellenter Kenner von Java, SDK-zeugs und Maschinencode bzw. Zwischencode sein) braucht mehrere Monate bis eher Jahre dafür.

Threads spielen da mMn. kaum mit rein. AFAIK wird alles was Threads angeht von der JVM und dem JIT Compiler erledigt. Den Frontent Compiler muss das nicht interessieren.
Ebenso muss man sich mit Maschinencode nicht auskennen wenn man nur den Frontent Compiler entwickeln soll.

Und wie schon mehrfach erwähnt ist das ein Uniprojekt, da muss nichts produktiv brauchbares rausschauen.

deejey schrieb:

"Ich soll" klingt nach einer begrenzten Projektaufgabe/Hausarbeit (ist nicht abwertend gemeint) oder sowas, da käme aus meiner Sicht höchstens eine Art einfacher Pseudocode-Compiler in Frage.

Erstmal sind es 9 Jungs (Mädels?) die das zusammen machen sollen, und dann hatte ich den Eindruck dass sie dafür auf jeden Fall mehrere Monate Zeit haben.

Ich finde die Aufgabe auch nicht ganz ohne, aber ich halte das auch nicht für komplett unschaffbar.