G.Heyer Algorithmen und Datenstrukturen II 1 10. Kapitel: Syntaxanalyse (Parsing) Es wurden verschiedene grundlegende Algorithmen entwickelt, um zulässige

G.Heyer Algorithmen und Datenstrukturen II1

10. Kapitel: Syntaxanalyse (Parsing)Es wurden verschiedene grundlegende Algorithmen entwickelt, um zulässige (korrekte ) Programme zu erkennen und sie in einer Weise zu zerlegen, die eine weitere Verarbeitung ermöglicht.Diese Operation, die Syntaxanalyse oder Parsing genannt wird, besitzt auch außerhalb der Informatik Anwendungen, da sie unmittelbar mit der Untersuchung der Struktur von Sprachen im Allgemeinen zusammenhängt.Z. B. spielt die Syntaxanalyse in Systemen, die versuchen, natürliche ( menschliche ) Sprachen zu verstehen, eine ebenso wichtige Rolle wie in Systemen für die Übersetzung einer Sprache in eine andere.Von Interesse ist auch der Spezialfall der Übersetzung aus einer höheren Programmiersprache, wie etwa C ( geeignet für die Benutzung durch den Anwender), in eine Assembler- oder Maschinensprache (geeignet für die Ausführung durch den Computer). Ein Programm für die Realisierung einer solchen Übersetzung wird Compiler genannt.


Zwei grundsätzliche Vorgehensweisen werden für dieSyntaxanalyse genutzt.Top-Down-ablaufende Methoden überprüfen ein Programm auf Zulässigkeit, indem sie zuerst die Teile eines zulässigen Programms bestimmen, dann Teile von Teilen usw., bis die Teile klein genug sind, um direkt auf Übereinstimmung mit den Eingabedaten geprüft werden können.Bottom-up-Methoden setzen Teile der Eingabedaten in einer strukturierten Weise zusammen, dass immer größere Teilstücke entstehen, bis ein zulässiges Programm konstruiert worden ist.Im Allgemeinen sind Top-Down-Methoden rekursiv, sie lassen sich leichter implementieren,Bottom-up-Methoden dagegen sind iterativ, sie gelten als effizienter.


Kontextfreie GrammatikenBevor man ein Programm zur Bestimmung der Zulässigkeit

eines in einer gegebenen Sprache erstellten Programmes schreiben kann, benötigt man eine Beschreibung, die angibt, woraus genau ein zulässiges Programm zusammengesetzt ist.

Diese Beschreibung wird Grammatik genannt.

Programmiersprachen werden oft durch einen speziellen Grammatiktyp beschrieben, der kontextfreie Grammatik genannt wird.

Als Beispiel wird die kontextfreie Grammatik angegeben, die die Menge aller zulässigen regulären Ausdrücke definiert.

<Ausdruck> ::= <Term> | <Term> + <Ausdruck>

<Term> ::= <Faktor> | <Faktor> <Term>

<Faktor> ::= (<Ausdruck>) | v | (<Ausdruck>)* | v*


Diese Grammatik beschreibt reguläre Ausdrücke wie etwa( 1 + 01 )*(0 + 1 ) oder ( A*B + AC)D.

Jede Zeile in der Grammatik wird eine Produktion (production) oder Regel genannt.

Die Produktionen bestehen aus den in der beschriebenen Sprache benutzten terminalen Symbolen ( , ) , + und *

(„v“, ein spezielles Symbol, steht für einen beliebigen Buchstaben oder eine beliebige Ziffer ),

weiterhin aus den nichtterminalen Symbolen <Ausdruck>, <Term> und <Faktor>, die interne Symbole der Grammatik sind, sowie aus den Metasymbolen ::= und |, die verwendet werden, um die Bedeutung der Produktionen zu beschreiben.

Das Symbol ::= , das „ist ein“ gelesen werden kann, definiert die linke Seite der Produktion mit Hilfe der rechten Seite, und das Symbol | , welches als „oder“ gelesen werden kann, gibt mögliche Alternativen an.


Die verschiedenen Produktionen entsprechen trotz dieserknappen Schreibweise auf einfache Weise einer intuitiven

Beschreibung der Grammatik.

Beispielsweise könnte die zweite Produktion im angebenen Beispiel einer Grammatik wie folgt gelesen werden:

