Compilerbau

Moin moin,

ich beschäftige mich momentan im Rahmen meiner Ausbildung mit dem Thema des Parsens und syntaktischen Prüfens von Code. Ich habe mir diesbezüglich mal das sogenannte "Dragonbook" angeschaut und habe einige Fragen, was die Thematik angeht:

Im "Dragonbook" wird von Anfang an folgender Aufbau für das Design eines Compilers vorgeschlagen:
Lexer->Syntaxanalyse->Semantische Analyse->...
In dem Fall würde man die Zerlegung in Token und die Überprüfung der Syntax trennen. Bevor ich das Buch laß, hatte ich schon mehrmals die Gelegenheit, einige simple Lexer mit einfacher Syntaxprüfung zu schreiben. Allerdings hatte ich hier Lexer und Syntaxanalyse in ein Modul gepackt. Besonders weil es den Vorgang des Parsens deutlich vereinfachte: Durch die Vorgabe der Grammatik konnte man während des Parsens schon feststellen, welche(s) Token folgen müsste(n). Zudem konnte man den Vorgang des Parsens vorzeitig abbrechen, wenn während dieses Vorgangs ein "nicht erwünschtes" Token auftrat.
Welche Erfahrungswerte habt ihr in diesem Bereich gesammelt und welches Design wird in der Praxis angewendet; welche Vor- und Nachteile gibt es?
Ich habe theoretisch mal durchgespielt, die vom "Dragonbook" empfohlene Trennung zwischen Lexer und Syntaxanalyse einzusetzen. Allerdings stellen sich mir dort noch einige Fragen: Bisher hatte ich immer ein Satz an Strukturen, die einen gewissen Tokenbezeichner an einen regulären Ausdruck gebunden hatten. Durch die interne Verwebung von Lexer und syntaktischer Analyse konnte ich bisher relativ einfach bestimmen, welches Token und damit welcher reguläre Ausdruck als nächstes zu parsen war. Wie wird dies gehandhabt, wenn die lexikalische Einheit unabhängig von der syntatkischen ist? Den Satz von regulären Ausdrücken zu nehmen und diesen einfach auf den Text loszulassen wird nicht funktionieren.

Im Dragonbook war von einer Methode die Rede, den Text jeweils mithilfe zweier Pointer zu durchlaufen, wobei der erste - vorerst - fest gewählt wird und der zweite solange inkrementiert, bis der von den Pointern beschriebene Textbaustein auf einen regulären Ausdruck passt. Anschließen wird der erste Pointer auf die dem zweiten Pointer folgende Position gesetzt und das Spiel geht weiter. Allerdings muss man für diese Methode jeden möglichen Textbaustein - im worst case - gegen n verschiedene reguläre Ausdrücke prüfen. Was mache ich, wenn ein anderer reguläre Ausdruck auch auf diesen Textbaustein passt oder der reguläre Ausdruck eigentlich noch mehr Zeichen "konsumieren" könnte?

Welche Methoden werden hier angewandt, um die richtige Zerlegung zu gewährleisten? Wie fein müssen Token bzw. ihre "regulären Repräsentaten" zerlegt werden, damit Zweideutigkeiten beim Parsen des Textes vermieden werden?
Welche Methoden benutzt ihr, um den Text in Token zu zerlegen?

Welche zusätzliche Literatur gibt es auf diesem Gebiet? Besonders jene würden mich interessieren, die etwas praxisorientierter vermitteln und vielleicht auch mal eine Implementierung zeigen(bevorzugt C++, aber im Grunde egal).

So, jetzt aber erstmal genug der Fragen, ist schon spät

Siassei

Sevus,

Matzer schrieb:

Besonders jene würden mich interessieren, die etwas praxisorientierter vermitteln und vielleicht auch mal eine Implementierung zeigen(bevorzugt C++, aber im Grunde egal).

Hier findest du ein paar Implementationen, ansonsten kanst du mal beim GCC nachschauen, was der einsetzt.

Zeus

Lexer und Parser haben zwei verschiede Verantwortungsbereiche.
Lexer behandelt die Dateien, überprüft ob das Word gültig ist und versickt Nachrichten an den Parser.
Parser kennt die Sprache und überprüft ob die Sequenz der Nachrichtige ein gültiges Satz der Sprache handelt.
Meistens ist der Lexer ein Teil, als Komponente, des Parsers, immerhin werden beide Komponente anhand der Grammatik der Sprache erstellt.

Zweideutigkeiten werden nicht vom Lexer bewältig sonder die müssen aus der Transformation der Grammatik bewältigt werden.

Falls du interesse hast, kann ich dir meine Semesterarbeit mit Quellcode ein 'BoolCompiler' zuschicken.

Matzer

Siassei schrieb:

Hier findest du ein paar Implementationen, ansonsten kanst du mal beim GCC nachschauen, was der einsetzt.

Vielen Dank, dort werde ich mal durchschauen. Inbesondere der letzte Verweis auf der Seite scheint interessant zu sein. Den GCC-Quellcode habe ich auch, allerdings wird es seine Zeit brauchen da durchzusteigen.

Zeus schrieb:

