Automaten in Source Code

[Christian18]

Hallo,

ich beschäftige mich gerade mit Automaten. Ich habe gelernt viele Probleme damit zu lösen, die ich vorher noch nicht lösen konnte. Nun wollte ich mich damit beschäftigen, meine Ideen in Quellcode umzusetzen. Hat jemand eine Idee, wie mach das machen kann?

Vieleicht hat jemand auch ein kleinen Beispielautomat mit Source Code.

Vielen Dank im vorraus.

MfG Christian18

[Codewalker]

Ich gehe mal davon aus, du meinst einen endlichen Automaten. Prinzipiell ist es eine verschachtelte Case-Abfrage. Die äußere fragt ab, in welchem Zustand der Automat sich gerade befindet und jede innere fragt ab, welche Transition gewählt werden muss.

Ein Automat mit 3 Zuständen (q0,q1,q2) und einem Alphabet 'a' und 'b' wäre dann prinzipiell z.B. so:

Delphi-Quellcode:

{...}
case AktuellerZustand of
 q0:  case Zeichen of
      'a': // Führe Transition von q0 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
 q1:  case Zeichen of
      'a': // Führe Transition von q1 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
 q2:  case Zeichen of
      'a': // Führe Transition von q2 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
end;

[Christian18]

Hallo,

vielen Dank für deine Antwort. Wie Automaten funktionieren, habe ich verstanden. Ich lese immer nur bezüge auf ein Alphabet. Die Beispiele die ich habe nutzen auch immer nur das Alphabet. Kann es sein, das man Automaten nur in Kombination mit Strings verwenden kann?

So den richtigen Sinn habe ich glaube noch nicht so wirklich verstanden. Meiner Meinung nach würde ich sagen, kann ich Probleme auch mit weniger SourceCode lösen. Wozu dient also dieses "Konzept"?

MfG Christian18

[himitsu]

Strings werden wohl nur zufällig genommen

im Prinzip ist ein Zeichen/Char auch nur ein ordinaler Typ und man könnte stattdessen auch jeden anderen ordinalen Typen nehmen

Delphi-Quellcode:

while ... do
  case zustand of
    z0: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    z1: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    z2: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    ....
  end;

[Christian18]

Ich bin gerade noch ein bisschen am überlegen, ob man folgendes Problem mit Automaten lösen könnte.

Ich habe einen String:

123;321;keine_ahnung

Der Automat soll diesen String nun auseinander nehmen. Genau an den stellen, so die ; sind.

Also habe ich einen Start Zustand q0. In diesem soll er immer bleiben, wenn kein ; kommt.

Wenn ein ; kommt, dann soll er in den Zustand q1 wechseln. Der Theorie ist ja gar nicht so schwierig. Also müsste das eigentlich mit Automaten funktionieren. Aber wie würde das in SourceCode aussehen.

MfG Christian18

[SebE]

boah, war schon ewig nicht mehr hier - ich versuchs mal:

Delphi-Quellcode:

type
  zustant = (q0, q1);

var
  i, sLen: integer;
  s: zustand;
  b, r: string;

begin
i := 1;
sLen := length(b);
s := q0;
r := '';

while (i <= sLen do) begin
    case s of
    q0: begin
      if b[i] = ';' then
        s := q1
      else r := r + s[i]
      end;
    q1: begin // ";" gelesen
      writeln(r);
      r := '';
      s := q0
      end
    end;

  i := i  + 1
  end;

[SebE]

Das obige Beispiel (kann Fehler beinhalten) zeigt - ich nenn's mal - die "direkte" Möglichkeit mit Automaten zu arbeiten.

Eigentlich ist jedes Program ein Automat (man siehts es nur nicht auf den ersten Blick):
Nimm alle Variablen, die du verwendest zusammen - diese ergeben deinen "Zustand", dein Programm reagiert dann in Abhängigkeit dieses Zustandes.

Wenn man Rekursionen einbaut muss man den Stack-Inhalt (inkl. die Tiefe der Rekursion) als Teil des Zustandes zählen.
Hier sind wir dann schnell bei Parsern (Compilerbau) angelangt.

Damit kannst du dann "richtige" Grammatiken verwenden.

Deine (einfache) Grammatik sah so aus:
start ::= Text {";" Text}.
Text ::= { <alle Zeichen> }.

Mit Rekursionen geht auch folgendes ganz leicht:
Start ::= Anweisung.
Anweisung ::= Schleife1 | Schleife2 | ... .
Schleife1 ::= "REPEAT" Anweisung "UNTIL" Ausdruck.
Schleife2 ::= "WHILE" Ausdruck "DO" Anweisung.
...

Wollt ich einfach nochmal anbringen - mich interessiert das Thema Automaten (und Parserbau) auch :-)

[JasonDX]

Zitat:

Zitat von SebE

Eigentlich ist jedes Program ein Automat

Wenn wir von regulären Automaten sprechen, ist das nicht richtig. Reguläre Automaten sind deutlich ausdrucksärmer als Programme/Turingmaschinen/Lamdaterme.
Als Beispiel: Kein regulärer Automat dieser Welt kann x*x ausrechnen (Beweisbar durch Myhill-Nerode).

greetz
Mike

btw, zum Topic: Ein Theoretiker würde den Automaten in eine Regex umwandeln, und dann dafür existierende Funktionen verwenden :D

[alzaimar]

Mit Case würe ich das nie und nimmer machen: Viel zu umständlich und zu unübersichtlich.
Ich mache das so:
1. Eingabealphabet definieren
2. Zustandsgraph aufzeichnen
3. Zustände durchnummerieren.
4. Zustandsübergangstabelle erstellen (Spalten = Alphabet, Zeilen = Zustände aus (3))

Delphi-Quellcode:

