Zur Themenübersicht    

3. KellerParser und ParserKellerAutomat

1. UML-Diagramm


2. TKellerParser

Im Gegensatz zum alten Parser wird hier die Tokenliste nicht mehr stückchenweise an den ParserKellerAutomaten übergeben, da der Automat ja auch die nächsten k Eingabezeichen kennen muss.
Die Tokenliste wird vom ParserKellerAutomaten komplett durchgegangen, und es wird die Position des ersten Fehlers zurückgegeben. Weicht diese von -1 ab wird die entsprechende Fehlermeldung vom KellerParser ausgegeben und der fehlerhafte Token auf dem Hauptformular markiert.

2.1. Die wichtigsten Attribute und Methoden der Klasse TKellerParser

Mit dem Konstruktor "init" und dem Desktruktor "gibFrei" kann wie üblich eine Instanz der Klasse erzeugt bzw. vernichtet werden.
Das Attribut "hatParserAutomat" dient als Speicherplatz für die "Hat-Beziehung" zum ParserKellerAutomaten.

function parseTokenliste (pTokenListe: TTokenListe) : Boolean;
Diese Anfrage wird vom Formular aus aufgerufen. Als Parameter wird die vom Scanner erzeugte Tokenliste übergeben.
Sie überprüft, ob die Tokenliste die Regeln der Grammatik erfüllt und gibt entsprechend True oder False zurück. Dazu wird die Tokenliste an den ParserKellerAutomaten weitergegben.
Wenn ein Fehler aufgetreten ist, zeigt sie eine entsprechende Fehlermeldung an und markiert mithilfe des Methodenzeigers "MarkiereListBoxEintrag" den fehlerhaften Token.

MarkiereListBoxEintrag : procedure (FehlerPosition : Integer) of Object;
Dieser Methodenzeiger dient dazu, Einträge in der Listbox, die die Tokenliste auf der grafischen Oberfläche darstellt, zu markieren.

2.2. Entscheidende und interessante Codestellen






Die Tokenliste und eine Speicheradresse zum Ablegen der
entsprechenden Fehlermeldung werden an den Automaten übergeben.
Dessen Rückgabe gibt die Position des ersten Fehlers an.


Die Tokenliste enthält Fehler wenn die Fehlerposition von -1 abweicht.
Dann wird der entsprechende Token markiert und die an der zuvor übergebenen Speicheradresse abgelegte Fehlermeldung ausgegeben.
 
function TKellerParser.parseTokenliste (pTokenListe: TTokenListe) : Boolean;
var
  FehlerPosition : Integer;
  FehlerMeldung : String;