„ Ein <Term> ist eine <Faktor> oder ein <Faktor>, dem ein <Term> folgt“.

Ein nichtterminales Symbol, in diesem Falle <Ausdruck>, ist in dem Sinne herausragend, dass eine Folge von terminalen Symbolen dann und nur dann der durch die Grammatik beschriebenen Sprache angehört, wenn es eine Möglichkeit gibt, unter Anwendung der Produktionen diese Folge aus dem herausragenden nichtterminalen Symbol abzuleiten, indem man (in beliebig vielen Schritten ) ein nichtterminales Symbol durch irgendeine der Alternativen auf der rechten Seite einer Produktion für dieses nichtterminale Symbol ersetzt.


Ein natürlicher Weg zur Beschreibung des Ergebnissesdieses Ableitungsprozesses ist ein Syntaxbaum (parse tree), ein Diagramm der vollständigen grammatischen Struktur der Zeichenfolge, für die die Syntaxanalyse vorgenommen wird.

Beispielsweise zeigt der unten dargestellte Syntaxbaum, dass die Zeichenfolge (A*B + AC)D in der durch die obige Grammatik beschriebenen Sprache enthalten ist.

Syntaxbäume dieser Art werden manchmal für die deutsche Sprache benutzt, um einen Satz in Subjekt, Prädikat, Objekt usw. zu zerlegen.


Syntaxbaum für (A*B +AC)DAusdruck

Term

(

Ausdruck

Ausdruck )

Term

Faktor

Term

Term

Faktor*A

B

Faktor

Faktor Term

Term

+

C

A Faktor

D

Faktor


Die Hauptaufgabe eines Parsers besteht darin, Zeichenfolgen,die auf diese Weise abgeleitet werden können, anzunehmen

bzw. die, die bei denen das nicht möglich ist, zurückzuweisen, indem er versucht, für eine beliebige gegebene Zeichenfolge einen Syntaxbaum zu konstruieren.

Das bedeutet, dass der Parser erkennen kann, ob eine Zeichenfolge in der durch die Grammatik beschriebenen Sprache enthalten ist, indem er feststellt, ob für die Zeichenfolge ein Syntaxbaum existiert oder nicht.

Top-Down-Parser tun dies, indem sie den Baum in der Weise aufbauen, dass sie mit dem herausragenden nichtterminalen Symbol oben beginnen und dann abwärts in Richtung auf die unten befindliche zu erkennende Zeichenfolge vorgehen.

Bottom-up-Parser arbeiten, indem sie mit der Zeichenfolge unten beginnen und rückwärts nach oben in Richtung auf das herausragende nichtterminale Symbol vorgehen.


Ein weiteres Beispiel für eine kontextfreie Grammatikbeschreibt zulässige C-Programme.

Die betrachteten Prinzipien für die Erkennung und Verwendung zulässiger Ausdrücke lassen sich unmittelbar auf die komplexe Aufgabe der Compilierung und Ausführung von C-Programmen anwenden.

Z. B. beschreibt die folgende Grammatik eine sehr kleine Teilmenge von C, nämlich arithmetische Ausdrücke, in denen Addition und Multiplikation vorkommen:

<Ausdruck> ::= <Term> | <Term> + <Ausdruck>

<Term> ::= <Faktor> | <Faktor> * <Term>

<Faktor> ::= (<Ausdruck>) | v


Diese Regeln legen fest, woraus „zulässige“ arithmetischeAusdrücke bestehen.

Auch hier ist v ein spezielles Symbol, das für einen beliebigen Buchstaben steht, doch in dieser Grammatik bezeichnen die Buchstaben gewöhnliche Variablen, die Zahlenwerte annehmen.

Beispiele zulässige Zeichenfolgen für diese Grammatik sind

