Now the segment-pattern matching functions. segment -match is similar to the version presented as part of ELIZA. The difference is in how we determine pos, the position of the first element of the input that could match the next element of the pattern after the segment variable. In ELIZA, we assumed that the segment variable was either the last element of the pattern or was followed by a constant. In the following version, we allow nonconstant patterns to follow segment variables. The function f i rs t - ma t c h - pos is added to handle this. If the following element is in fact a constant, the same calculation is done using pos i t i on. If it is not a constant, then we just return the first possible starting position-unless that would put us past the end of the input, in which case we return nil to indicate failure:

(defun segment-match (pattern input bindings &optional ( s t a r t 0))

"Match the segment pattern ((?* var) . pat) against i n p u t ."

( l e t ((var (second ( f i r s t p a t t e r n ) ) )

(pat ( r e s t p a t t e r n ) ) )

( i f ( n u l l pat)

(match-variabl e var input bindings)

( l e t ((pos ( f i r s t -match-pos ( f i r s t pat) input s t a r t ) ) )

( i f ( n u l l pos)

f a i 1

( l e t ((b2 (pat-match pat (subseq input pos)

(match-vari abl e var (subseq input 0 pos)

bindings))))

;; If t h i s match f a i l e d , t r y another longer one

( i f (eq -b2 f a i l

(segment-match pattern input bindings (+ pos 1))

b2)))))))

(defun f i r s t -match-pos ( p a t l input s t a r t )

"Find the f i r s t position that patl could possibly match input, s t a r t i n g a t position s t a r t . If patl i s non-constant, then j u s t return s t a r t ."

(cond ((and (atom pat11 (not (variable-p patl)))

( p o s i t i o n patl input : s t a r t s t a r t : t e s t #'equal))

((< s t a r t (length i n p u t ) ) s t a r t )

(t n i l ) ) )