Robert Sedgewick: Algorithmen

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


21. Syntaxanalyse (Parsing)



Der rekursive Abstieg (Top-Down-Syntaxanalyse)

Es gibt eine Methode der Syntaxanalyse, die zur Erkennung von Zeichenfolgen der beschriebenen Sprache eine unmittelbar aus der Grammatik erzeugte Rekursion verwendet. Einfach ausgedrückt, die Grammatik ist eine derart vollständige Beschreibung der Sprache, daß sie unmittelbar in ein Programm umgewandelt werden kann!

Jede Produktion entspricht einer Prozedur, die nach dem nichtterminalen Symbol auf der linken Seite benannt ist. Nichtterminale Symbole auf der rechten Seite der Eingabe entsprechen (möglicherweise rekursiven) Prozeduraufrufen; terminale Symbole entsprechen dem Durchlaufen der eingegebenen Zeichenfolge. Zum Beispiel ist die folgende Prozedur Teil eines Top-Down-Parsers für unsere Grammatik der regulären Ausdrücke:*)

    procedure expression;
      begin
      term;
      if p[j]='+' then
        begin j:=j+1; expression end
      end;

Ein Feld p enthält den regulären Ausdruck, der Gegenstand der Syntaxanalyse ist, und ein Index j zeigt auf das Zeichen, dessen Untersuchung gerade beginnt. Um die Syntaxanalyse für einen gegebenen regulären Ausdruck vorzunehmen, speichern wir ihn in p[1..M] (mit einem Marken-Zeichen in p[M+1], das in der Grammatik nicht benutzt wird), setzen j auf 1 und rufen expression (Ausdruck) auf. Wenn dies dazu führt, daß j auf M+1 gesetzt wird, so ist der reguläre Ausdruck in der durch die Grammatik beschriebenen Sprache enthalten. Wenn nicht, so werden wir weiter unten sehen, wie verschiedene Fehlerbedingungen behandelt werden können.

Das erste, was Ausdruck bewirkt, ist ein Aufruf der Prozedur Term, deren Implementation etwas komplizierter ist:

    procedure term;
      begin
      factor;
      if (p[j]='(') or letter(p[j]) then term
      end;

Da nach unserer Grammatik ein Term entweder ein Faktor oder eine von einem Term gefolgter Faktor ist, muß die Prozedur Term einen anderen Weg als die Prozedur Ausdruck einschlagen, um zu überprüfen, welche beiden Alternativen bei der Ableitung zu wählen ist. Bei der Prozedur Ausdruck stand hierfür das terminale Symbol + zur Verfügung. Die Prozedur Term hingegen muß einen Teil der Aufgabe der Prozedur Faktor übernehmen und überprüfen, ob nach dem Aufruf von Faktor zu Beginn ein weiterer Faktor folgt (der laut unserer Grammatik mit einer öffnenden Klammer oder einem Buchstaben v beginnen muß). Dieser Prozeß der Prüfung des nächsten Zeichens ohne Inkrementieren von j zwecks Entscheidung, was zu tun ist, wird look-ahead (Vorausschau) genannt. Für manche Grammatiken ist dies nicht notwendig; für andere ist sogar noch mehr look-ahead erforderlich.

Die Implementation von Faktor ergibt sich nun unmittelbar aus der Grammatik. Wenn das Eingabezeichen, das gerade durchlaufen wird, keine Klammer »(« und kein Buchstabe ist, wird eine Prozedur error aufgerufen, um die Fehlerbedingung zu behandeln:

    procedure factor;
      begin
      if p[j]='(' then
        begin
        j:=j+1;
        expression;
        if p[j]=')' then j:=j+1 else error
        end
      else if letter(p[j]) then j:=j+1 else error;
      if p[j]='*' then j:=j+1
      end;

Eine weitere Fehlerbedingung tritt auf, wenn eine Klammer »)« fehlt.

