Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


21. Syntaxanalyse (Parsing)



Compiler

Einen Compiler kann man sich als ein Programm vorstellen, das aus einer Sprache in eine andere übersetzt. Zum Beispiel übersetzt ein Pascal-Compiler Programme aus der Sprache Pascal in die Maschinensprache eines speziellen Computers. Wir werden eine Möglichkeit aufzeigen, wie sich dies realisieren läßt, indem wir mit unserem Beispiel des Pattern Matching für einen regulären Ausdruck fortfahren; nunmehr wollen wir jedoch die Felder ch, next1 und next2 des Programms match aus dem vorangegangenen Kapitel aus der Sprache regulärer Ausdrücke in eine »Sprache« für Pattern Matching-Automaten übersetzen.

Der Übersetzungsprozeß verläuft im wesentlichen »Eins zu eins«: Für jedes Zeichen im Muster (mit Ausnahme von Klammern) möchten wir einen Zustand für den Pattern Matching-Automaten erzeugen (einen Eintrag für jedes der Felder). Der Trick besteht darin, die in die Felder next1 und next2 einzutragende Information zwischenzuspeichern. Um das zu erreichen, wandeln wir jede der Prozeduren in unserem rekursivabsteigenden Parser in eine Funktion, die einen Pattern Matching-Automaten erzeugt. Jede Funktion fügt nach Bedarf neue Zustände am Ende der Felder ch, next1 und next2 an und gibt den Index des Anfangszustands des erzeugten Automaten zurück (der Endzustand wird immer der letzte Eintrag in den Feldern sein). Zum Beispiel erzeugt die nachfolgend für die Produktion <Ausdruck> angegebene Funktion die alternativen Zustände für den Pattern Matching-Automaten.

    function expression: integer;
      var t1,t2: integer;
      begin
      t1:=term; expression:=t1;
      if p[j]='+' then
        begin
        j:=j+1; state:=state+1;
        t2:=state; expression:=t2; state:=state+1;
        setstate(t2,' ',expression,t1);
        setstate(t2-1,' ',state,state);
        end;
      end;

Diese Funktion verwendet eine Prozedur setstate, welche einfach die Einträge in die Felder ch, next1 und next2, die mit dem ersten Argument indiziert sind, auf die Werte setzt, die im zweiten, dritten bzw. vierten Argument angegeben sind. Der Index state registriert den »aktuellen« Zustand in dem erzeugten Automaten: Jedesmal, wenn ein neuer Zustand erzeugt wird, wird state inkrementiert. Demzufolge liegen die Indizes des Zustands für den Automaten, die einem speziellen Prozeduraufruf entsprechen, zwischen dem Wert von state am Eingang und dem Wert von state am Ausgang. Der Index des Endzustands ist der Wert von state am Ausgang. (In Wirklichkeit »erzeugen« wir den Endzustand nicht durch explizit Inkrementieren von state vor dem Ausgang, da es dadurch einfach wird, den Endzustand mit späteren Anfangszuständen zu »vereinigen«, wie wir weiter unten sehen werden.)

Mit dieser Konvention läßt es sich leicht nachprüfen (Vorsicht mit dem rekursiven Aufruf!), daß das obige Programm die Regel für die Zusammensetzung zweier Automaten mittels der Operation oder, so wie sie im vorangegangenen Kapitel dargestellt wurde, implementiert. Zunächst wird der Automat für den ersten Teil des Ausdrucks erzeugt (rekursiv), dann werden zwei neue Nullzustände hinzugefügt und der zweite Teil des Ausdrucks erzeugt. Der erste Nullzustand (mit dem Index t2-1) ist der Endzustand für den Automaten des ersten Teils des Ausdrucks, welcher zu einem »no-op«-Zustand gemacht wird, um wie verlangt zum Endzustand für den Automaten für den zweiten Teil des Ausdrucks zu springen. Der zweite Nullzustand (mit dem Index t2) ist der Anfangszustand, so daß sein Index der Rückgabewert für Ausdruck ist und seine Eintragungen next1 und next2 auf die Anfangszustände der zwei Ausdrücke zeigen. Man beachte, daß diese in der entgegengesetzten Reihenfolge erzeugt werden, als man erwarten könnte, da der Wert von state für den Nicht-Operations-Zustand nicht bekannt ist, solange der rekursive Aufruf von Ausdruck nicht erfolgt ist.

