;;; -*- Mode: Lisp; -*-

;;;
;;; TRAVERSE arbeitet INPUT entsprechend der nicht-deterministischen
;;; automatenbeschreibung TABLE ab;
;;; liefert Elemente aus Spalte 0 bei erfolgreicher Erkennung, ansonsten NIL.
;;; Epsilon-Uebergaenge werden beruecksichtigt, bei Epsilon-Zykeln
;;; geraet die Funktion jedoch in eine Endlos-Schleife!
;;;


(defun traverse-string (table input &optional 
                                    (state 0) (position 0) (n (length input)))
  (append
    ;; Folge zunaechst allen Epsilon-Uebergaengen und sammele die Endzustaende
    (loop for next-eps-state in (aref table state 1)
          append (traverse-string table input next-eps-state position n))
    ;; Arbeite das naechste Eingabezeichen ab
    ;; oder
    ;; falls die Eingabe abgearbeitet ist
    (if (= n position)
        ;; ist es ein Endzustand ? Dann bestimme seinen "Wert".
        (when (aref table state 0) (list (aref table state 0)))
      ;; sonst arbeite das naechste Eingabezeichen ab.
      (loop for next-state in 
            (aref table state (token2code (schar input position)))
            append (traverse-string table input next-state (1+ position) n)))))