Die Prozeduren Ausdruck, Term und Faktor sind offensichtlich rekursiv; tatsächlich sind sie derart miteinander verflochten, daß sie in Pascal nicht kompiliert werden können, ohne die forward-Direktive zu verwenden, um die Regel zu umgehen, die die Benutzung einer zuvor nicht deklarierten Prozedur ausschließt.

Der Syntaxbaum für eine gegebene Zeichenfolge gibt die Struktur der rekursiven Aufrufe während der Syntaxanalyse an. Abbildung 21.2 stellt die Arbeitsweise der obigen drei Prozeduren dar, wenn p (A*B+AC)D enthält und Ausdruck mit j = 1 aufgerufen wird. Außer für das Pluszeichen wird das gesamte »Durchsuchen« in Faktor realisiert. Zur Verbesserung der Lesbarkeit wurden die von der Prozedur Faktor durchlaufenen Zeichen, mit Ausnahme der Klammern, in der gleichen Zeile wie der Aufruf Faktor dargestellt.

Abbildung 21.2
Abbildung 21.2 Syntaxanalyse von (A * B + AC)D.

Dem Leser wird empfohlen, diesen Prozeß in Beziehung zu der Grammatik und dem Baum in Abbildung 21.1 zu setzen. Der Prozeß entspricht der Preorder-Traversierung des Baumes, obwohl die Entsprechung nicht exakt ist, da unsere look-ahead-Strategie dem Wesen nach eine Änderung der Grammatik darstellt. Da wir an der Spitze des Baumes beginnen und nach unten vorgehen, ist die Herkunft der Bezeichnung »Top-Down« offensichtlich. Solche Parser werden auch oft rekursiv absteigende Parser genannt, da sie sich im Syntaxbaum rekursiv nach unten bewegen.

Der Top-Down-Ansatz führt nicht für alle möglichen kontextfreien Grammatiken zum Ziel. Zum Beispiel würden wir bei der Produktion <Ausdruck> ::= v | <Ausdruck> + <Term>> ein unerwünschtes Ergebnis erhalten, wenn wir der mechanischen Übersetzung in Pascal wie oben folgen würden:

    procedure badexpression;
      begin
      if letter(p[j]) then j:=j+1 else
        begin
        badexpression;
        if p[j]<>'+' then error else
          begin j:=j+1; term end
        end
      end;

Wenn diese Prozedur mit einem p[j] aufgerufen würde, das kein Buchstabe ist (wie in unserem Beispiel für j = 1), so würde sie in eine rekursive Endlosschleife einmünden. Die Vermeidung solcher Schleifen ist eine der Hauptschwierigkeiten bei der Implementation von rekursiv absteigenden Parsern. Für Term benutzten wir den look-ahead, um eine solche Schleife zu vermeiden; in diesem Falle besteht der geeignete Weg, dieses Problem zu umgehen, in einer Umformulierung der Grammatik nach <Term> + <Ausdruck>. Das Auftreten eines nichtterminalen Symbols als erstes Element auf der rechten Seite einer Regel für dieses gleiche Symbol wird Links-Rekursion genannt. In Wirklichkeit ist das Problem noch subtiler, da die Links-Rekursion indirekt auftreten kann, zum Beispiel bei den Produktionen <Ausdruck> ::= <Term> und <Term> ::= v | <Ausdruck> + <Term>. Rekursiv absteigende Parser sind für solche Grammatiken nicht geeignet; letztere müssen in äquivalente Grammatiken ohne Links-Rekursion umgewandelt werden, oder es muß ein anderes Syntaxanalyseverfahren benutzt werden. Im allgemeinen besteht eine enge und sehr gründlich erforschte Beziehung zwischen Parsern und den Grammatiken, die sie erkennen, und die Wahl des Syntaxanalyseverfahrens wird oft von den Merkmalen der zu analysierenden Grammatik diktiert.



*)
In diesem Abschnitt verwenden wir weiter die deutschen Begriffe Ausdruck, Term und Faktor, auch wenn wir uns auf die Prozeduren expression, term und factor beziehen, um den Lesefluß zu erleichtern. (A.d.Ü).


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