Programmieren mit Lex/Yacc

[AI Z. (matrix1)]

Hallo,
ich habe einen Compiler zur syntaktischen Analyse geschrieben, hab 
vieles hinbekommen, nun habe ich ein neues Problem am Hals komm nur 
nicht dahinter wie ich anfangen soll.Danke.

Bei einer normalen If-Anwisung, gibt mr meine Ausagbe alles aus was es 
tun soll, nur jetzt ist es einbißchen anders. Erst wenn ich einen JMP 
befehl eingegeben hatte hatte er es erkannt und hat zugleich den Label 
angegeben. Nun aber wenn z.B ich eine If anweisung angebe, und die 
Anweisung des If's zutrifft, tut er ja den Befehl aus, ansonsten (else) 
soll er eine andere Anweisung ausführen, aber bei der Ausgabe soll 
angegeben werden, if wurde benutzt, welcher operator Konstante 
Bezeichner, tut ja mein compiler auch, nun soll er die erste Anweisung 
ausgeben (vor dem else) und dann soll er direkt ausgeben, JMP zum ende 
der If Schleife, da die Anweisung erfüllt wurde und die Anweisung nach 
der else nicht nötig ist, dann erst soll er die zweite Anweisung 
ausgeben. Ich verdeutliche dies mal anhand eines Beispiels mit 
zugewiesenen Adressen:

Eingabe Adr Ausgabe

Code:

if(x==0)        10   if(x==0)
Wait 5          20   WAIT 5
else            30   JMP 50
Wait 1          40   WAIT 1
end             50   END

so ungefähr hoffe du verstehst was ich meine.

Danke Nochmals.

MfG
Ali

[Karl H. (kbuchegg)]

Du vermischt schon wieder verschiedene Dinge.
Das eine ist die Erzeugung des Syntaxbaumes.
Die andere ist die Generierung der Anweisungen.

Im Syntaxbaum besteht ein if einfach nur aus 3 Kindern

    child[0]      Bedingung
    child[1]      Statement, welches den then Teil bildet
    child[2]      Statement, welches den else Teil bildet

Das ist alles.
Mehr wird beim Baumaufbau nicht gemacht. Und dafür wird lex/yacc 
benutzt. Sobald der Baum steht, ist Lex/Yacc aus dem Rennen. Der Rest 
sind dann 'nur noch' Operationen, die auf dem Baum gemacht werden.

Der Rest erfolgt dann, wenn der Baum in eine lineare Sequenz von 
Anweisungen für die Zielmaschine umgesetzt wird. Die wird so ähnlich 
aussehen, wie deine PrintTree. Allerdings komplexer, weil sie sich genau 
um zb solche Dinge zu kümmern hat.

[AI Z. (matrix1)]

Hallo,
Danke für deine Antwort,
ich hatte es mir so überlegt, dass bei meiner Eingabe, dementsprechend 
die Ausgabe gegeben werden soll:

Eingabe:

if(x==0)
y=0;
else
y=1;
end;

Ausgabe:

