1 import scala.language.implicitConversions |
|
2 |
|
3 abstract class Rexp |
1 abstract class Rexp |
4 |
|
5 case object NULL extends Rexp |
2 case object NULL extends Rexp |
6 case object EMPTY extends Rexp |
3 case object EMPTY extends Rexp |
7 case class CHAR(c: Char) extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
8 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class STAR(r: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
11 |
|
12 // some convenience for typing in regular expressions |
|
13 def charlist2rexp(s : List[Char]) : Rexp = s match { |
|
14 case Nil => EMPTY |
|
15 case c::Nil => CHAR(c) |
|
16 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
17 } |
|
18 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
19 |
|
20 |
8 |
21 // nullable function: tests whether the regular |
9 // nullable function: tests whether the regular |
22 // expression can recognise the empty string |
10 // expression can recognise the empty string |
23 def nullable (r: Rexp) : Boolean = r match { |
11 def nullable (r: Rexp) : Boolean = r match { |
24 case NULL => false |
12 case NULL => false |
48 } |
36 } |
49 |
37 |
50 // main matcher function |
38 // main matcher function |
51 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
39 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
52 |
40 |
53 //example |
41 //example from the homework |
54 //val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
42 //val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
55 //der('a', r) |
43 //der('a', r) |
56 //der('b', r) |
44 //der('b', r) |
|
45 //der('c', r) |
57 |
46 |
58 //one or zero |
47 //optional: one or zero times |
59 def OPT(r: Rexp) = ALT(r, EMPTY) |
48 def OPT(r: Rexp) = ALT(r, EMPTY) |
60 |
49 |
61 //n-times |
50 //n-times |
62 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
51 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
63 case 0 => EMPTY |
52 case 0 => EMPTY |
64 case 1 => r |
53 case 1 => r |
65 case n => SEQ(r, NTIMES(r, n - 1)) |
54 case n => SEQ(r, NTIMES(r, n - 1)) |
66 } |
55 } |
67 |
56 |
68 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
57 // the evil regular expression a?{n} a{n} |
|
58 def EVIL(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
69 |
59 |
|
60 //for measuring time |
70 def time_needed[T](i: Int, code: => T) = { |
61 def time_needed[T](i: Int, code: => T) = { |
71 val start = System.nanoTime() |
62 val start = System.nanoTime() |
72 for (j <- 1 to i) code |
63 for (j <- 1 to i) code |
73 val end = System.nanoTime() |
64 val end = System.nanoTime() |
74 (end - start)/(i * 1.0e9) |
65 (end - start)/(i * 1.0e9) |
75 } |
66 } |
76 |
67 |
77 for (i <- 1 to 29) { |
68 for (i <- 1 to 29) { |
78 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
69 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
79 } |
70 } |
80 |
|
81 |
|