diff -r 2f3c077359c4 -r 9541e073f2ed progs/matcher/re3.sc --- a/progs/matcher/re3.sc Mon Sep 25 13:14:34 2023 +0100 +++ b/progs/matcher/re3.sc Mon Sep 25 15:12:11 2023 +0100 @@ -1,10 +1,10 @@ -// A version of the matcher with simplification +// A version of the simple matcher with simplification // of derivatives // -// this keeps the regular expressions small, which +// this keeps the regular expressions (often) small, which // is good for the run-time // -// call the test cases with X = {1,2} +// call the test cases with X = {1,2,3,4} // // amm re3.sc testX // @@ -23,7 +23,6 @@ case class NTIMES(r: Rexp, n: Int) extends Rexp - // the nullable function: tests whether the regular // expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { @@ -67,7 +66,7 @@ case r => r } -// the derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der and simp) def ders(s: List[Char], r: Rexp) : Rexp = s match { case Nil => r case c::s => ders(s, simp(der(c, r))) @@ -81,7 +80,7 @@ // Test Cases //============ -// one or zero +// optional is still just defined def OPT(r: Rexp) = ALT(r, ONE) // evil regular expressions: (a?){n} a{n} and (a*)* b @@ -130,7 +129,8 @@ // now the size of the derivatives grows -// much, much slower +// much, much slower and actually maxes out +// at size 8 size(ders("".toList, EVIL2)) // 5 size(ders("a".toList, EVIL2)) // 8 @@ -139,6 +139,8 @@ size(ders("aaaa".toList, EVIL2)) // 8 size(ders("aaaaa".toList, EVIL2)) // 8 +size(ders(("a" * 20000).toList, EVIL2)) // 8 + @arg(doc = "All tests.") @main