# HG changeset patch # User Christian Urban # Date 1564272041 -3600 # Node ID 47a299e7010f406295db8f40edc1054de0d13f7c # Parent b47e140bcccdd2b95186c7253a6a8be0d82c754a updated diff -r b47e140bcccd -r 47a299e7010f progs/dfa.scala --- a/progs/dfa.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/dfa.scala Sun Jul 28 01:00:41 2019 +0100 @@ -1,13 +1,13 @@ // DFAs in Scala using partial functions import scala.util.Try -// type abbreviation for partial functions +// a type abbreviation for partial functions type :=>[A, B] = PartialFunction[A, B] -case class DFA[A, C](start: A, // starting state - delta: (A, C) :=> A, // transition (partial fun) - fins: A => Boolean) { // final states +case class DFA[A, C](start: A, // the starting state + delta: (A, C) :=> A, // transitions (partial fun) + fins: A => Boolean) { // the final states def deltas(q: A, s: List[C]) : A = s match { case Nil => q @@ -52,7 +52,7 @@ case object S2 extends S case object Sink extends S -// transition function with a sink state +// a transition function with a sink state val sigma : (S, Char) :=> S = { case (S0, 'a') => S1 case (S1, 'a') => S2 diff -r b47e140bcccd -r 47a299e7010f progs/enfa.scala --- a/progs/enfa.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/enfa.scala Sun Jul 28 01:00:41 2019 +0100 @@ -2,7 +2,7 @@ // (needs :load dfa.scala // :load nfa.scala in REPL) -// fixpoint construction +// a fixpoint construction import scala.annotation.tailrec @tailrec def fixpT[A](f: A => A, x: A): A = { @@ -11,9 +11,9 @@ } // translates eNFAs directly into NFAs -def eNFA[A, C](starts: Set[A], // starting states - delta: (A, Option[C]) :=> Set[A], // epsilon-transitions - fins: A => Boolean) : NFA[A, C] = { // final states +def eNFA[A, C](starts: Set[A], // the starting states + delta: (A, Option[C]) :=> Set[A], // the epsilon-transitions + fins: A => Boolean) : NFA[A, C] = { // the final states // epsilon transitions def enext(q: A) : Set[A] = diff -r b47e140bcccd -r 47a299e7010f progs/nfa.scala --- a/progs/nfa.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/nfa.scala Sun Jul 28 01:00:41 2019 +0100 @@ -4,18 +4,18 @@ // needs :load dfa.scala for states -// type abbreviation for partial functions +// a type abbreviation for partial functions type :=>[A, B] = PartialFunction[A, B] -// return an empty set, when parial function is not defined +// return an empty set, when a parial function is not defined def applyOrElse[A, B](f: A :=> Set[B], x: A) : Set[B] = Try(f(x)) getOrElse Set[B]() // NFAs -case class NFA[A, C](starts: Set[A], // starting states - delta: (A, C) :=> Set[A], // transition function - fins: A => Boolean) { // final states +case class NFA[A, C](starts: Set[A], // the starting states + delta: (A, C) :=> Set[A], // the transition function + fins: A => Boolean) { // the final states // given a state and a character, what is the set of // next states? if there is none => empty set diff -r b47e140bcccd -r 47a299e7010f progs/re1.scala --- a/progs/re1.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/re1.scala Sun Jul 28 01:00:41 2019 +0100 @@ -1,8 +1,8 @@ -// Simple matcher for basic regular expressions +// A simple matcher for basic regular expressions abstract class Rexp case object ZERO extends Rexp // matches nothing -case object ONE extends Rexp // matches the empty string +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 @@ -19,9 +19,7 @@ case STAR(_) => true } - - -// derivative of a regular expression w.r.t. a character +// the derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { case ZERO => ZERO case ONE => ZERO @@ -33,18 +31,18 @@ case STAR(r1) => SEQ(der(c, r1), STAR(r1)) } -// derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der) def ders (s: List[Char], r: Rexp) : Rexp = s match { case Nil => r case c::s => ders(s, der(c, r)) } -// main matcher function +// the main matcher function def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) -//examples from the homework +// examples from the homework val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) der('a', r) @@ -57,10 +55,10 @@ der('z', der('y', der('x', r2))) -//optional regular expression (one or zero times) +// the optional regular expression (one or zero times) def OPT(r: Rexp) = ALT(r, ONE) -//n-times regular expression (explicitly expanded) +// the n-times regular expression (explicitly expanded) def NTIMES(r: Rexp, n: Int) : Rexp = n match { case 0 => ONE case 1 => r @@ -76,40 +74,31 @@ // the evil regular expression (a*)*b val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) -//for measuring time +// for measuring time def time_needed[T](i: Int, code: => T) = { val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - (end - start)/(i * 1.0e9) + "%.5f".format((end - start) / (i * 1.0e9)) } -//test: (a?{n}) (a{n}) +// test: (a?{n}) (a{n}) println("Test (a?{n}) (a{n})") -for (i <- 1 to 20) { - println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) -} -for (i <- 1 to 20) { - println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) +for (i <- 0 to 20 by 2) { + println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") } -//test: (a*)* b +// test: (a*)* b println("Test (a*)* b") -for (i <- 1 to 20) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) -} - -for (i <- 1 to 20) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) +for (i <- 0 to 20 by 2) { + println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") } - - -// size of a regular expressions - for testing purposes +// the size of a regular expressions - for testing purposes def size(r: Rexp) : Int = r match { case ZERO => 1 case ONE => 1 @@ -126,7 +115,7 @@ size(EVIL1(3)) // 17 size(EVIL1(5)) // 29 size(EVIL1(7)) // 41 - +size(EVIL1(20)) // 119 // given a regular expression and building successive // derivatives might result into bigger and bigger @@ -147,6 +136,6 @@ size(ders(("ab" * 200).toList, BIG)) // 366808 -for (i <- 1 to 21) { - println(i + " " + "%.5f".format(time_needed(2, matches(BIG, "ab" * i)))) +for (i <- 0 to 200 by 10) { + println(s"$i: ${time_needed(2, matches(BIG, "ab" * i))}") } diff -r b47e140bcccd -r 47a299e7010f progs/re2.scala --- a/progs/re2.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/re2.scala Sun Jul 28 01:00:41 2019 +0100 @@ -1,4 +1,4 @@ -// Version with an explicit n-times regular expression; +// A Version with an explicit n-times regular expression; // this keeps the size of the regular expression in the // EVIL1 test-case quite small @@ -44,14 +44,14 @@ def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) -//optional regular expression: one or zero times -//this regular expression is still defined in terms of ALT +// the optional regular expression: one or zero times +// this regular expression is still defined in terms of ALT def OPT(r: Rexp) = ALT(r, ONE) // Test Cases -//evil regular expressions +// evil regular expressions def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) @@ -59,32 +59,23 @@ val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - (end - start)/(i * 1.0e9) -} - - -//test: (a?{n}) (a{n}) -for (i <- 1 to 1201 by 100) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) -} - -for (i <- 1 to 1201 by 100) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) -} - - -//test: (a*)* b -for (i <- 1 to 21) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) -} - -for (i <- 1 to 21) { - println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) + "%.5f".format((end - start) / (i * 1.0e9)) } -// size of a regular expressions - for testing purposes +// test: (a?{n}) (a{n}) +for (i <- 0 to 1000 by 100) { + println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") +} + +// test: (a*)* b +for (i <- 1 to 21) { + println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") +} + + +// the size of a regular expressions - for testing purposes def size(r: Rexp) : Int = r match { case ZERO => 1 case ONE => 1 @@ -103,6 +94,7 @@ size(EVIL1(3)) // 7 size(EVIL1(5)) // 7 size(EVIL1(7)) // 7 +size(EVIL1(20)) // 7 size(ders("".toList, EVIL1(5))) // 7 size(ders("a".toList, EVIL1(5))) // 16 diff -r b47e140bcccd -r 47a299e7010f progs/re3.scala --- a/progs/re3.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/re3.scala Sun Jul 28 01:00:41 2019 +0100 @@ -14,7 +14,7 @@ -// nullable function: tests whether the regular +// the nullable function: tests whether the regular // expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { case ZERO => false @@ -26,7 +26,7 @@ case NTIMES(r, i) => if (i == 0) true else nullable(r) } -// derivative of a regular expression w.r.t. a character +// the derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { case ZERO => ZERO case ONE => ZERO @@ -57,35 +57,35 @@ } -// derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der) def ders(s: List[Char], r: Rexp) : Rexp = s match { case Nil => r case c::s => ders(s, simp(der(c, r))) } -// derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der) def dersp(s: List[Char], r: Rexp) : Rexp = s match { case Nil => r case c::s => dersp(s, der(c, r)) } -// main matcher function +// the main matcher function def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) -//tests +// tests val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) dersp("x".toList, q) dersp("xy".toList, q) dersp("xyz".toList, q) -//one or zero +// one or zero def OPT(r: Rexp) = ALT(r, ONE) // Test Cases -//evil regular expressions: (a?){n} a{n} and (a*)* b +// evil regular expressions: (a?){n} a{n} and (a*)* b def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) diff -r b47e140bcccd -r 47a299e7010f progs/re3a.scala --- a/progs/re3a.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/re3a.scala Sun Jul 28 01:00:41 2019 +0100 @@ -9,7 +9,7 @@ case class NTIMES(r: Rexp, n: Int) extends Rexp case class UPNTIMES(r: Rexp, n: Int) extends Rexp -// nullable function: tests whether the regular +// the nullable function: tests whether the regular // expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { case ZERO => false @@ -22,7 +22,7 @@ case UPNTIMES(r: Rexp, n: Int) => true } -// derivative of a regular expression w.r.t. a character +// the derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { case ZERO => ZERO case ONE => ZERO @@ -58,20 +58,20 @@ } -// derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der) def ders (s: List[Char], r: Rexp) : Rexp = s match { case Nil => r case c::s => ders(s, simp(der(c, r))) } -// main matcher function -def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) +// the main matcher function +def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) -//one or zero +// one or zero def OPT(r: Rexp) = ALT(r, ONE) -//evil regular expressions +// evil regular expressions def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) val EVIL3 = SEQ(STAR(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a')))), CHAR('b')) @@ -80,26 +80,18 @@ val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - (end - start)/(i * 1.0e9) + "%.5f".format((end - start) / (i * 1.0e9)) } -//test: (a?{n}) (a{n}) -for (i <- 1 to 8001 by 1000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) +// test: (a?{n}) (a{n}) +for (i <- 0 to 8000 by 1000) { + println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") } -for (i <- 1 to 8001 by 1000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) -} - -//test: (a*)* b -for (i <- 1 to 6000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) -} - -for (i <- 1 to 6000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) +// test: (a*)* b +for (i <- 0 to 6000000 by 500000) { + println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") } @@ -113,8 +105,8 @@ //test: (a|aa)* b /* -for (i <- 1 to 7001 by 500) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i ++ "c")))) +for (i <- 0 to 100 by 10) { + println(s"$i: ${time_needed(2, matches(EVIL3, "a" * i ++ "c"))}") } */ diff -r b47e140bcccd -r 47a299e7010f progs/re4.scala --- a/progs/re4.scala Thu Jul 25 14:39:37 2019 +0100 +++ b/progs/re4.scala Sun Jul 28 01:00:41 2019 +0100 @@ -1,4 +1,4 @@ -// Version which attempts to move whole strings, not +// A version which attempts to move whole strings, not // just characters, under derivatives whenever possible abstract class Rexp @@ -10,7 +10,7 @@ case class STAR(r: Rexp) extends Rexp case class NTIMES(r: Rexp, n: Int) extends Rexp -// nullable function: tests whether the regular +// the nullable function: tests whether the regular // expression can recognise the empty string def nullable (r: Rexp) : Boolean = r match { case ZERO => false @@ -22,7 +22,7 @@ case NTIMES(r, i) => if (i == 0) true else nullable(r) } -// derivative of a regular expression w.r.t. a character +// the derivative of a regular expression w.r.t. a character def der (c: Char, r: Rexp) : Rexp = r match { case ZERO => ZERO case ONE => ZERO @@ -52,7 +52,7 @@ case r => r } -//example +// an example val r = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) der('x', r) der('y', der('x', r)) @@ -60,7 +60,7 @@ simp(der('z', der('y', der('x', r)))) // *new* -// derivative w.r.t. a string (iterates der) +// the derivative w.r.t. a string (iterates der) def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match { case (Nil, r) => r case (s, ZERO) => ZERO @@ -71,11 +71,11 @@ case (c::s, r) => ders2(s, simp(der(c, r))) } -// main matcher function -def matcher(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r)) +// the main matcher function +def matches(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r)) -//one or zero +// one or zero def OPT(r: Rexp) = ALT(r, ONE) @@ -84,35 +84,29 @@ def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) - +// for measuring time def time_needed[T](i: Int, code: => T) = { val start = System.nanoTime() for (j <- 1 to i) code val end = System.nanoTime() - (end - start)/(i * 1.0e9) -} - -//test: (a?{n}) (a{n}) -for (i <- 1 to 7000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) + "%.5f".format((end - start) / (i * 1.0e9)) } -for (i <- 1 to 7000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) + +// test: (a?{n}) (a{n}) +for (i <- 0 to 7000000 by 500000) { + println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") } -//test: (a*)* b + +// test: (a*)* b for (i <- 1 to 7000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) -} - -for (i <- 1 to 7000001 by 500000) { - println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) + println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") } -// size of a regular expressions - for testing purposes +// the size of a regular expressions - for testing purposes def size(r: Rexp) : Int = r match { case ZERO => 1 case ONE => 1 @@ -140,7 +134,7 @@ // test: ("a" | "aa")* val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) -//test: ("" | "a" | "aa")* +// test: ("" | "a" | "aa")* val EVIL3 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) val t1 = ders2("a".toList, EVIL3)