Procedure DEA (aInput : TAlphabetStream);
Begin
  State := START;
  While Not (State in [ERROR, STOP]) Do
    State := DEA[State, NextToken(aInput)];
    ProcessState(State);
  End;
  If State = ERROR Then
    ShowError
  else
    Success;
End;

Damit lassen sich dann alle DEAs dieser Welt abarbeiten.

[SebE]

Das mit der Automatentabelle ist auch eine gute Idee (wie's bei Bottom-Up-Parsern gemacht wird).
Muss man abwägen (Gesachmackssache).

Ich finde die Case-Variante übersichtlicher und EVTL. auch schneller erweiterbar.
Die Tabelle wird in manchen Fällen einfach nur (physikalisch) groß (Beispiel: viele Zustände mit dem gleichen Verhalten).

@JasonDX:

Zitat:

Wenn wir von regulären Automaten sprechen, ist das nicht richtig.

Ich hab mich aber nicht auf DEAs festgelegt ;-)

[markusj]

Man könnte sogar schön objektorientiert arbeiten und für jeden Zustand eine Klasse definieren - damit erspart man sich ellenlange Case-Strukturen ;)

mfG
Markus

[Codewalker]

Zitat:

Zitat von markusj

Man könnte sogar schön objektorientiert arbeiten und für jeden Zustand eine Klasse definieren - damit erspart man sich ellenlange Case-Strukturen

Wobei ich zu behaupten wage, dass auch eine große case-Struktur effektiveren Assembler ergibt, also eine entsprechende Automatenkonstruktion mit Objekten. Aber da lasse ich mich gerne eines besseren belehren.

[Meflin]

Zitat:

Zitat von Christian18

Kann es sein, das man Automaten nur in Kombination mit Strings verwenden kann?

Bitte wie kommst du darauf :gruebel: Valide Eingaben eines Automaten könnten auch Gras, Wasser und TK-Pizza sein. Kommt halt auf den Automaten an (oder Integer, Bools, Floats, ...).

[SebE]

Zitat:

Zitat von markusj

Man könnte sogar schön objektorientiert arbeiten und für jeden Zustand eine Klasse definieren - damit erspart man sich ellenlange Case-Strukturen ;)

mfG
Markus

Wie soll denn das aussehen?

Ist mein abstrakter Zustand vom Typ Basisklasse und jeder aktuelle (reale) Zusatnd dann von einer abgeleiteten Klasse?
(das wären sehr viele speicheroperationen)

Ich bitte um Aufklärung

[alzaimar]

Zitat:

Zitat von SebE

Ich finde die Case-Variante übersichtlicher und EVTL. auch schneller erweiterbar.
Die Tabelle wird in manchen Fällen einfach nur (physikalisch) groß (Beispiel: viele Zustände mit dem gleichen Verhalten).

Nun ja. Was ist schon groß? Der Code mit 'CASE' sieht bei mehr als -sagen wir- 20 Zuständen auch nicht gerade übersichtlich aus (Spaghetti-Code). Bei einer DEA-Tabelle habe ich den Vorteil, das der eigentliche Code sehr übersichtlich ist. Und der Automat kann anhand der Tabelle extern abgelegt, automatisch generiert oder direkt gezeichnet werden. Bei einer CASE-Struktur tut man sich damit schon schwer.

Bei komplexeren (N)DEA würde ich eh zu einem Tool wie LEX/YACC greifen. Dann ist mir die interne Implementierung wurscht, und ich kann mich auf die Aktionen der Zustände konzentrieren.

Zitat:

Zitat von SebE

Ist mein abstrakter Zustand vom Typ Basisklasse und jeder aktuelle (reale) Zustand dann von einer abgeleiteten Klasse?

So vielleicht?

Delphi-Quellcode:

Type
  IAbstractState = Interface
  Public
     Function NextState (Token : TSymbol) : IAbstractState; 
     Procedure DoProcessState; 
     Function IsStopState : Boolean;
     Function IsErrorState : Boolean;
  End;
...
  State := CoStartState.Create;
  While Not State.IsStopState Do Begin
    State := State.NextState; 
    State.DoProcessState();
  End;

Jeder Zustand implementiert o.g. Interface. Fertig.

Zitat:

(das wären sehr viele speicheroperationen)

Ja und? In Zeiten von 8xCore 6GHz Prozessoren eher zweitrangig. Übersichtlichkeit und Erweiterbarkeit sind heutzutage wichtiger als Performance. Und wenn du schnell sein willst, nimm eben eine Tabelle oder von mir aus eine ewig lange CASE-Struktur. Die Performanceunterschiede würden mich mal interessieren. Ein CASE wird ja nicht als JUMP-Tabelle abgebildet, sondern als Kette von Vergleichen auf 0 und Subtraktionen ...

[jfheins]

Zitat:

Zitat von alzaimar

Ein CASE wird ja nicht als JUMP-Tabelle abgebildet, sondern als Kette von Vergleichen auf 0 und Subtraktionen ...

Sicher? http://www.delphipraxis.net/internal...=280190#280190

[himitsu]

Zitat:

Delphi-Quellcode:

State := CoStartState.Create;
While Not State.IsStopState Do Begin
  State := State.NextState;
  State.DoProcessState();
End;

ich würde es dann eher so machen

Delphi-Quellcode:

State := CoStartState.Create;
While Not State.IsStopState Do Begin
  State.DoProcessState();
  State := State.NextState;
End;

so würde der StartState auch verarbeitet
und im Fall eines StopStates würde die Schleife auch verlassen, bevor der StopState verarbeitet würde.

Delphi-Quellcode:

Type
  IAbstractState = Interface
  Public
     Function NextState (Token : TSymbol) : IAbstractState;
     Procedure DoProcessState;
     Function IsStopState : Boolean;
     Function IsErrorState : Boolean;
     Function GetErrorText : WideString;
  End; 

State := CoStartState.Create;
While Not State.IsStopState and Not State.IsErrorState Do Begin
  State.DoProcessState();
  State := State.NextState;
