Automaten in Source Code

[Meflin]

Zitat:

Zitat von SebE

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)

Diese Lösung ist noch wesentlich "God-Classiger". Ist das nicht eigentlich offensichtlich :gruebel:

[SebE]

Weil die - ich nenn sie jetzt Graph-Klasse - über die Zustände "herrscht".

Eingentlich nicht.
Es ist doch nicht schlimm, wenn eine Klasse, andere Klassen handelt.

Es geht doch bei OO um "Aufgaben-Verteilung" und die ist mir meiner Lösung gut umgesetzt.

"von unten nach oben" entwickeln.
Erst due Zustände modellieren und danach die Verbindung zwischen ihnen (Grapf)

[Khabarakh]

Zitat:

Zitat von SebE

Weil die - ich nenn sie jetzt Graph-Klasse - über die Zustände "herrscht".

So ähnlich wie Gott über seine Schäfchen ;) ?

Ich denke, wir könnten uns auf folgende Regeln einigen, die mehr oder weniger schon genannt wurden:

• Jede State-Klasse kennt nur die Klassen ihrer Folgezustände ("kennen" beinhaltet natürlich auch "erzeugen können").
• Außerhalb davon ist nur die Klasse des Startzustandes und das Interface bekannt.

Ich glaube, du nimmst das Problem immer noch zu holistisch in Angriff. Den Automaten zu Beginn einmal aufzumalen, ist natürlich alles andere als falsch, aber während der Implementierung darf niemals der gesamte Graph in deinem Kopf herumschwirren, sondern immer nur direkt voneinander abhängige Bestandteile.

[SebE]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von SebE

Weil die - ich nenn sie jetzt Graph-Klasse - über die Zustände "herrscht".

So ähnlich wie Gott über seine Schäfchen ;) ?

Nein eine Gott-Klasse übernimmt jede (oder zumindest zu viel) Aufgabe(n).
"Meine" Graphklasse übernimmt nur die Handhabung, was die Zustände intern machen, ist ihr Wurst.

Zitat:

Ich denke, wir könnten uns auf folgende Regeln einigen, die mehr oder weniger schon genannt wurden:

• Jede State-Klasse kennt nur die Klassen ihrer Folgezustände ("kennen" beinhaltet natürlich auch "erzeugen können").
• Außerhalb davon ist nur die Klasse des Startzustandes und das Interface bekannt.

Eben nicht.

[Meflin]

Hää?? Deine Klasse erstellt ALLE Instances und ist damit weniger "Gott" als die Version, wo jede Instance die Instances der Folgezustände erstellt (und damit einen wirklich wesentlich eingeschränkteren Funktionsumfang & "Sichtweite" hat). Das ergibt einfach keinen Sinn. Khabarakh hat schon ganz recht... "Deine" Klasse kennt ALLES, in der von uns vorgeschlagene Version kennt jede Instance ihre Folgezustände... wo ist also hier der Gott?? Entweder du hast es nicht verstanden, oder aber ich verstehe einfach nicht was deine Klasse nun eigentlich machen soll...

Steuerungsklassen sind IMMER ein sehr sehr deutlicher Indikator für schlechte Klassenstruktur. Ja, immer :P

[markusj]

Zumindest in unserer Softwaretechnik-Vorlesung wurde die Variante "Jeder Zustand kennt/erzeugt _nur_ seinen Nachfolger" favorisiert. Allgemeiner Strukturen/Aufgaben wurde dabei in der Elternklasse implementiert, die zustandsspezifischen Methoden wurden erst in den einzelnen Zustandsklassen implementiert.
Im übrigen bietet sich bei dieser Variante auch gleich den Einsatz von Singletons an ...

Letztendlich ist es auch immer eine Frage des Geschmacks und der Problemkomplexität, gerade das zerlegen in die einzelnen Zustände verteilt den Aufwand und die Komplexität gleichmäßiger als ein schwer wartbares Case.

mfG
Markus

[SebE]

Zitat:

Zitat von Meflin

Hää?? Deine Klasse erstellt ALLE Instances und ist damit weniger "Gott" als die Version, wo jede Instance die Instances der Folgezustände erstellt (und damit einen wirklich wesentlich eingeschränkteren Funktionsumfang & "Sichtweite" hat). Das ergibt einfach keinen Sinn. Khabarakh hat schon ganz recht... "Deine" Klasse kennt ALLES, in der von uns vorgeschlagene Version kennt jede Instance ihre Folgezustände... wo ist also hier der Gott?? Entweder du hast es nicht verstanden, oder aber ich verstehe einfach nicht was deine Klasse nun eigentlich machen soll...

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

