Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung...

Automatensimulator

Klaus Becker

2006

2 Miniprojekt „Automatensimulator“

Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung und Programmierung wiederholen Einen Einblick in das Arbeiten mit dynamischen Datenstrukturen

(Liste, Baum) gewinnen

3 Teil 1

Entwicklung eines einfachen Automatensimulators

4 Zielsetzung

Ziel ist es, einen einfachen Automatensimulator zu entwickeln.

5 Anforderungen

Grundversion

/1/ Der Simulator wird für einen ganz bestimmten Automaten konzipiert (hier: zur Erkennung von Email-Adressen).

/2/ Der Benutzer kann ein beliebiges Wort (über dem zu Grunde liegenden Alphabet) eingeben.

/3/ Der Simulator analysiert dieses Wort und zeigt das Ergebnis am Ende der Simulation an.

/4/ Während des Analysevorgangs werden die jeweils durchlaufenen Zustände des Automaten angezeigt.

6 Anforderungen

Erweiterungsmöglichkeiten

/1/ Die Zeichen des zu Grunde liegenden Alphabets können auch komplexere Einheiten (beliebige Zeichenketten) sein. Wenn man z. B. als Alphabet die Menge {<b>, </b>, <p>, </p>} wählt, dann könnte man über diesem Alphabet das Wort <b><p></p><p></p></b> bilden. Ein Automat könnte demnach die Struktur von solchen „Tag“-Wörtern untersuchen.

/2/ Ein „echter“ Simulator kann beliebige Automaten simulieren. Damit das möglich wird, soll der Simulator eine geeignete Automatenbeschreibung einlesen können und gemäß dieser Automatenbeschreibung agieren. Günstig wäre es, wenn der zu entwickelnde Simulator kompatibel mit JFlap wäre und das Automatenbeschreibungsformat unterstützen würde, das JFlap beim Abspeichern eines Automaten benutzt.

7 Objektorientierte Analyse

Welche „Einheiten“ mit klaren Zuständigkeitsbereichen gibt es in der Miniwelt?

Eingabewort: c@ab.a

Ergebnis: ok!

Miniwelt

8 Identifikation der Objekte

Eingabewort: c@ab.a

Ergebnis: ok!

Miniwelt

automatsimulatorverwaltet d. aktuellen Zustand; führt Zustandsübergänge in Abhängigkeit d. Eingaben aus

zerlegt schrittweise d. Eingabewort und aktiviert d. Automaten;erzeugt das Ergebnis

Modell

9 Klassenentwurf

Eingabewort: c@ab.a

Ergebnis:

TAutomat

zustand

! anfangszustand! naechsterZustand(eingabe)? endzustand? fehlerzustand

TSimulator

fertigergebnisbereitsVerarbeitetaktuellzuVerarbeiten

! initialisieren! verarbeiteZeichen

Bereits verarbeitete Zeichen: c@a

Aktuelles Zeichen: b

Noch zu verarbeitende Zeichen: .a Zustand: q3

kennt

10 Detail-Spezifikation

TAutomat

- zustand: integer

+ create+ anfangszustand+ naechsterZustand(eingabe: char)+ endzustand: boolean+ fehlerzustand: boolean+ getZustand: integer

TSimulator

- fertig: boolean- ergebnis: boolean- bereitsVerarbeitet: string- aktuell: char- zuVerarbeiten: string- automat: TAutomat

+ create(a: TAutomat)+ initialisieren+ verarbeiteZeichen+ getFertig: boolean+ getErgebnis: boolean+ getAktuell: string+ getBereitsVerarbeitet: string+ getZuVerarbeiten: string

kenntd.

Einfachheit halbervorerst

11 Aufgabe

Implementieren Sie zunächst die Klasse „TAutomat“. Objekte dieser Klasse sollen vereinfachte Email-Adressen analysieren können. Testen Sie diese Klasse mit Hilfe einer sehr einfachen Testumgebung.

12 Aufgabe

Implementieren Sie die Klasse „TSimulator“. Zum Testen können Sie die fertige Benutzungsoberfäche im Verzeichnis „Automatensimulator10“ benutzen.

