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:
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.
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:
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 |