Theoretische Informatik

Syntaxdiagramm

 aufwärts

Ein regulärer Ausdruck lässt sich sehr einfach in ein Syntax­diagramm überführen. Das Syntax­diagramm beschreibt die reguläre Sprache, die von dem regulären Ausdruck erzeugt wird, indem es in anschau­licher Weise zeigt, welche Wörter gebildet werden können.

Beispiel:  Der reguläre Ausdruck R  =  a | a(a|b)*a wird in folgendes Syntax­diagramm überführt (Bild 1):

Bild 1: Syntaxdiagramm für den regulären Ausdruck a | a(a|b)*a
Bild 1: Syntaxdiagramm für den regulären Ausdruck a | a(a|b)*a

Das Diagramm wird von links beginnend in Pfeil­richtung bis zum Ausgang durchlaufen. Dabei werden die Alphabet­zeichen, die an den durch­laufenen Pfeilen stehen, zu einem Wort aneinander­gereiht. Jeder mögliche Pfad durch das Diagramm, der vom Eingang bis zum Ausgang verläuft, entspricht auf diese Weise einem Wort der Sprache, die von dem regulären Ausdruck R erzeugt wird.

Wird beispiels­weise das Diagramm geradeaus von links nach rechts durchlaufen, so wird das Wort aa gebildet. Wird unterwegs einmal die Schleife mit dem b durchlaufen, ergibt sich das Wort aba. Für das Wort a wird der große Umweg unten herum gewählt.

Es gibt zwei Sichtweisen, wie ein Syntax­diagramm eine Sprache definiert: indem es Wörter der Sprache erzeugt, oder indem es Wörter der Sprache erkennt. Im ersten Fall beginnen wir mit einem leeren Wort und hängen beim Durchlaufen des Syntax­diagramms Zeichen um Zeichen an, im anderen Fall liegt uns ein Wort vor und wir arbeiten es zeichenweise ab, während wir das Syntax­diagramm durchlaufen.

In beiden Fällen ist das Durchlaufen eines Syntax­diagramms im allgemeinen ein nicht­deterministischer Vorgang. Wenn wir an Verzweigungs­punkte des Diagramms gelangen, haben wir die Wahl, in welche Richtung wir abbiegen. Gelegentlich müssen wir die richtige Wahl sozusagen mit schlaf­wandlerischer Sicherheit treffen. Um beispiels­weise das Wort aaa zu erzeugen bzw. zu erkennen, müssen wir im Syntax­diagramm an der ersten Verzweigung geradeaus gehen, an der nächsten Verzweigung nach oben abbiegen und einmal in der a-Schleife kreisen, und beim nächsten Mal an dieser Verzweigung geradeaus zum Ausgang gehen. Biegen wir falsch ab, gelingt es uns nicht, das Wort aaa zu erzeugen bzw. zu erkennen.

Ein Syntax­diagramm besagt also im allgemeinen nicht, wie ein bestimmtes Wort erzeugt oder erkannt wird, sondern nur ob es prinzipiell erzeugt oder erkannt werden kann.

Wörter allerdings, die nicht zu der Sprache gehören, die durch das Syntax­diagramm definiert ist, lassen sich auf keine Weise beim Durchlaufen des Syntax­diagramms erzeugen bzw. erkennen.

In obigem Beispiel lässt sich etwa das Wort abb nicht erzeugen. Denn es gibt keinen Pfad durch das Syntax­diagramm, der diesem Wort entspricht. Beim Versuch das Wort abb zu erkennen, erreichen wir zwar mit a die Schleife, die mit b markiert ist, durchlaufen diese zweimal, aber kommen dann nicht weiter bis zum Ausgang des Syntax­diagramms.

Syntax von Programmiersprachen

Die Syntax von Programmier­sprachen wurde schon sehr früh in Form von Syntax­diagrammen angegeben. Als einfachstes Beispiel zeigt Bild 2 das Syntax­diagramm für identifier in der Programmier­sprache Pascal, wie es im Pascal User Manual and Report von 1975 angegeben ist [JW 75]. Durch das Syntax­diagramm wird festgelegt, wie identifier, also Bezeichner für Programm­variablen oder Funktionen gebildet werden: Ein Bezeichner fängt mit einem Buchstaben (letter) an und geht dann mit beliebig vielen Buchstaben (letter) oder Ziffern (digit) weiter. Im Unterschied zu unserer Darstellung von Syntax­diagrammen sind in den Pascal-Syntax­diagrammen die Beschriftungen der Pfeile nicht darüber oder darunter angebracht, sondern in Form von Ovalen oder Kästchen in die Pfeile eingebettet.