A + ( B * C ) und A* (((B + C) * (D * E )) + F.

Gemäß der Definition sind gewisse Zeichenfolgen sowohl als arithmetische Ausdrücke als auch als reguläre Ausdrücke absolut zulässig.

Z. B. könnte A*(B+C) bedeuten „addiere B zu C und multipliziere das Ergebnis mit A“ oder „nehme eine beliebige Anzahl von As, denen entweder B oder C folgt“.

Dies verdeutlicht die Tatsache, dass die Prüfung der Zulässigkeit einer Zeichenfolge eine Angelegenheit ist, die Interpretation ihrer Bedeutung jedoch eine ganz andere.


Jeder reguläre Ausdruck ist selbst ein Beispiel für eine kontextfreie Grammatik: Jede Sprache, die durch einen regulären Ausdruck beschrieben werden kann, kann auch durch eine kontextfreie Grammatik beschrieben werden.

Die Umkehrung gilt nicht: z. B. kann die Forderung des „Ausgleichens“ von Klammern mit regulären Ausdrücken nicht erfasst werden.

Andere Arten von Grammatiken können Sprachen beschreiben, die kontextfreie Grammatiken nicht beschreiben können, z. B. sind kontextsensitive Grammatiken eben solche Grammatiken wie die obigen, mit dem Unterschied, dass die linken Seiten von Produktionen nicht einzelne nichtterminale Symbole sein müssen.


Der rekursive Abstieg (Top-Down-Syntaxanalyse)

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 rekursiv ) Prozeduraufrufen; terminale Symbole entsprechen dem Durchlaufen der eingegebenen Zeichenfolge.

Z. B. ist die folgende Prozedur Teil eines Top-Down-Parsers für unsere Grammatik der regulären Ausdrücke.


Prozedur als Teil eines Top-Down-Parsersexpression ()

{ term ();

if ( p [j] == „+“ )

( j++; expression() ; )

}

Eine Zeichenfolge p enthält den regulären Ausdruck, der Gegenstand der Syntaxanalyse ist, mit einem Index j, der auf das Zeichen zeigt, dessen Untersuchung gerade beginnt. Um die Syntaxanalyse für einen gegebenen regulären Ausdruck p vorzunehmen, setzt man j auf 0 und ruft expression (Ausdruck) auf.

Wenn dies dazu führt, dass j auf M gesetzt wird, so ist der reguläre Ausdruck in der durch die Grammatik beschriebenen Sprache enthalten .


Das erste, was Ausdruck bewirkt, ist ein Aufruf der Prozedur

Term, deren Implementation etwas komplizierter ist.

term()

{ faktor ();

if ( ( p [j] == „(„ ) || letter( p[j] )) term();

}

Da nach der vorgestellten Grammatik ein Term entweder ein Faktor oder ein von einem Term gefolgter Faktor ist, muss 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 muss einen Teil der Aufgabeder Prozedur Faktor übernehmen und überprüfen, ob nach

dem Aufruf von Faktor zu Beginn ein weiterer Faktor folgt (der laut der angegebenen Grammatik mit einer öffnenden Klammer oder einem Buchstaben v beginnen muss ).

Dieser Prozess der Prüfung des nächsten Zeichens ohne Inkrementieren von j zwecks Entscheidung, was zu tun ist, wird look-ahead (Vorausschau) genannt.

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.


Prozedur Faktorfactor ()

{

if ( p[j] == „(„ )

{

j++ ; expression() ;

if ( p[j] == „)“ ) j++; else error();

}

else if ( letter ( p[j] ) ) j++ ; else error();

if ( p[j] == „* “ ) j++ ;

}

Eine weitere Fehlerbedingung tritt auf, wenn eine

Klammer „)“ fehlt.


Syntaxanalyse von ( A * B + AC ) DAusdruck Term Faktor

( Ausdruck Term Faktor A *

TermFaktor B

+ Ausdruck

Term Faktor A Term

Faktor C)

TermFaktor D


Die Funktionen Ausdruck, Term und Faktor sind

offensichtlich rekursiv; tatsächlich sind sie derart miteinander verflochten, dass es keine Möglichkeit gibt, sie so aufzuzählen, dass jede Funktion deklariert wird, bevor sie benutzt wird (für manche Programmiersprachen ist dies ein Problem).

Der Syntaxbaum für eine gegebene Zeichenfolge gibt die Struktur der rekursiven Aufrufe während der Syntaxanalyse an. Die Abbildung 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.


Der Top-Down-Ansatz führt nicht für alle möglichen

kontextfreien Grammatiken zum Ziel, z. B. würde man bei der Produktion <Ausdruck> ::= v | <Ausdruck> + <Term> ein unerwünschtes Ergebnis erhalten, wenn man der mechanischen Übersetzung in C wie oben folgen würden:

badexpression( );

