1 // Main Part 3 about Regular Expression Matching |
1 // Main Part 3 about Regular Expression Matching |
2 //============================================== |
2 //============================================== |
3 |
3 |
4 object M3 { |
4 object M3 { |
5 |
5 |
6 // Regular Expressions |
|
7 abstract class Rexp |
6 abstract class Rexp |
8 case object ZERO extends Rexp |
7 case object ZERO extends Rexp |
9 case object ONE extends Rexp |
8 case object ONE extends Rexp |
10 case class CHAR(c: Char) extends Rexp |
9 case class CHAR(c: Char) extends Rexp |
11 case class ALTs(rs: List[Rexp]) extends Rexp // alternatives |
10 case class ALTs(rs: List[Rexp]) extends Rexp // alternatives |
16 //the usual binary choice and binary sequence can be defined |
15 //the usual binary choice and binary sequence can be defined |
17 //in terms of ALTs and SEQs |
16 //in terms of ALTs and SEQs |
18 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) |
17 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2)) |
19 def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2)) |
18 def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2)) |
20 |
19 |
21 // some convenience for typing in regular expressions |
20 |
22 import scala.language.implicitConversions |
21 // some convenience for typing regular expressions |
23 import scala.language.reflectiveCalls |
|
24 |
22 |
25 def charlist2rexp(s: List[Char]): Rexp = s match { |
23 def charlist2rexp(s: List[Char]): Rexp = s match { |
26 case Nil => ONE |
24 case Nil => ONE |
27 case c::Nil => CHAR(c) |
25 case c::Nil => CHAR(c) |
28 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
26 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
29 } |
27 } |
30 implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) |
28 |
31 |
29 import scala.language.implicitConversions |
32 implicit def RexpOps (r: Rexp) = new { |
30 |
|
31 given Conversion[String, Rexp] = (s => charlist2rexp(s.toList)) |
|
32 |
|
33 extension (r: Rexp) { |
33 def | (s: Rexp) = ALT(r, s) |
34 def | (s: Rexp) = ALT(r, s) |
34 def % = STAR(r) |
35 def % = STAR(r) |
35 def ~ (s: Rexp) = SEQ(r, s) |
36 def ~ (s: Rexp) = SEQ(r, s) |
36 } |
37 } |
37 |
38 |
38 implicit def stringOps (s: String) = new { |
39 // some examples for the conversion and extension: |
39 def | (r: Rexp) = ALT(s, r) |
40 |
40 def | (r: String) = ALT(s, r) |
41 // val areg : Rexp = "a" | "b" |
41 def % = STAR(s) |
42 // => ALTs(List(CHAR('a'), CHAR('b'))) |
42 def ~ (r: Rexp) = SEQ(s, r) |
43 // |
43 def ~ (r: String) = SEQ(s, r) |
44 // val sreg : Rexp = "a" ~ "b" |
44 } |
45 // => SEQs(List(CHAR('a'), CHAR('b'))) |
|
46 // |
|
47 // val star_reg : Rexp = ("a" ~ "b").% |
|
48 // => STAR(SEQs(List(CHAR('a'), CHAR('b')))) |
|
49 |
|
50 // ADD YOUR CODE BELOW |
|
51 //====================== |
45 |
52 |
46 // (1) |
53 // (1) |
47 def nullable (r: Rexp) : Boolean = r match { |
54 def nullable (r: Rexp) : Boolean = r match { |
48 case ZERO => false |
55 case ZERO => false |
49 case ONE => true |
56 case ONE => true |