Zur Themenübersicht     

Programmtechnische Umsetzung des rekursiven Abstiegs

Wir betrachten eine Realisierung, bei welcher der Weg durch den Syntaxbaum in einem ternären Baum (Knoten haben den Outdegree 3) gespeichert wird. Die Baumknoten werden folgendermaßen deklariert: 
Syntaxknoten 
TSyntaxknoten = class (TObject)
     public
        RegelNummer : integer;
        r1,r2,r3 : TSyntaxknoten;
        constructor Create;
  end;

Die Kanten des Baumes werden durch die Zeiger r1, r2, und r3 realisiert. Die Regelnummer gibt an, welche Regel als letzte angewendet wurde. Ein neu erzeugter Knoten besitzt die Regelnummer 0. 

Kern der Realisierung ist die Prozedur baumsuche mit den Unterprozeduren für die Regeln.

 

Erklärung,                                             Code

 
zu erkennender Ausdruck
der aktuelle Knoten im Syntaxbaum
bisher erzeugter Ausdruck
bis zu der untersucht wurde
gibt an, ob Suche erfolgreich









Rekursionsende bei erfolgreicher 
  Suche


Rekursionsende falls Eingabe 
  angearbeitet oder erzeugter
  Ausdruck zu lang.
Rekursionsende falls kein Nicht-
  terminalsymbol mehr da.

Backtracking: Regeln werden nach-
  einander ausprobiert.

procedure TForm1.Baumsuche(Eingabe : String;     
                           knoten:TSyntaxknoten; 
                           erzeugter_text : String;      
                           stelle : Integer; // bis zu der schon geprüft ist
                           var ok   : Boolean); //
var probetext :String;
    probeknoten : TSyntaxknoten;
    s_stelle : Integer;

(* Hier stehen die Unterprozeduren für die drei
   Regeln. Der Übersicht wegen werden sie unten
   getrennt erläutert *)

begin (* of Proc baumsuche *)
   if erzeugter_text = Eingabe then
      ok := true
   else begin
      ok := false;
      if (stelle <= length(Eingabe)) and
         (length(erzeugter_text) < length(Eingabe)) then
      begin
         s_stelle := pos('S',erzeugter_text);
         if s_stelle > 0 then
         begin
            regel1(ok);
            if not ok then  (*Backtrakking*)
               regel2(ok);
            if not ok then
               regel3(ok)
         end
      end
   end ;
end;

Regel 1 wird nur angewendet, wenn
  im zu erkennenden Text an der zu
  ersetzenden Stelle ( ) steht.
neuer Knoten wird ausprobiert
Zeiger r1 des aktuellen Knotens
   zeigt auf den Probeknoten.


baumsuche wird rekursiv hinter 
  dem neu eingefügten ( ) 
  fortgesetzt. 









baumsuche wird rekursiv hinter 
  dem ( vom eingefügten ( S ) 
  fortgesetzt. 






Da S durch S S ersetzt wird, wird
  die Baumsuche rekursiv an der
  gleichen Stelle fortgesetzt.

   procedure regel1(var stimmt : Boolean);
   begin
      if (Eingabe[s_stelle]='(') and
         (Eingabe[s_stelle+1]=')') then begin
         probeknoten := TSyntaxknoten.create;
         knoten.RegelNummer := 1;
         knoten.r1 := probeknoten;
         probetext := erzeugter_text;
         ersetze('S','()',probetext);
         baumsuche(Eingabe,probeknoten,probetext,s_stelle+2,stimmt)
      end
   end;

   procedure regel2(var stimmt:Boolean);
   begin
      if Eingabe[s_stelle]='(' then begin
         probeknoten := TSyntaxknoten.create;
         knoten.RegelNummer := 2;
         knoten.r2 := probeknoten;
         probetext := erzeugter_text;
         ersetze('S','(S)',probetext);
         baumsuche(Eingabe,probeknoten,probetext,s_stelle+1,stimmt)
      end
   end;

   procedure regel3(var stimmt:Boolean);
   begin
      probeknoten := TSyntaxknoten.create;
      knoten.RegelNummer := 3;
      knoten.r3 := probeknoten;
      probetext := erzeugter_text;
      ersetze('S','SS',probetext);
      baumsuche(Eingabe,probeknoten,probetext,stelle,stimmt)
   end;

Bei der obigen Lösung mit Baumknoten lässt sich der Weg durch den Syntaxbaum auch nach Beendigung des Suchvorganges nachvollziehen. Kann man darauf verzichten, durchlaufen die Prozeduren den Syntaxbaum auf dem gleichen Weg, auch wenn sie keine Knoten erzeugen. 
Die Prozeduren lassen sich damit folgendermaßen vereinfachen:

 

                                                         Lösung ohne Baumknoten:

 
Hier fehlt nur der Parameter
   'knoten'. 









Der Prozedurtext entspricht völlig 
  dem obigen Fall


procedure TForm1.Baumsuche(Eingabe : String;     
                           erzeugter_text : String;      
                           stelle : Integer; 
                           var ok   : Boolean); 
var probetext :String;
    s_stelle : Integer;

(* Hier stehen die Unterprozeduren für die drei
   Regeln. Der Übersicht wegen werden sie unten
   getrennt erläutert *)

begin (* of Proc baumsuche *)
   if erzeugter_text = Eingabe then
      ok := true
   else begin
      ok := false;
      if (stelle <= length(Eingabe)) and
         (length(erzeugter_text) < length(Eingabe)) then
      begin
         s_stelle := pos('S',erzeugter_text);
         if s_stelle > 0 then
         begin
            regel1(ok);
            if not ok then  (*Backtracking*)
               regel2(ok);
            if not ok then
               regel3(ok)
         end
      end
   end ;
end;

Die Prozeduren entsprechen
  den obigen Prozeduren.
  Es fehlen nur die Zeilen, in
  denen Knoten erzeugt und
  miteinander verknüpft werden.




   procedure regel1(var stimmt : Boolean);
   begin
      if (Eingabe[s_stelle]='(') and
         (Eingabe[s_stelle+1]=')') then begin
         probetext := erzeugter_text;
         ersetze('S','()',probetext);
         baumsuche(Eingabe,probeknoten,probetext,s_stelle+2,stimmt)
      end
   end;

   procedure regel2(var stimmt:Boolean);
   begin
      if Eingabe[s_stelle]='(' then begin
         probetext := erzeugter_text;
         ersetze('S','(S)',probetext);
         baumsuche(Eingabe,probeknoten,probetext,s_stelle+1,stimmt)
      end
   end;

   procedure regel3(var stimmt:Boolean);
   begin
      probetext := erzeugter_text;
      ersetze('S','SS',probetext);
      baumsuche(Eingabe,probeknoten,probetext,stelle,stimmt)
   end;

 

Zur Themenübersicht  
Zum Seitenanfang 
Zur vorigen Seite         Zur nächsten Seite  

    © 2000 LK 12 If und G. Kubitz  Hannah-Arendt-Gymnasium, Lengerich