wie bearbeitet ein Compiler if-Abfragen?

[dragi]

Hallo,

mal eine sehr theoretische Frage die mich gerade ziemlich beschäftigt: Wie bearbeitet ein Compiler if-Abfragen?
Er muss diese ja irgendwie parsen, das ist mir noch klar. Dann muss er die einzelnen Ausdrücke auswerten und dann die noch mit and, or, not in Verbindung bbringen...aber wie geht er da Sourcetechnisch mit um? Er muss ja beim Auswerten die Reihenfolge einhalten bzw. immer wissen was zusammengehört wenn z.B. ein or in dem Statement ist. Schreibt er das alles in eine Liste und arbeitet er das ab? Wenn man mal darüber nachdenkt, ist das alles gar nicht so einfach. Wenn man mal darüber nachdenkt nur nachzuprogrammieren wie man if-Abfragen bearbeiten soll...ich find dann wirds echt kompliziert.

Hat da jemand eine Idee zu wie man sowas programmiert? Also nur in der Theorie als Modell oder pseudo Code?

Gruss

Dragi

[Oxmyx]

Mit einer Baumstruktur. Es gibt einen If-Zweig, einen Then-Zweig, und einen Else-Zweig. Zuerst wird der If-Zweig ausgeführt. Trifft die Bedingung im Gesamten zu, dann wird der Then-Zweig ausgeführt, anderenfalls der Else-Zweig.

[Schubi]

Die Bedingungen werden wohl nach den herrschenden Regeln zusammengefasst und jeder Term nacheinander ausgerechnet. So schwierig isses net. Man muss nur die Regeln beachten welche Verknüpfung vorrang hat

[PRehders]

Hallo dragi,

das ganze ist nicht schwierig, aber man muss etwas aufpassen und nachdenken. Da du etwas Quelltextmässiges haben wolltest, kann ich ja mal (grob) skizzieren, wie ein klassischer rekursiv-absteigender Compiler da rangeht. Ich nenne die Dinge mal mit den namen und N. Wirth, weil die meisten das wiedererkennen werden. Die ganzen sprachspezifischen Sonderdinge lass ich mal weg.

Das IF-Statement lautet z.B.: IF <Ausdruck> THEN <Anweisungen> ENDIF

Der Compiler sieht das IF und sagt sich: Aha, ein IF-Statement. Da folgt jetzt ein <Ausdruck>. Danach muss THEN folgen, danach <Anweisungen>, danach ein ENDIF.
Der Trick beim rekursiv-absteigenden Parser ist jetzt, dass das <Ausdruck> eben wieder eine Prozedur ist (genau wie <Anweisungen>).

Um deine Frage nach dem Operatoren-Vorrang zu beantworten, das geht so:

Ein <Ausdruck> ist <einfacher_Ausdruck> {<= <> < > <= >= <einfacher_Ausdruck>}

Ein <einfacher_Ausdruck> ist <Term> { + - <Term>}

Ein <Term> ist <Faktor> {* / <Faktor>}

Ein <Faktor> ist eine Variable, ein Literal, oder aber auch wieder ein <Ausdruck> in Klammern.
Die {} bedeuten hier null oder mehrere Wiederholungen. Jede Struktur (einfacher_Ausdruck, Term, Faktor) bekommt eine eigene Prozedur zum Parsen, die dann wieder die darunterliegenden teile aufruft.

In dieser Struktur wird im Speicher ein Baum aufgebaut, der den Ausdruck abbildet und danach in Code umgesetzt werden kann. Dadurch, dass ein <Faktor> wieder ein geklammerter Ausdruck sein kann, hat man eine rekursive Struktur.

Probier's mal mit X + Y * Z; dabei wird durch die Aufteilung in Term und Faktor automatisch der Ausdruck beim "+" aufgeteilt, und das "*" wird dem Y und dem Z zugeordnet, wo es ja auch hingehört.

