/
RegexMatchCPS.scala
55 lines (48 loc) · 1.63 KB
/
RegexMatchCPS.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
object RegexMatchCPS {
class Regex
case class Literal(s: String) extends Regex
case class Concat(r1: Regex, r2: Regex)
extends Regex
case class Choice(r1: Regex, r2: Regex)
extends Regex
case class Star(r: Regex) extends Regex
def accept (regex: Regex,
chars: Seq[Char],
k: Seq[Char] => Boolean): Boolean = {
printf("%s |- %s\n", regex, chars)
regex match {
case Literal(expected) =>
if(chars.take(expected.length).sameElements(expected))
k(chars.drop(expected.length))
else false
case Concat(regex1, regex2) =>
accept(regex1, chars, remaining =>
accept(regex2, remaining, k))
case Choice(regex1, regex2) =>
accept(regex1, chars, k) || accept(regex2, chars, k)
case Star(repeatable) =>
k(chars) ||
accept(repeatable, chars, remaining =>
accept(regex, remaining, k))
}
}
def complete (remaining: Seq[Char]): Boolean = {
printf("Complete? '%s'\n", remaining)
remaining.length == 0
}
def showAccept(regex: Regex, chars: String, expected: Boolean) {
println
val result = accept(regex, chars, complete)
printf("%s => %b [%s]\n", chars, result,
if(result == expected) "OK" else "error")
}
val regex1 = Concat(Star(Literal("ab")), Literal("abc"))
val regex2 = Choice(Star(Literal("ab")),
Concat(Literal("a"), Star(Literal("ba"))))
def main(args: Array[String]) {
showAccept(Literal("abc"), "abc", true)
showAccept(regex1, "abababc", true)
showAccept(regex1, "abababd", false)
showAccept(regex2, "abababa", true)
}
}