Material	OOP Grundlagen Delphi Software-Technik Bonsai Digitaltechnik Ereignisse Grafik UML Netze Fischertechnik Tipps Werkzeuge Literatur Automaten Sprachen Datenbanken XML Prolog Berechenbarkeit Pfad: Startseite / Fächer / Informatik / Material
Autor: mk 13.06.2008 14:46 3045	Automatentheorie

Fließkomma-Akzeptor

Fließkommazahlen kommen in allen Programmiersprachen vor. Es soll ein Akzeptor konstruiert werden, der Zahlen wie 3 , -7 , +12.3 , -5e-7 , 12.345E+987 akzeptiert.

zur Fragestellung und möglicher, alternativer Lösung

Das Werkzeug GoldParser konstruiert solche Automaten selbständig. Voraussetzung ist eine klare Beschreibung der Token z.B. durch reguläre Ausdrücke. GoldParser verwendet dazu eine eigene Notation, die hier erläutert wird.

GoldParser-Beschreibung

float.grm

GoldParser-Lösung

Übertragung auf einen Automatengraphen

Interessanterweise ist der automatisch konstruierte Automat bis auf die Berücksichtigung der Whitespaces und anderer Benennung identisch zu dem "von Hand" konstruierten.

Pascal-Funktion is_real

  function is_real(s : string) : boolean;
  type
    TZustand = (s0,v1,z1,p,z2,e,v2,z3,f);
    TEingabe = (pm,ziff,exp,punkt,sonst);
  const
    Zeichen : array[TEingabe] of set of char =
              ( ['+','-'],
                ['0'..'9'],
                ['e','E'],
                ['.'],
                [chr(0)..chr(255)]-['+','-']-['0'..'9']-['e','E']-['.']);
    startzustand = s0;
    Endzustaende : set of TZustand = [z1,z2,z3];
    fue   : array[TZustand,TEingabe] of TZustand =
            ((v1,z1,f,f,f),
             (f,z1,f,f,f),
             (f,z1,e,p,f),
             (f,z2,f,f,f),
             (f,z2,e,f,f),
             (v2,z3,f,f,f),
             (f,z3,f,f,f),
             (f,z3,f,f,f),
             (f,f,f,f,f));
    (*
       die Tabelle ist so aufgebaut:
       ( (alle Folgezustände zum ersten Zustand s0,
          geordnet nach den möglichen Eingaben),
         (alle Folgezustände zum zweiten Zustand v1),
         ....
         (alle Folgezustände zum letzten Zustand f) )
    *)
  var
    zustand     : TZustand;
    eingabe,ein : TEingabe;
    i           : integer;
  begin
    // Startzustand setzen
    zustand := startzustand;
    // alle Eingabezeichen durchgehen
    for i := 1 to Length(s) do
    begin
      // Ermittlung der Eingabe
      for ein := low(TEingabe) to high(TEingabe) do
        if s[i] in Zeichen[ein] then eingabe := ein;
      // neuer Zustand
      zustand := fue[zustand,eingabe];
    end;
    // zustand Endzustand?
    result := zustand in Endzustaende;
  end;

is_real.zip

lokal