Wenn du noch mehr Erläuterung brauchst, kannst Du dich ja nochmal melden. Ist am Anfang etwas verwirrend, aber wenn man es einmal kapiert hat, geht's recht leicht.

Viel Spass

Peter

[dragi]

Hallo,

vielen Dank für die Antworten. Ich glaub so langsam steig ich ja dahinter aber...wie programmiert man den eine Baumstrucktur? Ich denke mal mit einer klasse die sich selbst wieder aufruft...ist das vielleicht ein Ansatz? Mir geht es darum mal nach zu programmieren wie das geht natürlich mit bekannten variablen weil ich nur den Teil zwischen if und then bearbeiten möchte...

Gruss

Dragi

[moritz]

Hallo,

schau dir mal auf meiner Homepage das Programm GDev an. Wenn du das mit dem Parameter -backup startest, legt es in den eigenen Dateien backups der Programme an. Dabei ist auch eine ASM-Datei. Da siehst du, wie in dem Gall von GDev "Wenn"-Strukturen umgesetzt werden. Die sind zwar bei weitem nicht so komplex wie die in Delphi möglichen IfStrukturen, aber das Prinzip ist das gleiche.

Gruß, Moritz

[dragi]

@ moritz

Danke für den Tip mit deinem Programm! Aber soweit stecke ich dann doch noch nicht in der Materie um die ASM Datei zu verstehen
Wenn ich die mit einem Edtor öffne verstehe ich da zur Zeit nur Bahnhof

Aber ein wirklich geniales Programm was du da geschrieben hast. RESPEKT!!!

Gruss

Dragi

[PRehders]

Hallo,

sorry für die Unterbrechung; war abwesend.
Ich werde mal ein bischen was formulieren, dauert aber ein paar Minuten. Noch ein paar Fragen:
- Du willst nur die Bedingung parsen?
- Variablen etc. sind alle bekannt?
- Die Variablen sind "simpel" (also keine Arrays, Records, Pointer, Strings etc.)?
- Willst du den Ausdruck beim Parsen unmittelbar auswerten oder erst zu einem späteren Zeitpunkt?

Ich schraub mal etwas (Pseudo-)Code zusammen, der dir die Sache vielleicht etwas klarer macht.

Bis dann

Peter

[dragi]

Hallo,

find ich ja super das man hier so gut hilfe bekommt! Danke!

Ja, ich möchte nur die Bedingung parsen und die Variablen sind bekannt. Nach dem parsen soll dann die entscheidung fallen ob das komplette Statement nun True oder False ist.

Ich glaub mein Problem ist, das ich nicht weiss wie ich den "Baum" den ich in der Theorie erzeuge in Sourcecode wandeln soll...

Gruss

Dragi

[PRehders]

Hallo nochmal,

jetzt mal ein bischen was konkretes.

Zuerst: Du brauchst einen Scanner, der dir immer sagt, welcher Art das nächste Zeichen ist.
Und dieses auch aufbereitet. Dies nennt man häufig einen "Tokenizer", da er den Eingabezeichenstrom in sogenannte Tokens zerlegt. Ein solches Token wäre z.B. "Identifier" (Variable), oder "Literal" (irgendeine Zahl, ein Buchstabe in ""), oder "Operator" (+ - * / = <> <= < >= > AND OR NOT) wobei man hier besser alle Operatoren einzelnd benennen sollte, da sie
unterschiedliche Gewichtung haben, schliesslich noch die Klammern "(" und ")", denn die braucht man ja, um den Vorrang der Operatoren zu ändern.
Dein Tokenizer sollte also eine Funktion "next_token()" haben, der immer das nächste Symbol zurückgibt. Für die Symbole nimmst du am besten einen Aufzählungstyp. Wenn er sagt, dass es eine Variable ist, musst er natürlich auf Nachfrage auch sagen, welche denn überhaupt genannt wurde (ähnlich bei einem Literal).

