--- a/progs/scala/autos.scala Wed Mar 29 05:50:38 2017 +0800
+++ b/progs/scala/autos.scala Sun Apr 02 02:14:01 2017 +0800
@@ -247,6 +247,7 @@
case object ONE extends Rexp
case class CHAR(c: Char) extends Rexp
case object ALL extends Rexp
+case object ALLPlus extends Rexp
case class ALT(r1: Rexp, r2: Rexp) extends Rexp
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
case class STAR(r: Rexp) extends Rexp
@@ -299,7 +300,7 @@
case ALT(r1, r2) => (simp(r1), simp(r2)) match {
case (ZERO, r2s) => r2s
case (r1s, ZERO) => r1s
- case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
+ case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s)
}
case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
case (ZERO, _) => ZERO
@@ -310,8 +311,14 @@
}
case NTIMES(r, n) => if (n == 0) ONE else NTIMES(simp(r), n)
case UPNTIMES(r, n) => if (n == 0) ONE else UPNTIMES(simp(r), n)
+ /*
case NOT(r) => NOT(simp(r))
- case AND(r1, r2) => AND(simp(r1), simp(r2))
+ case AND(r1, r2) => (simp(r1), simp(r2)) match {
+ case (ALL, r2s) => r2s
+ case (r1s, ALL) => r1s
+ case (r1s, r2s) => if (r1s == r2s) r1s else AND(r1s, r2s)
+ }
+ */
case r => r
}
@@ -322,7 +329,8 @@
case ZERO => false
case ONE => true
case CHAR(_) => false
- case ALL => false
+ case ALL => true
+ case ALLPlus => false
case ALT(r1, r2) => nullable(r1) || nullable(r2)
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
case STAR(_) => true
@@ -337,7 +345,8 @@
case ZERO => ZERO
case ONE => ZERO
case CHAR(d) => if (c == d) ONE else ZERO
- case ALL => ONE
+ case ALL => ALL
+ case ALLPlus => ALL
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
case SEQ(r1, r2) =>
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
@@ -351,7 +360,7 @@
if (i == 0) ZERO
else SEQ(der(c, r1), UPNTIMES(r1, i - 1))
case NOT(r) => NOT(der(c, r))
- // AND case?
+ case AND(r1, r2) => AND(der(c, r1), der(c, r2))
}
@@ -361,7 +370,8 @@
case ZERO => Set()
case ONE => Set()
case CHAR(d) => if (c == d) Set(ONE) else Set()
- case ALL => Set(ONE)
+ case ALL => Set(ALL)
+ case ALLPlus => Set(ALL)
case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2)
case SEQ(r1, r2) =>
(for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++
@@ -396,44 +406,67 @@
}
-
+// partial derivatives including NOT and AND according to
+// PhD-thesis: Manipulation of Extended Regular Expressions
+// with Derivatives; these partial derivatives are also not
+// finite...for example NOT((a*)a)
-def seq_add(rss: Set[Set[Rexp]], r2: Rexp) : Set[Set[Rexp]] =
- for (rs <- rss) yield (for (r <- rs) yield (SEQ(r, r2) : Rexp))
+def seq_compose(rs: Set[Rexp], r2: Rexp) : Set[Rexp] =
+ for (r <- rs) yield (SEQ(r, r2) : Rexp)
-def not_add(rss: Set[Set[Rexp]]) : Set[Set[Set[Rexp]]] =
- for (rs <- rss) yield (for (r <- rs) yield (Set(NOT(r)) : Set[Rexp]))
+def not_compose(rs: Set[Rexp]) : Set[Rexp] =
+ Set(rs.fold(ALL)((r1, r2) => AND(r1, NOT(r2))))
-def and_compose(rss1: Set[Set[Rexp]], rss2: Set[Set[Rexp]]) : Set[Set[Rexp]] =
- for (rs1 <- rss1; rs2 <- rss2) yield rs1 ++ rs2
+def and_compose(rs1: Set[Rexp], rs2: Set[Rexp]) : Set[Rexp] =
+ for (r1 <- rs1; r2 <- rs2) yield AND(r1, r2)
-def pder2(c: Char, r: Rexp) : Set[Set[Rexp]] = r match {
+def pder2(c: Char, r: Rexp) : Set[Rexp] = r match {
case ZERO => Set()
case ONE => Set()
- case CHAR(d) => if (c == d) Set(Set(ONE)) else Set()
- case ALL => Set(Set(ONE))
+ case ALL => Set(ALL)
+ case ALLPlus => Set(ALL)
+ case CHAR(d) => if (c == d) Set(ONE) else Set()
case ALT(r1, r2) => pder2(c, r1) ++ pder2(c, r2)
case SEQ(r1, r2) => {
- val prs1 = seq_add(pder2(c, r1), r2)
+ val prs1 = seq_compose(pder2(c, r1), r2)
if (nullable(r1)) (prs1 ++ pder2(c, r2)) else prs1
}
- case STAR(r1) =>
- seq_add(pder2(c, r1), STAR(r1))
+ case STAR(r1) => seq_compose(pder2(c, r1), STAR(r1))
case AND(r1, r2) => and_compose(pder2(c, r1), pder2(c, r2))
- case NOT(r1) => {
- val prs1 = not_add(pder2(c, r1))
- if (prs1.isEmpty) Set() else
- prs1.tail.foldRight(prs1.head) { (rs1, rs2) => rs1 ++ rs2 }
- }
+ case NOT(r1) => nder2(c, r1)
}
-def pmatcher2(rss: Set[Set[Rexp]], s: List[Char]): Boolean = s match {
- case Nil => rss.exists((rs) => rs.exists((r) => nullable(r)))
- case c::cs => pmatcher2(rss.flatMap(_.flatMap(pder2(c, _))), cs)
+def nder2(c: Char, r: Rexp) : Set[Rexp] = r match {
+ case ZERO => Set(ALL)
+ case ONE => Set(ALL)
+ case ALL => Set()
+ case ALLPlus => Set()
+ case CHAR(d) => if (c == d) Set(ALLPlus) else Set(ALL)
+ case ALT(r1, r2) => and_compose(nder2(c, r1), nder2(c, r2))
+ case SEQ(r1, r2) => if (nullable(r1))
+ and_compose(not_compose(seq_compose(pder2(c, r1), r2)), nder2(c, r2))
+ else not_compose(seq_compose(pder2(c, r1), r2))
+ case STAR(r1) => not_compose(pder2(c, STAR(r1)))
+ case AND(r1, r2) => nder2(c, r1) ++ nder2(c, r2)
+ case NOT(r1) => pder2(c, r1)
+}
+
+
+def pmatcher2(rs: Set[Rexp], s: List[Char]): Boolean = s match {
+ case Nil => rs.exists(nullable(_))
+ case c::cs => pmatcher2(rs.flatMap(pder2(c, _)), cs)
}
+// pder2/nder2 example
-// quick-and-dirty translation of a pder automaton
+val r_ex = AND("aa" | "a", AND(STAR("a"), NOT(STAR("a") ~ "a")))
+nder2('a', r_ex).map(simp(_)).mkString("\n")
+
+
+
+
+
+// quick-and-dirty translation of a pder-automaton
val r = STAR(ALL) ~ "a" ~ NTIMES(ALL, 3) ~ "bc"
val pder_nfa = NFA[Set[Rexp], Char](Set(Set(r)),
@@ -509,7 +542,11 @@
-// Antimirov Partial derivative automata construction ... definitely terminates
+// Antimirov Partial derivative automata construction ... definitely
+// terminates but does not work for extensions of NOT and AND
+//
+// for this we have to use the extended partial derivatives
+// pder2/nder2
// to transform (concrete) Maps into functions
@@ -517,7 +554,7 @@
{ case (q, c) => m(q, c) }
def pgoto(sigma: Set[Char], delta: STrans, qs: DStates, q: DState, c: Char) : (DStates, STrans) = {
- val qders = pder(c, q).map(simp(_)) // set of simplified partial derivatives
+ val qders = pder2(c, q).map(simp(_)) // set of simplified partial derivatives
qders.foldLeft((qs, delta)) { case ((qs, delta), qnew) => padd(sigma, delta, qs, q, qnew, c) }
}
@@ -586,19 +623,13 @@
matcher(rnot, "/*aaabaa*/".toList) // true
matcher(rnot, "/*/**/".toList) // true
matcher(rnot, "/*aaa*/aa*/".toList) // false
-matcher(rnot, "/aaa*/aa*/".toList) // false
+matcher(rnot, "/aaa*/aa*/".toList) // false
-pmatcher(Set(rnot), "/**/".toList) // true
-pmatcher(Set(rnot), "/*aaabaa*/".toList) // true
-pmatcher(Set(rnot), "/*/**/".toList) // true
-pmatcher(Set(rnot), "/*aaa*/aa*/".toList) // false ?????
-pmatcher(Set(rnot), "/aaa*/aa*/".toList) // false
-
-pmatcher2(Set(Set(rnot)), "/**/".toList) // true
-pmatcher2(Set(Set(rnot)), "/*aaabaa*/".toList) // true
-pmatcher2(Set(Set(rnot)), "/*/**/".toList) // true
-pmatcher2(Set(Set(rnot)), "/*aaa*/aa*/".toList) // false ?????
-pmatcher2(Set(Set(rnot)), "/aaa*/aa*/".toList) // false
+pmatcher2(Set(rnot), "/**/".toList) // true
+pmatcher2(Set(rnot), "/*aaabaa*/".toList) // true
+pmatcher2(Set(rnot), "/*/**/".toList) // true
+pmatcher2(Set(rnot), "/*aaa*/aa*/".toList) // false
+pmatcher2(Set(rnot), "/aaa*/aa*/".toList) // false
// example from automata paper with counters and backreferences