diff -r ef54868a9226 -r 2f3c077359c4 progs/matcher/re1.sc --- a/progs/matcher/re1.sc Sat Sep 23 23:53:06 2023 +0100 +++ b/progs/matcher/re1.sc Mon Sep 25 13:14:34 2023 +0100 @@ -121,6 +121,9 @@ } } + + + // the size of a regular expressions - for testing purposes def size(r: Rexp) : Int = r match { case ZERO => 1 @@ -147,34 +150,31 @@ // derivatives might result into bigger and bigger // regular expressions...here is an example for this: -// (a+b)* o a o b o (a+b)* -val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b'))) -val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux))) + +// (a + aa)* +val BIG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) size(ders("".toList, BIG)) // 13 -size(ders("ab".toList, BIG)) // 51 -size(ders("abab".toList, BIG)) // 112 -size(ders("ababab".toList, BIG)) // 191 -size(ders("abababab".toList, BIG)) // 288 -size(ders("ababababab".toList, BIG)) // 403 -size(ders("abababababab".toList, BIG)) // 536 +size(ders("aa".toList, BIG)) // 51 +size(ders("aaaa".toList, BIG)) // 112 +size(ders("aaaaaa".toList, BIG)) // 191 +size(ders("aaaaaaaa".toList, BIG)) // 288 +size(ders("aaaaaaaaaa".toList, BIG)) // 403 +size(ders("aaaaaaaaaaaa".toList, BIG)) // 536 -size(ders(("ab" * 200).toList, BIG)) // 366808 +size(ders(("a" * 30).toList, BIG)) // 31010539 -@arg(doc = "Test (a + b)* o (a o b) o (a + b)*") @main def test3() = { - println("Test (a + b)* o (a o b) o (a + b)*") + println("Test (a + aa)*") - for (i <- 0 to 200 by 10) { - println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f") + for (i <- 0 to 30 by 5) { + println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f") } } - - @arg(doc = "All tests.") @main def all() = { test1(); test2() ; test3() }