equal
deleted
inserted
replaced
61 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
61 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
62 case Nil => r |
62 case Nil => r |
63 case c::s => ders(s, simp(der(c, r))) |
63 case c::s => ders(s, simp(der(c, r))) |
64 } |
64 } |
65 |
65 |
66 // the derivative w.r.t. a string (iterates der) |
|
67 def dersp(s: List[Char], r: Rexp) : Rexp = s match { |
|
68 case Nil => r |
|
69 case c::s => dersp(s, der(c, r)) |
|
70 } |
|
71 |
|
72 |
66 |
73 // the main matcher function |
67 // the main matcher function |
74 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
68 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
75 |
69 |
76 // tests |
|
77 val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
|
78 dersp("x".toList, q) |
|
79 dersp("xy".toList, q) |
|
80 dersp("xyz".toList, q) |
|
81 |
70 |
82 // one or zero |
71 // one or zero |
83 def OPT(r: Rexp) = ALT(r, ONE) |
72 def OPT(r: Rexp) = ALT(r, ONE) |
84 |
73 |
85 |
74 |
97 (end - start)/(i * 1.0e9) |
86 (end - start)/(i * 1.0e9) |
98 } |
87 } |
99 |
88 |
100 |
89 |
101 //test: (a?{n}) (a{n}) |
90 //test: (a?{n}) (a{n}) |
102 for (i <- 1 to 7001 by 1000) { |
91 for (i <- 0 to 7000 by 1000) { |
103 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) |
92 println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") |
104 } |
|
105 |
|
106 for (i <- 1 to 7001 by 1000) { |
|
107 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) |
|
108 } |
93 } |
109 |
94 |
110 //test: (a*)* b |
95 //test: (a*)* b |
111 for (i <- 1 to 6000001 by 500000) { |
96 for (i <- 0 to 6000000 by 500000) { |
112 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
97 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
113 } |
|
114 |
|
115 for (i <- 1 to 6000001 by 500000) { |
|
116 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
|
117 } |
98 } |
118 |
99 |
119 |
100 |
120 // size of a regular expressions - for testing purposes |
101 // size of a regular expressions - for testing purposes |
121 def size(r: Rexp) : Int = r match { |
102 def size(r: Rexp) : Int = r match { |