End;
If State.IsErrorState Then ShowError(State.GetErrorText);

[Reinhard Kern]

Hallo,

bei µP in Assembler war das noch herrlich einfach und klar: ein Zustandsautomat mit n Zuständen und m Ereignissen war softwaremässig eine n x m grosse Sprungtabelle. Bei geeigneter Namensgebung war das schon fast selbstdokumentierend. Ausserdem fiel gleich auf, wenn das Programm unvollständig war, weil im Zustand x für das Ereignis y keine geeignete Reaktion definiert war.

Nun gibt es eigentlich in Pascal keine Sprünge, aber zusammenbauen könnte man sich so eine Tabelle schon und an jedem Schnittpunkt eine Prozedur für das Ereignis y im Zustand x eintragen. Natürlich ist das einer 2 fach verschachtelten Case-Struktur völlig gleichwertig. Aber wenn man das im Source-Code auch als n x m Tabelle schreiben kann, wird es sehr übersichtlich.

Gruss Reinhard

[SebE]

So Leute, ich hab mal die "reine imperative" und die tabellengesteuerte Variante implementiert (haben beide auf Anhieb funktioniert ;-))

Achso: die Automaten lesen eine Kommazahl und ersetzten das "," zu "-".

Delphi-Quellcode:

unit Imperative;

interface

type
  state = (sStart, sFrac, sTrunc, sStop);

type
  DEA_imperative = class
    private
      fInput,
      fOutput: string;
      fPos: BYTE;
      fState: state;
    public
      constructor _create(const input: string);
      destructor _destroy;

      procedure _execute;

      function _getOutput: string;
    end;

implementation

constructor DEA_imperative._create(const input: string);
begin
fInput := input + #0
end;

destructor DEA_imperative._destroy;
begin

end;

procedure DEA_imperative._execute;
begin
fPos := 1;
fState := sStart;
fOutput := '';

while fState <> sStop do begin
    case fState of
    sStart:
        case fInput[fPos] of
        '1'..'9': begin
          fOutput := fInput[fPos];

          fState := sTrunc
          end
        else fState := sStop
        end;
    sTrunc:
        case fInput[fPos] of
        '1'..'9': fOutput := fOutput + fInput[fPos];
        ',': begin
          fOutput := fOutput + '-';

          fState := sFrac
          end
        else fState := sStop
        end;
    sFrac:
        case fInput[fPos] of
        '1'..'9': fOutput := fOutput + fInput[fPos];
        else fState := sStop
        end
    end;

  fPos := fPos + 1
  end
end;

function DEA_imperative._getOutput: string;
begin
_getOutput := fOutput
end;

end.

Delphi-Quellcode:

unit TableControlled;

interface

type
  state = (sStart, sTrunc, sTruncToFrac, sFrac, sStop);

type
  DEA_tablecontrolled = class
    private
      fTable: array[sStart..sFrac] of array[CHAR] of state;
      fInput,
      fOutput: string;
      fPos: BYTE;
      fState: state;
    public
      constructor _create(const input: string);
      destructor _destroy;

      procedure _execute;

      function _getOutput: string;
    end;

implementation

constructor DEA_tablecontrolled._create(const input: string);
var
  i: CHAR;
begin
fInput := input + #0;

for i := #0 to #225 do begin
  fTable[sStart][i] := sStop;
  fTable[sTrunc][i] := sStop;
  fTable[sTruncToFrac][i] := sStop;
  fTable[sFrac][i] := sStop
  end;

fTable[sStart]['0'] := sTrunc; //KANN MAN DIE TABELLE "SCHÖNER" FÜLLEN?
fTable[sStart]['1'] := sTrunc;
fTable[sStart]['2'] := sTrunc;
fTable[sStart]['3'] := sTrunc;
fTable[sStart]['4'] := sTrunc;
fTable[sStart]['5'] := sTrunc;
fTable[sStart]['6'] := sTrunc;
fTable[sStart]['7'] := sTrunc;
fTable[sStart]['8'] := sTrunc;
fTable[sStart]['9'] := sTrunc;

fTable[sTrunc]['0'] := sTrunc;
fTable[sTrunc]['1'] := sTrunc;
fTable[sTrunc]['2'] := sTrunc;
fTable[sTrunc]['3'] := sTrunc;
fTable[sTrunc]['4'] := sTrunc;
fTable[sTrunc]['5'] := sTrunc;
fTable[sTrunc]['6'] := sTrunc;
fTable[sTrunc]['7'] := sTrunc;
fTable[sTrunc]['8'] := sTrunc;
fTable[sTrunc]['9'] := sTrunc;

fTable[sTrunc][','] := sTruncToFrac;

fTable[sTruncToFrac]['0'] := sFrac;
fTable[sTruncToFrac]['1'] := sFrac;
fTable[sTruncToFrac]['2'] := sFrac;
fTable[sTruncToFrac]['3'] := sFrac;
fTable[sTruncToFrac]['4'] := sFrac;
fTable[sTruncToFrac]['5'] := sFrac;
fTable[sTruncToFrac]['6'] := sFrac;
fTable[sTruncToFrac]['7'] := sFrac;
fTable[sTruncToFrac]['8'] := sFrac;
fTable[sTruncToFrac]['9'] := sFrac;

fTable[sFrac]['0'] := sFrac;
fTable[sFrac]['1'] := sFrac;
fTable[sFrac]['2'] := sFrac;
fTable[sFrac]['3'] := sFrac;
fTable[sFrac]['4'] := sFrac;
fTable[sFrac]['5'] := sFrac;
fTable[sFrac]['6'] := sFrac;
fTable[sFrac]['7'] := sFrac;
fTable[sFrac]['8'] := sFrac;
fTable[sFrac]['9'] := sFrac
end;

