1 // Core Part about Regular Expression Matching |
1 // Main Part 3 about Regular Expression Matching |
2 //============================================= |
2 //============================================= |
3 |
3 |
4 object CW8c { |
4 object M3 { |
5 |
5 |
6 // Regular Expressions |
6 // Regular Expressions |
7 abstract class Rexp |
7 abstract class Rexp |
8 case object ZERO extends Rexp |
8 case object ZERO extends Rexp |
9 case object ONE extends Rexp |
9 case object ONE extends Rexp |
10 case class CHAR(c: Char) extends Rexp |
10 case class CHAR(c: Char) extends Rexp |
11 case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative |
11 case class ALTs(rs: List[Rexp]) extends Rexp // alternatives |
12 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
12 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
13 case class STAR(r: Rexp) extends Rexp // star |
13 case class STAR(r: Rexp) extends Rexp // star |
14 |
14 |
15 |
15 |
16 // some convenience for typing regular expressions |
16 // some convenience for typing regular expressions |
|
17 |
|
18 //the usual binary choice can be defined in terms of ALTs |
|
19 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) |
|
20 |
17 |
21 |
18 import scala.language.implicitConversions |
22 import scala.language.implicitConversions |
19 import scala.language.reflectiveCalls |
23 import scala.language.reflectiveCalls |
20 |
24 |
21 def charlist2rexp(s: List[Char]): Rexp = s match { |
25 def charlist2rexp(s: List[Char]): Rexp = s match { |
54 // regular expression w.r.t. a character. |
58 // regular expression w.r.t. a character. |
55 |
59 |
56 def der (c: Char, r: Rexp) : Rexp = ??? |
60 def der (c: Char, r: Rexp) : Rexp = ??? |
57 |
61 |
58 |
62 |
59 // (3) Complete the simp function according to |
63 // (3) Implement the flatten function flts. It |
60 // the specification given in the coursework; this |
64 // deletes 0s from a list of regular expressions |
61 // function simplifies a regular expression from |
65 // and also 'spills out', or flattens, nested |
|
66 // ALTernativeS. |
|
67 |
|
68 def flts(rs: List[Rexp]) : List[Rexp] = ??? |
|
69 |
|
70 |
|
71 |
|
72 // (4) Complete the simp function according to |
|
73 // the specification given in the coursework description; |
|
74 // this function simplifies a regular expression from |
62 // the inside out, like you would simplify arithmetic |
75 // the inside out, like you would simplify arithmetic |
63 // expressions; however it does not simplify inside |
76 // expressions; however it does not simplify inside |
64 // STAR-regular expressions. |
77 // STAR-regular expressions. Use the _.distinct and |
|
78 // flts functions. |
65 |
79 |
66 def simp(r: Rexp) : Rexp = ??? |
80 def simp(r: Rexp) : Rexp = ??? |
67 |
81 |
68 |
82 |
69 // (4) Complete the two functions below; the first |
83 // (5) Complete the two functions below; the first |
70 // calculates the derivative w.r.t. a string; the second |
84 // calculates the derivative w.r.t. a string; the second |
71 // is the regular expression matcher taking a regular |
85 // is the regular expression matcher taking a regular |
72 // expression and a string and checks whether the |
86 // expression and a string and checks whether the |
73 // string matches the regular expression |
87 // string matches the regular expression |
74 |
88 |
75 def ders (s: List[Char], r: Rexp) : Rexp = ??? |
89 def ders (s: List[Char], r: Rexp) : Rexp = ??? |
76 |
90 |
77 def matcher(r: Rexp, s: String): Boolean = ??? |
91 def matcher(r: Rexp, s: String): Boolean = ??? |
78 |
92 |
79 |
93 |
80 // (5) Complete the size function for regular |
94 // (6) Complete the size function for regular |
81 // expressions according to the specification |
95 // expressions according to the specification |
82 // given in the coursework. |
96 // given in the coursework. |
83 |
97 |
84 def size(r: Rexp): Int = ??? |
98 def size(r: Rexp): Int = ??? |
85 |
99 |