Anwendungen und Beispiele (BP: Items 1, 15)

Beispiel: Morgendlicher Gruß als Mealy-Automat

Zumindest in der Unterstufe gibt es an vielen Schulen ein Begrüßungritual: Die Lehrerin betritt den Raum und wartet bis alle stehen; die Schüler erheben sich, warten auf ihren Gruß und erwidern ihn; die Lehrerin sagt „Setzt euch“ und die Klasse setzt sich.

Wenn man die einzelnen Aktionen als „Nach­richten“ zwischen den Beteiligten versteht, sieht dieses sehr einfache Protokoll im Sequenzdiagramm so aus wie in Abbil­dung 9.

Während das Sequenzdiagramm den Nachrichtenaustausch in den Mittelpunkt stellt, durch­laufen auch die Teilnehmer selbst während des Protokolls bestimmte Phasen, die sich als Zustän­de eines Automaten dar­stel­len lassen; beim Eintreffen einer „Nachricht“ wechselt der Auto­mat den Zustand. Mit Mealy-Automaten kann man so model­lieren, dass die Ausgaben des einen Automaten als Nachrichten an den anderen gehen, der sie dann als Eingaben verarbeitet.

Abbildung 10 zeigt einen Mealy-Auto- maten für die Rolle der Klasse beim morgendlichen Begrüßen; die Aktio- nen der Lehrerin sind die Eingaben für diesen „Schülerautomaten“. Ein ähn- licher Automat kann umgekehrt die Aktionen und Reaktionen der Lehrerin beschreiben.

Übrigens gibt es für die Erstellung von Sequenzdiagrammen natürlich Werkzeuge; Abbildung 9 wurde beispielsweise von dem Generator auf der Seite https://sequencediagram.org/ aus folgender Beschreibung erzeugt:

title Klassengruß
Lehrerin->Klasse: betritt den Raum
Lehrerin->Klasse: wartet, bis alle stehen
activate Klasse
Lehrerin -> Klasse: "Guten Morgen, liebe 5B!"
Klasse->Lehrerin: "Guten Morgen, Frau Klug!"
Lehrerin -> Klasse: "Setzt euch, wir fangen an..."
deactivate Klasse

Auch hier kommt übrigens eine Spezialsprache (zur Beschreibung von Sequenzdiagrammen) zum Einsatz, die von entsprechenden Werkzeugen gelesen, überprüft und interpretiert wird.

Beispiel: Vereinfachtes TCP als Mealy-Automat

Als größeres Beispiel zeigt Abbildung 11 sehr stark verein- facht den Verbindungsaufbau („Handshake“) und Datenaus- tausch einer TCP-Verbindung. Der Handshake beinhaltet den Austausch und die gegenseitige Bestätigung von zufälligen Sequenznummern (hier ab 174 für Datenpakete vom Client zum Server und 309 für die Gegenrichtung). Während der Austauschphase werden die Datenpakete durchnummeriert; nach Eingang bestätigt der Empfänger sie („ACKnowledge“) und nennt dabei die Sequenznummer. Bleibt eine Bestäti- gung aus, muss der Absender das Paket erneut schicken oder (nach einigen Fehlversuchen) annehmen, dass die Verbindung abgerissen ist.

Der Verbindungsabbau, der ebenfalls zu TCP gehört, ist hier nicht dargestellt.

Die Software, die eine Seite eines solchen Protokolls durch- führt, heißt üblicherweise Treiber.

Auch in diesem Beispiel lassen sich die TCP-Treiber von Server und Client als Mealy-Automat darstellen. Zwar kann ein endlicher Automat im engeren Sinne nicht unbegrenzt Sequenznummern hochzählen; dennoch ist die Vorstellung, dass Protokolltreiber „Zustände“ haben, zwischen denen sie bei bestimmten Ereignissen wechseln, ein hilfreiches Modell für eine strukturierte Implementierung.

Abbildung 12 skizziert einen Automaten für diesen Treiber: Der obere Pfad wird durchlaufen, wenn der Treiber selbst den Verbindungsaufbau initiiert; der untere, wenn von außen eine Verbindungsanfrage eingeht. Nachdem die Verbindung aufgebaut und die Sequenznummern vereinbart sind (SeqIn für eingehende, SeqOut für ausgehende Datenpakete), kann der Treiber Daten sowohl verschicken als auch empfangen; nach jedem empfangenen bzw. verschickten Paket wird die jeweilige Sequenznummer erhöht. Bekommt der Treiber für ein gesendetes Paket keine Quittung, wechselt er von q6 nach q7; nach dem zweiten Fehlversuch (auch in q7 wieder ein Timeout) betrachtet er die Verbindung als abgerissen und wechselt ganz zurück nach q0.

Der Ablauf ist hier aus didaktischen Gründen sehr stark vereinfacht: Er enthält beispielsweise keinen Verbindungsabbau, ignoriert Störungen des Verbindungsaufbaus sowie Pakete, die in falscher Reihenfolge ankommen, verwendet die Sequenznummern anders als „richtiges“ TCP dast tut, und vieles mehr.

Anwendung: Automaten für Scanner, Parser und Compiler

Die Compilierung eines Programms ist ein komplexer Vorgang, der mehrfach Gebrauch von formalen Sprachen und entsprechenden Werkzeugen macht.

Ein Java-Schnipsel wie...

1 for (int wert; wert <= 5; wert ++) {
2   if(zahl % 17 == 0) {
3     System.out.println(„durch 17 teilbar:“ + k);
4    }
5 }

wird dabei für die lexikalische Analyse zunächst von einem sogenannten Scanner (auch „Lexer“ genannt) gelesen. Der fasst die Eingabe zunächst als Zeichenstrom auf...

... und versucht darin Bedeutungseinheiten, sogenannte Tokens, der betreffenden Programmiersprache zu finden. Das Ergebnis ist ein Tokenstream:

Im Tokenstream kommen nur noch Elemente vor, die syntaktisch bedeutsam sind; Leerzeichen, Zeilenumbrüche und Kommentare tragen keine Bedeutung und fehlen daher.

Die Buchstabenfolge i n t wurde vom Scanner als Java-Schlüsselwort erkannt und zu einem INT-Token zusammengefasst. Das ist zwar nicht trivial, weil er die Zeichenkette i n t e r n natürlich nicht als INT-Token einstufen, sondern als „Identifier“ erkennen und daraus ein ID- Token erzeugen müsste. Dennoch kann die lexikalische Analyse von DEAs erledigt werden. Die Sprache der in Java erlaubten Tokens ist also regulär. Passt eine Zeichenfolge zu keinem Token, meldet der Scanner einen lexikalischen Fehler.

Der Tokenstream ist ein Zwischenprodukt und dient anschließend als Eingabe für den sogenannten Parser, der die syntaktische Analyse des Programms durchführt, also seine Struktur prüft. Ein Fehler auf dieser Ebene heißt dementsprechend syntaktischer Fehler. Wie zuvor erläu­tert, ist wegen der Klammerungsebenen dafür mindestens ein Kellerautomat erforderlich, bei den meisten Program­mier­sprachen darüber hinaus zusätzliche Hilfsmittel wie z.B. eine Symboltabelle (als Verzeichnis schon deklarier­ter Variablen, Funktionen usw.). Das Ergebnis dieser Phase ist oft ein Syntaxbaum, der die Hierarchie des Programms wiedergibt. In diesem Baum besteht z.B. das Programm aus Klassen, die Klassen aus Attributen und Methoden, die Methoden aus Kopf und Rumpf, ein Methodenrumpf aus Anweisungen usw.

Anschließend (in vielen Compilern auch schon gleichzeitig mit dem Parsing) wird als Ausgabe natürlich noch das compilierte, lauffähige Programm erzeugt.

Durch die Theorie der formalen Sprachen und der zugehörigen Automaten hat sich das Erstellen von Compilern drastisch vereinfacht. Der erste FORTRAN-Compiler wurde in den 50er Jahren noch vollständig von Hand programmiert, was einen Aufwand von 18 Mannjahren(!) verursacht haben soll²⁶ . Die Erstellung des Scanners hingegen erledigt heute ein Generator: Die Entwickle- rin muss nur noch die Tokens mit regulären Ausdrücken beschreiben – der zugehörige NEA wird automatisch erzeugt, in einen DEA umgewandelt und minimiert. Anschließend erzeugt der Generator sogar noch ein Programm, das die lexikalische Analyse durchführt. Mit etwas Übung baut man damit den Scanner für eine nicht allzu komplizierte Programmiersprache innerhalb weniger Stunden oder Tage. Der Parser (der auf einem Kellerautomat basiert) wird auf ähnliche Weise aus einer Grammatik erzeugt, die die Struktur der zu compilierenden Sprache beschreibt. Zwar ergeben Scanner und Parser noch keinen vollständigen Compiler; trotzdem lässt sich der Gewinn durch Übersichtlichkeit, Flexibilität und Zeitersparnis gar nicht hoch genug einschätzen!

Scanner- und Parsergeneratoren wurden vor allem dadurch möglich, dass die Theorie der formalen Sprachen und ihrer Automaten so gründlich verstanden ist. Diese Hilfsmittel und etwas Didaktik erlauben es sogar, kleine Compiler binnen einiger Unterrichtswochen im Unterricht von Schülern erstellen zu lassen (zumindest im Leistungsfach).

Hier zeigen sich zwei Eigenheiten der Informatik, die der Unterricht bei solchen Gelegenheit auch gerne hervorheben darf:

• Erstens geht Informatik recht einfallsreich mit Sprache um: Informatikerinnen benutzen nämlich Sprache nicht nur, um damit anspruchsvolle Ideen auszudrücken – wir sind viel kreativer und erfinden sogar bei Bedarf Spezialsprachen, die wir auf bestimmte Zwecke passgenau zuschneiden. Welche Anglistin, welcher Philologe hat das jemals getan? Java, Assembler, SQL, XML und HTML sind Beispiele künstlicher Sprachen, die alle besondere Eigenschaften haben und sich für ihren speziellen Zweck jeweils besonders gut eignen. Der Informatikunterricht behandelt einige solche Sprachen, und tatsächlich bezeichnet in der Informatik sogar fast jede Abkürzung auf -L irgendwas mit „language“. Techniken wie reguläre Ausdrücke und Grammatiken dienen gar als Meta-Sprachen für die Beschreibung eben dieser Sprachen – wo sonst außer in der Informatik lernen Schülerinnen so etwas kennen?
• Zweitens ist es vor allem sehr gut verstandene Theorie, die die erwähnten Generatoren mit ihren ungeheuren praktischen Auswirkungen möglich macht. Hier bewahrheitet sich mal wieder das Bonmot

Nichts ist so praktisch wie eine gute Theorie.

 

²⁶ Quelle: http://web.cs.wpi.edu/~kal/comp409/overview.html

 

Hintergrundinformationen: Herunterladen [odt][669 KB]

 

Weiter zu Materialien