7 // or |
7 // or |
8 // |
8 // |
9 // amm re1.sc all |
9 // amm re1.sc all |
10 // |
10 // |
11 |
11 |
12 |
12 |
13 // regular expressions (as enum in Scala 3) |
13 // regular expressions (as enum in Scala 3) |
14 enum Rexp { |
14 enum Rexp { |
15 case ZERO // matches nothing |
15 case ZERO // matches nothing |
16 case ONE // matches an empty string |
16 case ONE // matches an empty string |
17 case CHAR(c: Char) // matches a character c |
17 case CHAR(c: Char) // matches a character c |
18 case ALT(r1: Rexp, r2: Rexp) // alternative |
18 case ALT(r1: Rexp, r2: Rexp) // alternative |
19 case SEQ(r1: Rexp, r2: Rexp) // sequence |
19 case SEQ(r1: Rexp, r2: Rexp) // sequence |
20 case STAR(r: Rexp) // star |
20 case STAR(r: Rexp) // star |
21 } |
21 } |
22 import Rexp._ |
22 import Rexp._ |
|
23 |
|
24 |
|
25 /* |
|
26 UPDATE: The videos and handouts still us the older syntax |
|
27 with classes, which still works but is more verbose |
|
28 |
|
29 abstract class Rexp |
|
30 case object ZERO extends Rexp |
|
31 case object ONE extends Rexp |
|
32 case class CHAR(c: Char) extends Rexp |
|
33 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
34 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
35 case class STAR(r: Rexp) extends Rexp |
|
36 */ |
23 |
37 |
24 // nullable function: tests whether a regular |
38 // nullable function: tests whether a regular |
25 // expression can recognise the empty string |
39 // expression can recognise the empty string |
26 def nullable(r: Rexp) : Boolean = r match { |
40 def nullable(r: Rexp) : Boolean = r match { |
27 case ZERO => false |
41 case ZERO => false |
215 } |
229 } |
216 |
230 |
217 @main |
231 @main |
218 def all() = { test1(); test2() ; test3() ; test4() } |
232 def all() = { test1(); test2() ; test3() ; test4() } |
219 |
233 |
220 |
|
221 |
|
222 |
|
223 |
|
224 // partial derivatives produce a set of regular expressions |
|
225 def pder(c: Char, r: Rexp) : Set[Rexp] = r match { |
|
226 case ZERO => Set() |
|
227 case ONE => Set() |
|
228 case CHAR(d) => if (c == d) Set(ONE) else Set() |
|
229 case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2) |
|
230 case SEQ(r1, r2) => { |
|
231 (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ |
|
232 (if (nullable(r1)) pder(c, r2) else Set()) |
|
233 } |
|
234 case STAR(r1) => { |
|
235 for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1)) |
|
236 } |
|
237 } |
|
238 |
|
239 def pders(s: List[Char], rs: Set[Rexp]) : Set[Rexp] = s match { |
|
240 case Nil => rs |
|
241 case c::s => pders(s, rs.flatMap(pder(c, _))) |
|
242 } |
|
243 |
|
244 def pders1(s: String, r: Rexp) = pders(s.toList, Set(r)) |
|
245 |
|
246 |
|