13 Teil 2

Exkurs: Listen, Stapel, Schlangen

14 Zielsetzung

Wenn die Zeichen des zu Grunde liegenden Alphabets komplexere Einheiten (beliebige Zeichenketten) sein können, dann benötigt man eine geeignete Datenstruktur, um Wörter über diesem Alphabet verwalten zu können. Das Alphabet könnte beispielsweise die Menge {<b>, </b>, <p>, </p>} sein. Zur Verwaltung von Wörtern über diesem Alphabet wie z. B. <b><p></p><p></p></b> benötigt man eine Datenstruktur, die eine beliebig lange Folge von komplexeren Zeichen verwalten kann.

Eingabewort: <b><p></p><p></p></b>

Ergebnis:

Bereits verarbeitete Zeichen: <b><p>

Aktuelles Zeichen: </p>

Noch zu verarbeit. Zeichen: <p></p></b>

15 Listen

Eine Liste ist eine Datenstruktur, mit der man eine endliche, beliebig lange Folge von Elementen verwalten kann. An beliebiger Stelle können vorhandene Elemente gelöscht bzw. neue Elemente eingefügt werden.

loeschen einfuegen

16 Schlange

Eine Schlange ist eine Datenstruktur, der nach dem FIFO-Prinzip (first in, first out) arbeitet:

mitLetztem erstes ohneErstes

Als letztes Element

hinzufügen

liefert das erste Element

das erste Element

entfernen

17 Stapel

Ein Stapel / Keller ist eine Datenstruktur, der nach dem LIFO-Prinzip (last in, first out) arbeitet:

mitErstempush

erstestop

ohneErstespop

Als erstes Element

hinzufügen

liefert das erste Element

das erste Element

entfernen

18 Aufgabe

Delphi stellt u. a. eine Klasse TStringList zur Verwaltung von Listen mit Elementen vom Typ String zur Verfügung. Benutzen Sie die Delphi-Hilfe, um sich mit den Details der Attribute und Methoden dieser Klasse vertraut zu machen.

TStringList

+ Count: integer+ Strings[Index: Integer]: string+ Text: string...

+ create+ Delete(Index: Integer)+ Insert(Index: Integer; const S: string)...

„property“

19 Aufgabe

Die hier vorgegebene Klasse „TMyStringList“ dient dazu, den Zugriff auf das erste und letzte Listenelement zu erleichtern und so Schlangen und Stapel mit Elementen vom Typ String einfach verwalten zu können. Diese Klasse ist als Erweiterung der von Delphi vorgegebenen Klasse „TStringList“ konzipiert.

Schauen Sie sich die Implementierung dieser Klasse an (Datei: uMyStringList).

unit uMyStringList;

interface

uses classes {TStringList};

type

TMyStringList = class(TStringList) private public constructor create; procedure leeren; function istLeer: boolean; function erstes: string; procedure ohneErstes; procedure mitErstem(s: string); function letztes: string; procedure ohneLetztes; procedure mitLetztem(s: string); function getAnzahl: integer; function getElement(i: integer): string; function getListeAlsString: string; end;

20 Aufgabe

Ziel ist es, die Funktionalitäten der Klasse TMyStringList zu testen. Ein Eingabewort vom Typ TStringList soll zunächst „übernommen“ werden und dann Zeichen für Zeichen „verarbeitet“ (hier kopiert) werden.

<b><p></p><p></p></b>

übernehmen

<p></p><p></p></b> <b>

<b> </p><p></p></b> <p>

verarbeiten

<b><p> <p></p></b> </p>

verarbeiten

<b><p></p> </p></b> <p>

verarbeiten

...

21 Aufgabe

Hinweise:Benutzen und ergänzen Sie das vorgegebene Delphi-Projekt im Verzeichnis „Listenverarbeitung0“. Beachten Sie, dass ein Listenobjekt (vom Typ „TMyStringList“) zunächst erzeugt werden muss, bevor es zur Verwaltung von Daten benutzt werden kann.Benutzen Sie ein „Memofeld“ zur Eingabe einer Folge von Zeichenketten. Beachten Sie, dass „MEingabe.Lines“ ein Ergebnis vom Typ „TStringList“ liefert, das zunächst mit „TMyStringList(MEingabe.Lines)“ in den spezielleren Typ „TMyStringList“ umgewandelt werden muss, bevor es als spezielle Liste vom Typ „TMyStringList“ weiterverarbeitet werden kann. <b><p></p><p></p></b>