Bild 2: Syntaxdiagramm für identifier in der Programmiersprache Pascal
Bild 2: Syntaxdiagramm für identifier in der Programmiersprache Pascal

Mögliche Bezeichner sind also

x, x34, counter, getNext, uv2wx2y.

Keine Bezeichner dagegen sind

3n, next-state, my Text, a.next,

da diese Zeichen­ketten mit einer Ziffer anfangen oder Zeichen enthalten, die keine Buchstaben oder Ziffern sind.

 

Weitere Ausdrucks­kraft erlangen Syntax­diagramme, wenn sie Kästchen enthalten, die als Platzhalter wiederum für andere Syntax­diagramme stehen. Hiervon wird später die Rede sein; zunächst erlauben wir dies nicht.

Syntaxdiagramm als Brettspiel

Wir verändern Syntax­diagramme nun geringfügig in einer bestimmten Weise. Am Anfang des Syntax­diagramms führen wir ein Startfeld ein, am Ende ein Endfeld, und an den Knoten­punkten des Syntax­diagramms führen wir quasi als Zwischen­stationen weitere Felder ein.

Beispiel:  Das folgende Bild 3 zeigt das entsprechend umgestaltete Syntax­diagramm aus dem voran­gegangenen Beispiel. Am Eingang und am Ausgang sowie an den Knoten­punkten des Syntax­diagramms sind Felder eingeführt worden, dargestellt durch Kreise. Das Startfeld ist durch einen "aus dem Nichts kommenden" Pfeil markiert, das Endfeld durch einen doppelten Kreis. Alle anderen Felder sind Zwischen­stationen.

Bild 3: Syntaxdiagramm mit eingeführten Zwischenstationen
Bild 3: Syntaxdiagramm mit eingeführten Zwischenstationen

Ein so umgestaltetes Syntax­diagramm lässt sich als eine Art Brettspiel verwenden. Auf die Felder können wir eine Spielfigur, zum Beispiel ein "Mensch-ärgere-dich-nicht"-Männchen, setzen. Wir beginnen beim Startfeld, ziehen mit der Spielfigur entlang der Pfeile von Feld zu Feld und reihen dabei die Zeichen, die uns begegnen, aneinander. Das Spiel ist "gewonnen", wenn es gelingt, vom Startfeld bis zum Endfeld zu ziehen und dabei ein vorgegebenes Wort wie etwa abba zu erzeugen bzw. zu erkennen, je nach Sichtweise.

Beispiel:  Im oben abgebildeten Spiel ziehen wir vom Startfeld zunächst drei Felder geradeaus. Dabei begegnet uns das Zeichen a. Dann kreisen wir zweimal entlang der unteren Schleife, dabei begegnen uns zwei b's. Zum Schluss ziehen wir zwei Felder geradeaus bis zum Endfeld; dabei begegnet uns ein a. Auf diese Weise haben wir das Wort abba erzeugt bzw. erkannt.

Das Wort abb dagegen können wir nicht erzeugen bzw. erkennen, weil wir damit nicht zum Endfeld durchkommen.

Wir werden später das Brettspiel noch so verändern, dass wir mit der Spielfigur nicht mehr intuitiv richtig ziehen müssen, um zum Endfeld zu gelangen. Stattdessen spielen wir alle Zug­möglich­keiten parallel durch, indem wir mehrere Spielfiguren verwenden.

Zusammenhang mit nichtdeterministischen endlichen Automaten

Wie wir im nächsten Abschnitt sehen werden, ist ein so erstelltes Brettspiel nichts anderes als der Zustands­graph eines nicht­deterministischen endlichen Automaten. Die Felder sind die Zustände des Automaten, die Pfeile sind ent­sprechende Zustands­übergänge. Es treten auch Zustands­übergänge auf, die mit keinem Zeichen markiert sind. Diese Zustands­übergänge stellen sogenannte Epsilon-Übergänge dar. Der ent­sprechende Automat ist also ein nicht­deterministischer endlicher Automat mit Epsilon-Übergängen.

Literatur

[JW 75]K. Jensen, N. Wirth: Pascal User Manual and Report. 2. Auflage, Springer (1975)

 

 

 

Weiter mit:   [Nichtdeterministischer endlicher Automat]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 20.01.2011   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik