Was bedeutet syntaxgesteuerte Übersetzung?

Question

Kann jemand in einfachen Worten erklären, was "Syntax Directed Translation" bedeutet? Ich fing an, das Thema von Dragon Book zu lesen, konnte aber nicht verstehen. Die Wiki article hat auch nicht geholfen.

Answer 1

In einfachen Worten bedeutet "Syntax gerichtete Übersetzung", dass der gesamte Kompilierungs- (Übersetzungs-) Prozess mit dem Syntax-Erkenner (dem Parser) gesteuert wird. Der Prozess des Kompilierens eines Programms (das Übersetzen von Quellcode in Maschinencode) beginnt konzeptionell mit einem Parser, der einen Syntaxbaum erzeugt, und transformiert diesen Parsingbaum dann durch eine Sequenz von Baum- oder Graphtransformationen, von denen jede einzelne davon ist ist weitgehend unabhängig, was zu einem endgültigen vereinfachten Baum oder Graphen führt, der durchlaufen wird, um Maschinencode zu erzeugen.

Diese Ansicht, obwohl in der Theorie schön, hat einen Nachteil, dass, wenn Sie versuchen, es direkt zu implementieren, genügend Speicher für mindestens zwei Kopien der gesamten Struktur oder Grafik benötigt wird. Damals, als das Drachenbuch geschrieben wurde (und als viel von dieser Theorie ausgehebelt wurde), wurden Computerspeicher in Kilobyte gemessen, und 64K waren eine Menge. So könnte das Kompilieren großer Programme schwierig sein.

Mit Syntax Directed Translation organisieren Sie alle Diagrammumwandlungen in der Reihenfolge, in der der Parser den Syntaxbaum erkennt. Anstatt einen vollständigen Parse-Baum zu erzeugen, baut Ihr Parser kleine Teile davon auf und führt diese Bits dann den nachfolgenden Durchläufen des Compilers zu, wodurch schließlich ein kleiner Teil des Maschinencodes erzeugt wird, bevor der Parsing-Prozess fortgesetzt wird, um das nächste Parset zu bauen Baum. Da zu jeder Zeit nur kleine Mengen des Parsebaums (oder der nachfolgenden Graphen) existieren, ist viel weniger Speicher erforderlich. Da der Syntaxerkenner der Master-Sequenzer ist, der all dies steuert (die Reihenfolge, in der die Dinge passieren), wird dies Syntax-gerichtete Übersetzung genannt.

Da dies eine effektive Möglichkeit ist, den Speicherverbrauch niedrig zu halten, haben die Leute sogar die Sprache neu gestaltet, um es einfacher zu machen - ideal, um einen "Single Pass" -Compiler zu haben, der tatsächlich den gesamten Prozess durch Parsing erledigen könnte um die Code-Generierung in einem einzigen Durchgang zu automatisieren.

Heutzutage ist die Speicherkapazität nicht so hoch, so dass weniger Druck entsteht, um alles in einen einzigen Durchgang zu zwingen. Stattdessen verwenden Sie in der Regel Syntax Direct Translation nur für das Frontend, Syntaxanalyse, Typchecking und andere semantische Prüfungen und einige einfache Transformationen, die alle vom Parser stammen und eine interne Form (drei Adresscodes, Bäume oder Dags) erzeugen) und dann separate Optimierungs- und Back-End-Pässe haben, die unabhängig sind (und nicht syntaxgesteuert sind). Selbst in diesem Fall könnten Sie behaupten, dass diese späteren Übergänge zumindest teilweise syntaxgesteuert sind, da der Compiler so organisiert sein kann, dass er große Teile der Eingabe bearbeitet (wie ganze Funktionen oder Module) und alle Durchläufe durchläuft, bevor er weitergeht nächstes Stück Eingabe.

Tools wie yacc sind um die Idee von Syntax Directed Translation entwickelt - das Tool erzeugt einen Syntax-Erkenner, der Code-Fragmente ('Aktionen' im Tool-Sprachgebrauch) direkt ausführt, während Produktionen (Fragmente des Parse-Baumes) erkannt werden , ohne jemals einen wirklichen "Baum" zu erschaffen. Diese Aktionen können direkt aufrufen, was später im Compiler logisch später übergeben wird, und dann zurückkehren, um mit dem Parsen fortzufahren. Die imperative Hauptschleife, die all dies antreibt, ist die Token-Lesezustandsmaschine des Parsers.

Answer 2

Vor dem Dragon Book gab es Syntax-gesteuerte Compiler-Compiler. META II und TREE META wurden in den 1960er Jahren entwickelt. Sie sind Metasprachen Compiler (Metacompiler). Sie sind Top-Down-Parser, die eine Reihe von Parsing-Regeln verwenden, die tatsächlich Funktion sind, die den Erfolg eines Fehlers zurückgeben. Jede Regel ist ein logischer Analyseausdruck. Die oberste treibende Regel definierte den Inhalt der Quelldatei. Zum Beispiel könnte eine Programmiersprache aus einer Reihe von Deklarationen bestehen.Die oberste Fahrregel würde also wie folgt aussehen:

program = $declarations; 

Das $ bedeutet null oder mehr. $ declarations gibt an, dass die zu kompilierende Quelle aus einer Anzahl von Deklarationen besteht. Deklarationen würden dann die Deklarationstypen definieren. Möglicherweise benötigen Sie externe Verknüpfungsdeklarationen, Datendeklarationen, Funktions- oder Prozedurdeklarationen.

declarations = linkage_decl | data_decl | code_decl; 

Die Deklarationstypen sind jeweils eine separate Regel. Die Syntax würde steuern, wann die Codegenerierung stattfindet. Die Metacompiler kontrollierten die semantische Verarbeitung aus den Syntaxregeln. Zuerst in der Regel ist es selbst. Später verwandelten sie die Quelle in Baum- und Listenstrukturen und übergaben sie an semantische Regeln, die ihre Ausgabe erzeugten. Zum Beispiel könnte eine arithmetische Zuweisungsanweisung transformiert und an eine semantische Regel übergeben werden.

asign = id '=' expr ';' :ASSIGN!2 arith_gen(*1); 
expr = term $(('+':ADD | '-':SUB) term !2); 
term = factor $(('*':MPY | '//' :REM | '/':DIV) factor!2); 
factor = id | number | '(' expr ')'; 

Es wurde gesagt, dass diese Sprachen bnf mögen. Aber das ist nicht der Fall. Dies sind analytische Top-down-Syntaxanalysatoren. arith_gen würde dann codiert werden, um die Baumstrukturen zu erkennen, die durch den eingebetteten Baum, ':' und '!' Betreiber. Die verwendete Baumnotation ist der Knoten gefolgt von den Baumzweigen, die in '[' und ']' eingeschlossen und durch ',' getrennt sind. Die obige analytische Syntax definiert die mathematische Hierarchie eines Ausdrucks. Multiplikation, Division und Rest werden vor der Addition oder Subtraktion durchgeführt. Ein arithmetischer Zuweisungsausdruck, der in einen Funktionslistenausdruck umgewandelt wird. Die Syntax steuert die Umwandlung der Eingabe in eine funktionale Notation.

x = a + (b - c)/d; 

erzeugt eine funktionale Notation Baum: ASSIGN [x, ADD [a, DIV [SUB [b, c], d]]]

Diese alten metacompilers nicht genau die aktuelle Terminologie anzupassen.

Siehe Wiki Metacompiler META II und TREE META Themen und es ist Diskussions-Seite für weitere Informationen