Automaten in Source Code

[JasonDX]

Zitat:

Zitat von SebE

Ja, wie man es OO löst wurde hier noch nicht gelöst ;-)

Was ist an meinem Code noch ungelöst? Die Entscheidung, welcher Pfad im Graph gewählt wird, wird vom jeweiligen Zustand getroffen. Der Automat selbst kennt nur den aktuellen Zustand, und greift auf dessen Methoden zurück, um den Zielzustand der korrekten Kante zu ermitteln.
Die Festlegung der Übergänge für einen bestimmten Zustand kann dabei vom Automaten selbst, oder aber auch von außen gesteuert werden - je nach belieben. Notwendig dafür sind weder Tabellen, noch unübersichtliche case-Strukturen. Was will man mehr? ;)

greetz
Mike

[SebE]

Nein, ich hatte das nicht so gemeint.

Du hast doch mitbekommen, dass es hier eine philosophische Diskussion über die OO-Lösung gab (und DIE ist nocht nicht gelöst).

In meinen Augen, ist deine Lösung äquivalent zu meiner (wenn ich davon ausgehe, deinen Code richtig verstanden zu haben) (also der "Zustandsbaum"-Lösung, die den Graph KOMPLETT aufbaut)

[Khabarakh]

Zitat:

Zitat von SebE

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

Na dann erzähl doch mal, was dir an der ersten nicht gefällt (das Destroy übernimmt natürlich die ausführende Schleife). Es dürfte doch unbestreitbar sein, dass das die minimale, von der Logik her direkteste Variante ist: Jeder Zustand sagt, mit welchem es weiter gehen soll, fertig. Das ist KISS.
Wenn dir dabei unnötig viele Instanzen erzeugt werden, kann ich dich sogar verstehen. Eine bereits genannte Lösung wäre Singletons. Gäbe dann allerdings bei verarbeitenden Automaten und Multi-Threading Probleme. Also führe ich wie JasonDX einen Owner ein:

Delphi-Quellcode:

function TZustand1.GetNextState(const aToken : Char): TState;
begin
  case aToken of
  ...
  '0'..'9': begin
    ...
    Result := Owner.GetOrCreate(TZustand2);
    end;
  end;
end;

Der große Unterschied? Mein Owner hat keine Ahnung, welche Klassen er enthält, er ist effektiv ein TDictionary<TStateClass, TState>, ein dummer Cache. Und hält so meine beiden Regeln ein.

So, das war jetzt die simpelste Lösung, die ich mir vorstellen kann. JasonDX' Code ist mir ehrlich gesagt zu komplex, da nehme ich doch lieber wieder Tabellen in prozeduralem Code ;) .

Zitat:

Zitat von SebE

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

Gut, das ist deine Meinung und die werde ich dir nicht aussprechen. Es muss dir nur klar sein, dass in etwa gleiche viele Leute sie mit dir teilen wie deinen Code-Style.

[Khabarakh]

Zitat:

Zitat von Daniel G

Ich kann mir nicht vorstellen, wie ich den Zustandsgraphen (der mir ja durchaus bewusst ist) komplett in OOP und als Tabelle implementiere. :gruebel:

Nach ein wenig Überlegen sage ich mal, wie ich persönlich es machen würde: Sicherlich nicht mit OOP :zwinker: .

Zuallererst würde ich die Sprache auf jeden Fall in EBNF fassen - schon allein, um eine prägnante, von der Implementierung unabhängige Definition zu haben. Jetzt kommt es drauf an: Wenn die Grammatik nicht zu komplex und vor allem LL(1) ist, geht meine Stimme an einen Recursive Descent Parser. Viel Theorie und Fachwörter, aber imho eigentlich eine der simpelsten und zugleich übersichtlichsten Methoden. Entspricht auch ziemlich genau dem OOP-Ansatz (der ohne Gott-Klasse :zwinker:), aber ohne diesen ganzen Syntax-Overhead *schauder* .

Erstmal brauchen wir eine halbwegs taugliche Repräsentation des Inputs:

Delphi-Quellcode:

type TTokenStream = class
  public
    property Current : Char read;
    property Eof : Boolean read;
    procedure MoveNext;
    procedure Expect(aToken : Char); // MoveNext, falls Current = aToken, sonst Exception
end;

Eine Grammatik für deine Dateien könnte etwa so aussehen:

Code:

lines = line, [ newline, lines ] ;

line = comment | constant | entry ;

comment = "//", { symbol } ;

constant = identifier, "=", { symbol - ";" }, ";" ;

...

Diese werden dann in rekursive Funktionen umgeformt:

Delphi-Quellcode:

function TFile Lines(aStream : TTokenStream);
begin
  Result := TFile.Create;
  repeat
    if not Comment(aStream) then
    begin  
      var constant := Constant(aStream);
      if Assigned(constant) then
         Result.AddConstant(constant)
       else
      begin
        var entry := Entry(aStream);
        Assert(Assigned(entry));
        Result.AddEntry(entry);
      end;
     end;
   
    if not aStream.Eof then
      Assert(Newline(aStream));
  until aStream.Eof;
end;

function Boolean Comment(aStream : TTokenStream);
begin
  Result := aStream.Current = '/';
  if Result then
  begin
   aStream.Expect('/');
    while not Newline(aStream) do;
  end;
end;

function TConstant Constant(aStream : TTokenStream);
begin
  var name : String := Identifier(aStream);
  if not Assigned(identifier) then
    Exit(nil);
   
  var constant := TConstant.Create;
  constant.Name := name;
  
  aStream.Expect('=');
  
  constant.Value := '';
  
  while aStream.Current <> ';' do
  begin
    constant.Value += aStream.Current;
   aStream.MoveNext;
  end;
  
  aStream.Expect(';');
end;

.
.
.

Keine Ahnung, ob das jetzt nachvollziehbar war, das Ergebnis finde ich aber äußerst übersichtlich. Wie gesagt entspricht es der OOP-Variante: Jede Funktion ist unabhängig und kennt nur ihre Teilfunktionen, ein Aufruf der Startfunktion bringt alles ins Rollen.
Wir haben uns damit zwar etwas von Automaten wegbewegt, was ich aber wirklich nicht schade finde: BNF kann einfach viele winzige Zustände in eine zusammenhängende Regel fassen, bei der Umsetzung in rekursive Funktionen können es sogar noch weniger werden. Man rückt von einzelnen Zeichen ab und denkt in größeren Blöcken.

Was aber, wenn die Sprache doch etwas zu komplex ist? Dann gibt es imo keine Ausrede mehr, nicht gleich zu einem Parser-Generator zu greifen:

Zitat:

Zitat von http://en.wikipedia.org/wiki/Recursive_descent_parser

Although predictive parsers are widely used, programmers often prefer to create LR or LALR parsers via parser generators without transforming the grammar into LL(k) form.

Spätestens, wenn eine ordentliche Fehlerausgabe gefordert ist, wird jede handgestrickte Lösung, öhm... lustig ;) .

[Mithrandir]

:thumb:

Danke, ich werde mir das die Tage mal zu Gemüte führen und dann sehen, ob ich die Klasse nicht entsprechend anpassen kann. :)