Automaten in Source Code

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