1 // A version with simplification of derivatives; |
1 // A version of the matcher with simplification |
|
2 // of derivatives |
|
3 // |
2 // this keeps the regular expressions small, which |
4 // this keeps the regular expressions small, which |
3 // is good for the run-time |
5 // is good for the run-time |
4 // |
6 // |
5 // call the test cases with X = {1,2} |
7 // call the test cases with X = {1,2} |
6 // |
8 // |
46 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
48 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
47 case NTIMES(r, i) => |
49 case NTIMES(r, i) => |
48 if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1)) |
50 if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1)) |
49 } |
51 } |
50 |
52 |
|
53 // simplification |
51 def simp(r: Rexp) : Rexp = r match { |
54 def simp(r: Rexp) : Rexp = r match { |
52 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
55 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
53 case (ZERO, r2s) => r2s |
56 case (ZERO, r2s) => r2s |
54 case (r1s, ZERO) => r1s |
57 case (r1s, ZERO) => r1s |
55 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
58 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
62 case (r1s, r2s) => SEQ(r1s, r2s) |
65 case (r1s, r2s) => SEQ(r1s, r2s) |
63 } |
66 } |
64 case r => r |
67 case r => r |
65 } |
68 } |
66 |
69 |
67 |
|
68 |
|
69 // the derivative w.r.t. a string (iterates der) |
70 // the derivative w.r.t. a string (iterates der) |
70 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
71 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
71 case Nil => r |
72 case Nil => r |
72 case c::s => ders(s, simp(der(c, r))) |
73 case c::s => ders(s, simp(der(c, r))) |
73 } |
74 } |
74 |
75 |
75 |
|
76 // the main matcher function |
76 // the main matcher function |
77 def matcher(r: Rexp, s: String) : Boolean = |
77 def matcher(r: Rexp, s: String) : Boolean = |
78 nullable(ders(s.toList, r)) |
78 nullable(ders(s.toList, r)) |
79 |
79 |
80 |
80 |
|
81 // Test Cases |
|
82 //============ |
|
83 |
81 // one or zero |
84 // one or zero |
82 def OPT(r: Rexp) = ALT(r, ONE) |
85 def OPT(r: Rexp) = ALT(r, ONE) |
83 |
|
84 |
|
85 // Test Cases |
|
86 |
86 |
87 // evil regular expressions: (a?){n} a{n} and (a*)* b |
87 // evil regular expressions: (a?){n} a{n} and (a*)* b |
88 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
88 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
89 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
89 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
90 |
90 |