43
Automatensimulator Klaus Becker 2006

Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

Embed Size (px)

Citation preview

Page 1: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

Automatensimulator

Klaus Becker

2006

Page 2: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

2 Miniprojekt „Automatensimulator“

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

(Liste, Baum) gewinnen

Page 3: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

3 Teil 1

Entwicklung eines einfachen Automatensimulators

Page 4: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

4 Zielsetzung

Ziel ist es, einen einfachen Automatensimulator zu entwickeln.

Page 5: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 6: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 7: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

7 Objektorientierte Analyse

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

Eingabewort: [email protected]

Ergebnis: ok!

Miniwelt

Page 8: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

8 Identifikation der Objekte

Eingabewort: [email protected]

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

Page 9: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

9 Klassenentwurf

Eingabewort: [email protected]

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

Page 10: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 11: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 12: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

12 Aufgabe

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

Page 13: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

13 Teil 2

Exkurs: Listen, Stapel, Schlangen

Page 14: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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>

Page 15: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 16: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 17: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 18: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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“

Page 19: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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;

Page 20: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

...

Page 21: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 22: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 23: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

23 Teil 3

Exkurs: Bäume

Page 24: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

[email protected]

Simulator

Ok!

Page 25: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

25 Aufgabe

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

Page 26: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 27: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 28: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 29: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 30: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 31: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 32: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 33: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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

Page 34: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 35: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

35 Die Klasse TDomNode

TDomNode

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

...

„property“

Page 36: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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);

Page 37: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

37 Baumdurchlauf

aktuellerKnoten := doc aktuellerKnoten := aktuellerKnoten.FirstChild

Page 38: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

38 Baumdurchlauf

aktuellerKnoten := aktuellerKnoten.NextSibling

Page 39: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 40: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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.

Page 41: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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;

Page 42: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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“.

Page 43: Automatensimulator Klaus Becker 2006. 2 Miniprojekt Automatensimulator Zielsetzung Spracherkennung mit Automaten vertiefen Objektorientierte Modellierung

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