begin


  FehlerPosition := hatParserKellerAutomat.verarbeiteEingabe(pTokenListe, FehlerMeldung);




  if FehlerPosition <> - 1 then
  begin
    MarkiereListBoxEintrag(FehlerPosition);
    MessageDlg('Fehler: ' + #13#10 + FehlerMeldung, mtError,[mbOk], 0);
    result := false;
  end
  else
  begin
    MessageDlg('Der Programmtext ist Syntaktisch korrekt.', mtInformation,[mbOk], 0);
    result := true;
  end;
end;


3. TParserKellerAutomat

Beim Parser Automaten handelt es sich um einen Kellerautomaten, der immer im Startzustand bleibt, da für das Parsen unser Sprache der Keller ausreicht.

3.1. Typendefinitionen

Um die verschiedenen Kellersymbole zu verwalten wird folgender Typ definiert.
type
  TZustand = (zStart, zFehler);

type
  TKellerSymbol = (S, nNOT, nSONST, BEFEHL, ANFRAGE, kNIL,  //Nichtterminale
                  wenn, dann, sonst, solangewie, tue, tNot, KA, KZ, vor, drehe_links,
                  drehe_rechts, nimm, gib, vornefrei, itemda, blicktnach_links, blicktnach_rechts,
                  blicktnach_oben, blicktnach_unten, itemsimrucksack);

3.2. Die wichtigsten Attribute und Methoden der Klasse TParserKellerAutomat

Mit dem Konstruktor "init" und dem Desktruktor "gibFrei" kann wie üblich eine Instanz der Klasse erzeugt bzw. vernichtet werden.
Die Attribute "aktuellerZustand : TZustand" und "startZustand : TZustand" speichern den aktuellen- und den Startzustand. Diese sind jedoch ohne Bedeutung, da der Automat immer im Startzustand bleibt. In "KellerStartSymbol : TKellerSymbol;" wird das Startsymbol der Grammatik gespeichert.

NichtterminaleKellerSymbole : Set of TKellerSymbol;
In diesem Attribut wird die Menge der nichtterminalen Kellersymbole gemerkt.

hatKeller : TKeller;
Hier wird der Keller gespeichert. Es handelt sich dabei um unseren üblichen Stapel, auf den KellerSymbole gelegt werden können.

procedure TParserKellerAutomat.setzeZurueck;
Dieser Auftrag setzt den aktuellen Zustand auf den Startzustand, leert den Keller und legt das Kellerstartsymbol auf den Keller.

function TParserKellerAutomat.UebergangsFunktionF (pAktuellerZustand: TZustand; pEingabe: TTokenListe) : TZustand;
Die Übergangsfunktion ist ohne Bedeutung, da der Automat immer im Startzustand bleibt.

function TParserKellerAutomat.kellerSymbolToString(pKellerSymbol : tKellerSymbol) : String;
Diese Anfrage wandelt ein Kellersymbol in einen string um und gibt diesen zurück. Dies ist vor allem für das Vergleichen eines nichtterminalen Kellersymbols mit dem aktuellen Eingabezeichen von Bedeutung.

function TParserKellerAutomat.LegeErsetzungFuerNTSAufStapel (pNichtterminalesKellerSymbol : TKellersymbol; pEingabe: TTokenListe; pPosition : Integer; var FehlerMeldung : String) : Boolean;
Diese Anfrage ermittelt aus einem nichtterminalen KellerSymbol, dem aktuellen Eingabezeichen (und den nächsten k Eingabezeichen) die entsprechende Ersetzungsregel. Danach legt sie die durch die Ersetzungsregel vorgegebenen Folge von Kellersymbolen auf den Keller. Sie gibt zurück, ob eine passende Regel gefunden wurde. Falls dies nicht der Fall ist, speichert sie in der via "var FehlerMeldung : String" übergebenen Speicheradresse eine entsprechende Fehlermeldung.

function TParserKellerAutomat.verarbeiteEingabe (pEingabe: TTokenListe; var FehlerMeldung : String) : Integer;
Diese Anfrage geht die übergebene Tokenliste durch und prüft, ob sie der Grammatik entspricht. Sie gibt zurück ob und wo dabei ein Fehler auftrat. Falls dies der Fall ist speichert sie in der via "var FehlerMeldung : String" übergebenen Speicheradresse die entsprechende Fehlermeldung.

3.3. Entscheidende und interessante Codestellen






Keller zurücksetzen.





Zunächst das oberste Symbol vom Keller nehmen

Wenn es sich um ein NTS handelt, dann lege
die entsprechende Ersetzung auf den Keller.
Wenn keine Ersetzung gefunden wurde, dann
gehört der zu prüfende Ausdruck nicht zu Sprache.



Wenn es sich um ein Terminalsymbol handelt...

...aber bereits das Ende der Eingabe erreicht ist, dann kann der Ausdruck nicht zur Sprache gehören und die entsprechende Fehlermeldung wird gespeichert.




...und das aktuelle Eingabzeichen nicht mit dem obersten Kellersymbol übereinstimmt, dann kann der Ausdruck nicht zur Sprache gehören und die entsprechende Fehlermeldung wird gespeichert.




...und das aktuelle Eingabzeichen mit dem obersten Kellersymbol übereinstimmt, dann kann das nächste Eingabezeichen verarbeitet werden



Wiederhole bis ein Fehler aufgetreten ist, oder der Keller leer ist.
 
Wenn zwar noch kein Fehler aufgetreten ist, aber bei leerem Keller noch nicht alle Eingabezeichen abgearbeitet sind (also am Ende noch Eingaben stehen, die nicht in die Grammatik passen), dann gehört der Ausdruck ebenfalls nicht zur Sprache.



Falls der Fehler hinter dem letzten Token vorliegt (also z. B. der Keller noch nicht leer ist, aber keine Eingabezeiche mehr vorhanden sind) soll der letzte Token als fehlerhaft markiert werden.
 
function TParserKellerAutomat.verarbeiteEingabe (pEingabe: TTokenListe; var FehlerMeldung : String) : Integer;
var
  AktuelleEingabe : TToken;
  AktuellesKellerSymbol : TKellerSymbol;
  Position, FehlerPosition : Integer;
begin
  setzeZurueck;
  Position := 0;
  FehlerPosition := -1;
  result := -1;

  repeat

    AktuellesKellerSymbol := hatKeller.gibOberstes;


    if AktuellesKellerSymbol in NichtterminaleKellerSymbole then
    begin
      if not LegeErsetzungFuerNTSAufStapel(AktuellesKellerSymbol, pEingabe, position, FehlerMeldung)
        then FehlerPosition := position;
    end


    else
    begin

      if position = length(pEingabe) then
      begin
        FehlerPosition := position;
        FehlerMeldung := '"' + kellerSymbolToString(AktuellesKellerSymbol) +
                         '" erwartet, aber keine weiteren Eingaben vorhanden.';
      end
      else
      begin
        if kellerSymbolToString(AktuellesKellerSymbol) <> pEingabe[position][2] then
        begin
          FehlerPosition := position;
          FehlerMeldung := '"' + kellerSymbolToString(AktuellesKellerSymbol) +
                           '" erwartet, aber "' + pEingabe[position][2] + '" gefunden.';
        end




          else position := position + 1;
      end;
    end;


  until (FehlerPosition <> -1) or (hatKeller.istLeer);




  if (FehlerPosition = -1) and (hatKeller.istLeer) and (position < length(pEingabe))
      then FehlerPosition := Position;



  if FehlerPosition >= length(pEingabe)
    then result := length(pEingabe) - 1
    else result := FehlerPosition;
end;




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

    © 2004 LK 13 If und G. Kubitz  Hannah-Arendt-Gymnasium, Lengerich