Zur Themenübersicht

2. Der Rekursiv Parser

1. UML-Diagramm

2. TRekursivParser

Dem RekursivParser wird die komplette Tokenliste übergeben. Er gibt zurück, ob die Tokenliste syntaktisch korrekt ist. Im Gegensatz zum KellerParser ist er nicht in der Lage anzuzeigen, welcher Token fehlerhaft ist und welche Art von Fehler vorliegt, da er ja nur überprüft, ob der Ausdruck mit der gegebenen Grammatik überhaupt erzeugt werden kann..

2.1. Die wichtigsten Attribute und Methoden der Klasse TRekursivParser

Mit dem Konstruktor "init" und dem Desktruktor "gibFrei" kann wie üblich eine Instanz der Klasse erzeugt bzw. vernichtet werden.

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 zunächst in einen Stringarray umgewandelt, in dem der Ausdruckstyp nicht mehr enthalten ist, da für den Rekursivparser nur noch der konkrete Ausdruck relevant ist. Danach wird der Stringarray zusammen mit dem Startsymbol der Grammatik an die rekursive Methode "Pruefe" übergeben. Der Rückgabewert der Methode "Pruefe" wird dann auch von der Methode "parseTokenliste" zurückgegeben.

function TRekursivParser.AnzahlDerNichtterminalSymbole (pStringArray: TStringArray) : Integer;
Diese Methode gibt die Anzahl der Nichtterminalsymbole in dem als Parameter übergebenen StringArray zurück.

function TRekursivParser.gibPositionVomErstenNTS (pStringArray: TStringArray) : Integer;
Diese Methode gibt die Position des ersten Nichtterminalsymbols in dem als Parameter übergebenen StringArray zurück.

function TRekursivParser.IstNichtTerminalSymbol (pSymbol : String) : Boolean;
Diese Methode gibt an, ob der als Parameter übergebenen String ein Nichtterminalsymbol ist.

function TRekursivParser.StringArraysGleich(pArray1 : TStringArray; pArray2 : TStringArray) : Boolean;
Diese Methode überprüft, ob die als Parameter übergebenen StringArrays komplett übereinstimmen.

function TRekursivParser.StringArraysBisPositionGleich(pArray1 : TStringArray; pArray2 : TStringArray; pPosition : Integer) : Boolean;
Diese Methode überprüft, ob die als Parameter übergebenen StringArrays bis zum Index "pPosition - 1" übereinstimmen.

function TRekursivParser.gibRegelAnzahlFuerErstesNTS (pStringArray: TStringArray) : Integer;
Diese Methode gibt die Anzahl der Ersetzungsregeln für das erste Nichtterminalsymbol in dem als Parameter übergebenen StringArray zurück.

function TRekursivParser.ersetzeErstesNTSNachRegel (pStringArray: TStringArray; pRegelIndex: Integer) : TStringArray;
Diese Methode ersetzt das erste Nichtterminalsymbol im als Parameter übergebenen StringArrays nach der Regel Nummer "pRegelIndex" und gibt den neu entstandenen StringArray zurück.

function TRekursivParser.Pruefe (pZuPruefen, pBisherErzeugt: TStringArray) : Boolean;
Die Methode prüft, ob der zu prüfende Ausdruck aus dem bisher erzeugten Ausdurck durch Ersetzung aller Nichtterminalsymbole entstehen kann. Wenn dies der Fall ist, gibt sie true zurück, andernfalls false. Dazu ersetzt sie zunächst das erste Nichtterminalsymbol nach allen möglichen Regeln und ruft sich dann mit den neu erzeugten Ausdrücken selbst auf.

2.2. Entscheidende und Interessante Codestellen

Wenn der bisher erzeugte Ausdruck mit dem zu prüfendem überinstimmt, dann gehört er zur Sprache und die Rekursion kann enden.

Wenn keine Nichtterminalsymbole mehr im bisher erzeugten Ausdruck vorhanden sind, oder wenn sich die beiden Ausdrücke bis zum ersten Nichtterminalsymbol unterscheiden, dann kann aus dem bisher erzeugten nicht mehr der zu prüfende Ausdruck hervorgehen. Daher kann die Rekursion hier enden.

Wenn beides nicht der Fall ist, dann ist eine Übereinstimmung noch möglich.

Daher wird das erste Nichtterminalsymbol nun nach allen möglichen Regeln ersetzt und die dabei erzeugten neuen Ausdrücke rekursiv an die Methode "Pruefe" übergeben. Wenn aus einem der neuen Ausdrücke der zu prüfende hervorgegangen ist, müssen die anderen Regeln nicht mehr überprüft werden.

Wenn durch eine der Ersetzungen der zu prüfende Ausdruck hervorgegangen ist, dann ist der Rückgabewert der Methode true, andernfalls false.

function TRekursivParser.Pruefe (pZuPruefen, pBisherErzeugt: TStringArray) : Boolean;
var
  RegelAnzahl, aktuelleRegelNummer : Integer;
  tmpNeuerBaum : TBaum;
  letztesErgebniss : Boolean;
begin
  if StringArraysGleich(pBisherErzeugt, pZuPruefen)
    then result := true;
  else
  begin
    if gibPositionVomErstenNTS(pBisherErzeugt) = -1
      then result := false
    else
    begin
      if not StringArraysBisPositionGleich(pBisherErzeugt, 
					   pZuPruefen, 
                                           gibPositionVomErstenNTS(pBisherErzeugt))
        then result := false
      else
      begin
        //Übereinstimmung noch nicht vorhanden, aber noch möglich
        aktuelleRegelNummer := 1;
        letztesErgebniss := false;

        RegelAnzahl := gibRegelAnzahlFuerErstesNTS(pBisherErzeugt);
        while (aktuelleRegelNummer <= RegelAnzahl) and (not letztesErgebniss) do
        begin
          letztesErgebniss := Pruefe(pZuPruefen,ersetzeErstesNTSNachRegel(pBisherErzeugt,
                                     aktuelleRegelNummer),
                                     pInfoNachrichtenAnzeigen);
          aktuelleRegelNummer := aktuelleRegelNummer + 1;
        end;
        result := letztesErgebniss;
      end;
    end;
  end;
end;

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite

Hannah-Arendt-Gymnasium, Lengerich