10 case class CHAR(c: Char) extends Rexp |
10 case class CHAR(c: Char) extends Rexp |
11 case class ALTs(rs: List[Rexp]) extends Rexp // alternatives |
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 // some convenience for typing in regular expressions |
|
16 |
|
17 |
15 |
18 //the usual binary choice can be defined in terms of ALTs |
16 //the usual binary choice can be defined in terms of ALTs |
19 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) |
17 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) |
20 |
18 |
21 |
19 // some convenience for typing in regular expressions |
22 import scala.language.implicitConversions |
20 import scala.language.implicitConversions |
23 import scala.language.reflectiveCalls |
21 import scala.language.reflectiveCalls |
24 |
|
25 |
22 |
26 def charlist2rexp(s: List[Char]): Rexp = s match { |
23 def charlist2rexp(s: List[Char]): Rexp = s match { |
27 case Nil => ONE |
24 case Nil => ONE |
28 case c::Nil => CHAR(c) |
25 case c::Nil => CHAR(c) |
29 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
26 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
74 else SEQ(der(c, r1), r2) |
71 else SEQ(der(c, r1), r2) |
75 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
72 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
76 } |
73 } |
77 |
74 |
78 |
75 |
|
76 // (3) Implement the flatten function flts. It |
|
77 // deletes 0s from a list of regular expressions |
|
78 // and also 'spills out', or flattens, nested |
|
79 // ALTernativeS. |
79 |
80 |
80 def flts(rs: List[Rexp]) : List[Rexp] = rs match { |
81 def flts(rs: List[Rexp]) : List[Rexp] = rs match { |
81 case Nil => Nil |
82 case Nil => Nil |
82 case ZERO::tl => flts(tl) |
83 case ZERO::tl => flts(tl) |
83 case ALTs(rs1)::rs2 => rs1 ::: flts(rs2) |
84 case ALTs(rs1)::rs2 => rs1 ::: flts(rs2) |
84 case r::rs => r :: flts(rs) |
85 case r::rs => r :: flts(rs) |
85 } |
86 } |
86 |
87 |
87 // (3) Complete the simp function according to |
88 // (4) Complete the simp function according to |
88 // the specification given in the coursework; this |
89 // the specification given in the coursework; this |
89 // function simplifies a regular expression from |
90 // function simplifies a regular expression from |
90 // the inside out, like you would simplify arithmetic |
91 // the inside out, like you would simplify arithmetic |
91 // expressions; however it does not simplify inside |
92 // expressions; however it does not simplify inside |
92 // STAR-regular expressions. |
93 // STAR-regular expressions. |
108 case r => r |
109 case r => r |
109 } |
110 } |
110 |
111 |
111 simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) |
112 simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) |
112 |
113 |
113 // (4) Complete the two functions below; the first |
114 // (5) Complete the two functions below; the first |
114 // calculates the derivative w.r.t. a string; the second |
115 // calculates the derivative w.r.t. a string; the second |
115 // is the regular expression matcher taking a regular |
116 // is the regular expression matcher taking a regular |
116 // expression and a string and checks whether the |
117 // expression and a string and checks whether the |
117 // string matches the regular expression. |
118 // string matches the regular expression. |
118 |
119 |
122 } |
123 } |
123 |
124 |
124 // main matcher function |
125 // main matcher function |
125 def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r)) |
126 def matcher(r: Rexp, s: String) = nullable(ders(s.toList, r)) |
126 |
127 |
127 // (5) Complete the size function for regular |
128 // (6) Complete the size function for regular |
128 // expressions according to the specification |
129 // expressions according to the specification |
129 // given in the coursework. |
130 // given in the coursework. |
130 |
131 |
131 |
132 |
132 def size(r: Rexp): Int = r match { |
133 def size(r: Rexp): Int = r match { |
144 |
145 |
145 //matcher(("a" ~ "b") ~ "c", "abc") // => true |
146 //matcher(("a" ~ "b") ~ "c", "abc") // => true |
146 //matcher(("a" ~ "b") ~ "c", "ab") // => false |
147 //matcher(("a" ~ "b") ~ "c", "ab") // => false |
147 |
148 |
148 // the supposedly 'evil' regular expression (a*)* b |
149 // the supposedly 'evil' regular expression (a*)* b |
149 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
150 // val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
150 |
151 |
151 //println(matcher(EVIL, "a" * 1000 ++ "b")) // => true |
152 //println(matcher(EVIL, "a" * 1000 ++ "b")) // => true |
152 //println(matcher(EVIL, "a" * 1000)) // => false |
153 //println(matcher(EVIL, "a" * 1000)) // => false |
153 |
154 |
154 // size without simplifications |
155 // size without simplifications |