|
1 package Handouts |
|
2 |
|
3 import io.Source |
|
4 import scala.util.matching.Regex |
|
5 import scala.util._ |
|
6 |
|
7 object Handout2 { |
|
8 abstract class Rexp |
|
9 case object NULL extends Rexp |
|
10 case object EMPTY extends Rexp |
|
11 case class CHAR(c: Char) extends Rexp |
|
12 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
13 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
14 case class STAR(r: Rexp) extends Rexp |
|
15 case class NTIMES(r: Rexp, n: Int) extends Rexp |
|
16 |
|
17 def OPT(r: Rexp) = ALT(r, EMPTY) //> OPT: (r: Handouts.Handout2.Rexp)Handouts.Handout2.ALT |
|
18 |
|
19 /* |
|
20 def NTIMES(r: Rexp, n: Int): Rexp = n match { |
|
21 case 0 => EMPTY |
|
22 case 1 => r |
|
23 case n => SEQ(r, NTIMES(r, n - 1)) |
|
24 } |
|
25 */ |
|
26 |
|
27 def nullable(r: Rexp): Boolean = r match { |
|
28 case NULL => false |
|
29 case EMPTY => true |
|
30 case CHAR(_) => false |
|
31 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
32 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
33 case STAR(_) => true |
|
34 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
|
35 } //> nullable: (r: Handouts.Handout2.Rexp)Boolean |
|
36 |
|
37 def der(c: Char, r: Rexp): Rexp = r match { |
|
38 case NULL => NULL |
|
39 case EMPTY => NULL |
|
40 case CHAR(d) => if (c == d) EMPTY else NULL |
|
41 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
42 case SEQ(r1, r2) => |
|
43 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
44 else SEQ(der(c, r1), r2) |
|
45 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
46 case NTIMES(r, i) => |
|
47 if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1)) |
|
48 } //> der: (c: Char, r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp |
|
49 |
|
50 def _ders(s: List[Char], r: Rexp): Rexp = s match { |
|
51 case Nil => r |
|
52 case c :: s => ders(s, der(c, r)) |
|
53 } //> _ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp |
|
54 |
|
55 def ders(s: List[Char], r: Rexp): Rexp = s match { |
|
56 case Nil => r |
|
57 case c :: s => ders(s, simp(der(c, r))) |
|
58 } //> ders: (s: List[Char], r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp |
|
59 |
|
60 def matches(r: Rexp, s: String): Boolean = |
|
61 nullable(ders(s.toList, r)) //> matches: (r: Handouts.Handout2.Rexp, s: String)Boolean |
|
62 |
|
63 def simp(r: Rexp): Rexp = r match { |
|
64 case ALT(r1, r2) => { |
|
65 val r1s = simp(r1) |
|
66 val r2s = simp(r2) |
|
67 (r1s, r2s) match { |
|
68 case (NULL, _) => r2s |
|
69 case (_, NULL) => r1s |
|
70 case _ => if (r1s == r2s) r1s else ALT(r1s, r2s) |
|
71 } |
|
72 } |
|
73 case SEQ(r1, r2) => { |
|
74 val r1s = simp(r1) |
|
75 val r2s = simp(r2) |
|
76 (r1s, r2s) match { |
|
77 case (NULL, _) => NULL |
|
78 case (_, NULL) => NULL |
|
79 case (EMPTY, _) => r2s |
|
80 case (_, EMPTY) => r1s |
|
81 case _ => SEQ(r1s, r2s) |
|
82 } |
|
83 } |
|
84 case NTIMES(r, n) => NTIMES(simp(r), n) |
|
85 case r => r |
|
86 } //> simp: (r: Handouts.Handout2.Rexp)Handouts.Handout2.Rexp |
|
87 |
|
88 /************************************************************************************************************************************/ |
|
89 // der test |
|
90 // r = {(a.b) + b}* |
|
91 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
|
92 //> r : Handouts.Handout2.STAR = STAR(ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b))) |
|
93 |
|
94 // => [{(_.b) + null} . {(a.b)+b}*] |
|
95 der('a', r) //> res0: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(EMPTY,CHAR(b)),NULL),STAR(ALT(SE |
|
96 //| Q(CHAR(a),CHAR(b)),CHAR(b)))) |
|
97 // => [{(null.b) + _} . {(a.b)+b}*] |
|
98 der('b', r) //> res1: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),EMPTY),STAR(ALT(SE |
|
99 //| Q(CHAR(a),CHAR(b)),CHAR(b)))) |
|
100 // => [{(null.b) + _} . {(a.b)+b}*] |
|
101 der('c', r) //> res2: Handouts.Handout2.Rexp = SEQ(ALT(SEQ(NULL,CHAR(b)),NULL),STAR(ALT(SEQ |
|
102 //| (CHAR(a),CHAR(b)),CHAR(b)))) |
|
103 |
|
104 val r2 = ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')) |
|
105 //> r2 : Handouts.Handout2.ALT = ALT(SEQ(CHAR(a),CHAR(b)),CHAR(b)) |
|
106 der('a', r2) //> res3: Handouts.Handout2.Rexp = ALT(SEQ(EMPTY,CHAR(b)),NULL) |
|
107 |
|
108 val r3 = SEQ(CHAR('a'), CHAR('b')) //> r3 : Handouts.Handout2.SEQ = SEQ(CHAR(a),CHAR(b)) |
|
109 der('a', r3) //> res4: Handouts.Handout2.Rexp = SEQ(EMPTY,CHAR(b)) |
|
110 |
|
111 val r4 = CHAR('a') //> r4 : Handouts.Handout2.CHAR = CHAR(a) |
|
112 der('a', r4) //> res5: Handouts.Handout2.Rexp = EMPTY |
|
113 |
|
114 nullable(r) //> res6: Boolean = true |
|
115 nullable(r2) //> res7: Boolean = false |
|
116 nullable(r3) //> res8: Boolean = false |
|
117 nullable(r4) //> res9: Boolean = false |
|
118 } |