3 case object ONE extends Rexp |
3 case object ONE extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
|
8 case class RANGE(cs: List[Char]) extends Rexp |
|
9 case class PLUS(r: Rexp) extends Rexp |
|
10 case class OPT(r: Rexp) extends Rexp |
|
11 case class NTIMES(r: Rexp, n : Int) extends Rexp |
|
12 case class NMTIMES(r: Rexp, n : Int, m : Int) extends Rexp |
|
13 |
8 |
14 |
9 // nullable function: tests whether the regular |
15 // nullable function: tests whether the regular |
10 // expression can recognise the empty string |
16 // expression can recognise the empty string |
11 def nullable (r: Rexp) : Boolean = r match { |
17 def nullable (r: Rexp) : Boolean = r match { |
12 case ZERO => false |
18 case ZERO => false |
13 case ONE => true |
19 case ONE => true |
14 case CHAR(_) => false |
20 case CHAR(_) => false |
15 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
21 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
16 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
22 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
17 case STAR(_) => true |
23 case STAR(_) => true |
|
24 |
18 } |
25 } |
19 |
26 |
20 // derivative of a regular expression w.r.t. a character |
27 // derivative of a regular expression w.r.t. a character |
21 def der (c: Char, r: Rexp) : Rexp = r match { |
28 def der (c: Char, r: Rexp) : Rexp = r match { |
22 case ZERO => ZERO |
29 case ZERO => ZERO |