destructor DEA_tablecontrolled._destroy;
begin

end;

procedure DEA_tablecontrolled._execute;
begin
fPos := 1;
fState := sStart;
fOutput := '';

while fState <> sStop do begin
  fState := fTable[fState][fInput[fPos]];

    case fState of //ich habe es mir gespart, die einzelnen Routinen in die Tabelle zu übernehmen
    sTrunc: fOutput := fOutput + fInput[fPos];
    sTruncToFrac: fOutput := fOutput + '-';
    sFrac: fOutput := fOutput + fInput[fPos]
    end;

  fPos := fPos + 1
  end
end;

function DEA_tablecontrolled._getOutput: string;
begin
_getOutput := fOutput
end;

end.

Fazit:
mit der Case-Variante beschreibt man die Zustandsaktion UND die Übergänge!
=> Weniger Zustände.

=> Meine Meinung: Case-Var. (in DIESEM Beispiel) besser.


Zur OOP-Variante hab ich eine Frage:
Nicht dass ich nicht mit Klassen, Vererbung, etc. umgehen kann, ich bring mir grad selbst die Konzepte bei (Probleme lösen mittels OOP)

Wie erzeugt man am besten die Zustände?
Im Beispiel steht:

Delphi-Quellcode:

State := CoStartState.Create;

erzeugt der StartZustand automatisch den "NextState" und das geht rekursiv immer so weiter bis StopZustand?

Ist das die "gute" OOP-Lösung?
Ich finde diese unübersichtlich und fehleranfällig.

Wie hat die OOP-Fraktion dieses Problem gelöst?

[Namenloser]

Zitat:

Zitat von SebE

Ist das die "gute" OOP-Lösung?
Ich finde diese unübersichtlich und fehleranfällig.

Wie hat die OOP-Fraktion dieses Problem gelöst?

Übersichtlichkeit liegt immer auch im Auge des Betrachters (*), aber wieso fehleranfällig?

(*) Ich z.B. finde deine Code-Formatierung sehr unübersichtlich.

[SebE]

@NamenLozer:

Fehleranfällig in der Hinsicht, dass man nicht SOFORT erkennt, wer was wo erzeugt.

Es ist besser, wenn die Zustände in der Gesamtheit von Anfang an "fest stehen", also existieren.

Zu meinem Code:
Wegen der BEGIN-END-Positionierung?
Jedem das seine, das meinte ich aber nicht, hier ist nicht die Formatierung das Thema, sondern die Semantik!

[Namenloser]

Zitat:

Zitat von SebE

Zu meinem Code:
Wegen der BEGIN-END-Positionierung?

Unter anderem, aber z.B. auch, dass du alle Methodennamen mit einem Unterstrich beginnst. Was soll das bitte?

[Mithrandir]

NamenLozer,

ist doch völlig Latte. :roll:

Es entspricht so zwar nicht dem Style Guide, auf den sich viele immer beziehen, aber es ist immernoch leserlich. Also wieder zurück zum Thema.

[alzaimar]

Zitat:

Zitat von SebE

...[/delphi]
.. //KANN MAN DIE TABELLE "SCHÖNER" FÜLLEN?
[/delphi]

Ja.
Da es dem Automaten egal ist, ob es sich um eine 1, 2 usw. handelt, kann man das drastisch verkürzen: Der DEA kennt nur Ziffern, Komma, das Terminalsymbol (Ende der Eingabe) sowie ungültige Zeichen. Da ungültige Zeichen zu einem sofortigen Abruch führen, wird die Tabelle ziemlich klein. So klein, wie das Problem, das der DEA lösen soll:

Delphi-Quellcode:

Const
  DEA : Array [symDigit..symTerminal, stStart..stDecimals] =
//           symDigit  , symKomma,    symTerminal
{stStart }  (stDigits  , stError    , stError),  
{stDigits}  (stDigits  , stComma    , stStop),   
{stComma}   (stDecimals, stError    , stError),  
{stDecimals}(stDecimals, stError    , stStop)
            );
// Natürlich implementiert man eine Funktion/Methode, die das nächste Symbol der Eingabe extrahiert, 
// klassifiziert und sowohl Symbolklasse als auch das Symbol selbst zurückliefert.

So sehr Du an dem Case-Konstrukt zu hängen scheinst, es verstößt gegen diverse Grundregeln des 'clean coding' (DRY, KISS), weshalb ich das persönlich ablehne. Das ist aber Geschmackssache.

Ich stell mir nur gerade ein Case-Konstrukt mit 1700 Zuständen vor, bei dem nur bei 3 Zuständen etwas passiert... :zwinker:
Bei der Implementierung als Tabelle habe ich die Tabelle in einer Resource. Diese Tabelle wurde vorher vermutlich automatisch generiert und ist daher fehlerfrei. Die Implementierung selbst ist extrem kompakt und übersichtlich.

Zitat:

Zitat von SebE

Nicht dass ich nicht mit Klassen, Vererbung, etc. umgehen kann...erzeugt der StartZustand automatisch den "NextState" und das geht rekursiv immer so weiter bis StopZustand?

Äh..Nein.

Zitat:

Zitat von SebE

Ist das die "gute" OOP-Lösung?

Imho schon.

Zitat:

Zitat von SebE

Ich finde diese unübersichtlich und fehleranfällig.

Nein. Jede Klasse, die das IAbstractState-Interface implementiert, MUSS Code für den Übergang zur nächsten Klasse implementieren, sowie den eigenen Zustand dokumentieren (IsStop, IsError). Spaghetti-Code ist hingegen unübersichtlich und fehleranfällig, da man sich jedesmal neu hineindenken muss und es ein leichtes ist, irgendwo einen Korken eingebaut zu haben (siehe unten)

Zitat:

Zitat von himitsu

ich würde es dann eher so machen...

