Zur Themenübersicht

4. Parser und ParserAutomat

1. UML-Diagramm

2. TParser

Zum Parsen des Programmtextes wird die Tokenliste an den Parser übergeben, dieser gibt die einzelnen Token stückchenweise an den ParserAutomaten weiter.
Dieser wechselt je nach Token seinen Zustand. Ist eine Tokenliste syntaktisch korrekt, befindet sich der ParserAutomat am Ende in einem akzeptierenden Zustand. Tritt ein Fehler auf, wird der fehlerhafte Token und die Fehlermeldung des ParserAutomaten angezeigt.

2.1. Die wichtigsten Attribute und Methoden der Klasse TParser

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

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 des Syntaxdiagramms erfüllt und gibt entsprechend True oder False zurück.
Wenn ein Fehler aufgetreten ist, zeigt sie außerdem die letzte Ausgabe (also die Fehlermeldung) des ParserAutomaten an.

2.2. Entscheidende und interessante Codestellen

Solange wie noch nicht das Ende der
Tokenliste erreicht ist und noch kein Fehler
aufgetreten ist, wird ein Token nach dem anderen
an den ParserAutomaten eingegeben. Dabei wird
seine Ausgabe gespeichert.

Wenn ein Fehler auftrat, wird die letzte Ausgabe
des ParserAutomaten als Fehlermeldung
ausgegeben.

Die Tokenliste ist fehlerfrei, wenn der Automat
sich am Ende in einem akzeptierenden Zustand
befindet.

function TParser.parseTokenliste (pTokenListe: TTokenListe) : Boolean;
var
  position : Integer;
  letzteAusgabe : String;
begin

  position := 0;
  hatParserAutomat.setzeZurueck;

  while (position < length(pTokenListe)) and (not hatParserAutomat.istInFehlerZustand) do
  begin
    letzteAusgabe := hatParserAutomat.verarbeiteEingabe(pTokenListe[position]);
    position := position + 1;
  end;

  if hatParserAutomat.istInFehlerZustand
    then MessageDlg('Fehler beim Parsen des Tokens Nr: ' + IntToStr(position) + 
                    ' (' + pTokenListe[position - 1][2] + ') Fehlermeldung: ' + #13#10 + 
                    letzteAusgabe, mtError,[mbOk], 0);


  result := hatParserAutomat.istInAkzeptiertemZustand;
end;

3. TParserAutomat

Beim Parser Automaten handelt es sich um einen erkennden endlichen deterministschen Automaten, der zusätzlich noch eine Ausgabefunktion besitzt.
Weist die Tokenliste syntaktische Fehler auf, wird die Fehlermeldung von der Ausgabefunktion zurückgegeben.

3.1. Typendefinitionen

Um die verschiedenen Zustände zu verwalten wird folgender Typ definiert.

type
  TZustand = (zStart, zNwenn, zNwennNot, zNwennAnfrage, zNDann, 
	      zNDannKA, zNDannKZ, zNSonst, zNsonstKZ, zNSonstKA, 
              zNSolange, zNSolangeNot, zNSolangeAnfrage, zNTue, 
              zNTueKA, zNTueKZ, zFehler);

3.2. G-Flep Zustandsgraph

Die Umsetzung des Syntaxdiagramms ergibt den folgenden Zustandsgraphen für unseren Automaten.
Hier ist jedoch nur die Übergangsfunktion dargestellt. Die Ausgabefunktion ist aus Übersichtsgründen nicht im Zustandsgraph enthalten.
An den Übergängen zum Fehlerzustand wurden die entsprechenden Eingaben weggelassen. Wie üblich führen von einem Zustand alle nicht anderweitig zugeordneten Eingaben zum Fehlerzustand.

Anders als man erwarten würde, sind neben dem Startzustand auch die Zustände "NDann}", "NSonst}" und "NTue}" akzeptierend.
Dies liegt daran, dass eine Tokenliste ja auch unmittelbar nach der geschlossenen Klammer eines Dann-, Sonst- oder Tue-Abschnitts enden kann. Es ist jedoch insbesondere nach dem Dann Teil nicht ausreichend, mit der geschlossenen Klammer wieder in den Startzustand zu wechseln, da ja anders als im Startzustand sowohl ein Sonst wie auch nichts bzw. ein Befehl o. ä., kommen kann.
Damit alles einheitlich bleibt haben wie die gleiche Vorgehensweise in allen drei Fällen angewendet.

3.3. Die wichtigsten Attribute und Methoden der Klasse TScannerAutomat

Mit dem Konstruktor "init" und dem Desktruktors "gibFrei" kann wie üblich eine Instanz der Klasse erzeugt bzw. vernichtet werden.
Die Attribute "aktuellerZustand : TZustand", "startZustand : TZustand" und "fehlerZustand : TZustand;" speichern den Aktuellen-, den Start- und den Fehlerzustand.
Mit "akzeptierteZustaende : Set of TZustand;" wird die Menge der akzeptierenden Zustände gemerkt.