{ if (letter ( p[j] )) j++ ; else

{ badexpression ( ) ;

if ( p[j] == „+“ ) { j++ ; term( ) ; }

else error ( ) ;

}

}


Wenn diese Prozedur mit einem p[j] aufgerufen würde,das kein Buchstabe ist (wie im 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.


Bottom-up AnalyseZur Syntaxanalyse gehört mehr als die einfache Prüfung, ob die eingegebene Zeichenfolge zulässig ist; die Hauptsache besteht in der Produktion des Syntaxbaumes für die weitere Verarbeitung (selbst wenn dies wie beim Top-Down-Parser nur implizit erfolgt).

Ein Typ eines Parsers, der in dieser Weise abläuft, ist der sogenannte shift-reduce-Parser. Die Idee besteht darin, einen Stapel zu verwenden, der terminale und nichtterminale Symbole aufnimmt. Jeder Schritt der Syntaxanalyse ist entweder ein verschiebender (shift) Schritt, bei dem das nächste eingegebene Zeichen einfach im Stapel abgelegt wird, oder ein reduzierender (reduce) Schritt, bei dem die im Stapel oben befindlichen Zeichen auf Übereinstimmung mit der rechten Seite einer Produktion in der Grammatik geprüft und auf das auf der linken Seite dieser Produktion befindliche nichtterminale Symbol „reduziert“ (d. h. durch dieses ersetzt ) werden.


Verbindungen zum Pattern MatchingOft ist es wünschenswert, eine Suche nach einem nur

unvollständigen Muster vorzunehmen, z. B. kann es vorkommen, dass Benutzer eines Texteditors nur einen Teil eines Musters vorgeben wollen, oder ein Muster, welches zu mehreren verschiedenen Wörtern passen würde, oder dass sie festlegen wollen, dass eine beliebige Anzahl bestimmter spezifischer Zeichen ignoriert werden soll.

Die bisher untersuchten Algorithmen sind entscheidend von der vollständigen Vorgabe des Musters abhängig, so dass man jetzt andere Methoden benutzen muss.

Die grundlegenden Mechanismen, die betrachtet werden, ermöglichen die Entwicklung eines sehr leistungsfähigen Verfahrens zur Suche in Zeichenfolgen, welches komplizierte Muster aus M Zeichen an Text-Zeichenfolgen aus N Zeichen anpassen kann, in einer Zeit, die im ungünstigsten Fall proportional zu MN2 ist, in typischen Anwendungsfällen jedoch wesentlich schneller abläuft.


Zunächst muss man eine Methode entwickeln, um die Musterzu beschreiben; eine „Sprache“, die benutzt werden kann, um

die oben genannten Probleme der partiellen Suche in Zeichenfolgen exakt zu spezifizieren.

Diese Sprache wird leistungsfähigere elementare Operationen umfassen als die bisher verwendete einfache Operation „Überprüfen“, ob das i-te Zeichen der Text-Zeichenfolge mit dem j-ten Zeichen des Musters übereinstimmt.


Beschreibung von MusternDie hier betrachteten Musterbeschreibungen erfolgen mit Hilfe

von Symbolen, welche mittels der folgenden drei grundlegenden Operationen miteinander verknüpft sind:

1) Verkettung (Concatenation): Dies ist die Operation, die bisher benutzt wurde. Falls zwei Zeichen im Musterbenachbart sind, so liegt genau dann und nur dann eine Übereinstimmung vor, wenn die im Text gleichen beiden Zeichen benachbart sind, z. B. bedeutet AB, dass B auf A folgt.

2) Oder (Or): Dies ist die Operation, die uns die Möglichkeit gibt, Alternativen im Muster vorzugeben. Wenn sich zwischen zwei Zeichen ein oder befindet, so liegt dann und nur dann eine Übereinstimmung vor, wenn eines der Zeichen im Text auftritt. Diese Operation wird durch die Benutzung des Symbols + bezeichnet und es werden Klammern verwendet, um sie mit der Verkettung in beliebig komplexer Weise zu kombinieren, z. B. bedeutet A+B „entweder A oder B“; C( AC+B)D bedeutet „entweder CACD oder CBD“;

(A+C)((B+C)D) bedeutet „entweder ABD oder CBD oder ACD oder CCD“ .


3) Hüllenbildung (Closure): Diese Operation gestattet es,