Logisch, ich wollte nur den von mir einmal gemachten Fehler (im Codebeispiel für die Abarbeitung der Tabelle) nicht implizit korrigieren.

Zitat:

Zitat von Reinhard Kern

..in Assembler war das noch herrlich einfach ... war das schon fast selbstdokumentierend. Ausserdem fiel gleich auf, wenn das Programm unvollständig war, ... Natürlich ist das einer 2 fach verschachtelten Case-Struktur völlig gleichwertig. Aber wenn man das im Source-Code auch als n x m Tabelle schreiben kann, wird es sehr übersichtlich.

Siehe oben. :mrgreen:

Zitat:

Zitat von SebE

Fehleranfällig in der Hinsicht, dass man nicht SOFORT erkennt, wer was wo erzeugt.

@SebE: Ich habe deinen Code abgeschrieben. Er funktioniert nicht. Wieso?

Delphi-Quellcode:

unit Imperative;
interface

type
  state = (sStart, sFrac, sTrunc, sStop);

type
  DEA_imperative = class
    private
      fInput,
      fOutput: string;
      fPos: BYTE;
      fState: state;
    public
      constructor _create(const input: string);
      destructor _destroy;

      procedure _execute;

      function _getOutput: string;
    end;

implementation

constructor DEA_imperative._create(const input: string);
begin
fInput := input + #0
end;

destructor DEA_imperative._destroy;
begin

end;

procedure DEA_imperative._execute;
begin
fPos := 1;
fState := sStart;
fOutput := '';

while fState <> sStop do begin
    case fState of
    sStart:
        case fInput[fPos] of
        '1'..'9': begin
          fOutput := fInput[fPos];

          fState := sTrunc
          end
        else fState := sStop
        end;
    sTrunc:
        case fInput[fPos] of
        '1'..'9': fOutput := fOutput + fInput[fPos];
        ';': begin
          fOutput := fOutput + '-';

          fState := sFrac
          end
        else fState := sStop
        end;
    sFrac:
        case fInput[fPos] of
        '1'..'8': fOutput := fOutput + fInput[fPos];
        else fState := sStop
        end
    end;

  fPos := fPos + 1
  end
end;

function DEA_imperative._getOutput: string;
begin
_getOutput := fOutput
end;

end.

Man muss sich in den kompletten Code eindenken und ALLES lesen, bis man den Fehler gefunden hat.

[jfheins]

Nachdem ich sowas gerade in ner Übung vorgesetzt bekommen habe, äußere ich mich auch mal :)

Für kleine Aufgaben reicht definitiv ein case-Statement. Rückblickend (mir ist diese Woche erst in den Sinn gekommen dass diese Zustandsautomaten existieren und Sinn machen) muss ich allerdings sagen dass ein case-Statement schwer wartbar ist.

Für größere Sachen (die Grenze liegt je nach Geschmack woanders ... für mich vll. so bei 4x4 oder so) ist definitiv eine Tabelle von Vorteil.

Die Tabelle kann man dann auch in einer Datei ablegen, damit erübrigt sich auch die Frage, wie man eine 10x10 Tabelle übersichtlich im Source deklariert ^^

Das was ich letztens gemacht habe war so ne Art Drag 'n Drop um mit ein paar grafischen Objekten zu spielen. Es lief dann darauf hinaus, dass ich ein "CurrentTool" (Typ: Enum) habe, und in den Events (MouseDown, MouseMove und MouseUp) jeweils ein Case-Statement in dem dann ein paar Sachen gemacht werden. (Das Tool kann nur über Buttons am Rand geändert werden, in den Maus-Events finden also keine Tool-Änderungen statt)
Wenn man das mit so einer Tabelle machen würde, wären wahrscheinlich ganz schön viele Zustände dabei und ziemlich viele "Error-Zustände" - sobald ich den Überblick verliere werde ich das Programm entsprechend umgestalten ;)

[SebE]

@NamenLozer:
der Unterstrich macht mir deutlich, was MIR gehört und was vordefiniert (oder Compilermagic) ist.

@alzaimar:

Zitat:

SebE hat folgendes geschrieben:
Nicht dass ich nicht mit Klassen, Vererbung, etc. umgehen kann...erzeugt der StartZustand automatisch den "NextState" und das geht rekursiv immer so weiter bis StopZustand?

Äh..Nein.

Wer erzeugt die Zustände denn dann?
Im Beispiel wurde nur der Startzustand erzeugt!
-> Meine Frage lautete:
erzeugt der Startzustand SEINEN NextState automatisch?

Delphi-Quellcode:

StartZustantsInstanz := StartZustand.Create; //erzeugt von selbst zB Zustant2, den man mittels StartZustantsInstanz.GetNext verwenden kann

Wenn dem so WÄRE, DANN wäre es unübersichtlich.
(entspricht nicht meinem Gedanken von Überschaulichkeit)


Ich versteh nicht wieso man beim Case den gesamten Code durchdenken muss - es handelt sich immer um den gleichen Aufbau.
(Zustand suchen, Eingabe suchen und ändern)

Ich hab nichts gegen die Tabellenlösung (ab einer gewissen größe würde ich auch nicht auf diese Möglichkeit verzichten wollen), aber ICH finde, dass man sich die Tabelle bei evtl. Änderungen genauer ansehen müsste als "meine" Case.

[SebE]

Was mir grad noch auffällt:

Delphi-Quellcode:

Const 
  DEA : Array [symDigit..symTerminal, stStart..stDecimals] = 
//           symDigit  , symKomma,    symTerminal 
{stStart }  (stDigits  , stError    , stError),  
{stDigits}  (stDigits  , stComma    , stStop),    
{stComma}   (stDecimals, stError    , stError),  
{stDecimals}(stDecimals, stError    , stStop) 
            );

Du musst deine Eingabe (wir gehen davon aus, dass wir sie als String bekommen) erst einmal in deine Token/Symbole umwandeln.
Spricht du brauchst einen Scanner/Lexer -> dann kommst du ja auch nicht um deine Case-Anweisung.

