codepad

Language:

; regular expressions, part 2

(define (rx-match? rx text)
  (cond ((null? rx) #t)
        ((equal? (car rx) '(bol))
          (match-here (cdr rx) (string->list text)))
        (else (match rx (string->list text)))))

(define (match rx text)
  (cond ((null? rx) #t)
        ((null? text) (match-here rx text))
        (else (or (match-here rx text) (match rx (cdr text))))))

(define (match-here rx text)
  (if (null? rx) #t
    (case (caar rx)
      ((eol) (null? text))
      ((clo) (match-star rx text))
      (else (and (pair? text)
                 (match-one (car rx) (car text))
                 (match-here (cdr rx) (cdr text)))))))

(define (match-star rx text)
  (cond ((match-here (cdr rx) text) #t)
        ((and (pair? text) (match-one (cdar rx) (car text)))
          (match-star rx (cdr text)))
        (else #f)))

(define (match-one rx text)
  (case (car rx)
    ((any) #t)
    ((lit) (char=? (cadr rx) text))
    ((ccl) (member text (cdr rx)))
    ((ncl) (not (member text (cdr rx))))))

(display (rx-match? '((ccl #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) (clo ccl #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9)) "hello")) (newline)

(display (rx-match? '((bol) (any) (clo any) (eol)) "hello")) (newline)

(display (rx-match? '((lit #\h) (lit #\e) (lit #\l) (lit #\l) (lit #\o)) "hello")) (newline)

(display (rx-match? '((bol) (clo lit #\space) (lit #\h) (lit #\e) (lit #\l) (lit #\l) (lit #\o) (clo lit #\space) (eol)) "hello")) (newline)

(display (rx-match? '((bol) (ncl #\x) (clo any) (ccl #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9) (clo lit #\space) (lit x) (eol)) "hello")) (newline)

Private [?]

Run code