(define (match? p dat)
  (or (nullable? p)
      (and (not (null? dat))
	   (initial? p (car dat))
	   (match? (delta p (car dat)) (cdr dat)))))

(define (nullable? p)
  (case (tag p)
    ((0) #f)
    ((1) #t)
    ((c) #f)
    ((+) (or (nullable? (pat1 p)) (nullable? (pat2 p))))
    ((&) (and (nullable? (pat1 p)) (nullable? (pat2 p))))
    ((*) #t)))

(define (initial? p sym)
  (case (tag p)
    ((0) #f)
    ((1) #f)
    ((c) (eqv? (pat1 p) sym))
    ((+) (or (initial? (pat1 p) sym) (initial? (pat2 p) sym)))
    ((&) (or (initial? (pat1 p) sym)
	     (and (nullable? (pat1 p)) (initial? (pat2 p) sym))))
    ((*) (initial? (pat1 p) sym))))

(define (delta p sym)
  (case (tag p)
    ((0) zero)
    ((1) zero)
    ((c) (if (eqv? (pat1 p) sym) one zero))
    ((+) (build-+ (delta (pat1 p) sym)
		  (delta (pat2 p) sym)))
    ((&) (build-+ (build-& (delta (pat1 p) sym) (pat2 p))
		  (if (nullable? (pat1 p)) 
		      (delta (pat2 p) sym)
		      zero)))
    ((*) (build-& (delta (pat1 p) sym) p))))

; Note that the delta rules for & and * introduce duplication --
; the result is really a dag, not a tree.  Ouch.

(define zero            '(0))
(define one             '(1))
(define (build-c sym)   (list 'c sym))
(define (build-+ p1 p2) (list '+ p1 p2))
(define (build-& p1 p2) (list '& p1 p2))
(define (build-* p1)    (list '* p1))

(define (tag p)         (car p))
(define (pat1 p)        (cadr p))
(define (pat2 p)        (caddr p))
