--- a/progs/matcher/re1.sc	Mon Feb 03 13:25:59 2025 +0000
+++ b/progs/matcher/re1.sc	Fri Sep 05 16:59:48 2025 +0100
@@ -10,15 +10,16 @@
 //
 
  
-// regular expressions
-abstract class Rexp
-case object ZERO extends Rexp                    // matches nothing
-case object ONE extends Rexp                     // matches an empty string
-case class CHAR(c: Char) extends Rexp            // matches a character c
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp  // alternative
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp  // sequence
-case class STAR(r: Rexp) extends Rexp            // star
-
+// regular expressions (as enum in Scala 3)
+enum Rexp {
+  case ZERO                     // matches nothing
+  case ONE                      // matches an empty string
+  case CHAR(c: Char)            // matches a character c
+  case ALT(r1: Rexp, r2: Rexp)  // alternative
+  case SEQ(r1: Rexp, r2: Rexp)  // sequence
+  case STAR(r: Rexp)            // star
+}
+import Rexp._
 
 // nullable function: tests whether a regular 
 // expression can recognise the empty string  
@@ -172,9 +173,74 @@
   }
 }
 
+
+
+// Some code for pretty printing regexes as trees
+
+def implode(ss: Seq[String]) = ss.mkString("\n")
+def explode(s: String) = s.split("\n").toList
+
+def lst(s: String) : String = explode(s) match {
+  case hd :: tl => implode(" └" ++ hd :: tl.map("  " ++ _))
+  case Nil => ""
+}
+
+def mid(s: String) : String = explode(s) match {
+  case hd :: tl => implode(" ├" ++ hd :: tl.map(" │" ++ _))
+  case Nil => ""
+}
+
+def indent(ss: Seq[String]) : String = ss match {
+  case init :+ last => implode(init.map(mid) :+ lst(last))
+  case _ => ""
+}
+
+def pp(e: Rexp) : String = e match {
+  case ZERO => "0\n"
+  case ONE => "1\n"
+  case CHAR(c) => s"$c\n"
+  case ALT(r1, r2) => "ALT\n" ++ pps(r1, r2)
+  case SEQ(r1, r2) => "SEQ\n" ++ pps(r1, r2)
+  case STAR(r) => "STAR\n" ++ pps(r)
+}
+def pps(es: Rexp*) = indent(es.map(pp))
+
+
 @main
-def all() = { test1(); test2() ; test3() } 
+def test4() = {
+  println(pp(r2))
+  println(pp(ders("x".toList, r2)))
+  println(pp(ders("xy".toList, r2)))
+  println(pp(ders("xyz".toList, r2)))
+}
+
+@main
+def all() = { test1(); test2() ; test3() ; test4() } 
 
 
 
 
+
+// partial derivatives produce a set of regular expressions
+def pder(c: Char, r: Rexp) : Set[Rexp] = r match {
+  case ZERO => Set()
+  case ONE => Set()
+  case CHAR(d) => if (c == d) Set(ONE) else Set()
+  case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2)
+  case SEQ(r1, r2) => {
+    (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++
+    (if (nullable(r1)) pder(c, r2) else Set())
+  }
+  case STAR(r1) => {
+    for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1))
+  }
+}
+
+def pders(s: List[Char], rs: Set[Rexp]) : Set[Rexp] = s match {
+  case Nil => rs
+  case c::s => pders(s, rs.flatMap(pder(c, _)))
+}
+
+def pders1(s: String, r: Rexp) = pders(s.toList, Set(r))
+
+