function TParserAutomat.verarbeiteEingabe (pEingabe: TToken) : String;
Diese Methode wird vom Parser aufgerufen. Sie ermittelt zunächst mithilfe der Ausgabefunktion eine eventuelle Fehlermeldung und schreibt diese in das result.
Danach wechselt sie anhand der Kombination aus Token und dem aktuellen Zustand mit der Übergangsfunktion den aktuellen Zustand.

function TParserAutomat.UebergangsFunktionF (pAktuellerZustand: TZustand; pEingabe: TToken) : TZustand;
Hier wird aus dem aktuellen Zustand und einem Token der Folgezustand ermittelt und zurückgegeben.

function TParserAutomat.AusgabeFunktionG (pAktuellerZustand: TZustand; pEingabe: TToken) : String;
Hier wird aus dem aktuellen Zustand und einem eingegebenen Token eine eventuelle Fehlermeldung ermittelt und diese zurückgegeben.

function TParserAutomat.istInFehlerZustand : Boolean;
Diese Anfrage gibt an, ob sich der Automat im Fehlerzustand befindet.

function TParserAutomat.istInAkzeptiertemZustand : Boolean;
Diese Anfrage gibt an, ob der Automat sich in einem akzeptierenden Zustand befindet.

procedure TParserAutomat.setzeZurueck;
Die Methode setzt den aktuellenZustand auf den Startzustand.

3.4. Entscheidende und Interessante Codestellen

Da die Ausgabe- und Übergangsfunktion sehr lang sind, wird hier aus Übersichtgründen darauf verzichtet sie komplett zu zeigen.

Wenn der Kombination aus Eingabe und aktuellem Zustand
kein Folgezustand zugeordnet werden kann, ist der Folgezustand der Fehlerzustand.

Andernfalls wird je nach aktuellem Zustand und eingegebenen Token ein Folgezustand entsprechend dem oben gezeigten
Zustandsgraphen zurückgegeben.

function TParserAutomat.UebergangsFunktionF (pAktuellerZustand: TZustand; pEingabe: TToken) : TZustand;
begin
  result := FehlerZustand;

  case pAktuellerZustand of

    zStart : begin
      if pEingabe[1] = 'befehl'
        then result := zStart
      else if pEingabe[1] = 'anfrage'
        then result := zStart
      else if pEingabe[2] = 'wenn'
        then result := zNwenn
      else if pEingabe[2] = 'solangewie'
        then result := zNSolange

    end; //of pAktuellerZustand : zStart

    zNwenn : begin
      if pEingabe[2] = 'not'
        then result := zNwennNot
      else if pEingabe[1] = 'anfrage'
        then result := zNwennAnfrage

    end; //of pAktuellerZustand : zNwenn

    zNwennNot : begin
      if pEingabe[1] = 'anfrage'
        then result := zNwennAnfrage


[...]


    zNTueKZ : begin
      if pEingabe[1] = 'befehl'
        then result := zStart
      else if pEingabe[1] = 'anfrage'
        then result := zStart
      else if pEingabe[2] = 'wenn'
        then result := zNwenn
      else if pEingabe[2] = 'solangewie'
        then result := zNSolange

    end; //of pAktuellerZustand : zNTueKZ


  end;
end;

Wenn der Kombination aus Eingabe und aktuellem Zustand
keine Fehlermeldung zugeordnet werden kann, ist die
zurückgegebene Meldung leer.

Andernfalls wird je nach aktuellem Zustand und eingegebenen Token die entsprechende Fehlermeldung zurückgegeben.


function TParserAutomat.AusgabeFunktionG (pAktuellerZustand: TZustand; pEingabe: TToken) : String;
begin
  result := '';
  case pAktuellerZustand of

    zStart : begin
      if (pEingabe[2] = 'dann') or
         (pEingabe[2] = 'sonst') or
         (pEingabe[2] = 'tue') or
         (pEingabe[2] = #123) or
         (pEingabe[2] = #125) or
         (pEingabe[2] = 'not')
        then result := pEingabe[2] + ' ist in diesem Kontext erlaubt.'

    end; //of pAktuellerZustand : zStart

    zNwenn : begin
      if (pEingabe[1] = 'befehl') or
         (pEingabe[2] = 'wenn') or
         (pEingabe[2] = 'dann') or
         (pEingabe[2] = 'sonst') or
         (pEingabe[2] = 'solangewie') or
         (pEingabe[2] = 'tue') or
         (pEingabe[2] = #123) or
         (pEingabe[2] = #125)
        then result := 'Nur "not" oder eine Anfrage sind nach "Wenn" erlaubt.'

    end; //of pAktuellerZustand : zNwenn


[...]


    zNTueKZ : begin
      if (pEingabe[2] = 'dann') or
         (pEingabe[2] = 'sonst') or
         (pEingabe[2] = 'tue') or
         (pEingabe[2] = #123) or
         (pEingabe[2] = #125) or
         (pEingabe[2] = 'not')
        then result := pEingabe[2] + ' ist in diesem Kontext erlaubt.'


    end; //of pAktuellerZustand : zNTueKZ


  end;
end;

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

Hannah-Arendt-Gymnasium, Lengerich