Zur Themenübersicht

Programmtechnische Umsetzung des rekursiven Abstiegs bei vorausschauender Grammatik

Die Suche im Syntaxbaum lässt sich wesentlich vereinfachen, wenn die anzuwendende Regel durch das jeweils betrachtete Zeichen (oder eine feste Zahl von Folgezeichen) des zu erkennenden Ausdrucks eindeutig festgelegt ist.
In diesem Fallen lassen sich nämlich Sackgassen im Syntaxbaum vermeiden.

Wir betrachten dies am Beispiel der Grammatik G2 für wohldefinierte Klammerterme:

S ::= ( S ) S Regel 1

S ::= - (nichts) Regel 2

Realisierung des Abstiegs im Syntaxbaum mit Grammatik 2 ohne Baumknoten
Prozedurkopf bleibt gleich Die Regeln sind als Unter- prozeduren realisiert. Regel 1 der Grammatik G2 Regel 2 der Grammatik G2 (ersetzen durch nichts) Hier sieht man, dass die anzu- wendende Regel von Symbol des zu erkennenden Textes an der entsprechenden Stelle abhängt. Backtracking entfällt.	procedure TForm1.Baumsuche(Eingabe : String; erzeugter_text : String; stelle : Integer; var ok : Boolean); var probetext :String; s_stelle : Integer; procedure regel1(var stimmt:Boolean); begin probetext := erzeugter_text; ersetze('S','(S)S',probetext); baumsuche(Eingabe,probeknoten,probetext,s_stelle+1,stimmt) end; procedure regel2(var stimmt:Boolean); begin probetext := erzeugter_text; ersetze('S','',probetext); baumsuche(Eingabe,probeknoten,probetext,stelle,stimmt) end;(* of Proc regel 3 ) begin ( of Proc baumsuche *) if erzeugter_text = Eingabe then ok := true else begin ok := false; if (stelle <= length(Eingabe)) then begin s_stelle := pos('S',erzeugter_text); if s_stelle > 0 then begin if Eingabe[s_stelle]='(' then regel1(ok) else regel2(ok); end end end ; end;

Realisierung des Abstiegs im Syntaxbaum mit Grammatik 2 ohne Baumknoten

Prozedurkopf bleibt gleich






Die Regeln sind als Unter-
  prozeduren realisiert.

Regel 1 der Grammatik G2






Regel 2 der Grammatik G2
  (ersetzen durch nichts)











Hier sieht man, dass die anzu-
  wendende Regel von Symbol
  des zu erkennenden Textes
  an der entsprechenden Stelle
  abhängt.
Backtracking entfällt.

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

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

   procedure regel2(var stimmt:Boolean);
   begin
      probetext := erzeugter_text;
      ersetze('S','',probetext);
      baumsuche(Eingabe,probeknoten,probetext,stelle,stimmt)
   end;(* of Proc regel 3 *)

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

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

Hannah-Arendt-Gymnasium, Lengerich