Die Funktion für <Term> erzeugt zuerst den Automaten für einen <Faktor> und vereinigt dann, falls erforderlich, den Endzustand dieses Automaten mit dem Anfangszustand des Automaten für einen anderen <Term>. Dies ist leichter getan als gesagt, da state der Index des Endzustands des Aufrufs von Faktor ist. Ein Aufruf von Term ohne Inkrementieren von state führt zum Ziel:

    function term;
      var t: integer;
      begin
      term:=factor;
      if (p[j]='(') or letter(p[j]) then t:=term
      end;

(Wir haben für den vom zweiten Aufruf von Term gelieferten Index des Anfangszustands keine Verwendung, doch Pascal zwingt uns, ihn irgendwo zu verwenden, daher beseitigen wir ihn, indem wir ihn in einer temporären Variablen t abspeichern.)

Die Funktion für <Faktor> verwendet für die Behandlung ihrer drei Fälle ähnliche Techniken: Eine Klammer erfordert einen rekursiven Aufruf von Ausdruck, ein v erfordert eine einfache Verkettung mit einem neuen Zustand, und ein * erfordert Operationen, die denen in Ausdruck ähnlich sind, entsprechend dem Schema für die Hüllenbildung aus dem vorangegangenen Abschnitt:

    function factor;
      var t1,t2: integer;
      begin
      t1:=state;
      if p[j]='(' then
        begin
        j:=j+1; t2:=expression;
        if p[j]=')' then j:=j+1 else error
        end
      else if letter(p[j]) then
        begin
        setstate(state,p[j],state+1,state+1);
        t2:=state; j:=j+1; state:=state+1
        end
      else error;
      if p[j]<>'*' then factor:=t2 else
        begin
        setstate(state,' ',state+1,t2);
        factor:=state; next1[t1-1]:=state;
        j:=j+1; state:=state+1;
        end;
      end;

Abbildung 21.3 zeigt, wie die Zustände für das Muster (A*B+AC)D, unser Beispiel aus dem vorangegangenen Kapitel, konstruiert werden. Zuerst wird für das A Zustand 1 konstruiert. Dann wird Zustand 2 für den Hüllenbildungsoperator konstruiert, und Zustand 3 wird für das B angehängt. Danach wird das »+« gefunden, und die Zustände 4 und 5 werden mittels Ausdruck erzeugt, doch ihre Felder können erst nach einem rekursiven Aufruf von Ausdruck ausgefüllt werden, und dies führt schließlich zur Produktion der Zustände 6 und 7. Schließlich wird die Verkettung mit dem D mittels Zustand 8 behandelt, und Zustand 9 verbleibt als der Endzustand.

Abbildung 21.3
Abbildung 21.3 Herstellung eines Pattern Matching-Automaten für (A*B+AC)D.

Der abschließende Schritt bei der Entwicklung eines allgemeinen Pattern Matching-Algorithmus für reguläre Ausdrücke besteht darin, diese Prozeduren mit der Prozedur match zu verbinden:

    procedure matchall;
      begin
      j:=1; state:=1;
      next1[0]:=expression; 
      setstate(state,' ',0,0);
      for i:=1 to N-1 do
        if match(i)>=i then writeln(i);
      end;

Dieses Programm gibt alle Zeichenpositionen in einer Text-Zeichenfolge a[1..N] aus, bei denen ein Muster p[1..M] zu einer Übereinstimmung führt.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]