Compilerbau: Komplexer ausdruck (vereinfachen)



  • Hallo Leute,

    ich bin neu im Gebiet Compilerbau, und hab mal ne frage zu folgedem!

    Ich habe einen Scanner, der mir aus einem Ausdruck nen ExpressionTree erzeugt!

    X = ((A + (K * O)) * (B - I)) + (((D -E) + F) + (H / C))

    nun will ich diesen ausdruck in teil instruktions auflösen (denke für diesen prozess gibt best. schon ein verfahren bzw. bezeichnung dafür??):

    T1 = (H/C)
    X = ((A + (K * O)) * (B - I)) + (((D -E) + F) + T1)

    T2 = (D-E)
    X = ((A + (K * O)) * (B - I)) + ((T2 + F) + T1)

    T2 = (T2 + F)
    X = ((A + (K * O)) * (B - I)) + (T2 + T1)

    T2 = (T2 + T1)
    X = ((A + (K * O)) * (B - I)) + T2

    T1 = (B - I)
    X = ((A + (K * O)) * T1) + T2

    T3= (K * O)
    X = ((A + T3) * T1) + T2

    T3= (A + T3)
    X = (T3 * T1) + T2

    T3= (T3 * T1)
    X = T3 + T2

    Am ende habe ich dann nur noch einfache Ausdrücke, welcher der Compiler nacheinander abarbeitet:

    T1 = (H/C)
    T2 = (D-E)
    T2 = (T2 + F)
    T2 = (T2 + T1)
    T1 = (B - I)
    T3= (K * O)
    T3= (A + T3)
    T3= (T3 * T1)
    X = T3 + T2

    Aus diesen will ich später wieder einen ausdruck zurück transformieren!

    Wie nennt man den Algorithmus für sowas? Gibt da Strategien um so wenig wie möglich an zwischen Variablen (hier T1,T2,T3) zu verwenden?

    Danke und Grüße



  • Register allocation.

    Ansonsten einfach deine Infix-Notation nach Postfix-Notation umwandeln, quasi eine simple Stackmaschine.



  • Wenn du neu auf dem Gebiet bist, wärs nicht erstmal sinnvoll erstmal was funktionierendes auf die Beine zu stellen bevor du hier hochkomplizierte Optimierungen angehst ?

    Aus diesen will ich später wieder einen ausdruck zurück transformieren!

    Bitte was ? Worum genau gehts dir jetzt, darum dass du möglichst wenig Zwischenvariablen für die Rechnung willst oder... ?



  • @Knivil: Danke für die Stichworte:)

    @Shadow:Ne ich hab mir überlegt ob für eine solche transformation (unabhängig der komplexität des ausdrucks) endlich viele Temp variablen gebraucht werden..

    Mit Zurücktransformieren meine ich, dass ich aus den Infix befehlen, wieder zu dem postfix ausdruck komme!



  • und ja ich würde möglich wenig temporäre variablen wollen, je nach strategie der transformation kann das ja optimiert werden!?



  • endlich viele Temp variablen gebraucht

    Ja, eben weil der Ausdruck endlich ist.



  • NullBockException schrieb:

    Am ende habe ich dann nur noch einfache Ausdrücke, welcher der Compiler nacheinander abarbeitet:

    T1 = (H/C)
    T2 = (D-E)
    T2 = (T2 + F)
    T2 = (T2 + T1)
    T1 = (B - I)
    T3= (K * O)
    T3= (A + T3)
    T3= (T3 * T1)
    X = T3 + T2

    Aus diesen will ich später wieder einen ausdruck zurück transformieren!

    Wie nennt man den Algorithmus für sowas?

    "Einsetzen"?

    ps: Achso...
    Du musst das natürlich in SSA Form machen. Also quasi

    T1 = (H/C)
    T2 = (D-E)
    T2' = (T2 + F)
    T2'' = (T2' + T1)
    T1' = (B - I)
    T3= (K * O)
    T3'= (A + T3)
    T3''= (T3' * T1')
    X = T3'' + T2''

    Dann isses super easy das zurückzuübersetzen.

    Die SSA Form kannst du natürlich aus der non-SSA Form zurückgewinnen. Ist ja trivial, einfach bei der 2. und jeder weiteren Zuweisung die Variable umbenennen.



  • hustbaer schrieb:

    Die SSA Form kannst du natürlich aus der non-SSA Form zurückgewinnen. Ist ja trivial, einfach bei der 2. und jeder weiteren Zuweisung die Variable umbenennen.

    Nur innerhalb von Basisblöcken natürlich.



  • Mit Zurücktransformieren meine ich, dass ich aus den Infix befehlen, wieder zu dem postfix ausdruck komme!

    Wie kommst du jetzt aus Postfix ? Das ist alles Infix... 😕

    Ich würde das ganze auch als Stackmaschine aufbauen, kannst dir ja mal anschaun wie die Java VM das macht 😃



  • Das erinnert mich stark an die Kontextfreie Grammatik.



  • Ich würde das ganze auch als Stackmaschine aufbauen, kannst dir ja mal anschaun wie die Java VM das

    Und ich rate zu Forth als Einstieg.



  • Bashar schrieb:

    hustbaer schrieb:

    Die SSA Form kannst du natürlich aus der non-SSA Form zurückgewinnen. Ist ja trivial, einfach bei der 2. und jeder weiteren Zuweisung die Variable umbenennen.

    Nur innerhalb von Basisblöcken natürlich.

    Ja, klar, nur so lange keine Fallunterscheidungen gibt.
    Falls es das ist was "nur innerhalb von Basisblöcken" bedeutet.



  • Ja, so ungefähr. Keine Sprünge rein oder raus.



  • Danke für eure Beiträge, aber wie nennt man den jetzt eig. so ein Verfahren, in dem man komplexe ausdrücke "vereinfacht" ?

    Grüße


Log in to reply