Das war der Grund, warum meine Tabelle so riesig geworden ist (zwar groß, aber schnell).

Es bleibt natürlich immernoch Geschmackssache.
Ich für meinen Teil, bastle mir meine Parser (TopDown) ohne Generatoren -> Ich bin an die Cases gewöhnt.
Die Tabellenlösung kommt aus der "BottomUp-Ecke".

PS: die Quellcodes tun das, was ich von ihnen verlangt habe (Delphi 7 PE)

[Medium]

@_: Lustig ist, dass Delphi in der Unit System gerade die Funktionen die Compilermagic sind, mit einem vorangestellten _ definiert :) (Zumindest sagt mir mein Elefantenhirn das, dass dies mal vor ein paar zweistelligen Monaten gesehen hat... *hust*)

[alzaimar]

Zitat:

Zitat von SebE

Spricht du brauchst einen Scanner/Lexer -> dann kommst du ja auch nicht um deine Case-Anweisung.

Äh..Doch: Ein Scanner benötigt kein CASE. Ein Scanner implementiert einen NDEA. Du meinst aber eher soetwas:

Delphi-Quellcode:

Var
  SymbolClass : Array [Char] Of TSymbol;

Entsprechend befüllen, fertig. Dann einfach 'Symbol[CurrentChar]' nehmen und freuen, wie einfach das Leben sein kann.

Zitat:

Zitat von SebE

(zwar groß, aber schnell).

Wer primär auf Nanosekunden schaut, hat noch nicht kapiert, worum es beim Programmieren geht.

Zitat:

Zitat von SebE

die Quellcodes tun das, was ich von ihnen verlangt habe (Delphi 7 PE)

Ja, aber Du findest einen Fehler nicht so leicht. Hast Du meine denn gefunden? Du verwendest zudem zig mal den gleichen Code (case..of '0'..'9'). Das ist doch überflüssig und verstößt eben gegen Grundprinzipien der sauberen Programmierung.
Aber ich gebe zu, bei so keinen Geschichten ist ein Mini-DEA wirklich nett anzusehen (wenn man das nochmal sauberer hinbekommt) und ausreichend.

Zitat:

Zitat von SebE

Wer erzeugt die Zustände denn dann?

Jede State-Klasse wäre dann dafür zuständig für jede Symbolklasse einen Folgezustand zu definieren.

Zitat:

Zitat von SebE

Im Beispiel wurde nur der Startzustand erzeugt!

Nö.

Delphi-Quellcode:

 State := State.NextState;

Was macht denn diese Zeile?

Zitat:

Zitat von SebE

-> Meine Frage lautete: erzeugt der Startzustand SEINEN NextState automatisch?

Nein, nur wenn man ihn darum bittet ('NextState')

Zitat:

Zitat von SebE

(entspricht nicht meinem Gedanken von Überschaulichkeit)

Aber Du hast doch noch gar keine Ahnung von Interfaces, Klassen usw. Wie willst Du dir denn dann ein Urteil erlauben? :gruebel:

Zitat:

Ich versteh nicht wieso man beim Case den gesamten Code durchdenken

Hast Du den Fehler denn gefunden? Man tippt so viel und irgendwo vertippt man sich. Tippt man weniger, weil man sich z.B. nicht wiederholt, vertippt man sich auch nicht so oft. Ist doch logisch, oder?
Mein Code ist wesentlich weniger fehleranfällig, schneller einsatzbereit (weil weniger Zeilen), wiederverwendbar, allgemeingültig, robust und leichter verständlich (Als DEA). Deiner nicht. In deinem Code ist es viel leichter möglich, einen Fehler einzubauen (siehe mein Beispiel). Er ist nicht für einen ähnlichen DEA verwendbar, sondern muss komplett neu geschrieben werden. Viel Spass, wenn der DEA auch Buchstaben oder Zahlen à la '1,234E+99' verarbeiten soll.

Eine DEA-Tabelle ist natürlich kryptisch. Das stimmt.

Bleib halt bei deinen CASE-Konstrukten und -vor allen Dingen- kodiere Parser, Scanner, Lexer und DEA per Hand. :zwinker:

Zitat:

Zitat von jfheins

Wenn man das mit so einer Tabelle machen würde, ...

Dafür ist es dann für alle Eingaben 100% korrekt und man muss sich keine Gedanken mehr machen.

[SebE]

Zitat:

Ja, aber Du findest einen Fehler nicht so leicht.

Tut mir Leid, ich beharre darauf, dass man (in diesem Beispiel) nicht sagen kann, dass CASE unüberschaubarer sein soll.

Ob ich die Case durchsuchen muss oder die Tabelle neu "berechnen" muss - ist für mich der gleiche Aufwand!

Zitat:

Du verwendest zudem zig mal den gleichen Code (case..of '0'..'9')

Nur als Denkanstoß:

Delphi-Quellcode:

Const 
  DEA : Array [symDigit..symTerminal, stStart..stDecimals] = 
//           symDigit  , symKomma,    symTerminal 
{stStart }  (stDigits  , stError    , stError),  
{stDigits}  (stDigits  , stComma    , stStop),    
{stComma}   (stDecimals, stError    , stError),  
{stDecimals}(stDecimals, stError    , stStop) 
            );

Man muss bei jeder Variante JEDEN Zusstandsübergang angeben/implementieren.
Wenn ich nun möchte, dass mein Automat ("0"en hab ich übrigens vergessen) nach dem Komma nur Ziffern "1".."8" akzeptieren soll, dann hab ich hier schon keinen Doppelten Code.
Will sagen: es ist Zufall, dass hier doppelter Text steht.

Wenn DU keine Fehler in der Tabelle machst, dann mache ICH keinen in meiner Case.

Zitat:

