亲手实现一个正则引擎！
众所周知，一类经典的自动机是有限状态自动机。它们识别的语言是正则语言，而正则表达式能够匹配的字符串的集合也是正则语言。
（如果你之前没有了解过，询问 AI 或是使用搜索引擎都很适合快速了解）
导数法#
要匹配一个正则表达式，最经典的方法就是构造对应的 NFA，然后通过一些手法转化为 DFA。但这太复杂了。有没有更简单的方法呢？
有一种被称为“导数法”的方法。
思想非常简单：我们将构造出的 DFA 编码为一个正则。这样，转移之后相当于产生了一个新的自动机，也就是一个新的正则表达式。
原始正则表达式是 $r$。那么，$r$“吃掉”一个字符 $c$ 之后产生的表达式 $r'$，能匹配的所有字符串就是所有满足 (match? (cat c s) r) 的字符串 $s$。
读者可以自行思考一下导数公式。
我想用代码表示是最清晰的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| (define (derive re c)
(match re
[(Void) (Void)]
[(Eps) (Void)]
[(Dot) (Eps)]
[(Chr ch) (if (char=? ch c) (Eps) (Void))]
[(Alt e1 e2)
(make-alt (derive e1 c) (derive e2 c))]
[(Cat e1 e2)
(if (nullable? e1)
(make-alt (make-cat (derive e1 c) e2) (derive e2 c))
(make-cat (derive e1 c) e2))]
[(Star e)
(make-cat (derive e c) (Star e))]))
|
导数法将是我们使用的核心算法。
特性与抽象语法#
我们将实现支持连接（cat），选择（alt）与闭包（kleene star）三种特性的正则表达式。同时添加“任意字符”（Dot）这种有用的语法糖（为了辅助包含匹配）。
使用 S-expression 以及 racket 结构体表达正则：
1
2
3
4
5
6
7
| regexp ::= (Void)
| (Eps)
| (Chr Char)
| (Cat regexp regexp)
| (Alt regexp regexp)
| (Star regexp)
| (Dot)
|
定义语法树节点：
1
2
3
4
5
6
7
| (struct Eps () #:transparent) ;; 空串 ε
(struct Void () #:transparent) ;; 空集 φ (匹配失败)
(struct Chr (c) #:transparent) ;; 字符 c
(struct Cat (e1 e2) #:transparent) ;; 连接 e1 e2
(struct Alt (e1 e2) #:transparent) ;; 选择 e1 | e2
(struct Star (e) #:transparent) ;; 克林闭包 e*
(struct Dot () #:transparent) ;; 语法糖：匹配任意字符
|
接下来我们要定义 Cat 和 Alt 的构造函数。这很重要，因为其中引入了一些简单的化简。这些化简是防止复杂度退化的重要工具。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| (define (make-cat a b)
(match* (a b)
[((Void) _) (Void)]
[(_ (Void)) (Void)]
[((Eps) r) r]
[(r (Eps)) r]
[(_ _) (Cat a b)]))
(define (make-alt a b)
(match* (a b)
[((Void) _) b]
[(_ (Void)) a]
[(r r) r]
[(_ _) (Alt a b)]))
|
流程设计#
导数法是步进式的：给定一个正则和一个字符，返回一个新的正则。所以我们的匹配也是步进式的。
我们将字符串转换为列表（相当于没有惰性求值的字符流）。然后一个一个吃字符，直到吃完为止。
这时如何看匹不匹配呢？我们需要一个 nullable? 函数来判断一个正则能否匹配空串。如果字符串结束时的正则是 nullable? 的，则匹配（接受），否则不匹配（拒绝）。
依然请读者自行思考实现。
1
2
3
4
5
6
7
8
9
| (define (nullable? re)
(match re
[(Eps) #t]
[(Void) #f]
[(Dot) #f]
[(Chr _) #f]
[(Star _) #t]
[(Alt a b) (or (nullable? a) (nullable? b))]
[(Cat a b) (and (nullable? a) (nullable? b))]))
|
有许多正则表达式，它们关于特定字符的后继会被多次计算。这是很大的开销，所以我们用哈希表把它们存起来。
我们将使用一个二维哈希表，即 Hash<regexp -> Hash<char -> regexp>>。
这样，判定给定字符串是否被给定正则接受就是简单的了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| (define (make-matcher re)
(define cache (make-hash))
(define (match-loop cur s)
(cond
[(null? s) (nullable? cur)]
[else
(let ([c (car s)])
(define next
(hash-ref!
(hash-ref! cache cur (lambda () (make-hash)))
c
(lambda ()
(derive cur c))))
(if (Void? next)
#f
(match-loop next (cdr s))))]))
(lambda (str)
(match-loop re (string->list str))))
|
至此，我们实现了一个基础的正则判定器。同时埋下伏笔。
从头到尾扫描并对每个子串暴力判定显然是不好的，就像 brute-force 字符串模式匹配一样。
要匹配正则在字符串的哪个地方出现了，我们有更精妙的做法。
辅助正则#
1
| (define forward (Cat (Star (Dot)) regexp))
|
用这个正则去匹配字符串（的前缀），我们就知道原始正则 regexp 在字符串中是否出现过了。
通过对匹配过程的魔改，我们可以知道辅助正则匹配的第一个（或者最后一个，甚至中间任意一个）字符串前缀是什么。具体而言，对于所有 forward 满足 nullable? 的下标，我们记录其最小值或最大值。
至于记录最小值还是最大值，决定了匹配行为。我的代码选择了最小值，也就是最左最短匹配。如果要实现贪婪匹配，需要记录最大值。
我们记被我们记录的那个（能够被辅助正则匹配的）字符串前缀为 S，长度为 E。
1
| (define backward (re-reverse re))
|
这是另一个辅助正则。其中，re-reverse 函数用来将一个正则表达式“反转”。即原始正则能匹配的任意字符串反转后都能被它返回的正则匹配，且它返回的正则不能匹配其他任何字符串。
它的实现在这里：
1
2
3
4
5
6
| (define (re-reverse re)
(match re
[(Cat e1 e2) (make-cat (re-reverse e2) (re-reverse e1))]
[(Alt e1 e2) (make-alt (re-reverse e1) (re-reverse e2))]
[(Star e) (Star (re-reverse e))]
[_ re]))
|
二遍扫描#
将 S 反转。
然后用 backward 匹配它（反转后的新字符串）的一个前缀。记长度为 T。
那么原始正则 regexp 能够匹配的子串（的下标区间）就是 $[E - T, E)$.
完整代码#
精确判定和位置匹配都有一些测试用例。Gemini 写的。有比较好的注释。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
| #lang racket
(require srfi/13)
;; ---------------------------------------------------------
;; 1. 定义正则表达式的 AST (抽象语法树)
;; ---------------------------------------------------------
(struct Eps () #:transparent) ;; 空串 ε
(struct Void () #:transparent) ;; 空集 φ (匹配失败)
(struct Chr (c) #:transparent) ;; 字符 c
(struct Cat (e1 e2) #:transparent) ;; 连接 e1 e2
(struct Alt (e1 e2) #:transparent) ;; 选择 e1 | e2
(struct Star (e) #:transparent) ;; 克林闭包 e*
(struct Dot () #:transparent) ;; 语法糖：匹配任意字符
(define (make-cat a b)
(match* (a b)
[((Void) _) (Void)]
[(_ (Void)) (Void)]
[((Eps) r) r]
[(r (Eps)) r]
[(_ _) (Cat a b)]))
(define (make-alt a b)
(match* (a b)
[((Void) _) b]
[(_ (Void)) a]
[(r r) r]
[(_ _) (Alt a b)]))
(define (nullable? re)
(match re
[(Eps) #t]
[(Void) #f]
[(Dot) #f]
[(Chr _) #f]
[(Star _) #t]
[(Alt a b) (or (nullable? a) (nullable? b))]
[(Cat a b) (and (nullable? a) (nullable? b))]))
(define (derive re c)
(match re
[(Void) (Void)]
[(Eps) (Void)]
[(Dot) (Eps)]
[(Chr ch) (if (char=? ch c) (Eps) (Void))]
[(Alt e1 e2)
(make-alt (derive e1 c) (derive e2 c))]
[(Cat e1 e2)
(if (nullable? e1)
(make-alt (make-cat (derive e1 c) e2) (derive e2 c))
(make-cat (derive e1 c) e2))]
[(Star e)
(make-cat (derive e c) (Star e))]))
(define (make-matcher re)
(define cache (make-hash))
(define (match-loop cur s)
(cond
[(null? s) (nullable? cur)]
[else
(let ([c (car s)])
(define next
(hash-ref!
(hash-ref! cache cur (lambda () (make-hash)))
c
(lambda ()
(derive cur c))))
(if (Void? next)
#f
(match-loop next (cdr s))))]))
(lambda (str)
(match-loop re (string->list str))))
;; ---------------------------------------------------------
;; 测试
;; ---------------------------------------------------------
;; 正则: a(b|c)*d
(define my-re
(make-cat (Chr #\a)
(make-cat (Star (make-alt (Chr #\b) (Chr #\c)))
(Chr #\d))))
(define matches? (make-matcher my-re))
(displayln "Test Cases:")
(displayln (matches? "ad")) ;; #t
(displayln (matches? "abd")) ;; #t
(displayln (matches? "abccbd")) ;; #t
(displayln (matches? "add")) ;; #f
(displayln (matches? "a")) ;; #f
;; 压力测试：状态缓存机制
;; 第一次运行会构建缓存，第二次运行直接查表
(time (for ([i 10000]) (matches? "abcbcd")))
(define (re-reverse re)
(match re
[(Cat e1 e2) (make-cat (re-reverse e2) (re-reverse e1))]
[(Alt e1 e2) (make-alt (re-reverse e1) (re-reverse e2))]
[(Star e) (Star (re-reverse e))]
[_ re]))
(define (make-search re)
(define forward (make-cat (Star (Dot)) re))
(define backward (re-reverse re))
(define cache (make-hash))
(define (match-loop cur s idx)
(cond
[(nullable? cur) idx]
[(>= idx (string-length s)) #f]
[else
(let ([c (string-ref s idx)])
(define next
(hash-ref!
(hash-ref! cache cur (lambda () (make-hash)))
c
(lambda ()
(derive cur c))))
(if (Void? next)
#f
(match-loop next s (add1 idx))))]))
(lambda (str)
(define E (match-loop forward str 0))
(if E
(begin
(let ([T (match-loop backward (string-reverse str 0 E) 0)])
(cons (- E T) E)))
#f)))
;; ---------------------------------------------------------
;; 4. 测试用例
;; ---------------------------------------------------------
(define search (make-search my-re))
(displayln "=== Standard Cases ===")
(displayln (search "ad")) ;; '(0 . 2)
(displayln (search "xxxad")) ;; '(3 . 5)
(displayln (search "adxxx")) ;; '(0 . 2) -- 验证最左匹配
(displayln (search "xxxadxxx")) ;; '(3 . 5)
(displayln (search "abccbd")) ;; '(0 . 6)
(displayln (search "z")) ;; #f
(displayln "=== Edge Cases ===")
;; 多个匹配，应该返回最左边的那个
(displayln (search "ad...ad")) ;; '(0 . 2)
;; 贪婪/非贪婪行为测试
;; 这里的实现是"最短匹配" (reluctant)，因为遇到 nullable 就立即返回了
;; 对于 a(b|c)*d，如果输入 abdbd
;; forward 会在第一个 d 处 (index 3) 停止。
;; backward 从 d 反向匹配到 a。
;; 结果应该是 '(0 . 3) -> "abd"
(displayln (search "abdbd")) ;; '(0 . 3)
;; 复杂一点的
(displayln (search "zzzaaaaaaddddzzz")) ;; '(8 . 10) -> 匹配了第一个 a..d 即 "ad"
;; 解释：因为 forward 匹配 .*a(b|c)*d。
;; .* 吃了 "zzzaaaa"，然后 a 匹配 "a"，然后 d 匹配 "d"。
;; 这里其实取决于 .* 的结合性，但在导数语义下，一旦 nullable 就停，这通常意味着匹配了"能匹配的最短前缀"。
|
复杂度问题#
收回伏笔。
1
2
3
4
5
6
7
8
9
10
| (define (test-performance n)
(printf "Testing n=~a... " n)
(define part1 (for/fold ([acc (Eps]) ([i n]) (make-cat (make-alt (Eps) (make-chr #\a)) acc)))
(define part2 (for/fold ([acc (Eps]) ([i n]) (make-cat (make-chr #\a) acc)))
(define re (make-cat part1 part2))
(define matcher (make-matcher re))
(define input (make-string (* 2 n) #\a))
(time (matcher input)))
(test-performance 50)
|
这是一个经典的 hack。用类似下面的正则去匹配全 a 字符串：
1
| #(struct:Cat #(struct:Cat #(struct:Alt (#(struct:Chr a) #(struct:Eps))) #(struct:Alt (#(struct:Chr a) #(struct:Eps)))) #(struct:Cat #(struct:Chr a) #(struct:Chr a)))
|
即 a|Eps a|Eps a a。
你会注意到数据规模达到 50 的时候卡死了。事实上，我们的简单引擎在这个 hack 下是指数复杂度（具体是 $O(2^n)$）的。
问题的发掘，以及效率优化#
问题在于缓存没有生效。具体而言，(Alt (Alt (Chr #\a) (Chr #\a)) (Chr #\b)) 和 (Alt (Alt (Chr #\a) (Chr #\b)) (Chr #\a)) 在语义上是相同的，但是结构上却不相等。这时两个状态都会被分别扔进缓存，复杂度就退化了。
如何解决？我们需要把 Alt 节点拍平，并且按照一定顺序排序。
“按照一定顺序排序”意味着我们需要给节点定义一个全序关系。这是难办的。
直接递归比较会导致复杂度退化。
经验丰富的读者们大概会想到给每个节点赋一个唯一的 uid。这是一个好主意，但是需要添加新的字段（表达式问题的一个侧面）。我比较懒，不想这么做。
我们可以利用一种类似符号类型的驻留机制。使用哈希表存储所有出现过的表达式节点，来实现对于两个值相同的节点，保证它们是 eq? 的（即在内存中是同一个对象）。对于一个新构造的节点，如果它在哈希表中出现过，返回哈希表中记录的值，否则将这个节点构造出来扔进哈希表。
这样，比较时就可以利用 eq-hash-code。虽然可能有冲突，但是概率很小（因为 eq-hash-code 的返回值是 61-62 位整数）。
这份代码是 Gemini 帮忙写的。对于上面那个性能测试，在 $n=100$ 时大概需要一秒多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
| #lang racket
(require srfi/13)
;; 1. 定义 AST，通过 gen:equal+hash 强制 O(1) 比较
;; 只要对象是驻留的，equal? 逻辑就等同于 eq?
(struct Eps () #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Void () #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Chr (c) #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Cat (e1 e2) #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Alt (e-list) #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Star (e) #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
(struct Dot () #:transparent
#:methods gen:equal+hash
[(define (equal-proc a b recur) (eq? a b))
(define (hash-proc a recur) (eq-hash-code a))
(define (hash2-proc a recur) (eq-hash-code a))])
;; 2. 驻留池 (Weak Hash Table)
;; 注意：池的 Key 必须使用 vector，因为 vector 的 equal? 会递归检查其内容
;; 而内容（子节点）已经是驻留的，所以比较子节点是 O(1) 的 eq?
(define pool (make-weak-hash))
(define (intern key constructor)
(hash-ref! pool key constructor))
;; 基础常量
(define phi (intern (vector 'Void) (λ () (Void))))
(define eps (intern (vector 'Eps) (λ () (Eps))))
(define dot (intern (vector 'Dot) (λ () (Dot))))
;; 3. 辅助排序函数：利用 eq-hash-code 实现常数时间全序
(define (re-type-rank r)
(cond [(Void? r) 0] [(Eps? r) 1] [(Dot? r) 2] [(Chr? r) 3]
[(Star? r) 4] [(Cat? r) 5] [(Alt? r) 6]))
(define (re-compare r1 r2)
(let ([t1 (re-type-rank r1)] [t2 (re-type-rank r2)])
(if (= t1 t2)
(< (eq-hash-code r1) (eq-hash-code r2))
(< t1 t2))))
;; 4. 智能构造函数
(define (make-chr c)
(intern (vector 'Chr c) (λ () (Chr c))))
(define (make-star e)
(cond [(Void? e) eps]
[(Eps? e) eps]
[(Star? e) e]
[else (intern (vector 'Star e) (λ () (Star e)))]))
(define (make-cat e1 e2)
(cond [(or (Void? e1) (Void? e2)) phi]
[(Eps? e1) e2]
[(Eps? e2) e1]
[else (intern (vector 'Cat e1 e2) (λ () (Cat e1 e2)))]))
(define (make-alt l)
(define (flatten es)
(append-map (λ (x) (if (Alt? x) (Alt-e-list x) (list x))) es))
(let* ([flat (flatten l)]
[no-phi (filter-not Void? flat)]
;; 使用 eq-hash-code 排序，确保 ACI 规范化
[sorted (sort no-phi re-compare)]
[unique (remove-duplicates sorted eq?)])
(cond
[(null? unique) phi]
[(null? (cdr unique)) (car unique)]
[else (intern (vector 'Alt unique) (λ () (Alt unique)))])))
;; 5. 导数与判空
(define (nullable? re)
(match re
[(Eps) #t]
[(Star _) #t]
[(Alt es) (ormap nullable? es)]
[(Cat e1 e2) (and (nullable? e1) (nullable? e2))]
[_ #f]))
(define (derive re c)
(match re
[(Void) phi]
[(Eps) phi]
[(Dot) eps]
[(Chr ch) (if (char=? ch c) eps phi)]
[(Alt es) (make-alt (map (λ (e) (derive e c)) es))]
[(Cat e1 e2)
(if (nullable? e1)
(make-alt (list (make-cat (derive e1 c) e2) (derive e2 c)))
(make-cat (derive e1 c) e2))]
[(Star e) (make-cat (derive e c) re)]))
;; ---------------------------------------------------------
;; 1. 匹配器构造 (完全匹配)
;; ---------------------------------------------------------
(define (make-matcher re)
(define cache (make-hash)) ;; 状态转移缓存: cur -> char -> next
(lambda (str)
(let loop ([cur re] [s (string->list str)])
(if (null? s)
(nullable? cur)
(let ([next (hash-ref! (hash-ref! cache cur (λ () (make-hash)))
(car s)
(λ () (derive cur (car s))))])
(if (Void? next)
#f
(loop next (cdr s))))))))
;; ---------------------------------------------------------
;; 2. 正则表达式反转
;; ---------------------------------------------------------
(define (re-reverse re)
(match re
[(Cat e1 e2) (make-cat (re-reverse e2) (re-reverse e1))]
[(Alt es) (make-alt (map re-reverse es))]
[(Star e) (make-star (re-reverse e))]
[_ re]))
;; ---------------------------------------------------------
;; 3. 搜索器构造 (子串匹配: 最左最短)
;; ---------------------------------------------------------
(define (make-search re)
;; 前向搜索: 匹配 .*RE
(define forward-re (make-cat (make-star dot) re))
;; 后向搜索: 匹配 RE_reversed
(define backward-re (re-reverse re))
(define f-cache (make-hash))
(define b-cache (make-hash))
(define (step cache cur c)
(hash-ref! (hash-ref! cache cur (λ () (make-hash)))
c
(λ () (derive cur c))))
(lambda (str)
(let* ([chars (string->list str)])
;; 1. 前向扫描：寻找第一个能让 (.*RE) 变成 nullable 的位置 E
(define E
(let f-loop ([cur forward-re] [s chars] [idx 0])
(cond
[(nullable? cur) idx] ;; 找到匹配终点
[(null? s) #f]
[else
(let ([next (step f-cache cur (car s))])
(if (Void? next) #f (f-loop next (cdr s) (add1 idx))))])))
(if E
;; 2. 后向扫描：从 E 位置开始向左匹配 RE_rev，寻找最短的起点
;; 提取前 E 个字符并反转
(let* ([prefix-rev (reverse (take chars E))]
[T (let b-loop ([cur backward-re] [s prefix-rev] [idx 0])
(cond
[(nullable? cur) idx] ;; 找到匹配起点（距离 E 的偏移）
[(null? s) (if (nullable? cur) idx #f)]
[else
(let ([next (step b-cache cur (car s))])
(if (Void? next) #f (b-loop next (cdr s) (add1 idx))))]))])
(cons (- E T) E))
#f))))
;; ---------------------------------------------------------
;; 测试脚本
;; ---------------------------------------------------------
(define (run-tests)
(define a (make-chr #\a))
(define b (make-chr #\b))
(define c (make-chr #\c))
(define d (make-chr #\d))
;; 正则: a(b|c)*d
(define my-re (make-cat a (make-cat (make-star (make-alt (list b c))) d)))
(printf "=== Testing Matcher ===\n")
(define matches? (make-matcher my-re))
(displayln (list 'ad (matches? "ad"))) ; #t
(displayln (list 'abd (matches? "abd"))) ; #t
(displayln (list 'abccbd (matches? "abccbd"))) ; #t
(displayln (list 'add (matches? "add"))) ; #f
(displayln (list 'a (matches? "a"))) ; #f
(printf "\n=== Testing Searcher ===\n")
(define search (make-search my-re))
(displayln (list 'search-ad (search "ad"))) ; '(0 . 2)
(displayln (list 'search-xxxad (search "xxxad"))) ; '(3 . 5)
(displayln (list 'search-adxxx (search "adxxx"))) ; '(0 . 2)
(displayln (list 'search-abccbd (search "abccbd"))) ; '(0 . 6)
(displayln (list 'search-none (search "xyz"))) ; #f
(printf "\n=== Testing Complex Search (Shortest-Left) ===\n")
;; 多个匹配，应该返回最左边的那个
(displayln (list 'multi-ad (search "ad...ad"))) ; '(0 . 2)
;; 贪婪/非贪婪行为测试
;; 在 "abdbd" 中，forward 会在第一个 d (index 3) 停止，然后 backward 找到 a。
(displayln (list 'abdbd (search "abdbd"))) ; '(0 . 3) -> "abd"
;; 验证 a...d 在长字符串中的表现
(displayln (list 'long-str (search "zzzaaaaaaddddzzz"))) ; '(8 . 10) -> "ad"
(printf "\n=== Testing Reverse Logic ===\n")
;; 测试反转后的匹配 (d (b|c)* a)
(define rev-matches? (make-matcher (re-reverse my-re)))
(displayln (list 'rev-da (rev-matches? "da"))) ; #t
(displayln (list 'rev-dbca (rev-matches? "dbca"))) ; #t
(displayln (list 'rev-ad (rev-matches? "ad"))) ; #f
(printf "\nAll functional tests finished.\n"))
(run-tests)
|