38 } |
40 } |
39 |
41 |
40 // main matcher function |
42 // main matcher function |
41 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
43 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
42 |
44 |
|
45 |
43 //examples from the homework |
46 //examples from the homework |
|
47 |
44 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
48 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
45 der('a', r) |
49 der('a', r) |
46 der('b', r) |
50 der('b', r) |
47 der('c', r) |
51 der('c', r) |
48 |
52 |
49 //optional (one or zero times) |
53 //optional regular expression (one or zero times) |
50 def OPT(r: Rexp) = ALT(r, ONE) |
54 def OPT(r: Rexp) = ALT(r, ONE) |
51 |
55 |
52 //n-times (explicitly expanded) |
56 //n-times regular expression (explicitly expanded) |
53 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
57 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
54 case 0 => ONE |
58 case 0 => ONE |
55 case 1 => r |
59 case 1 => r |
56 case n => SEQ(r, NTIMES(r, n - 1)) |
60 case n => SEQ(r, NTIMES(r, n - 1)) |
57 } |
61 } |
|
62 |
|
63 |
|
64 // Test Cases |
58 |
65 |
59 // the evil regular expression a?{n} a{n} |
66 // the evil regular expression a?{n} a{n} |
60 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
67 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
61 |
68 |
62 // the evil regular expression (a*)*b |
69 // the evil regular expression (a*)*b |
86 |
93 |
87 for (i <- 1 to 20) { |
94 for (i <- 1 to 20) { |
88 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
95 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
89 } |
96 } |
90 |
97 |
|
98 |
|
99 |
|
100 |
|
101 // size of a regular expressions - for testing purposes |
|
102 def size(r: Rexp) : Int = r match { |
|
103 case ZERO => 1 |
|
104 case ONE => 1 |
|
105 case CHAR(_) => 1 |
|
106 case ALT(r1, r2) => 1 + size(r1) + size(r2) |
|
107 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
108 case STAR(r) => 1 + size(r) |
|
109 } |
|
110 |
|
111 // the expicit expansion in EVIL1(n) increases |
|
112 // drastically its size |
|
113 |
|
114 size(EVIL1(1)) // 5 |
|
115 size(EVIL1(3)) // 17 |
|
116 size(EVIL1(5)) // 29 |
|
117 size(EVIL1(7)) // 41 |