Wer primär auf Nanosekunden schaut, hat noch nicht kapiert, worum es beim Programmieren geht.

Aus dem Zusammenhang gerissene Zitate verarbeiten tust du gern, gell?


NOCHMAL:

Also werden alle Zustände "on demand" erzeugt(?).

Wenn aktueller Zustand in den nächsten übergehen soll, erzeugt dieser (wenn nicht schon getan) den Neuen.

WENN das die Lösung ist, geht mir hier OOP eindeutig zu weit (oder auch nicht(?)).

Ich würde ein Objekt, welches die Tabelle an sich repräsentiert modellieren, die dann alle Zustände erzeugt.
Sonst wären ja die Zustandsüberführungen über große Text-Entfernungen hinweg definiert.

Es ist nicht die Aufgabe eines jeden Zustandes, sich um den nächsten zu kümmern. (MEINE Meinung)

Zitat:

Aber Du hast doch noch gar keine Ahnung von Interfaces, Klassen usw. Wie willst Du dir denn dann ein Urteil erlauben?

Mit solchen Äußerungen wär ich an deiner Stelle vorsichtig!

Zitat:

Bleib halt bei deinen CASE-Konstrukten und -vor allen Dingen- kodiere Parser, Scanner, Lexer und DEA per Hand.

Du hast dem Anschein nach keinen Spaß mehr am (von-Hand-)Programmieren?

@Medium:
Was interessiert es den Programmierer, wie die die interne Umsetzung von etwas aussieht?
Ich GLAUBE, dass machen auch C-Compiler so (im Assembler-Code stehen dann "_" oder "__" vor allen Routinen)

[jfheins]

Nein, das ist nicht der gleiche Aufwand.

Die Tabelle muss immer vollständig sein (leere Felder sieht man sofort => da fehlt was) bei dem case sieht man es nicht sofort wenn man was vergessen hat.

Und wenn man ein Ereignis hinzufügt, muss man sich bei der Tabelle Gedanken machen, wass in jedem Zustand passieren soll - beim case läuft man Gefahr, einen Zustand zu vergessen (Dann wird ja der else-Zweig ausgeführt), und man hat möglicherweise einen Bug.

Und die Tabelle kann man gut seperat validieren. z.B. eine Excel-Arbeitsmappe die die Tabelle überprüft und ggf. auf Sackgassen oder nicht zusammenhängende Bereiche aufmerksam macht.

Das ganze wird natürlich wichtiger, je komplexer das ganze wird. Ob diese Grenze (oberhalb der man bereit ist, eine zusätzliche Abstraktion einzuführen) bei 3 Ereignissen und 4 Zuständen schon erreicht ist, ist subjektiv.

Btw.: Zu der Zustandsmatrix gehört eigentlich auch eine Vorgangsmatrix oder sowas - die Zustandsmatrix gibt zu einem Zustand und einem Ereignis den neuen Zustand an, und die Vorgangsmatrix gibt die Aktion an, die passieren soll ... oder nicht?

[SebE]

Die "Vorgangsmatrix" steckt in ProcessState:

Delphi-Quellcode:

State := CoStartState.Create; 
While Not State.IsStopState Do Begin 
  State.DoProcessState(); 
  State := State.NextState; 
End;

Zitat:

Nein, das ist nicht der gleiche Aufwand.

Die Tabelle muss immer vollständig sein (leere Felder sieht man sofort => da fehlt was) bei dem case sieht man es nicht sofort wenn man was vergessen hat.

Und wenn man ein Ereignis hinzufügt, muss man sich bei der Tabelle Gedanken machen, wass in jedem Zustand passieren soll - beim case läuft man Gefahr, einen Zustand zu vergessen (Dann wird ja der else-Zweig ausgeführt), und man hat möglicherweise einen Bug.

Das ist ein Streitpunkt, aus dem wir nicht rausfinden.
Ich sage, es ist der gleiche Aufwand.

Wenn man "viele" Zustände hat, ist man gut daran einen Graphen zu zeichnen, wenn ich diesen ändere, WEIß ich sofort, wo ich in der Tabelle/Case etwas zu ändern habe.

Zur Klarstellung (nur weil das bestimmte Personen evtl so sehen): Ich habe mich nie GEGEN die Tabellenlösung als solches ausgesprochen.
Ich finde die Case (vor allem in unserem kleinen Beispiel) ebenwürdig.

Das kommt auch daher, dass die Case-Variante immer mächtiger ist.

Kleines Beispiel:
Man nehme an, man "füttert" seinen Automaten nicht mit einer Liste von Charactern (String) sondern mit einer Liste von zwei, drei, ... Zeichen pro Terminalsymbol.

Eingabe: "ABC#32DE", hier soll #32 EIN Smbol darstellen.

Bitte keine Bezüge zu "Bändern" von denen der Automat liest.

Hier benötigt man einen Scanner mit CASE.

Alternative: Man könnte natürlich den Scanner wiederum als separaten Automaten modellieren, der pro Aufruf ein TerminalSymbol rauswirft.

[Meflin]

Zitat:

Zitat von SebE

Es ist nicht die Aufgabe eines jeden Zustandes, sich um den nächsten zu kümmern.

Wessen Aufgabe denn dann? Was man bei gutem OOP ja garnicht haben will sind sg. "God-Classes"... Insofern ist das Vorgehen garnicht so verkehrt.

[SebE]

Das ist das Thema, welches mich interessiert.

Kannst du mir Quellen geben, die die (Entwicklungs-)Prinzipien des Paradigmas erklären, dass zB "God-Classes" nicht gern gesehen werden.

Ein Beispiel (erstellen einer Liste):

1. Man erstellt nur die Elemente der Liste und diese organisiert sich "indirekt" selbst.
2. man erstellt Elemente, die IHRE eigene Aufgabe (und nur DIESE) erfüllen; und dazu eine "Schale", die die Organisation übernimmt

