Automaten in Source Code

[Khabarakh]

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.

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

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 ), 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 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 .