If
  Id: x
  const: 0
    Assign to: y
      const: 0
       JMP  (soll den Sprung zum Ende des if's anzeigen)
   Assign to: y
      const: 1


also meinst du dies ist nicht so möglich wie ich es möchte, das heißt 
ohne den JMP Befehl einzugeben würde die If Anweisung nicht den JMP 
ausgeben.
Mein obiges Beispiel verdeutlicht mein Anliegen, mein problem ist, der 
JMP befehl soll erscheinen ohne ihn vorher eingeben zu müssen, da wenn 
in der If Schleife die erste Anweisung erfüllt ist soll JMP vor dem 
ELSE, soll er natürlich dann zum Ende der Schleife springen, dann wird 
die Zweite Anweisung ausgegeben.Danke.

Gruß
Ali

[Karl H. (kbuchegg)]

Ali imran Zafar schrieb:

> also meinst du dies ist nicht so möglich wie ich es möchte, das heißt
> ohne den JMP Befehl einzugeben würde die If Anweisung nicht den JMP
> ausgeben.

Nein.
Warum auch.
Den JMP musst DU während des Ausgebens generieren.

Dazu musst du deine PrintTree Funktion ein wenig anders generieren.
Der Rundumschlag am Schluss, bei dem sich alle Kinder ausgeben, muss 
weg, und dafür spezisch bei jedem Statemenet gemacht werden

Dazu brauchst du dann noch vom Compiler generierte Label.
Der Teil ist aber leicht, weil dein Benutzer Beschränkungen hat, welche 
Labelnamen er wählen darf. Aus diesen Beschränkungen ergibt sich dann zb 
ein Schema, welches der Compiler für sich benutzen kann um zwischendurch 
Labels zu erzeugen, wenn er sie braucht.

[Karl H. (kbuchegg)]

Warum sieht dein IF so kompliziert aus?
Beim IF gibt es nur 2 Möglichkeiten:
Entweder es kommt ein else, oder es kommt keines

if_stmt: IF exp stmt_seq END 
      { $$ = newStmtNode(IfK);
        $$->child[0] = $2;
        $$->child[1] = $3;
      }

    | IF exp stmt_seq ELSE stmt_seq END 
      { $$ = newStmtNode(IfK);
        $$->child[0] = $2;
        $$->child[1] = $3;
        $$->child[2] = $5;
      }

[AI Z. (matrix1)]

Karl heinz Buchegger schrieb:

> Den JMP musst DU während des Ausgebens generieren.

Das versteh ich nicht, wie soll ich denn den JMP Befehl während des 
ausgebens generieren.

Kannst du mir das näher erläutern.Danke.

Gruß

[Karl H. (kbuchegg)]

int  nextLabelNr = 0;
char nextLabel[20];

void generateLabel( char * LabelPrefix )
{
  sprintf( "!_%s_%04d", LabelPrefix, nextLabelNr );
  nextLabelNr++;
}

void printTree(TreeNode * tree )
{
  static int indentno=0;
  int i;
  char compilerLabel[20];

  indentno += 2;  

  while (tree != NULL){

    for(i=0;i<indentno;i++)
      printf(" ");

    if (tree->nodekind==StmtK){

      switch (tree->kind.stmt){
        case IfK:
          printf("If\n");
          printTree( child[0] );                    // Bedingung
          printTree( child[1] );                    // Then Teil

          if( child[2] != NULL ) {                  // wenn es einen else Teil gibt
            generateLabel( "IF" );                  // einen Labelnamen generieren lassen ...
            strcpy( compilerLabel, nextLabel );     // ... und merken
            printf( "JMP  %s\n", compilerLabel );   // dann mit einem JMP aus dem then Teil
                                                    // den else Teil überspringen
            printTree( child[2] );                  // der else Teil soll seinen Code anhängen
            printf( "Label: %s\n", compilerLabel ); // und das Sprungziel für den JMP in Form
                                                    // eines Labels einfügen
          }
          break;


        case RepeatK:
          printf("Repeat\n");
          break;

...


//
// Das geht so nicht mehr
// Die Kinder müssen bei den einzelnen Anweisungen gedruckt werden
// wenn sie tatsächlich gebraucht werden
/*
    for(i=0;i<4;i++){
      if ((tree->child[1] != NULL) 
     && (tree->child[2] != NULL) 
     && (tree->child[i] != NULL))
        printf("\n"); 
      printTree(tree->child[i]);
    }
*/

    tree = tree->sibling;
  }
  indentno -= 2;;
}

Dein Rundumschlag 'Alle Kinder auf Biegen und Brechen ausgeben' 
funktioniert nicht mehr. Ab jetzt musst du die bei jeder Anweisung nur 
die Kinder ausgeben, die auch tatsächlich vorhanden sind. Dies deshalb, 
weil sich während der Ausgabe der Kinder auch noch andere Anweisungen 
(wie zb der JMP bei einem IF) ergeben, die zwischendrinn kommen müssen.

[Karl H. (kbuchegg)]

Das ist jetzt eine Möglichkeit, wie man das lösen kann.

Eine andere Möglichkeit (und nicht die schlechteste), wäre es, eine 
Funktion zu schreiben, die den Baum abklappert, gezielt nach IF mit 
einem ELSE Teil sucht und die entsprechenden JMP und Label (mit 
generierten Labelnamen) einfügt.

In diesem speziellen Fall, hätte man auch die entsprechende 
Baumergänzung direkt im während der yacc Phase machen können. Dazu würde 
man wieder zusätzliche Spezialfunktionen benötigen, dia an eine 
Statementsequence, deren TreeNode Pointer man hat, hinten einen JMP mit 
einem Label drann hängt, bzw. eine Funktion, die an eine 
Statementsequence ein Label drann hängt.

Möglichkeiten gibt es mehrere. Aber alle setzen voraus, dass du mit 
Bäumen erst mal nicht auf Kriegsfuss stehst. Und daran wirds wohl schon 
wieder scheitern.

[AI Z. (matrix1)]

hallo,
es klappt, man du bist einfach genial, suuuuuperrrr gut das es diese 
Foren gibt habe vieeeel hier gelernt, Ich bedank mich sehr bei dir, du 
bist voll cool.Danke nochmals.

MfG
Ali

[Karl H. (kbuchegg)]

Ali imran Zafar schrieb:
> hallo,
> es klappt, man du bist einfach genial

Leider nicht.

Das ist Standardverfahren für jeden, der Compilerbau gelernt hat. Und 
auch wenn dir das wie Magie vorkommt:
* Die gepostete Lösung in printTree ist nicht besonders gut
* Die Lösung ist ziemlich naheliegend.

Spätestens wenn es darum geht, die symbolischen Labelnamen durch 
Adressen zu ersetzen, wirst du merken, dass die Lösung im printTree 
sogar extrem schlecht ist.

Hätte ich blos 3 Minuten länger über das Problem nachgedacht, und diese 
printTree Modifiktion nie vorgeschlagen. Soviel aufwändiger wäre die 
direkte Baummanipulation auch nicht gewesen.

[AI Z. (matrix1)]

Hallo,

OK, das ist mein nächster Schritt die LAbelnamen durch Adressen ersetzen 
na gut, muss mir dann genauer angucken.Aber danke nochmals.

Gruß

[Karl H. (kbuchegg)]

Machs nochmal rückgängig.
Die printTree Modifikation ist Murx. Die kannst du so nicht lassen, da 
mach ich mich strafbar.

Machs so

void appendStatement( TreeNode* sequence, TreeNode* statement )
{
  //
  // das letzte Statement in der Sequenz suchen
  //
  while( sequence->sibling != NULL )
    sequence = sequence->sibling;

  //
  // und das neue Statement drannhängen
  //
  sequence->sibling = statement;
}

if_stmt: IF exp stmt_seq END 
      { $$ = newStmtNode(IfK);
        $$->child[0] = $2;
        $$->child[1] = $3;
      }

    | IF exp stmt_seq ELSE stmt_seq END 
      { TreeNode* pJmp;
        TreeNode* pLabel;

        $$ = newStmtNode(IfK);
        $$->child[0] = $2;
        $$->child[1] = $3;
        $$->child[2] = $5;

        if( $$->child[2] != NULL ) {
          generateLabel();                     // einen Labelnamen erzeugen lassen

          pJmp = newStmtNode(JmpK);            // einen JMP erzeugen zu diesem Label
          pJmp->attr.name = strdup( nextLabel );

          pLabel = newStmtNode(LabelK);        // einen Labelknoten mit dem Namen erzeugen
          pLabel->attr.name = strdup( nextLabel );

          appendStatement( $$->child[1], pJmp );      // der JMP kommt hinten an den then Teil
          appendStatement( $$->child[2], pLabel );    // und das Label kommt hinten an den else Teil
        }
      }

Auf die Art werden der JMP und das Label bereits richtig in den Baum 
eingebaut, so dass in printTree nichts mehr hinzugefügt werden muss.

[AI Z. (matrix1)]

Hallo,
wo soll ich deinen Code einfügen, deine vorige version habe ich 
rückgängig gemacht, aber versteh nicht wo ich den neuen Code hinmachen 
soll.
Soll ich etwa das void statt dem void den ich habe ersetzen und 
anschließend das while ebenfalls oder wie Danke.

Mfg
Ali