Automaten in Source Code

[SebE]

Falls es von Interesse ist:
Alle markierten Bereiche in Zitaten, die ich angeführt haben, entstanden durch mich und dienten der Verdeutlicheung.
Danke für den Hinweis.

Zitat:

Das ist deine Interpretation - ich würde das nicht so einschränken. Es wird ein Folge-Zustand zurückgegeben. Das sagt aber nichts darüber aus, wo er herkommt

Sicher ist das MEINE Interpretation - Und das ist der Punkt, der die letzten Seiten besprochen wurde/wird.

Funktionieren tun sicher alle Methoden.
Aber welche der OOP entspricht, wa/ist die Frage.

Zitat:

Garbage Collection

Hier ist der nächste Punkt: ist es gutes OOP, wenn man sich auf den Garbage Collector verlässt?

[Uwe Raabe]

Zitat von SebE:

Hier ist der nächste Punkt: ist es gutes OOP, wenn man sich auf den Garbage Collector verlässt?

Hat auch niemand behauptet und gehört eigentlich auch in einen separaten Thread.

Wie ich schon sagte: Die Verwaltung der implementierenden Objekte ist IMHO nicht Aufgabe der State-Machine.

[Khabarakh]

Zitat von SebE:

Vom Zeitpunkt der Entwicklung aus gesehen, kennt dein Zustand auch jeden anderen!
(da er ihn ja (rekursiv) erzeugt)

So langsam würde mich deine Definition von "kennen" schon interessieren, es kann jedenfalls nichts mit OOP/Encapsulation zu tun haben...
Zustand1 erzeugt/fordert eine Instanz von Zustand2 an, welche sich Zustand3 holt. Hat Zustand1 Zugriff auf die Zustand3-Instanz oder kann er irgendwie wissen, dass es diese überhaupt gibt? Nein, hier kann unmöglich von "kennen" gesprochen werden!

Zitat von SebE:

Hier ist der nächste Punkt: ist es gutes OOP, wenn man sich auf den Garbage Collector verlässt?

Wie gesagt, langsam wird's OT, aber wenn du schonmal einen GC benutzt hättest, würdest du diese Frage nicht stellen .

[SebE]

Noch einmal, ich finde ein Zustand sollte keinen schreibenden Zugriff auf einen Anderen ausüben dürfen.

Zurückgeben: Ja
Erzeugen: Nein

Es wär nicht verkehrt, eine OO-Lösung in Form von Quellcode vorzustellen.

Zumindest die GetNextState-Methode und evtl. den Konstruktor.

@GC:
Ich halte es nicht gerade für ein gutes Pattern, ihn zu verwenden

[Mithrandir]

Moah... Also, jetzt wurde hier fast 50 Beiträge lang diskutiert, debattiert, rumgeschoben, angemeckert usw. Ich versteh langsam immer weniger. Automaten sind mir bekannt, und ich find sie faszinierend, da man mit ihnen nahezu alle Probleme (= Aufgaben) lösen kann.

Ich habe hier für SmallTune eine Übersetzungsklasse geschrieben. Ich habe ein Dateiformat erstellt, das so aussieht:

Delphi-Quellcode:

// Translation File for SmallTune
// Language: German
// Author: Daniel Gilbert
// Mail: [email][e-mail][/email]

// Must match Application Minor Version
// e.g. "0.3" will work for SmallTune 0.3.0, SmallTune 0.3.1, SmallTune 0.3.2 and so on, but not SmallTune 0.4.0...
TRANS_FILE_VERSION=0.3;

//Short Description:
//
//The default Format is:
//
//index:'Text';
//
//In case you need a ' in your text (e.g.: isn't), you can write it like this:
//
//0:'This isn\'t a problem';
//
//In case you need a linebreak, this can be done this way:
//
//0:'This is the first line \n this is the next line';
//
// NEVER EVER change the index and the line order. Doing so will result in an error and the language won't be loaded

//Windows XP or NT 4.0 needed!
0:'Windows XP or NT 4.0 needed!';
//[Playing]
1:'[Playing]';
//[Pause]
2:'[Pause]';

Der Parser beachtet die Versionsangabe noch nicht. Ich habe auf die klassische "Case"-Variante zurückgegriffen, die alzaimar überhaupt nicht zusagt.

