-
Ritter
Geht es darum wie ein Computer aus Einsen und Nullen komplexere Befehle ausführt, oder um den Aufbau eines Compilers?
Das wird glücklicherweise mittlerweile gut getrennt.
Der CPU-Hersteller gibt einen bestimmten Befehlssatz vor, oft mit nur rudimentären Operationen (Speicherzugriffe, Einfache Rechenoperationen, Shiften und ein paar Sprunganweisungen).
Für einen Compiler ist das natürlich das begehrte Zielformat.
Der Schritt vom Quellcode zum fertigen Programm ist relativ komplex und wird daher in verschiedene Schritte unterteilt.
1. Lexing
Der Quellcode wird mithilfe von regulären Ausdrücken in eine Reihe von synaktischen Tokens zerlegt. Statt eines Zeichenstroms kriegt der nachfolgende Parser die einzelnen syntaktischen Bausteine Stück für Stück. (Statt, "if x > 1 then y" liest der parser: if-token, identifier, greater, constant, then, identifier)
In dem Schritt werden auch Whitespaces und Kommentare "überlesen".
2. Parser
Der Parser arbeitet auf diesem Tokenstream des Lexers und muss entscheiden ob der Input ein syntaktisch korrektes Programm darstellt oder nicht. Hier wird mit kontextfreien Grammatiken (bzw. mit etwas eingeschränkten kfG) gearbeitet. Der Parser baut als Output einen Syntax-Baum auf (genau genommen einen sogenanntne "Abstrakten Syntax Baum" AST, da der konkret zum Parsen verwendete Syntaxbaum für die spätere Arbeit etwas unhandlich ist)
In der Regel spricht man direkt den Parser an, der dann jeweils den Lexer aufruft um das nächste Token zu kriegen. Da Parsing ein relativ komplexes Problem ist baut man mittlerweile eher selten Parser von Hand. Stattdessen gibt es Programme, die für eine gegebene Grammatik einen entsprechenden Parser oder Lexer (oder beides) generieren.
Ich benutz jetzt mal eine einfache Anweisung wie "y = x + 2" als Beispiel.
Im AST hätten wir also hier einen Zuweisungsknoten, dessen linkes Kind ein Identifier Knoten wäre (die variable y), der rechte Knoten wäre ein Add-Knoten, mit den jeweiligen Kindern: Identifier-Knoten (variable x) und Konstante-Knoten (die 2).
Auf diesem AST kann man nun Typchecking (stimmen die typen der kinder des add-knoten für eine addition, ist der ergebene typ des Add-Knotens kompatibel mit dem typ von y) und diverse Optimierungen vornehmen.
Am Ende ist es relativ "simpel" für einen bestimmten Knoten im AST den entsprechenden Assemblercode zu generieren. Für obiges Beispiel wäre das zB:
1. Lade die Adresse des linken Kinderknoten (des Ziels) in ein Register A
2. Führe den Code zur Berechnung des Rechten Kinderknotens aus (Ergebnis steht in einem fest definierten Register B)
3. Kopiere den Wert aus B an die Adresse, die in A steht
Ich hab auf der Platte noch den Compiler (Source Code) für eine einfache Programmiersprache liegen, den wir letztes Semester als Projekt schreiben mussten. Der Compiler ist in Java geschrieben und erzeugt als Output Code für einen Assembler, der das ganze in Java-bytecode übersetzt. Falls du Interesse hast, kannst du ihn gerne haben =).
Berechtigungen
- Neue Themen erstellen: Nein
- Themen beantworten: Nein
- Anhänge hochladen: Nein
- Beiträge bearbeiten: Nein
-
Foren-Regeln