17 case class CHAR(c: Char) extends Rexp // matches a character c |
17 case class CHAR(c: Char) extends Rexp // matches a character c |
18 case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative |
18 case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative |
19 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
19 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence |
20 case class STAR(r: Rexp) extends Rexp // star |
20 case class STAR(r: Rexp) extends Rexp // star |
21 |
21 |
|
22 |
22 // nullable function: tests whether a regular |
23 // nullable function: tests whether a regular |
23 // expression can recognise the empty string |
24 // expression can recognise the empty string |
24 |
|
25 def nullable(r: Rexp) : Boolean = r match { |
25 def nullable(r: Rexp) : Boolean = r match { |
26 case ZERO => false |
26 case ZERO => false |
27 case ONE => true |
27 case ONE => true |
28 case CHAR(_) => false |
28 case CHAR(_) => false |
29 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
29 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
52 // the main matcher function |
52 // the main matcher function |
53 def matcher(r: Rexp, s: String) : Boolean = |
53 def matcher(r: Rexp, s: String) : Boolean = |
54 nullable(ders(s.toList, r)) |
54 nullable(ders(s.toList, r)) |
55 |
55 |
56 |
56 |
|
57 // some examples from the homework |
57 |
58 |
58 val r = SEQ(CHAR('b'), CHAR('c')) |
59 val r = SEQ(CHAR('b'), CHAR('c')) |
59 matcher(r, "ac") |
60 matcher(r, "ac") |
60 |
61 |
61 // some examples from the homework |
62 val r1 = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
62 |
|
63 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
|
64 der('a', r) |
63 der('a', r) |
65 der('b', r) |
64 der('b', r) |
66 der('c', r) |
65 der('c', r) |
67 |
66 |
68 val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
67 val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
69 der('x', r2) |
68 der('x', r2) |
70 der('y', der('x', r2)) |
69 der('y', der('x', r2)) |
71 der('z', der('y', der('x', r2))) |
70 der('z', der('y', der('x', r2))) |
72 |
71 |
73 |
72 |
|
73 // Test Cases |
|
74 //============ |
|
75 |
74 // the optional regular expression (one or zero times) |
76 // the optional regular expression (one or zero times) |
75 def OPT(r: Rexp) = ALT(r, ONE) // r + 1 |
77 def OPT(r: Rexp) = ALT(r, ONE) // r + 1 |
76 |
78 |
77 // the n-times regular expression (explicitly expanded) |
79 // the n-times regular expression (explicitly expanded) |
78 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
80 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
79 case 0 => ONE |
81 case 0 => ONE |
80 case 1 => r |
82 case 1 => r |
81 case n => SEQ(r, NTIMES(r, n - 1)) |
83 case n => SEQ(r, NTIMES(r, n - 1)) |
82 } |
84 } |
83 |
|
84 |
|
85 // Test Cases |
|
86 //============ |
|
87 |
85 |
88 // the evil regular expression (a?){n} a{n} |
86 // the evil regular expression (a?){n} a{n} |
89 def EVIL1(n: Int) = |
87 def EVIL1(n: Int) = |
90 SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
88 SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
91 |
89 |