Wie würde man denn so einen Parser als Tabelle implementieren? Ich versteh an diesem Punkt ehrlich gesagt nur Bahnhof, und eine andere Möglichkeit als "Case" konnte ich mir bislang auch nicht vorstellen. Im Anhang gibt es die komplette Unit, hier den Auszug des Parsers:

Delphi-Quellcode:

function TdgstTranslator.ParseFile(Filename: String): Boolean;
var
  TranslationFile: TextFile;
  i: integer;
  tmp, tmp2: String;
begin
  Result := false;
  (* Initialize *)
  SetLength(fTranslations, 0);
  FileMode := fmOpenRead;
  tmp := '';
  tmp2 := '';
  (* Open File *)
  AssignFile(TranslationFile, FileName);
  try
    (* Reset File *)
    Reset(TranslationFile);
    while not EOF(TranslationFile) do
    begin
      (* Read the next line *)
      ReadLN(TranslationFile, tmp);
      fState := tpsNewLine;
      if Length(tmp) > 0 then
        for I := 1 to Length(tmp) do
          case fState of

            (* New Line Started *)
            tpsNewLine:
              begin
                case tmp[I] of

                  '/':
                  begin
                    (* This line is a comment *)
                    fState := tpsComment;
                    Break;
                  end;

                  else
                  begin
                    (* ReInit tmp2 *)
                    tmp2 := '';
                    tmp2 := tmp[I];
                    fState := tpsIndex;
                  end;
                end;
              end;

            (* Line with comment started, can be ignored *)
            tpsComment:
              begin
                fState := tpsNewLine;
                Break;
              end;

            (* Index found *)
            tpsIndex:
              begin
                case tmp[I] of

                  ':':
                    begin
                      (* Index ended, Text will start *)
                      SetLength(fTranslations, Length(fTranslations) + 1);
                      If not (StrToIntDef(tmp2, 0) = Length(fTranslations) - 1) then
                      begin
                        fState := tpsFailure;
                        Break;
                      end
                      else
                        fState := tpsTextBegin;
                    end;

                  else
                    begin
                      tmp2 := tmp2 + tmp[I];
                    end;
                end;
              end;

            (* New Text Begins *)
            tpsTextBegin:
              begin
                case tmp[I] of
                  '''':
                    begin
                      fState := tpsTextReading;
                      tmp2 := '';
                    end;
                end;
              end;

            (* Beginning was found, reading the current string *)
            tpsTextReading:
              begin
                case tmp[I] of
                  '\': fState := tpsCtrlCommand;
                  '''': fState := tpsTextEnd;
                  else
                    tmp2 := tmp2 + tmp[I];
                end;
              end;

            (* Text has ended *)
            tpsTextEnd:
              begin
                case tmp[i] of
                  ';':
                    begin
                      fTranslations[Length(fTranslations) - 1] := tmp2;
                      fState := tpsNewLine;
                    end;
                end;
              end;

            (* The control character has been found *)
            tpsCtrlCommand:
              begin
                case tmp[i] of
                  'n': tmp2 := tmp2 + #13#10;
                  '''': tmp2 := tmp2 + '''';
                  '\': tmp2 := tmp2 + '\'; 
                end;
                fState := tpsTextReading;
              end;
      end;
    end;
  finally
    CloseFile(TranslationFile);
  end;
end;

[SebE]

Auf Seite 2 hab ich grob gezeigt, wie beide Varianten funktioniern (es sind nicht die besten Lösungen).

Mal dir den Graphen auf.
Aus dem Grpahen erstellst du dir dann die Tabelle.

[JasonDX]

Eine (IMO sinnvolle(re)) OOP-Lösung wäre folgender Aufbau:

Delphi-Quellcode:

TDFAState = class;
TDFA = class
public
  property Alphabet: array of TToken; read;
  property StartState: TDFAState; read;
  property States: array of TDFAState; read;

  function Accepts(word: array of TToken): boolean;
end;

TDFAState = class
protected
  Transitions: TDictionary;
public
  propterty TDFA Owner; read;
  property IsFinalState: boolean; read;
  procedure Map(Targets: array of TDFAState); //Setzt Transitions (einmalig)
  function Transition(Token: TToken): TDFAState;