Teile des Musters beliebig oft zu wiederholen.

Bei der Hülle des Symbols liegt dann und nur dann eine Übereinstimmung vor, wenn das Symbol beliebig oft (einschließlich 0 mal ) erscheint. Die Hüllenbildung soll bezeichnet werden, indem nach dem zu wiederholenden Zeichen oder der zu wiederholenden , in Klammern eingeschlossenen Gruppe ein * gesetzt wird.

Z. B. stimmt AB* mit Zeichenfolgen überein, die aus einem A bestehen, dem eine beliebige Anzahl (oder kein ) B folgt, während (AB)* mit Zeichenfolgen übereinstimmt, die aus sich abwechselnden A und B bestehen.


Eine Folge von Symbolen, die unter Verwendung dieserdrei Operationen aufgebaut ist, wird regulärer Ausdruck

genannt. Jeder reguläre Ausdruck beschreibt viele spezielle Textmuster.

Das Ziel besteht darin, einen Algorithmus zu entwickeln, mit dem bestimmt werden kann, ob irgendeines der Muster, die durch einen gegebenen regulären Ausdruck beschrieben werden, in einer gegebenen Text-Zeichenfolge auftritt.


Der Pattern Matching-Algorithmus kann als eine Verallgemeinerung der groben Methode der Suche in Zeichenfolgen von links nach rechts angesehen werden.

Der Algorithmus sucht nach der am weitesten links stehenden Teil-Zeichenkette innerhalb der Text-Zeichenfolge, die mit der Beschreibung des Musters übereinstimmt, indem er die Text-Zeichenfolge von links nach rechts durchläuft und bei jeder Position prüft, ob eine bei dieser Position beginnende Teil-Zeichenfolge existiert, die mit der Beschreibung des Musters übereinstimmt.


Automaten für das Pattern MatchingDer Algorithmus von Knuth-Morris-Pratt kann als ein auf der

Grundlage des Suchmusters konstruierter endlicher Automat betrachtet werden, der den Text durchsucht. Die Methode, die man für das Pattern Matching regulärer Ausdrücke anwenden kann, ist eine Verallgemeinerung dieser Sichtweise.

Der endliche Automat für den Algorithmus von Knuth-Morris-Pratt geht von einem Zustand in den anderen über, indem er ein Zeichen aus der Text-Zeichenfolge untersucht und dann in einen Zustand übergeht, wenn eine Übereinstimmung vorliegt, und in einen anderen, wenn das nicht der Fall ist.

Eine Nichtübereinstimmung an irgendeiner Stelle bedeutet, dass das Muster in dem an dieser Stelle beginnenden Text nicht auftreten kann.

Der Algorithmus selbst kann als eine Simulation des Automaten angesehen werden. Die Eigenschaft des Automaten, die bewirkt, dass er leicht simuliert werden kann, ist, dass er deterministisch ist: Jeder Übergang von einem Zustand in einen anderen wird vollständig durch das nächste eingegebene Zeichen bestimmt.


Um reguläre Ausdrücke zu behandeln, ist es erforderlich,einen leistungsfähigeren abstrakten Automaten zu betrachten.

Aufgrund der Operation oder kann der Automat nicht durch Untersuchung von nur einem Zeichen feststellen, ob das Muster am einer gegebenen Stelle auftreten kann oder nicht; aufgrund der Hüllenbildung kann er noch nicht einmal feststellen, wie viele Zeichen betrachtet werden müssten, bevor eine Nichtübereinstimmung entdeckt wird.

Der natürlichste Weg zur Überwindung dieser Probleme besteht darin, den Automaten mit der Fähigkeit eines nichtdeterministischen Vorgehens auszustatten:

Bei Vorhandensein von mehreren Wegen, auf denen man versuchen kann, das Muster anzupassen, sollte der Automat den richtigen erraten.


Ein nichtdeterministischer Mustererkennungs-Automat

für (A*B + AC)D

A

A

D

C

B

05

6 7

1 2

98

3 4

Dieser Automat kann aus einem mit einem Zeichen markierten Zustand in den Zustand übergehen, auf den dieser Zustand „zeigt“, indem er dieses Zeichen in der Text-Zeichenfolge anpasst (und durchläuft). Was den Automat nichtdeterministisch macht, ist, dass es einige Zustände gibt (Nullzustände genannt), die nicht nur mit keinem Zeichen markiert sind, sondern auch auf zwei unterschiedliche Nachfolge-Zustände „zeigen“ können. Zustand 9 ist ein Nullzustand ohne Ausgänge, der den Automaten anhält.