Meistens ist der Lexer ein Teil, als Komponente, des Parsers, immerhin werden beide Komponente anhand der Grammatik der Sprache erstellt.

Bisher sah mein Design meist so aus, dass die Grammatik nur für die syntaktische Überprüfung anhand der Tokenbezeichner ausgelegt war. Den Lexer hab ich dann meist per Hand erstellt und nicht direkt aus der Grammatik konstruiert. Gibt es hier irgendwelche Schlagworte, nach denen man sich dahingehend mal genauer informieren könnte?

Zeus schrieb:

Zweideutigkeiten werden nicht vom Lexer bewältig sonder die müssen aus der Transformation der Grammatik bewältigt werden.

In dem Fall kann der Lexer aber doch nicht völlig unabhängig vom Parser selbst sein, so wie es das Dragonbook darstellt, oder?
Angenommen ich habe zwei verschiedene Tokenbezeichner, die aber anhand des gleichen regulären Ausdrucks aus dem Text "gelext" werden, so kann der Lexer während dieses Vorgangs alleine garnicht entscheiden, um welches Token es sich handelt? Kurz: Ist es möglich Lexing und syntaktische Überprüfen in zwei unabhängige Komponenten einzuteilen bzw. welche Anforderungen müssen dann an die Struktur des Textes gestellt werden?

Falls du interesse hast, kann ich dir meine Semesterarbeit mit Quellcode ein 'BoolCompiler' zuschicken.

Klar, ich wäre für alles dankbar, was mir irgendwie beim Verständnis hilft. Soll ich dir meine eMail zukommen lassen?

Zeus

Matzer schrieb:

...

Zeus schrieb:

Meistens ist der Lexer ein Teil, als Komponente, des Parsers, immerhin werden beide Komponente anhand der Grammatik der Sprache erstellt.

Bisher sah mein Design meist so aus, dass die Grammatik nur für die syntaktische Überprüfung anhand der Tokenbezeichner ausgelegt war. Den Lexer hab ich dann meist per Hand erstellt und nicht direkt aus der Grammatik konstruiert. Gibt es hier irgendwelche Schlagworte, nach denen man sich dahingehend mal genauer informieren könnte?

Wenn du rumprobierst, wirst du feststellen, dass du die Regeln für dein Lexer/Scanner erstellst, welche eine Teilmenge der Terminale deiner Grammatik entspricht. Da gibst gewissen künstlicher Freiheisten. Beispielweise das '>>'-Template-Problem bei den meisten C++ Compiler. Von automatisiert aus der Grammtik ableiten hab ich nicht gesprochen.

Matzer schrieb:

Zeus schrieb:

Zweideutigkeiten werden nicht vom Lexer bewältig sonder die müssen aus der Transformation der Grammatik bewältigt werden.

In dem Fall kann der Lexer aber doch nicht völlig unabhängig vom Parser selbst sein, so wie es das Dragonbook darstellt, oder?
Angenommen ich habe zwei verschiedene Tokenbezeichner, die aber anhand des gleichen regulären Ausdrucks aus dem Text "gelext" werden, so kann der Lexer während dieses Vorgangs alleine garnicht entscheiden, um welches Token es sich handelt? Kurz: Ist es möglich Lexing und syntaktische Überprüfen in zwei unabhängige Komponenten einzuteilen bzw. welche Anforderungen müssen dann an die Struktur des Textes gestellt werden?

Sie sind nicht völlig unabhängig, weil die Komponenten miteinandere intergieren, aber sie sollten so unabhängig sein, dass ihre Implementierung getrennt nach ihre Aufgaben sind.

Genau! Das kann der Lexer nicht wissen, und es muss es nicht wissen. Weil die Überprüfung die Aufgabe des Parsers oder die von einer weiteren Komponente ist.

Ablauf zwischen Lexer und Parser:
Lexer bekommt Token.
Lexer erkennt Bezeichner 'MyClass'
Lexer sendet dem Parser, dass er ein Bezeichner mit dem Wert 'MyClass' gefunden hat
Parser überprüft, ob dies gultig ist.

Dabei sollte ich noch sagen, was ich sage, ist nicht absolut.

Matzer schrieb:

Falls du interesse hast, kann ich dir meine Semesterarbeit mit Quellcode ein 'BoolCompiler' zuschicken.

Klar, ich wäre für alles dankbar, was mir irgendwie beim Verständnis hilft. Soll ich dir meine eMail zukommen lassen?

Ich hab meine ICQ Nr im Profile.

Ben04

Je nach Sprache ist es möglich den Lexer völlig abzutrennen. Du musst halt aufpassen, dass du keine >> vs > > Geschichten hast. Keywords allgemein sind auch schon blöd. Bei letzterem kann man aber mit (tok.type == identifier && tok.val == "foo") in der Syntaxanalyse "mogeln".

Allerdings spätestens wenn du brauchbare Fehlermeldungen einbauen willst, wirst du dein Design verwässern müssen.

Es gibt 1000 Varianten wie man einen Compiler im Detail strukturieren kann. Gib ein paar Anforderungen an deinen Compiler an, sonst macht es keinen Sinn über die detaillierte Struktur zu reden. Es gibt keinen Königsweg.