1 // A version of the simple matcher with simplification |
1 // A version of the simple matcher with simplification |
2 // of derivatives |
2 // of derivatives |
3 // |
3 // |
4 // this keeps the regular expressions (often) small, which |
4 // this keeps the regular expressions (often) small, which |
5 // is good for the run-time |
5 // is good for speed |
6 // |
6 // |
7 // call the test cases with X = {1,2,3,4} |
7 // call the test cases with X = {1,2,3,4} |
8 // |
8 // |
9 // amm re3.sc testX |
9 // amm re3.sc testX |
10 // |
10 // |
21 case SEQ(r1: Rexp, r2: Rexp) // sequence |
21 case SEQ(r1: Rexp, r2: Rexp) // sequence |
22 case STAR(r: Rexp) // star |
22 case STAR(r: Rexp) // star |
23 case NTIMES(r: Rexp, n: Int) // explicit n-times |
23 case NTIMES(r: Rexp, n: Int) // explicit n-times |
24 } |
24 } |
25 import Rexp._ |
25 import Rexp._ |
26 |
|
27 |
26 |
28 |
27 |
29 // the nullable function: tests whether the regular |
28 // the nullable function: tests whether the regular |
30 // expression can recognise the empty string |
29 // expression can recognise the empty string |
31 def nullable (r: Rexp) : Boolean = r match { |
30 def nullable (r: Rexp) : Boolean = r match { |
199 |
199 |
200 |
200 |
201 @arg(doc = "Tests that show not all is hunky-dory, but a solution leads too far afield.") |
201 @arg(doc = "Tests that show not all is hunky-dory, but a solution leads too far afield.") |
202 @main |
202 @main |
203 def fail() = { test3(); test4(); test5() } |
203 def fail() = { test3(); test4(); test5() } |
204 |
|
205 |
|
206 // simplification |
|
207 def simp2(r: Rexp) : Rexp = r match { |
|
208 case ALT(r1, r2) => (simp2(r1), simp2(r2)) match { |
|
209 case (ZERO, r2s) => r2s |
|
210 case (r1s, ZERO) => r1s |
|
211 //case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
|
212 case (r1s, r2s) => ALT(r1s, r2s) |
|
213 } |
|
214 case SEQ(r1, r2) => (simp2(r1), simp2(r2)) match { |
|
215 case (ZERO, _) => ZERO |
|
216 case (_, ZERO) => ZERO |
|
217 //case (ONE, r2s) => r2s |
|
218 //case (r1s, ONE) => r1s |
|
219 case (r1s, r2s) => SEQ(r1s, r2s) |
|
220 } |
|
221 case r => r |
|
222 } |
|
223 |
|
224 // some convenience for typing in regular expressions |
|
225 import scala.language.implicitConversions |
|
226 |
|
227 def charlist2rexp(s : List[Char]): Rexp = s match { |
|
228 case Nil => ONE |
|
229 case c::Nil => CHAR(c) |
|
230 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
231 } |
|
232 |
|
233 given Conversion[String, Rexp] = (s => charlist2rexp(s.toList)) |
|
234 |
|
235 val HELLO : Rexp = "hello" |
|
236 |
|
237 extension (r: Rexp) { |
|
238 def | (s: Rexp) = ALT(r, s) |
|
239 def % = STAR(r) |
|
240 def ~ (s: Rexp) = SEQ(r, s) |
|
241 } |
|
242 |
|
243 val re = (ONE | "a" | "ab") ~ ("c" | "bc") ~ ("d" | "e") |
|
244 simp2(der('d', der('c', der('b', der('a', re))))) |
|