… e: TMyStringList;

...

e := TMyStringList.create;

e := TMyStringList(MEingabe.Lines);

MEingabe: TMemo

22 Aufgabe

Entwickeln Sie einen Automatensimulator, mit dem man „HTML-artige“ Tag-Strukturen analysieren kann. Sie können die vorgegebene Benutzungsoberfläche im Verzeichnis „Automatensimulator20“benutzen.

23 Teil 3

Exkurs: Bäume

24 Zielsetzung

Ein „echter“ Simulator kann beliebige Automaten simulieren. Damit das möglich wird, soll der Simulator eine Automatenbeschreibung einlesen können und gemäß dieser Automatenbeschreibung agieren.

abba@caba.bb

Simulator

Ok!

25 Aufgabe

Schauen Sie sich mit einem Texteditor an, wie JFlap die eingegebenen Automaten abspeichert.

26 Automatenbeschreibung mit XML

Eine Automatenbeschreibung sollte möglichst in einem standardisierten Format erfolgen. Günstig ist es, die Dokumentenbeschreibungssprache XML für diesen Zweck zu nutzen. Wir werden im Folgenden die XML-Darstellung von JFlap nutzen.

<?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>

<type>fa</type><!--The list of states.--><state id="0">

<x>60.0</x><y>59.0</y><initial />

</state><state id="1">

<x>147.0</x><y>59.0</y>

</state>...<!--The list of transitions.--><transition>

<from>2</from><to>3</to><read>c</read>

</transition>...

</structure>EmailDA1.jff

27 Dokumentenbeschreibung mit XML

<?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>

<type>fa</type><!--The list of states.--><state id="0">

<x>60.0</x><y>59.0</y><initial />

</state><state id="1">

<x>147.0</x><y>59.0</y>

</state>...<!--The list of transitions.--><transition>

<from>2</from><to>3</to><read>c</read>

</transition>...

</structure>

Die Extensible Markup Language (engl. für „erweiterbare Auszeichnungs-Sprache“), abgekürzt XML, ist ein Standard zur Erstellung maschinen- und menschenlesbarer Dokumente in Form einer Baumstruktur, der vom World Wide Web Consortium (W3C) definiert wird. Siehe: http://de.wikipedia.org/wiki/XML

28 Aufgabe

Schauen Sie sich eine XML-Darstellung eines Automaten mit einem neueren Browser an. Machen Sie sich die Baumstruktur des Dokumentes klar.

Darstellung der XML-Datei EmailDA.jff mit Firefox

29 Baumstruktur

state

x

#text: 60.0

type

#text: fa

#comment:

#document

Id: 0

y

#text: 59.0

initial

<?xml version="1.0"?><!-- Created with JFLAP 4.0b13. --><structure>

<type>fa</type><!--The list of states.--><state id="0">

<x>60.0</x><y>59.0</y><initial />

</state>...

</structure>

#comment:

structure

state Id: 1

30 Baumstruktur

state

x

#text: 60.0

type

#text: fa

#comment:

#document

y

#text: 59.0

initial

#comment:

structure

state

Knoten

Wurzel

BlattEin Baum ist eine dynamische Datenstruktur, die mit Hilfe von Knoten aufgebaut wird.

31 Baum-Organisation

state

x

#text: 60.0

type

#text: fa

#comment:

#document

y

#text: 59.0

initial

#comment:

structure

state

PreviousSibling

FirstChild

LastChild

ParentNode

NextSibling

Operationen nach „OpenXML“

Grafik in: Introducing the Document Object Model using OpenXML (Part 1) by Craig Murphy

32 Realisierung mit Zeigern

state

x

#text: 60.0

type

#text: fa

#comment:

#document

y

#text: 59.0

initial

#comment:

structure

state