Der Automat hat einen eindeutigen Anfangszustand(dargestellt mit der frei beginnenden Linie links) und einen

eindeutigen Endzustand (kleines Quadrat rechts).

Wenn der Automat im Anfangszustand gestartet wird, ist er in der Lage, jede durch das Muster beschriebene Zeichenfolge zu „erkennen“, indem er Zeichen liest und seinen Zustand gemäß seinen Regeln verändert, wobei er am Ende zum „Endzustand“ gelangt.

Wenn der Automat auf einem gewöhnlichen Computer simuliert werden soll, muss man alle Möglichkeiten ausprobieren,

z. B. bei einer Musterbeschreibung (A*B + AC)D

in der Textzeichenfolge CDAABCAAABDDACDAAC

um die Zeichenfolge AAABD zu erkennen.


Konstruktion eines Zustandsautomaten:Für einen gegebenen Ausdruck kann man den Automaten

konstruieren, indem man für die einzelnen Komponenten des Ausdrucks Teilautomaten herstellt und für jede der drei Operationen Verkettung, oder und Hüllenbildung die Art und Weise definiert, wie zwei Teilautomaten zu einem größeren Automaten zusammengesetzt werden:

1.) Automat mit zwei Zuständen zur Erkennung eines Zeichens:

A

Anfangszustand, der auch das Zeichen erkennt und Endzustand.


2.) Konstruktion eines Zustandsautomaten: Verkettung

Um den Automaten für die Verkettung von zwei Ausdrücken aus den Automaten für die einzelnen Ausdrücke zu bilden, vereinigt man den Endzustand des ersten mit dem Anfangszustand des zweiten Automaten.

Automat 1

Automat 2

Automat 2Automat 1


3.) Konstruktion eines Zustandsautomaten: oder

Automat 1

Automat 2

Automat 1

Automat 2

Konstruktion in ähnlicher Weise, Hinzufügen eines neuen Nullzustandes, der auf die beiden Anfangszustände zeigt, und indem man einen Endzustand auf den anderen zeigen lässt, der dann zum Endzustand des kombinierten Automaten wird.


4.) Konstruktion eines Automaten: Hüllenbildung

Der Endzustand wird zum Anfangszustand und zeigt zurück zum alten Anfangszustand sowie zu einem neuen Endzustand.

Durch sukzessive Anwendung dieser Regeln kann für jeden beliebigen regulären Ausdruck ein ihm entsprechender Automat gebildet werden. Die Zustände werden entsprechend der Reihenfolge ihrer Erzeugung nummeriert (wenn der Automat konstruiert wird, indem das Muster von links nach rechts durchlaufen wird), so dass die Konstruktion des Automaten mit Hilfe der obigen Regeln leicht verfolgt werden kann.


Darstellung des AutomatenDa man oft nur über die Nummer auf die Zustände zugreifen

will, ist die zweckmäßigste Organisation für den Automaten eine Darstellung als Feld.

Es werden die drei mit dem Index state (Zustand) versehenen parallelen Felder ch, next1 und next2 verwendet, um den Automaten darzustellen.state 0 1 2 3 4 5 6 7 8 9

ch[state] A B A C D

next1[state] 5 2 3 4 8 6 7 8 9 0

next2[state] 5 2 1 4 8 2 7 8 9 0

Die mit dem Index state versehenen Einträge können als Anweisungen für den nichtdeterministischen Automaten von der Art „Wenn man sich in state befindet und ch[state] sieht, dann soll man das Zeichen durchlaufen und in den Zustand next1[state] (oder next2[state]) übergehen“ interpretiert werden. Zustand 9 ist der Endzustand in diesem Beispiel, und Zustand 0 ist ein Pseudo-Anfangszustand, dessen Einträge next die Nummer des eigentlichen Anfangszustandes sind.

Documents

G.Heyer Algorithmen und Datenstrukturen II 1 10. Kapitel: Syntaxanalyse (Parsing) Es wurden verschiedene grundlegende Algorithmen entwickelt, um zulässige