]>
Commit | Line | Data |
---|---|---|
5f125488 A |
1 | NOTE implicit vs. explicit repetitions : 2009-02-02 |
2 | ||
3 | # Glenn Fowler <gsf@research.att.com> | |
4 | # conforming matches (column 4) must match one of the following BREs | |
5 | # NOMATCH | |
6 | # (0,.)\((\(.\),\(.\))(?,?)(\2,\3)\)* | |
7 | # (0,.)\((\(.\),\(.\))(\2,\3)(?,?)\)* | |
8 | # i.e., each 3-tuple has two identical elements and one (?,?) | |
9 | ||
10 | E ((..)|(.)) NULL NOMATCH | |
11 | E ((..)|(.))((..)|(.)) NULL NOMATCH | |
12 | E ((..)|(.))((..)|(.))((..)|(.)) NULL NOMATCH | |
13 | ||
14 | E ((..)|(.)){1} NULL NOMATCH | |
15 | E ((..)|(.)){2} NULL NOMATCH | |
16 | E ((..)|(.)){3} NULL NOMATCH | |
17 | ||
18 | E ((..)|(.))* NULL (0,0) | |
19 | ||
20 | E ((..)|(.)) a (0,1)(0,1)(?,?)(0,1) | |
21 | E ((..)|(.))((..)|(.)) a NOMATCH | |
22 | E ((..)|(.))((..)|(.))((..)|(.)) a NOMATCH | |
23 | ||
24 | E ((..)|(.)){1} a (0,1)(0,1)(?,?)(0,1) | |
25 | E ((..)|(.)){2} a NOMATCH | |
26 | E ((..)|(.)){3} a NOMATCH | |
27 | ||
28 | E ((..)|(.))* a (0,1)(0,1)(?,?)(0,1) | |
29 | ||
30 | E ((..)|(.)) aa (0,2)(0,2)(0,2)(?,?) | |
31 | E ((..)|(.))((..)|(.)) aa (0,2)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2) | |
32 | E ((..)|(.))((..)|(.))((..)|(.)) aa NOMATCH | |
33 | ||
34 | E ((..)|(.)){1} aa (0,2)(0,2)(0,2)(?,?) | |
35 | E ((..)|(.)){2} aa (0,2)(1,2)(?,?)(1,2) | |
36 | E ((..)|(.)){3} aa NOMATCH | |
37 | ||
38 | E ((..)|(.))* aa (0,2)(0,2)(0,2)(?,?) | |
39 | ||
40 | E ((..)|(.)) aaa (0,2)(0,2)(0,2)(?,?) | |
41 | E ((..)|(.))((..)|(.)) aaa (0,3)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3) | |
42 | E ((..)|(.))((..)|(.))((..)|(.)) aaa (0,3)(0,1)(?,?)(0,1)(1,2)(?,?)(1,2)(2,3)(?,?)(2,3) | |
43 | ||
44 | E ((..)|(.)){1} aaa (0,2)(0,2)(0,2)(?,?) | |
45 | E ((..)|(.)){2} aaa (0,3)(2,3)(?,?)(2,3) | |
46 | E ((..)|(.)){3} aaa (0,3)(2,3)(?,?)(2,3) | |
47 | ||
48 | E ((..)|(.))* aaa (0,3)(2,3)(?,?)(2,3) | |
49 | ||
50 | E ((..)|(.)) aaaa (0,2)(0,2)(0,2)(?,?) | |
51 | E ((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
52 | E ((..)|(.))((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3)(3,4)(?,?)(3,4) | |
53 | ||
54 | E ((..)|(.)){1} aaaa (0,2)(0,2)(0,2)(?,?) | |
55 | E ((..)|(.)){2} aaaa (0,4)(2,4)(2,4)(?,?) | |
56 | E ((..)|(.)){3} aaaa (0,4)(3,4)(?,?)(3,4) | |
57 | ||
58 | E ((..)|(.))* aaaa (0,4)(2,4)(2,4)(?,?) | |
59 | ||
60 | E ((..)|(.)) aaaaa (0,2)(0,2)(0,2)(?,?) | |
61 | E ((..)|(.))((..)|(.)) aaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
62 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaa (0,5)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,5)(?,?)(4,5) | |
63 | ||
64 | E ((..)|(.)){1} aaaaa (0,2)(0,2)(0,2)(?,?) | |
65 | E ((..)|(.)){2} aaaaa (0,4)(2,4)(2,4)(?,?) | |
66 | E ((..)|(.)){3} aaaaa (0,5)(4,5)(?,?)(4,5) | |
67 | ||
68 | E ((..)|(.))* aaaaa (0,5)(4,5)(?,?)(4,5) | |
69 | ||
70 | E ((..)|(.)) aaaaaa (0,2)(0,2)(0,2)(?,?) | |
71 | E ((..)|(.))((..)|(.)) aaaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
72 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaaa (0,6)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,6)(4,6)(?,?) | |
73 | ||
74 | E ((..)|(.)){1} aaaaaa (0,2)(0,2)(0,2)(?,?) | |
75 | E ((..)|(.)){2} aaaaaa (0,4)(2,4)(2,4)(?,?) | |
76 | E ((..)|(.)){3} aaaaaa (0,6)(4,6)(4,6)(?,?) | |
77 | ||
78 | E ((..)|(.))* aaaaaa (0,6)(4,6)(4,6)(?,?) | |
79 | ||
80 | NOTE additional repetition tests graciously provided by Chris Kuklewicz www.haskell.org 2009-02-02 | |
81 | ||
82 | # These test a bug in OS X / FreeBSD / NetBSD, and libtree. | |
83 | # Linux/GLIBC gets the {8,} and {8,8} wrong. | |
84 | ||
85 | :HA#100:E X(.?){0,}Y X1234567Y (0,9)(7,8) | |
86 | :HA#101:E X(.?){1,}Y X1234567Y (0,9)(7,8) | |
87 | :HA#102:E X(.?){2,}Y X1234567Y (0,9)(7,8) | |
88 | :HA#103:E X(.?){3,}Y X1234567Y (0,9)(7,8) | |
89 | :HA#104:E X(.?){4,}Y X1234567Y (0,9)(7,8) | |
90 | :HA#105:E X(.?){5,}Y X1234567Y (0,9)(7,8) | |
91 | :HA#106:E X(.?){6,}Y X1234567Y (0,9)(7,8) | |
92 | :HA#107:E X(.?){7,}Y X1234567Y (0,9)(7,8) | |
93 | :HA#108:E X(.?){8,}Y X1234567Y (0,9)(8,8) | |
94 | :HA#110:E X(.?){0,8}Y X1234567Y (0,9)(7,8) | |
95 | :HA#111:E X(.?){1,8}Y X1234567Y (0,9)(7,8) | |
96 | :HA#112:E X(.?){2,8}Y X1234567Y (0,9)(7,8) | |
97 | :HA#113:E X(.?){3,8}Y X1234567Y (0,9)(7,8) | |
98 | :HA#114:E X(.?){4,8}Y X1234567Y (0,9)(7,8) | |
99 | :HA#115:E X(.?){5,8}Y X1234567Y (0,9)(7,8) | |
100 | :HA#116:E X(.?){6,8}Y X1234567Y (0,9)(7,8) | |
101 | :HA#117:E X(.?){7,8}Y X1234567Y (0,9)(7,8) | |
102 | :HA#118:E X(.?){8,8}Y X1234567Y (0,9)(8,8) | |
103 | ||
104 | # These test a fixed bug in my regex-tdfa that did not keep the expanded | |
105 | # form properly grouped, so right association did the wrong thing with | |
106 | # these ambiguous patterns (crafted just to test my code when I became | |
107 | # suspicious of my implementation). The first subexpression should use | |
108 | # "ab" then "a" then "bcd". | |
109 | ||
110 | # OS X / FreeBSD / NetBSD badly fail many of these, with impossible | |
111 | # results like (0,6)(4,5)(6,6). | |
112 | ||
113 | :HA#260:E (a|ab|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) | |
114 | :HA#261:E (a|ab|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) | |
115 | :HA#262:E (a|ab|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) | |
116 | :HA#263:E (a|ab|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) | |
117 | :HA#264:E (a|ab|c|bcd){4,}(d*) ababcd NOMATCH | |
118 | :HA#265:E (a|ab|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) | |
119 | :HA#266:E (a|ab|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) | |
120 | :HA#267:E (a|ab|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) | |
121 | :HA#268:E (a|ab|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) | |
122 | :HA#269:E (a|ab|c|bcd){4,10}(d*) ababcd NOMATCH | |
123 | :HA#270:E (a|ab|c|bcd)*(d*) ababcd (0,6)(3,6)(6,6) | |
124 | :HA#271:E (a|ab|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) | |
125 | ||
126 | # The above worked on Linux/GLIBC but the following often fail. | |
127 | # They also trip up OS X / FreeBSD / NetBSD: | |
128 | ||
129 | :HA#280:E (ab|a|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) | |
130 | :HA#281:E (ab|a|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) | |
131 | :HA#282:E (ab|a|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) | |
132 | :HA#283:E (ab|a|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) | |
133 | :HA#284:E (ab|a|c|bcd){4,}(d*) ababcd NOMATCH | |
134 | :HA#285:E (ab|a|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) | |
135 | :HA#286:E (ab|a|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) | |
136 | :HA#287:E (ab|a|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) | |
137 | :HA#288:E (ab|a|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) | |
138 | :HA#289:E (ab|a|c|bcd){4,10}(d*) ababcd NOMATCH | |
139 | :HA#290:E (ab|a|c|bcd)*(d*) ababcd (0,6)(3,6)(6,6) | |
140 | :HA#291:E (ab|a|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) |