1 NOTE implicit vs. explicit repetitions : 2009-02-02 2 3 # Glenn Fowler <gsf (a] 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,6)(3,6)(6,6) 127 :HA#261:E (a|ab|c|bcd){1,}(d*) ababcd (0,6)(3,6)(6,6) 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,6)(3,6)(6,6) 132 :HA#266:E (a|ab|c|bcd){1,10}(d*) ababcd (0,6)(3,6)(6,6) 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,6)(3,6)(6,6) 137 :HA#271:E (a|ab|c|bcd)+(d*) ababcd (0,6)(3,6)(6,6) 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 164
