Also, Ziel, Aufgabe: Terme, die anders gestellt sind, so umformen - dass sie gleich sind. Meine erste Idee bestand darin, ich habe ja den Assembler-Output erzeugt. Unnötige Klammern konnte ich entfernen. Meine Idee jetzt, um gleiche Terme zu bekommen. Ich habe ja jetzt die Assembler-Befehle, zum Beispiel add r1, 0, 1 add r2, 0, 2 Diese könnte ich umsortieren: add r2, 0, 2 add r1, 0, 1 Jetzt kommt das Thema Sortierung ins Spiel. Sollte ein Ausdruck, ein Mal add r1, 0, 1 add r2, 0, 2 und ein Mal add r2, 0, 2 add r1, 0, 1 ergeben, sortiere ich die zu: add r1, 0, 1 add r2, 0, 2 Der Ausdruck 1+2 und 2+1 könnte somit gleich gemacht werden. Die Aufgabe wäre zunächst alle Assembler-Befehle zu sortieren, die als eine Einheit mit Addition stattfinden. Das heißt, ich habe 4+3+6+1 Das ist eine Einheit, vor dem nächsten *, zum Beispiel (4+3+6+1)*2 Die kann ich sortieren 1+3+6+4 Jetzt sortiere ich die Register r1 r2 r3 r4 Das sind die Zielregister add r1 ... add r2 ... add r3 ... add r4 ... Das Problem ist, diese Ziel-Register sagen nichts. Also, lasse ich die Zielregister weg und nehme nur die Operanden add r1, 4, 1 Dann ist das 1+4 Und ich speichere 1 4 Das geht nach dem Motto 1 4 2 3 5 6 Jetzt ist das Problem, der zweite Quelloperand kann wieder ein Register sein. Also mache ich 1 4 2 3 5 6 Das sind alles Operanden von +. Die müssen sortiert werden 1 2 3 4 5 6 Jetzt habe ich eine Einheit. Die Summe. Jetzt kommen die * Im nächsten Schritt müssen alle *, der nächsten Höhe, also alle MUL sortiert werden. Nach dem Mal kommen wieder Summen. Damit haben wir Einheiten. Das führt zu einem Syntaxbaum. In dem Syntaxbaum muss sortiert werden. Jetzt ist die Frage wie: Ich habe einen Ast - der stellt zum Beispiel eine Summe dar. Jetzt sortiere ich alle Summen von einem Level. Was wir bei Bäumen oft machen, sind Level. Das heißt, das Level mit der ersten Ebene von Knoten. Im zweiten Level, im dritten. Hier ist das Level, die erste Summe, dann kommen mal im zweiten Level, dann + im dritten Level. Hat man den Syntaxbaum müsste man vor dem sortieren einen Vordurchlauf machen. Man fügt überall die Level, das heißt, folgt nach * +, also * bezogen auf eine Summe - dann wandern die + durch und tun sie alle ins selbe Level. Nachher wird sortiert. Dann werden erst alle im letzten Level sortiert. Dann wird im zweiten Level - die kompletten Bäume sortiert. Um sie sortieren zu können, müssen wir die Daten sortieren - das sind in dem Fall die Zahlen - z.B. 4 und 1. Und weil wir nachher ganze Teilbäume sortieren, würde es sich anbieten - aus den Daten einen String zu machen Zum Beispiel 37821 45902 Diese können wir mit strcmp vergleichen. Wir sortieren den Baum unabhängig davon, was im Vergleich steht. Den anderen sortieren wir auch. Doch jetzt haben wir eindeutige Darstellungen. Und jetzt können wir die Ausdrücke vergleichen.