Gott-Klasse heißt doch nichts anderes, als:
Ich entwickle etwas imperativ (am besten noch unstrukturiert) und schmeiß alles in eine Klasse (die macht alles -> Gott)

Meine Graph-Klasse hat aber nur EINE Aufgabe (es ist egal, wen sie alles KENNT), nämlich Organisation.
Was die Elemente der organisatorischen Einheit (Zustände) machen, ist der Graphklasse egal (nicht Gott, da Aufgaben weitergegeben wurden).

Nur weil eine Klasse mehrere (auch verschiedene) Klassen handhabt, wird sie nicht zu einer Gott-Klasse.

Zitat:

Steuerungsklassen sind IMMER ein sehr sehr deutlicher Indikator für schlechte Klassenstruktur. Ja, immer :P

Das versteh ich überhaupt nicht.

Wenn ich keine Klasse erstellen darf, die etwas steuert (auch andere Klassen), dann mach ich es doch imperativ (max. strukturiert) aber nicht OO!

Zusammenfassung: "Deine"/"Eure" Lösung halte ich für eine Gott-Klassen-Lösung, da ihr für mehrere Aufgaben EINE Klasse habt.

[Uwe Raabe]

Es ist übrigens nicht zwingend so, daß die Folge-Zustände von dem aktuellen Zustand erzeugt werden - sie werden lediglich von ihm zurückgegeben.

Ein denkbares Beispiel dafür ist ein Warte-Zustand W. Dieser wartet eine bestimmte Zeit T auf ein Ereignis E und gibt beim Eintreten den Zustand A zurück und bei einem Timeout den Zustand B. Die Zustände A und B können zusammen mit dem Ereignis E (Anonyme Funktionen gehen da ganz hervorragend) und einer Zeit T z.B. beim Erzeugen oder Eintreten in den Zustand W übergeben werden. Damit läßt sich dieser Wartezustand flexibel an unterschiedlichen Stellen einsetzen, ohne für jede Möglichkeit eine eigene Zustandsklasse zu deklarieren.

Ich verwende eine solche OOP-State-Machine gerade in einer Ablaufsteuerung und das funktioniert geradezu hervorragend. Gerade das Manipulieren einzelner Ablaufstränge, wie das Einfügen von Zwischenzuständen, Reagieren auf Fehler mit nachfolgendem Wiederaufsetzen ist wesentlich übersichtlicher als es mit einer Case- oder Tabellen-Lösung möglich wäre.

Wenn jemand Interesse an dem Artikel "Object-Oriented State Machine" von Julian Bucknell aus dem Delphi Magazine hat (Untertitel: Getting rid of case statements) - kurze PM an mich.

[SebE]

Zitat:

Es ist übrigens nicht zwingend so, daß die Folge-Zustände von dem aktuellen Zustand erzeugt werden - sie werden lediglich von ihm zurückgegeben.

...und nicht mehr.

Wenn ein Zustand in einen Anderen übergeht, löscht sich der aktuelle, oder?
Das verstößt doch sicher auch gegen irgendwelche Regeln (ich erzeuge im Lauf immer die SELBEN Objekte und lösche sie wieder)

[Uwe Raabe]

Zitat:

Zitat von SebE

Zitat:

Es ist übrigens nicht zwingend so, daß die Folge-Zustände von dem aktuellen Zustand erzeugt werden - sie werden lediglich von ihm zurückgegeben.

...und nicht mehr.

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.

Zitat:

Zitat von SebE

Wenn ein Zustand in einen Anderen übergeht, löscht sich der aktuelle, oder?
Das verstößt doch sicher auch gegen irgendwelche Regeln (ich erzeuge im Lauf immer die SELBEN Objekte und lösche sie wieder)

Effizienterweise implementiert man eine solche State-Machine dann auch nicht über Objekt-Variablen sondern über Interfaces. Wie die Lebensdauer der implementierenden Klassen-Instanzen geregelt ist (Referenzzählung, Pool oder Garbage Collection), kann dem Automaten dann nämlich egal sein.

Und nebenbei: Hiermit distanziere ich mich von der Formatierung in deinem Zitat.

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

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:

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:

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:

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... :gruebel: Ich kann mir nicht vorstellen, wie ich den Zustandsgraphen (der mir ja durchaus bewusst ist) komplett in OOP und als Tabelle implementiere. :gruebel:

[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

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