Was ist an Punkt 2 auszusetzen (mehr Schreibarbeit mal Außen vor gelassen).

Ich würde 1. bevorzugen, da zB die Suche in 2. über die Elemente funktioniert, die Elemente es aber überhaupt nicht zu interessieren hat.
Wenn sich nun die Organisation ändert, bekommen die Elemente nichts davon mit (was eigentlich erwünscht ist)

Prinzipien der OO sind doch:
- Jedes Objekt hat (s)eine Aufgabe
- Minimale Sichtbarkeiten
- ...

Liste darf (durch euch) erweitert werden

[SebE]

Ich seh grad auf Wiki (http://de.wikipedia.org/wiki/God_object):

God-Object = ein Objekt, dass "zu viel kennt".

Das entspricht aber der hier vorgestellten Lösung.
Ein ListenElement, welches seinen Nächsten kennt (und in unserem Automaten sogar noch "managed").

[Uwe Raabe]

Zitat:

Zitat von SebE

Ich seh grad auf Wiki (http://de.wikipedia.org/wiki/God_object):

God-Object = ein Objekt, dass "zu viel kennt".

Das entspricht aber der hier vorgestellten Lösung.
Ein ListenElement, welches seinen Nächsten kennt (und in unserem Automaten sogar noch "managed").

Das ist Ansichtssache: Das State-Objekt kennt nur seinen Zustand (nicht, wie er erreicht wurde) und unter welchen Bedingungen welcher Folge-Zustand erreicht wird. Alle anderen Zustände sind ihm fremd. Das ist ein klar abgegrenzter Zuständigkeitsbereich.

Im Gegenzug dazu müssen die Case-Anweisung und die Tabelle immer alle Zustände und möglichen und nicht-möglichenn Transitionen kennen.

Übrigens: hier gibt es eine schöne visuelle OOP-Implementierung einer Statemachine.

[SebE]

Zitat:

Das ist Ansichtssache: Das State-Objekt kennt nur seinen Zustand (nicht, wie er erreicht wurde) und unter welchen Bedingungen welcher Folge-Zustand erreicht wird

Das ist ja nicht das Problem, mir ging es um die Organisation - sprich: die Erzeugung der Folgezustände.

Es ist (in meinen Augen) NICHT die Aufgabe eines Zustandes den nächsten zu erstellen und ihn damit zu organisieren.

Es braucht einen "Hüter", der die Aufgabe der Tabelle oder CASE übernimmt, also den Automatengraphen "simuliert".

[Meflin]

Zitat:

Zitat von SebE

Es ist (in meinen Augen) NICHT die Aufgabe eines Zustandes den nächsten zu erstellen und ihn damit zu organisieren.

In Delphi muss halt nunmal irgendwer die Instance erzeugen. Und da ist es immernoch besser, eine Klasse erstellt ihre Folgezustände, als eine Klasse erzeugt ALLE Zustände. Optimal in dem Sinne wäre es vielleicht, class methods zu verwenden und beim ersten Aufruf den Zustand sich selbst erzeugen zu lassen. Andere Sprachen sind in der Hinsicht halt konsequenter...

[markusj]

Zitat:

Zitat von SebE

Wie soll denn das aussehen?

Ist mein abstrakter Zustand vom Typ Basisklasse und jeder aktuelle (reale) Zusatnd dann von einer abgeleiteten Klasse?
(das wären sehr viele speicheroperationen)

Ich bitte um Aufklärung

Genau so. Wenn man die einzelnen Zustände dann noch als Singleton anlegt, erspart man sich auch das ständige Erzeugen und Zerstören von Objekten, was der Geschwindigkeit zugute kommt.
Je nach Implementierung der Zustände kann man entweder eine Basisklasse verwenden und nur noch einzelne Methoden in den Kindklassen überschreiben, oder aber man verwendet nur ein Interface.

mfG
Markus

[SebE]

ich spreche Sprachunanhängig, es geht mir jetzt rein um OOP, OO oder OOT (wie mans nennen will).

Zitat:

Zitat von Meflin

Zitat:

Zitat von SebE

Es ist (in meinen Augen) NICHT die Aufgabe eines Zustandes den nächsten zu erstellen und ihn damit zu organisieren.

In Delphi muss halt nunmal irgendwer die Instance erzeugen. Und da ist es immernoch besser, eine Klasse erstellt ihre Folgezustände, als eine Klasse erzeugt ALLE Zustände. Optimal in dem Sinne wäre es vielleicht, class methods zu verwenden und beim ersten Aufruf den Zustand sich selbst erzeugen zu lassen. Andere Sprachen sind in der Hinsicht halt konsequenter...

dazu:

Zitat:

Wessen Aufgabe denn dann? Was man bei gutem OOP ja garnicht haben will sind sg. "God-Classes"... Insofern ist das Vorgehen garnicht so verkehrt.

Die Lösung "Jeder Zustand erzeugt seinen Nächsten" ist eine God-Class-Lösung.

Mein "eleganter" und "OO-Korrekter" Lösungsvorschlag: 2 Klassen.

- Klasse Zustand (diese speichert (organisiert) die Aktion, die Ausgabe (falls Mealy-Automat) und eventuall seinen Folgezustand)

- Klasse Tabelle/Case/Graph (managed alle Zustände, interne Realisierung ist persönliche Sache)

Das entspricht (soweit ich das einschätzen kann) einer guten OO.
Ich lerne selbst gerade erst damit umzugehen (ich bastle mir eine SymbolTabelle für einen Compiler rein OO).
Da hat man so manche philosophische Halbe Stunde :-)

Um Bezug zu nehmen auf das eigentliche Thema: die OO-Lösung die hier vorgestellt wurde ist unübersichtlich, das die Organisation sehr stark verteilt wurde (auf #Zustände-viele Klassen).