equal
deleted
inserted
replaced
1 |
1 |
2 abstract class Rexp |
2 abstract class Rexp |
3 case object ZERO extends Rexp |
3 case object ZERO extends Rexp // matches nothing |
4 case object ONE extends Rexp |
4 case object ONE extends Rexp // matches the empty string |
5 case class CHAR(c: Char) extends Rexp |
5 case class CHAR(c: Char) extends Rexp // matches a character c |
6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative |
7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
8 case class STAR(r: Rexp) extends Rexp |
8 case class STAR(r: Rexp) extends Rexp // star |
9 |
9 |
10 // nullable function: tests whether the regular |
10 // nullable function: tests whether a regular |
11 // expression can recognise the empty string |
11 // expression can recognise the empty string |
12 def nullable (r: Rexp) : Boolean = r match { |
12 def nullable (r: Rexp) : Boolean = r match { |
13 case ZERO => false |
13 case ZERO => false |
14 case ONE => true |
14 case ONE => true |
15 case CHAR(_) => false |
15 case CHAR(_) => false |
44 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
44 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
45 der('a', r) |
45 der('a', r) |
46 der('b', r) |
46 der('b', r) |
47 der('c', r) |
47 der('c', r) |
48 |
48 |
49 //optional: one or zero times |
49 //optional (one or zero times) |
50 def OPT(r: Rexp) = ALT(r, ONE) |
50 def OPT(r: Rexp) = ALT(r, ONE) |
51 |
51 |
52 //n-times |
52 //n-times (explicitly expanded) |
53 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
53 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
54 case 0 => ONE |
54 case 0 => ONE |
55 case 1 => r |
55 case 1 => r |
56 case n => SEQ(r, NTIMES(r, n - 1)) |
56 case n => SEQ(r, NTIMES(r, n - 1)) |
57 } |
57 } |