]>
Commit | Line | Data |
---|---|---|
94b46f34 XL |
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 ((..)|(.)){2} aaa (0,3)(2,3)(0,2)(2,3) RE2/Go | |
47 | E ((..)|(.)){3} aaa (0,3)(2,3)(?,?)(2,3) | |
48 | ||
49 | #E ((..)|(.))* aaa (0,3)(2,3)(?,?)(2,3) | |
50 | E ((..)|(.))* aaa (0,3)(2,3)(0,2)(2,3) RE2/Go | |
51 | ||
52 | E ((..)|(.)) aaaa (0,2)(0,2)(0,2)(?,?) | |
53 | E ((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
54 | E ((..)|(.))((..)|(.))((..)|(.)) aaaa (0,4)(0,2)(0,2)(?,?)(2,3)(?,?)(2,3)(3,4)(?,?)(3,4) | |
55 | ||
56 | E ((..)|(.)){1} aaaa (0,2)(0,2)(0,2)(?,?) | |
57 | E ((..)|(.)){2} aaaa (0,4)(2,4)(2,4)(?,?) | |
58 | #E ((..)|(.)){3} aaaa (0,4)(3,4)(?,?)(3,4) | |
59 | E ((..)|(.)){3} aaaa (0,4)(3,4)(0,2)(3,4) RE2/Go | |
60 | ||
61 | E ((..)|(.))* aaaa (0,4)(2,4)(2,4)(?,?) | |
62 | ||
63 | E ((..)|(.)) aaaaa (0,2)(0,2)(0,2)(?,?) | |
64 | E ((..)|(.))((..)|(.)) aaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
65 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaa (0,5)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,5)(?,?)(4,5) | |
66 | ||
67 | E ((..)|(.)){1} aaaaa (0,2)(0,2)(0,2)(?,?) | |
68 | E ((..)|(.)){2} aaaaa (0,4)(2,4)(2,4)(?,?) | |
69 | #E ((..)|(.)){3} aaaaa (0,5)(4,5)(?,?)(4,5) | |
70 | E ((..)|(.)){3} aaaaa (0,5)(4,5)(2,4)(4,5) RE2/Go | |
71 | ||
72 | #E ((..)|(.))* aaaaa (0,5)(4,5)(?,?)(4,5) | |
73 | E ((..)|(.))* aaaaa (0,5)(4,5)(2,4)(4,5) RE2/Go | |
74 | ||
75 | E ((..)|(.)) aaaaaa (0,2)(0,2)(0,2)(?,?) | |
76 | E ((..)|(.))((..)|(.)) aaaaaa (0,4)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?) | |
77 | E ((..)|(.))((..)|(.))((..)|(.)) aaaaaa (0,6)(0,2)(0,2)(?,?)(2,4)(2,4)(?,?)(4,6)(4,6)(?,?) | |
78 | ||
79 | E ((..)|(.)){1} aaaaaa (0,2)(0,2)(0,2)(?,?) | |
80 | E ((..)|(.)){2} aaaaaa (0,4)(2,4)(2,4)(?,?) | |
81 | E ((..)|(.)){3} aaaaaa (0,6)(4,6)(4,6)(?,?) | |
82 | ||
83 | E ((..)|(.))* aaaaaa (0,6)(4,6)(4,6)(?,?) | |
84 | ||
85 | NOTE additional repetition tests graciously provided by Chris Kuklewicz www.haskell.org 2009-02-02 | |
86 | ||
87 | # These test a bug in OS X / FreeBSD / NetBSD, and libtree. | |
88 | # Linux/GLIBC gets the {8,} and {8,8} wrong. | |
89 | ||
90 | :HA#100:E X(.?){0,}Y X1234567Y (0,9)(7,8) | |
91 | :HA#101:E X(.?){1,}Y X1234567Y (0,9)(7,8) | |
92 | :HA#102:E X(.?){2,}Y X1234567Y (0,9)(7,8) | |
93 | :HA#103:E X(.?){3,}Y X1234567Y (0,9)(7,8) | |
94 | :HA#104:E X(.?){4,}Y X1234567Y (0,9)(7,8) | |
95 | :HA#105:E X(.?){5,}Y X1234567Y (0,9)(7,8) | |
96 | :HA#106:E X(.?){6,}Y X1234567Y (0,9)(7,8) | |
97 | :HA#107:E X(.?){7,}Y X1234567Y (0,9)(7,8) | |
98 | :HA#108:E X(.?){8,}Y X1234567Y (0,9)(8,8) | |
99 | #:HA#110:E X(.?){0,8}Y X1234567Y (0,9)(7,8) | |
100 | :HA#110:E X(.?){0,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
101 | #:HA#111:E X(.?){1,8}Y X1234567Y (0,9)(7,8) | |
102 | :HA#111:E X(.?){1,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
103 | #:HA#112:E X(.?){2,8}Y X1234567Y (0,9)(7,8) | |
104 | :HA#112:E X(.?){2,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
105 | #:HA#113:E X(.?){3,8}Y X1234567Y (0,9)(7,8) | |
106 | :HA#113:E X(.?){3,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
107 | #:HA#114:E X(.?){4,8}Y X1234567Y (0,9)(7,8) | |
108 | :HA#114:E X(.?){4,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
109 | #:HA#115:E X(.?){5,8}Y X1234567Y (0,9)(7,8) | |
110 | :HA#115:E X(.?){5,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
111 | #:HA#116:E X(.?){6,8}Y X1234567Y (0,9)(7,8) | |
112 | :HA#116:E X(.?){6,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
113 | #:HA#117:E X(.?){7,8}Y X1234567Y (0,9)(7,8) | |
114 | :HA#117:E X(.?){7,8}Y X1234567Y (0,9)(8,8) RE2/Go | |
115 | :HA#118:E X(.?){8,8}Y X1234567Y (0,9)(8,8) | |
116 | ||
117 | # These test a fixed bug in my regex-tdfa that did not keep the expanded | |
118 | # form properly grouped, so right association did the wrong thing with | |
119 | # these ambiguous patterns (crafted just to test my code when I became | |
120 | # suspicious of my implementation). The first subexpression should use | |
121 | # "ab" then "a" then "bcd". | |
122 | ||
123 | # OS X / FreeBSD / NetBSD badly fail many of these, with impossible | |
124 | # results like (0,6)(4,5)(6,6). | |
125 | ||
126 | :HA#260:E (a|ab|c|bcd){0,}(d*) ababcd (0,1)(0,1)(1,1) | |
127 | :HA#261:E (a|ab|c|bcd){1,}(d*) ababcd (0,1)(0,1)(1,1) | |
128 | :HA#262:E (a|ab|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) | |
129 | :HA#263:E (a|ab|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) | |
130 | :HA#264:E (a|ab|c|bcd){4,}(d*) ababcd NOMATCH | |
131 | :HA#265:E (a|ab|c|bcd){0,10}(d*) ababcd (0,1)(0,1)(1,1) | |
132 | :HA#266:E (a|ab|c|bcd){1,10}(d*) ababcd (0,1)(0,1)(1,1) | |
133 | :HA#267:E (a|ab|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) | |
134 | :HA#268:E (a|ab|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) | |
135 | :HA#269:E (a|ab|c|bcd){4,10}(d*) ababcd NOMATCH | |
136 | :HA#270:E (a|ab|c|bcd)*(d*) ababcd (0,1)(0,1)(1,1) | |
137 | :HA#271:E (a|ab|c|bcd)+(d*) ababcd (0,1)(0,1)(1,1) | |
138 | ||
139 | # The above worked on Linux/GLIBC but the following often fail. | |
140 | # They also trip up OS X / FreeBSD / NetBSD: | |
141 | ||
142 | #:HA#280:E (ab|a|c|bcd){0,}(d*) ababcd (0,6)(3,6)(6,6) | |
143 | :HA#280:E (ab|a|c|bcd){0,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
144 | #:HA#281:E (ab|a|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) | |
145 | :HA#281:E (ab|a|c|bcd){1,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
146 | #:HA#282:E (ab|a|c|bcd){2,}(d*) ababcd (0,6)(3,6)(6,6) | |
147 | :HA#282:E (ab|a|c|bcd){2,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
148 | #:HA#283:E (ab|a|c|bcd){3,}(d*) ababcd (0,6)(3,6)(6,6) | |
149 | :HA#283:E (ab|a|c|bcd){3,}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
150 | :HA#284:E (ab|a|c|bcd){4,}(d*) ababcd NOMATCH | |
151 | #:HA#285:E (ab|a|c|bcd){0,10}(d*) ababcd (0,6)(3,6)(6,6) | |
152 | :HA#285:E (ab|a|c|bcd){0,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
153 | #:HA#286:E (ab|a|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) | |
154 | :HA#286:E (ab|a|c|bcd){1,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
155 | #:HA#287:E (ab|a|c|bcd){2,10}(d*) ababcd (0,6)(3,6)(6,6) | |
156 | :HA#287:E (ab|a|c|bcd){2,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
157 | #:HA#288:E (ab|a|c|bcd){3,10}(d*) ababcd (0,6)(3,6)(6,6) | |
158 | :HA#288:E (ab|a|c|bcd){3,10}(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
159 | :HA#289:E (ab|a|c|bcd){4,10}(d*) ababcd NOMATCH | |
160 | #:HA#290:E (ab|a|c|bcd)*(d*) ababcd (0,6)(3,6)(6,6) | |
161 | :HA#290:E (ab|a|c|bcd)*(d*) ababcd (0,6)(4,5)(5,6) RE2/Go | |
162 | #:HA#291:E (ab|a|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) | |
163 | :HA#291:E (ab|a|c|bcd)+(d*) ababcd (0,6)(4,5)(5,6) RE2/Go |