end;

//Manche Methoden:

function TDFA.accepts(word: array of TToken): boolean;
var
  CurrentState: TDFAState;
  i: integer;
begin
  CurrentState := self.StartState;
  for i := 0 to high(word) do
    CurrentState := CurrentState.Transition(word[i]);
  result := CurrentState.IsFinalState;
end;

procedure TDFAState.Map(Targets: array of TDFAState);
var
  i: integer;
begin
  if (Transitions = nil)
  begin
    Transitions := Dictionary.Create();
    for i := 0 to high(Owner.Alphabet) do
      Transitions.Add(Owner.Alphabet[i], Targets[i]);
  end;
end;

function Transition(Token: TToken): TDFAState;
begin
  if (not Transitions.Contains(Token))
    raise Exception.Create('Received Token not included in Alphabet');
  result := Transitions[Token];
end;

Gemacht wird das ganze dann so, dass im Konstruktor von TDFA:
1. Alle Zustände erstellt werden (sodass sie über TDFA.States verfügbar sind)
2. Alle Zustände eine Liste von Zuständen bekommen. Dabei gilt: Mit dem 1. Token des Alphabets kommt man in den 1. Zustand in der Liste. Ein Beispiel:

Delphi-Quellcode:

constructor TDFA.Create(...)
begin
  //Create States...
  //Map States
  States[0].Map([States[0], States[1], States[1]]);
  States[1].Map([States[2], States[0], States[0]]);
  States[2].Map([States[1], States[2], States[1]]);
end;

Syntaxmäßig gebe ich keine Garantie, auch ist der Klassenaufbau teilweise nur skizziert. Aber es dürfte für ein Verständnis der Idee reichen
Dictionary wusst ich jetzt nicht, ob/welche Klasse in Delphi dieses .NET-Äquivalent implementiert. Es ist jedenfalls einfach nur ein Mapping von TToken auf TDFAState.
Btw: Diese OOP-Variante hat den Vorteil, dass Bearbeitungsoperationen auf dem DFA implementiert werden können.

greetz
Mike

[SebE]

Danke für die Mühe.

So in etwa meinte ich das.

Wäre toll, wenn jemand von "der anderen Seite" seine Ideen zu Papier (Bildschirm) bringen könnte.


Meine Ideen, für "eure" Lösung:

1.

Delphi-Quellcode:

constructor Zustand1.Create;
begin

end;

function Zustand1.GetNextState(const token: CHAR): state;
begin
  case token of
  ...
  '0'..'9': begin
    ...
    GetNextState := Zustand2.Create;
    end;
  end;

Self.Destroy;
end;

2.

Delphi-Quellcode:

constructor Zustand1.Create;
begin
//wir befinden uns bspw. in Zustand1

Self.NextStateList[Digit] := Zustate2.Create;
Self.NextStateList[Letters] := Zustand3.Create;
end;

function Zustand1.GetNext(const token: symbol): state;
begin
GetNext := NextStateList[token]
end;

Ist eine davon "eure" OOP-Lösung?

Ich find (wenn es eren Ideen entspricht) beide nicht elegant.

[Mithrandir]

Zitat von SebE:

Mal dir den Graphen auf.
Aus dem Grpahen erstellst du dir dann die Tabelle.

Es tut mir Leid, ich komme aus diesem Case-Gedanken nicht raus... Ich kann mir nicht vorstellen, wie ich den Zustandsgraphen (der mir ja durchaus bewusst ist) komplett in OOP und als Tabelle implementiere.

[SebE]

Ja, wie man es OO löst wurde hier noch nicht gelöst
Für mich heißt OOP Aufgaben intelligent verteilen.

=> Tabelle oder Case in eine Klasse

ODER:
"Zustandsbaum" aufbauen:
Knoten (Zustand) als Klasse und untereinander "verbinden" (abhängig von der Eingabe), die letzte Aufgabe übernimmt (wenn ich's machen würde) die Hüllenklasse (würde dann die Tabelle/Case immitieren) übernehmen.

Ansonsten: schau dir noch einmal in ruhe alle Codes an, die hier gepostet wurden

Gute Nacht