51 lines
1.3 KiB
Racket
51 lines
1.3 KiB
Racket
#lang s-exp "../../lang/base.rkt"
|
|
|
|
(require "run-benchmark.rkt")
|
|
(provide recursive-nfa-benchmark)
|
|
|
|
; The recursive-nfa benchmark. (Figure 45, page 143.)
|
|
|
|
(define (recursive-nfa input)
|
|
|
|
(define (state0 input)
|
|
(or (state1 input) (state3 input) #f))
|
|
|
|
(define (state1 input)
|
|
(and (not (null? input))
|
|
(or (and (char=? (car input) #\a)
|
|
(state1 (cdr input)))
|
|
(and (char=? (car input) #\c)
|
|
(state1 input))
|
|
(state2 input))))
|
|
|
|
(define (state2 input)
|
|
(and (not (null? input))
|
|
(char=? (car input) #\b)
|
|
(not (null? (cdr input)))
|
|
(char=? (cadr input) #\c)
|
|
(not (null? (cddr input)))
|
|
(char=? (caddr input) #\d)
|
|
'state2))
|
|
|
|
(define (state3 input)
|
|
(and (not (null? input))
|
|
(or (and (char=? (car input) #\a)
|
|
(state3 (cdr input)))
|
|
(state4 input))))
|
|
|
|
(define (state4 input)
|
|
(and (not (null? input))
|
|
(char=? (car input) #\b)
|
|
(not (null? (cdr input)))
|
|
(char=? (cadr input) #\c)
|
|
'state4))
|
|
|
|
(or (state0 (string->list input))
|
|
'fail))
|
|
|
|
(define (recursive-nfa-benchmark)
|
|
(let ((input (string-append (make-string 133 #\a) "bc")))
|
|
(run-benchmark "Recursive nfa"
|
|
(lambda () (recursive-nfa input))
|
|
1000)))
|