PreviousSibling

FirstChild

LastChild

ParentNode

NextSiblingObjekt vom

Typ TDomNode

Referenz-attribute

Zeiger: verwaltet Adresse einer Speicherzelle

nil: Zeiger, d. a. nichts zeigt

33 OpenXML

„Open XML is a collection of XML and Unicode tools and components for the Delphi/Kylix™ programming language. All packages are freely available including source code.“

Siehe: http://www.philo.de/xml/index.shtml

34 Installation von OpenXML

Sie benötigen die „Utility Library v.2.0.9“ und das „Extended Document Object Model v.3.2.1“-Paket (siehe http://www.philo.de/xml/downloads.shtml).

Starten Sie die passenden Installationsdateien „UtilitiesD...“ und „Xdom_3_2Delphi...“ und folgen Sie jeweils den Anweisungen.

35 Die Klasse TDomNode

TDomNode

+ ParentNode: TDomNode+ FirstChild: TDomNode+ LastChild: TDomNode+ PreviousSibling: TDomNode+ NextSibling: TDomNode...+ NodeName+ NodeValue+ Attributes...

...

„property“

36 Erzeugung eines DOM-Baumes

doc: TDomDocument; // WurzelaktuellerKnoten: TDomNode;

...

// wandle Stringliste aus Memofeld in einen String um docString := MBeschreibung.Text;

// lösche die Zeilenumbrüche etc.docString := NormalizeWhiteSpace(docString);

// lösche die verbleibenden LeerzeichendocString := ersetze('> <', '><', docString);

// initialisiere die Referenz vom Parser XmlToDomParser1.DOMImpl := DomImplementation1;

// wandle d. XML-Beschreib. i. String-Form um i. e. DOM-Baum doc := XmlToDomParser1.stringToDom(docString, '', nil, true);

37 Baumdurchlauf

aktuellerKnoten := doc aktuellerKnoten := aktuellerKnoten.FirstChild

38 Baumdurchlauf

aktuellerKnoten := aktuellerKnoten.NextSibling

39 Aufgabe

Öffnen Sie das Delphi-Projekt im Verzeichnis „DOMBaum0“. Das begonnene Programm kann bereits eine XML-Datei in ein Memo-Feld laden, diese Textdarstellung in einen DOM-Baum umwandeln und die Operation „FirstChild“ ausführen. Ergänzen Sie die fehlenden Implementierungen der vorgesehenen Steuerungsschaltflächen.

Testen Sie das entwickelte System zum manuellen Durchlaufen eines DOM-Baumes.

40 Hinweis

Eine Lösung finden Sie im Verzeichnis „DOMBaum1“.

Im Verzeichnis „DOMBaum2“ finden Sie eine erweiterte Fassung, die den DOM-Baum mit weiteren Hilfsobjekten visualisiert.

41 Zugriff auf die „Knoteninhalte“

var attribute: tDomNodeList; attributeAlsString: string; i: integer;begin PName.Caption := aktuellerKnoten.nodeName; attributeAlsString := ''; if aktuellerKnoten.hasAttributes then begin attribute := aktuellerKnoten.attributes; for i := 0 to attribute.Length-1 do attributeString := attributeString + attribute.Item(i).nodeName + ': ' +attribute.Item(i).nodeValue + ' '; end; PAttribute.Caption := attributeString; PWert.Caption := aktuellerKnoten.NodeValue;end;

42 Aufgabe

Öffnen Sie das Delphi-Projekt im Verzeichnis „Automatensimulator30“. Schauen Sie sich die Implementierung der Klasse „TAutomat“ genauer an. Machen Sie sich am Beispiel der Methode „anfangszustand“ klar, wie man die benötigten Informationen aus dem DOMBaum erhalten kann.

Versuchen Sie, analog die Methode „naechsterZustand“ zu implementieren. Eine Lösung finden Sie im Verzeichnis „Automatensimulator31“.

43 Literaturhinweise

Weitere Hinweise zur Entwicklung von Automatensimulatoren finden man bei

K. Merkert:http://hsg.region-kaiserslautern.de/faecher/inf/material/automaten/getraenke/index.php