equal
deleted
inserted
replaced
1 |
1 |
2 abstract class Rexp { |
2 abstract class Rexp |
3 def simp : Rexp = this |
|
4 } |
|
5 |
3 |
6 case object NULL extends Rexp |
4 case object NULL extends Rexp |
7 case object EMPTY extends Rexp |
5 case object EMPTY extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
6 case class CHAR(c: Char) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
7 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
43 } |
41 } |
44 |
42 |
45 // derivative w.r.t. a string (iterates der) |
43 // derivative w.r.t. a string (iterates der) |
46 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
44 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
47 case Nil => r |
45 case Nil => r |
48 case c::s => ders(s, der(c, r).simp) |
46 case c::s => ders(s, der(c, r)) |
49 } |
47 } |
50 |
48 |
51 // main matcher function |
49 // main matcher function |
52 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
50 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
53 |
51 |
69 for (j <- 1 to i) code |
67 for (j <- 1 to i) code |
70 val end = System.nanoTime() |
68 val end = System.nanoTime() |
71 (end - start)/(i * 1.0e9) |
69 (end - start)/(i * 1.0e9) |
72 } |
70 } |
73 |
71 |
74 for (i <- 1 to 22) { |
72 for (i <- 1 to 29) { |
75 println(i + ": " + "%.5f".format(time_needed(1, matcher(RTEST(i), "a" * i)))) |
73 println(i + ": " + "%.5f".format(time_needed(1, matcher(RTEST(i), "a" * i)))) |
76 } |
74 } |
77 |
75 |
78 |
76 |