equal
deleted
inserted
replaced
9 case class CHAR(c: Char) extends Rexp |
9 case class CHAR(c: Char) extends Rexp |
10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
11 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
12 case class STAR(r: Rexp) extends Rexp |
12 case class STAR(r: Rexp) extends Rexp |
13 case class NTIMES(r: Rexp, n: Int) extends Rexp |
13 case class NTIMES(r: Rexp, n: Int) extends Rexp |
14 case class CSET(cs: Set[Char]) extends Rexp |
|
15 case class CFUN(f: Char => Bool) extends Rexp |
|
16 |
|
17 CSET(('a' to 'z').toSet) |
|
18 |
|
19 val CSET2(cs: Set[Char]) = CFUN((c:Char) => cs.contains(c)) |
|
20 |
14 |
21 |
15 |
22 // nullable function: tests whether the regular |
16 // nullable function: tests whether the regular |
23 // expression can recognise the empty string |
17 // expression can recognise the empty string |
24 def nullable (r: Rexp) : Boolean = r match { |
18 def nullable (r: Rexp) : Boolean = r match { |
77 def OPT(r: Rexp) = ALT(r, ONE) |
71 def OPT(r: Rexp) = ALT(r, ONE) |
78 |
72 |
79 |
73 |
80 // Test Cases |
74 // Test Cases |
81 |
75 |
82 //evil regular expressions |
76 //evil regular expressions: (a?){n} a{n} and (a*)* b |
83 def EVIL1(n: Int) = SEQ(NTIMEemacs re3S(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
77 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
84 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
78 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
85 |
79 |
86 |
80 |
87 def time_needed[T](i: Int, code: => T) = { |
81 def time_needed[T](i: Int, code: => T) = { |
88 val start = System.nanoTime() |
82 val start = System.nanoTime() |
131 size(ders("a".toList, EVIL2)) // 8 |
125 size(ders("a".toList, EVIL2)) // 8 |
132 size(ders("aa".toList, EVIL2)) // 8 |
126 size(ders("aa".toList, EVIL2)) // 8 |
133 size(ders("aaa".toList, EVIL2)) // 8 |
127 size(ders("aaa".toList, EVIL2)) // 8 |
134 size(ders("aaaa".toList, EVIL2)) // 8 |
128 size(ders("aaaa".toList, EVIL2)) // 8 |
135 size(ders("aaaaa".toList, EVIL2)) // 8 |
129 size(ders("aaaaa".toList, EVIL2)) // 8 |
|
130 |
|
131 |
|
132 |
|
133 |
|
134 |
|
135 // Examples from the Sulzmann paper |
|
136 val sulzmann = STAR(ALT(ALT(CHAR('a'), CHAR('b')), SEQ(CHAR('a'), CHAR('b')))) |
|
137 |
|
138 |
|
139 for (i <- 1 to 4501 by 500) { |
|
140 println(i + ": " + "%.5f".format(time_needed(1, matcher(sulzmann, "a" * i)))) |
|
141 } |
|
142 |
|
143 for (i <- 1 to 4501 by 500) { |
|
144 println(i + ": " + "%.5f".format(time_needed(1, matcher(sulzmann, "ab" * i)))) |
|
145 } |