Damit haben wir schon ein gutes Rüstzeug. Ich schreibe jetzt mal Pseudocode für den Fall, dass du den Ausdruck sofort auswerten willst und keinen Baum im Speicher aufbaust. Es gibt für jede Stufe der Auswertung eine Funktion, die mit TRUE zurückgibt, dass alles glattgegangen ist. Per Referenz wird eine Struktur übergeben, die das Ergebnis der Auswertung enthält (eine Struktur deshalb, weil es ja verschiedene Typen etc. geben kann). Nach der Rückkehr einer Function steht der Tokenizer auf dem nächsten Token.

Code:

 function Parse_Expression (VAR ergebnis): Boolean;
 begin
  if parse_SimpleExpression(ergebnisLeft)
   then if akt_token <relationaler Operator>
         then next_token()
              if parse_SimpleExpression (ergebnisRight)
               then return verarbeiteOperator(ergebnisLeft, ergebnisRight, operator, ergebnis);
               else return false
         else return false
   else return false;
 end;

 function Parse_SimpleExpression (VAR ergebnis): Boolean;
 begin
  if parse_Term(ergebnisLeft)
   then if akt_token <additiver Operator>
         then next_token()
              if parse_Term (ergebnisRight)
               then return verarbeiteOperator(ergebnisLeft, ergebnisRight, operator, ergebnis);
               else return false
         else return false
   else return false;
 end;

 function Parse_Term (VAR ergebnis): Boolean;
 begin
  if parse_Faktor(ergebnisLeft)
   then if akt_token <multiplikativer Operator>
         then next_token()
              if parse_Faktor (ergebnisRight)
               then return verarbeiteOperator(ergebnisLeft, ergebnisRight, operator, ergebnis);
               else return false
         else return false
   else return false;
 end;

 function Parse_faktor (VAR ergebnis): Boolean;
 begin
  if akt_token <Literal>
   then ergebnis := <Inhalt des Literals>
   else if akt_Token <Identifier>
         then ergebnis := <Inhalt der Variable>
         else if akt_token <Klammer auf>
               then next_token()
                    if parse_expression(ergebnis)
                     then if akt_token <Klammer zu>
                           then <nix>
                           else return false
                     else return false
               else return false;
  netxt_token();
  return true;
 end;

 function verarbeiteOperator(argument1, argument2, operator, VAR ergebnis):Boolean;
 begin
   <passt der Operator zum Typ der Argumente?>
   <passen die Typen der Argumente zueinander?>
   case Operator of
    "+" : ergebnis := argument1 + argument2
   ...
   end;
 end;

Das ist das Gerüst; wie man verschiedenen Typen umgeht, überlasse ich jetzt mal deiner Phantasie, aber ein RECORD könnte dabei eine Rolle spielen...
Der Trick an der Sache ist der, den Tokenizer zum richtigen Zeitpunkt weitergehen zu lassen. Wenn du es codest und im debugger durchgehst, merkst du aber schnell, wie es läuft.
Durch die Aufspaltung in die einzelnen Funktionen werden alle Informationen in den lokalen Variablen zwischengespeichert, bis sie verwendet werden, wie z.B. der jeweilige Operator.

In deinem Hauptprogramm rufst du dann nur noch auf: if parse_expression(ergebnis) then ... im ergebnis steht dann (hofffentlich) ein boolsches Feld mit dem Ergebnis. Steht im Input allerdings nur ein Teilausdruck wie "a+1", dann kommt natürlich etwas anderes heraus. Also: Abfragen, abfragen, abfragen. In der realen Welt besteht mindestens die Hälfte des
Codes aus Abfragen, ob alles korrekt läuft...

Ich habe es so formuliert, dass ein fehlerhafter Input die gesamte Verarbeitung beendet. Du solltest dich nie darauf verlassen, dass der Input syntaktisch korrekt ist!

Na dann mal viel Spaß!

Peter