APPENDIX B
Lisp Program to Generate State Tables
During the course of research work leading to this thesis it was often necessary to obtain the state tables of automata that realized the regular events being studied. The manual method of generating the state tables is lengthy, and highly prone to human error, so early on in the course of this work it was decided to automate this chore. Due to the high recursiveness of the process of finding derivatives of regular expressions [6], LISP 1.5 was chosen as the language in which to write the coding. Another advantage of lisp is its dynamic storage allocation, which allows recursing deeply to evaluate complex expressions, as all unused storage is available for each deep recursion. A brief description of the program follows:
READER reads the regular expressions to be processed.
EXP translates the expression into an internal list format. That is the expression ((L+0)(L+1))* becomes (STAR (CAT (UNION L 0) (UNION L 1))).
DERIV takes the derivative [6] of the given expression with respect to a given member of the alphabet.
SIMP uses various rules to reduce a regular expression to its simplest form.
AUT finds the state table of an automaton that realizes the regular expression, by taking successive derivatives until it terminates. [6].
PRINTER prints the expressions.
REVTAB reverses the state table, finding the table of the reverse event. Reversing the table twice yields the reduced state table of the automaton.
DIFF is the main-line program that calls the others in the appropriate order.
The other functions defined are used by the major functions to perform minor operations as required. The complete lisp program is reproduced below:
CSET (SIGMA (B C D E F G H I J K L M N O P Q R S T))
CSET (l l)
CSET (BETA (L 0 1))
CSET (L $$$L$)
DEFINE ((
(REVERSE (LAMBDA (X) (COND
((ATOM X) X)
((NULL (CDR X)) (LIST (REVERSE (CAR X))))
(T (APPEND (REVERSE (CDR X)) (LIST (REVERSE (CAR X))))) )))
(READER (LAMBDA () (PROG (X Y)
A
(SETQ X (ADVANCE))
(COND ((CCLASS X (QUOTE $$$ $)) (GO A ))
((CCLASS X (QUOTE $$$.$)) (RETURN (QUOTE END)))
((CCLASS X (QUOTE $$$,$)) (RETURN (REVERSE Y)))
((CCLASS X (QUOTE $$$($)) (SETQ X ( QUOTE LP)))
((CCLASS X (QUOTE $$$)$)) (SETQ X (QUOTE RP)))
((CCLASS X (QUOTE $$$*$)) (SETQ X (QUOTE ST)))
((CCLASS X (QUOTE $$$+$)) (SETQ X (QUOTE PL)))
((CCLASS X (QUOTE $$$'$)) (SETQ X (QUOTE NE)))
(T (SETQ X (PROG2 (PACK X) (MKATOM)))))
(SETQ Y (CONS X Y))
(GO A) )))
(DIFF (LAMBDA () (PROG (X Y)
(PRINT (QUOTE START))
A
(TERPRI) (TERPRI)
(SETQ X (READER))
(COND ((EQUAL X (QUOTE END)) (RETURN X)))
(PRINTER (SETQ X (AUT (EXP X))))
(PRINTER (SETQ X (REVTAB X)))
(PRINTER (SETQ X (REVTAB X)))
(GO A) )))
(ALPHA (LAMBDA (E) (COND
((MEMBER (CAR E) (CONS I BETA)) E)
(T NlL) )))
(PRIM (LAMBDA (E) (PROG (X)
(COND ((SETQ X (ALPHA E)) (RETURN X))
((NOT (EQ (CAR E) (QUOTE LP))) (RETURN NIL))
((NOT (SETQ X (EXP (CDR E))) (RETURN NIL))
((NULL (CDR X)) (RETURN NIL))
((EQ (CADR X) (QUOTE RP)) (RETURN (CONS (CAR X) (CDDR X))))
(T NlL)))))
(SEC (LAMBDA (E) (PROG (X)
(COND ((NULL (SETQ X (PRIM E))) (RETURN NIL))
((NULL (CDR X)) (RETURN X))
((EQ (CADR X) (QUOTE NE))
(RETURN (CONS (LIST (QUOTE NEG) (CAR X))
(CDDR X))))
((NOT (EQ (CADR X) (QUOTE ST))) (RETURN X))
(T (RETURN (CONS (LIST (QUOTE STAR) (CAR X)) (CDDR X))))
)))
(TERM (LAMBDA (E) (PROG (X Y Z)
(SETQ X (SEC E))
(COND ((OR (NULL X) (NULL (CDR X))) (RETURN X)))
(SETQ Z (CDR X))
(SETQ Y (QUOTE CAT))
(COND ((SETQ Z (TERM Z))
(RETURN (CONS (LIST Y (CAR X) (CAR Z)) (CDR Z))))
(T (RETURN X))) )))
(EXP (LAMBDA (E) (PROG (EX X Y)
(COND ((NULL E) (RETURN NIL))
((NULL (SETQ X (TERM E))) (RETURN NIL)))
(SETQ EX (CAR X))
E
(COND ((NULL (CDR X)) (RETURN EX))
((NULL (EQ (CADR X) (QUOTE PL))) (RETURN (CONS EX (CDR X))))
((NULL (SETQ Y (TERM (CDDR X)))) (RETURN NIL)))
(SETQ EX (LIST (QUOTE UNION) EX (CAR Y)))
(SETQ X Y)
(GO E) )))
(DELTA (LAMBDA (X) (COND
((AND (ATOM X) (EQ X L)) L)
((AND (ATOM X) (EQ X I)) L)
((AND (EQ (CAR X) (QUOTE CAT)) (DELTA (CADR X)) (DELTA (CADDR X))) L)
((AND (EQ (CAR X) (QUOTE UNION)) (OR (DELTA (CADR X)) (DELTA (CADDR X)))) L)
((EQ (CAR X) (QUOTE STAR)) L)
((EQ (CAR X) (QUOTE NEG)) (COND ((DELTA (CADR X)) NIL)(T L)))
(T NIL) )))
(DERIV (LAMBDA (X Y) (COND
((EQ Y L) X)
((ATOM X) (COND ((EQ X Y) L)
((EQ X I) I)
(T NIL) ))
((EQ (CAR X) (QUOTE CAT)) (LIST (QUOTE UNION)
(LIST (CAR X) (DERIV (CADR X) Y) (CADDR X))
(LIST (CAR X) (DELTA (CADR X)) (DERIV (CADDR X) Y)) ))
((EX (CAR X)(QUOTE UNION)) (LIST (CAR X) (DERIV (CADR X) Y)
(DERIV (CADDR X) Y) ))
((EQ (CAR X) (QUOTE STAR))
(LIST (QUOTE CAT) (DERIV (CADR X) Y) X))
((EQ (CAR X) (QUOTE NEG)) (LIST (CAR X) (DERIV (CADR X) Y)))
(T (NOT (PRINT (QUOTE $$$DERIV ERROR$)))) )))
(UNITE (LAMBDA (X) (COND
((ATOM X) (LIST X))
((NOT (EQ (CAR X) (QUOTE UNION))) (LIST X))
(T (APPEND (UNITE (CADR X)) (UNITE (CADDR X)))) )))
(MEMBAR (LAMBDA (X Y) (COND
((NULL Y) NIL)
((EQUAL X (CAR Y)) T)
(T (MEMBAR X (CDR Y))) )))
(SIMP (LAMBDA (X) (COND
((ATOM X) X)
(T (PROG (M N P)
(SETQ P (CAR X))
(SETQ M (SIMP (CADR X)))
(COND ((EQ P (QUOTE STAR)) (COND ((NULL M) (RETURN L))
((EQ M L) (RETURN L))
((EQ MI) (RETURN I))
((FULL M) (RETURN I))
((EQ (CAR M) (QUOTE STAR)) (RETURN M))
(T (RETURN (LIST P M)) )))
((EQ P (QUOTE NEG)) (COND
((NULL M) (RETURN I))
((EQ M I) (RETURN NIL))
((EQ (CAR M) (QUOTE NEG)) (RETURN (CADR M)) )
(T (RETURN (LIST P M))))))
(SETQ N (SIMP (CADDR X)))
(COND ((EQ P (QUOTE UNION) (COND ((NULL M) (RETURN N))
((NULL N) (RETURN M))
(((E M I) (RETURN I))
((EQ N I) (RETURN I))
((AND (ATOM N) (DELTA (DERIV M N))) (RETURN M))
((AND (ATOM M) (DELTA (DERIV N M))) (RETURN N))
(T RETURN (TREE (MERGE (APPEND (UNITE M) (UNITE N)))))) ))
((EQ P (QUOTE CAT)) (COND ((NULL M) (RETURN NIL))
((NULL N) (RETURN NIL))
((EQ M L) (RETURN N))
((EQ N L) (RETURN M))
(T (RETURN (LIST P M N)) )))
(T (RETURN (NOT (PRINT (QUOTE $$$SIMP ERROR$)))))) )) )))
(SAME (LAMBDA (X Y) (COND
((NULL Y) NIL)
((EQUAL X (CADR Y)) (CAR Y))
(T (SAME X (CDDR Y))) )))
(AUT LAMBDA (X) (PROG
(FINAL TEMP ALF NEW OLD SIG TABLE ROW)
(SETQ SIG SIGMA)
(SETQ FINAL (LIST (QUOTE A) X))
(SETQ TEMP FINAL)
(SETQ TABLE NIL)
NEXT
(COND ((NULL TEMP) (RETURN TABLE)))
(SETQ ROW (LIST (CAR TEMP)))
(PRIN1 (CAR TEMP))
(PRIN1(QUOTE $$$ = $))
(FORM (CADR TEMP))
(TERPRI)
(TERPRI)
(SETQ ALF (CDR BETA))
AGAIN
(SETQ NEW (SIMP (DERIV (CADR TEMP) (CAR ALF))))
(COND ((SETQ OLD (SAME NEW FINAL)) (GO AHEAD)))
(COND ((NULL (SETQ OLD (CAR SIG))) (RETURN TABLE)))
(SETQ SIG (CDR SIG))
(SETQ NEW (LIST OLD NEW))
(SETQ FINAL (APPEND FINAL NEW))
(SETQ TEMP (APPEND TEMP NEW))
AHEAD
(SETQ ROW (APPEND ROW (LIST OLD)))
(SETQ ALF (CDR ALF)
(COND (ALF (GO AGAIN)))
(SETQ ROW (APPEND ROW (DEL (CADR TEMP))))
(SETQ TEMP (CDDR TEMP))
(SETQ TABLE (APPEND TABLE (LIST ROW)))
(GO NEXT) )))
(DEL (LAMBDA (X) (COND
((DELTA X) (LIST (QUOTE LAM)))
(T (LIST (QUOTE PHI))) )))
(PRINTER (LAMBDA (X) (PROG (TAB)
(SETQ TAB X)
(TERPRI) (TERPRI)
AROUND
(COND ((NULL TAB) (RETURN NIL)))
(PRINT (CAR TAB))
(SETQ TAB (CDR TAB))
(GO AROUND) )))
(LAST (LAMBDA (X) (COND
((NULL X) NIL)
((NULL (CDR X)) (CAR X))
(T (LAST (CDR X))) )))
(MAPCAR (LAMBDA (X FN) (COND
((NULL X) NIL)
(T (CONS (FN (CAR X)) (MAPCAR (CDR X) FN))) )))
(REVTAB (LAMBDA (X) (PROG
((INPUT INP NEW OLD SIG TABLE ROW FINAL TEMP ALF)
(SETQ SIG SIGMA)
(SETQ NEW NIL)
(SETQ INP X)
OVER
(COND ((EQ (QUOTE LAM) (LAST (CAR INP)))
(SETQ NEW (APPEND NEW (LIST (CAAR INP))))))
(SETQ INP (CDR INP))
(COND (INP (GO OVER)))
(SETQ FINAL (LIST (QUOTE A) NEW))
(SETQ TEMP FINAL)
(SETQ TABLE NIL)
NEXT
(COND ((NULL TEMP) (RETURN TABLE)))
(SETQ ROW (LIST (CAR TEMP)))
(SETQ ALF (CDR BETA))
(SETQ INPUT X)
AGAIN
(SETQ NEW NIL)
(SETQ INPUT (MAPCAR INPUT (FUNCTION CDR)))
(SETQ OLD INPUT)
(SETQ INP X)
LOOP
(COND ((MEMBER (CAAR OLD) (CADR TEMP))
(SETQ NEW (APPEND NEW (LIST (CAAR INP))))))
(SETQ OLD (CDR OLD)
(SETQ INP (CDR INP))
(COND (OLD (GO LOOP)))
(COND ((SETQ OLD (SAME NEW FINAL)) (GO AHEAD)))
(SETQ OLD (CAR SIG))
(SETQ SIG (CDR SIG))
(SETQ NEW (LIST OLD NEW))
(SETQ FINAL (APPEND FINAL NEW))
(SETQ TEMP (APPEND TEMP NEW)
AHEAD
(SETQ ROW (APPEND ROW (LIST OLD)))
(SETQ ALF (CDR ALF))
(COND (ALF (GO AGAIN)))
(SETQ ROW (APPEND ROW (DELT (CADR TEMP))))
(SETQ TEMP (CDDR TEMP))
(SETQ TABLE (APPEND TABLE (LIST ROW)))
(GO NEXT) )))
(DELT (LAMBDA (X) (COND
((MEMBER (QUOTE A) X) (LIST (QUOTE LAM)))
(T (LIST (QUOTE PHI))) )))
(FULL (LAMBDA (X) (PROG (Y)
(SETQ Y (CDR BETA))
A
(COND ((NULL Y) (RETURN T))
((NULL (DELTA (DERIV X (CAR Y)))) (RETURN NIL)))
(SETQ Y (CDR Y))
(GO A) )))
(MERGE (LAMBDA (X) (COND
((NULL (CDR X)) X)
((MEMBAR (CAR X) (CDR X)) (MERGE (CDR X)))
(T (CONS (CAR X) (MERGE (CDR X)))) )))
(TREE (LAMBDA (X) (COND
((NULL (CDR X)) (CAR X))
(T (LIST (QUOTE UNION) (CAR X) (TREE (CDR X)))) )))
(FORM (LAMBDA (X) (PROG ()
(COND ((ATOM X) (PRIN1 X))
((EQ (CAR X) (QUOTE UNION) (UNIONP (CDR X)))
((EQ (CAR X) (QUOTE CAT)) (CATP (CDR X)))
((EQ (CAR X)(QUOTE STAR)) (STARP (CADR X)))
((EQ (CAR X) (QUOTE NEG)) (NEGP (CADR X))) ) )))
(UNIONP (LAMBDA (X) (PROG ()
(FORM (CAR X))
(PRIN1 (QUOTE $$$+$))
(FORM (CADR X)) )))
(CATP (LAMBDA (X) (PROG ()
(COND ((EQ (CAAR X) (QUOTE UNION)) (WRAP (CAR X)))
(T (FORM (CAR X))))
(COND ((EQ (CAADR X) (QUOTE UNION)) (WRAP (CADR X)))
(T (FORM (CADR X))) ) )))
(STARP (LAMBDA (X) (PROG ()
(COND ((ATOM X) (PRIN1 X))
(T (WRAP X)))
(PRIN1 (QUOTE $$$*$)) )))
(NEGP (LAMBDA (X) (PROG ()
(COND ((ATOM X) (PRIN1 X))
(T (WRAP X)))
(PRIN1 (QUOTE $$$'$)) )))
(WRAP (LAMBDA (X) (PROG ()
(PRIN1 (QUOTE $$$($))
(FORM X)
(PRIN1 (QUOTE $$$)$)) )))
))
DIFF ()
Note that to find automata of regular expressions over a larger alphabet, all that need be changed in this program is the initial CSET (BETA (L 0 1)) line.
