Re: Ugly loop

Ulrich Hobelmann <u.hobelmann@xxxxxx> writes:

> Hi, I just started coding what I always wanted to try out: doing some
> stuff with finite automata and later regular expressions.
> Right now I wrote a rather ugly loop to create an NFA from a
> sequential string:
> (loop with first = (make-instance 'state)
> with nfa = (make-instance 'nfa :start-state first)
> for c in (cons nil (loop for c across string collect c))
> for source = first then target
> for target = (make-instance 'state) then (make-instance 'state)
> do (progn (add-state nfa source)
> (link source c target))
> finally (progn (add-state nfa target)
> (setf (end-state nfa) target)
> (return nfa))))

I think it looks reasonable. (The "then" part of "for target" is
redundant.) A different possibility is a recursive solution, if
you're unhappy with the iteration (untested, of course; hope there are
no stupid mistakes):

(let ((nfa (make-instance 'nfa :start-state (make-instance 'state)))
(label-list (cons nil (loop for c across string collect c))))
(labels ((extend-nfa (source target)
(add-state nfa source)
(cond (label-list
(link source (pop label-list) target)
(extend-nfa target (make-instance 'state)))
(t (add-state nfa target)
(setf (end-state nfa) target)))))
(extend-nfa (start-state nfa) (make-instance 'state))

Rob St. Amant

Relevant Pages