412
|
1 |
def nullable(r: Rexp) : Boolean = r match {
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
case ZERO => false
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
case ONE => true
|
7
|
4 |
case CHAR(_) => false
|
|
5 |
case ALT(r1, r2) => nullable(r1) || nullable(r2)
|
|
6 |
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
|
|
7 |
case STAR(_) => true
|
|
8 |
}
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
|
412
|
10 |
def der(c: Char, r: Rexp) : Rexp = r match {
|
399
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
case ZERO => ZERO
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
case ONE => ZERO
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
case CHAR(d) => if (c == d) ONE else ZERO
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
case SEQ(r1, r2) =>
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
else SEQ(der(c, r1), r2)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
case STAR(r) => SEQ(der(c, r), STAR(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
|
412
|
21 |
def ders(s: List[Char], r: Rexp) : Rexp = s match {
|
261
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
case Nil => r
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
case c::s => ders(s, der(c, r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
def matches(r: Rexp, s: String) : Boolean =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
nullable(ders(s.toList, r))
|