# HG changeset patch # User Christian Urban # Date 1611881779 0 # Node ID 175a950470a96cd19f958cdd73e2e91ae85404b8 # Parent 4113d4d8cf629409469a214000c0827e1402ceda updated diff -r 4113d4d8cf62 -r 175a950470a9 cws/main_cw03.tex --- a/cws/main_cw03.tex Mon Jan 25 00:21:00 2021 +0000 +++ b/cws/main_cw03.tex Fri Jan 29 00:56:19 2021 +0000 @@ -406,7 +406,7 @@ \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested 50 or more times?\\ - \mbox{}\hfill[2 Mark] + \mbox{}\hfill[2 Marks] \end{itemize} \subsection*{Background} diff -r 4113d4d8cf62 -r 175a950470a9 main_marking2/danube_test.sh --- a/main_marking2/danube_test.sh Mon Jan 25 00:21:00 2021 +0000 +++ b/main_marking2/danube_test.sh Fri Jan 29 00:56:19 2021 +0000 @@ -19,12 +19,6 @@ # marks for core CW7 marks=$(( 0.0 )) -echo -e "" >> $out -echo -e "Below is the feedback for your submission danube.scala" >> $out -echo -e "" >> $out - - - # compilation tests @@ -49,6 +43,13 @@ } +echo -e "" >> $out +echo -e "Below is the feedback for your submission danube.scala" >> $out +echo -e "" >> $out + + + + ### compilation test echo -e "danube.scala runs?" | tee -a $out @@ -66,8 +67,8 @@ # var, .par return, ListBuffer test # -if [ $tsts -eq 0 ] - then +if [ $tsts -eq 0 ] +then echo -e "danube.scala does not contain VARS, RETURNS etc?" | tee -a $out if (scala_vars danube.scala) diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/mk --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/mk Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,33 @@ +#!/bin/sh +###set -e + +trap "exit" INT + +files=${1:-*/main3} + +for sd in $files; do + cd $sd + echo $sd + touch . + cp ../../../../../main_marking3/re_test.sh . + cp ../../../../../main_marking3/re_test1.scala . + cp ../../../../../main_marking3/re_test2.scala . + cp ../../../../../main_marking3/re_test3.scala . + cp ../../../../../main_marking3/re_test4.scala . + cp ../../../../../main_marking3/re_test5.scala . + cp ../../../../../main_marking3/re_test6.scala . + cp ../../../../../main_marking3/re_test7.scala . + ./re_test.sh output + rm re_test.sh + rm re_test1.scala + rm re_test2.scala + rm re_test3.scala + rm re_test4.scala + rm re_test5.scala + rm re_test6.scala + rm re_test7.scala + cd .. + cd .. +done + + diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,176 @@ +// Core Part about Regular Expression Matching +//============================================= + +object CW8c { + +// Regular Expressions +abstract class Rexp +case object ZERO extends Rexp +case object ONE extends Rexp +case class CHAR(c: Char) 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 + +// some convenience for typing in regular expressions + +import scala.language.implicitConversions +import scala.language.reflectiveCalls + + +def charlist2rexp(s: List[Char]): Rexp = s match { + case Nil => ONE + case c::Nil => CHAR(c) + case c::s => SEQ(CHAR(c), charlist2rexp(s)) +} +implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList) + +implicit def RexpOps (r: Rexp) = new { + def | (s: Rexp) = ALT(r, s) + def % = STAR(r) + def ~ (s: Rexp) = SEQ(r, s) +} + +implicit def stringOps (s: String) = new { + def | (r: Rexp) = ALT(s, r) + def | (r: String) = ALT(s, r) + def % = STAR(s) + def ~ (r: Rexp) = SEQ(s, r) + def ~ (r: String) = SEQ(s, r) +} + +// (1) Complete the function nullable according to +// the definition given in the coursework; this +// function checks whether a regular expression +// can match the empty string and Returns a boolean +// accordingly. + +def nullable (r: Rexp) : Boolean = r match { + case ZERO => false + case ONE => true + case CHAR(_) => false + case ALT(r1, r2) => nullable(r1) || nullable(r2) + case SEQ(r1, r2) => nullable(r1) && nullable(r2) + case STAR(_) => true +} + +// (2) Complete the function der according to +// the definition given in the coursework; this +// function calculates 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 + case CHAR(d) => if (c == d) ONE else ZERO + 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)) + else SEQ(der(c, r1), r2) + case STAR(r1) => SEQ(der(c, r1), STAR(r1)) +} + +// (3) Complete the simp function according to +// the specification given in the coursework; this +// function simplifies a regular expression from +// the inside out, like you would simplify arithmetic +// expressions; however it does not simplify inside +// STAR-regular expressions. + +def simp(r: Rexp) : Rexp = r match { + 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 SEQ(r1, r2) => (simp(r1), simp(r2)) match { + case (ZERO, _) => ZERO + case (_, ZERO) => ZERO + case (ONE, r2s) => r2s + case (r1s, ONE) => r1s + case (r1s, r2s) => SEQ(r1s, r2s) + } + case r => r +} + + +// (4) Complete the two functions below; the first +// calculates the derivative w.r.t. a string; the second +// is the regular expression matcher taking a regular +// expression and a string and checks whether the +// string matches the regular expression. + +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) = nullable(ders(s.toList, r)) + +// (5) Complete the size function for regular +// expressions according to the specification +// given in the coursework. + + +def size(r: Rexp): Int = r match { + case ZERO => 1 + case ONE => 1 + case CHAR(_) => 1 + case ALT(r1, r2) => 1 + size(r1) + size (r2) + case SEQ(r1, r2) => 1 + size(r1) + size (r2) + case STAR(r1) => 1 + size(r1) +} + + + +// some testing data + +//matcher(("a" ~ "b") ~ "c", "abc") // => true +//matcher(("a" ~ "b") ~ "c", "ab") // => false + +// the supposedly 'evil' regular expression (a*)* b +val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +//matcher(EVIL, "a" * 1000 ++ "b") // => true +//matcher(EVIL, "a" * 1000) // => false + +// size without simplifications +//size(der('a', der('a', EVIL))) // => 28 +//size(der('a', der('a', der('a', EVIL)))) // => 58 + +// size with simplification +//size(simp(der('a', der('a', EVIL)))) // => 8 +//size(simp(der('a', der('a', der('a', EVIL))))) // => 8 + +// Python needs around 30 seconds for matching 28 a's with EVIL. +// Java 9 and later increase this to an "astonishing" 40000 a's in +// around 30 seconds. +// +// Lets see how long it takes to match strings with +// 5 Million a's...it should be in the range of a +// couple of seconds. + +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) +} + +//for (i <- 0 to 5000000 by 500000) { +// println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL, "a" * i))) + " secs.") +//} + +// another "power" test case +//simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(100).next) == ONE + +// the Iterator produces the rexp +// +// SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE) +// +// where SEQ is nested 100 times. + + + +} diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test.sh --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test.sh Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,284 @@ +#!/bin/bash + +# to make the script fail safely +set -euo pipefail + +out=${1:-output} + +echo -e "" > $out + +echo -e `date` >> $out +echo -e "" >> $out +echo -e "Below is the feedback and provisional marks for your submission" >> $out +echo -e "for the Main Part 3 (Scala). Please note all marks are provisional until" >> $out +echo -e "ratified by the assessment board -- this is not an official" >> $out +echo -e "results transcript." >> $out +echo -e "" >> $out + +# marks for CW8 +marks=$(( 0 )) + +# compilation tests + +function scala_compile { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -Xprint:parser "$1" 2> c$out 1> c$out) +} + +# functional tests + +function scala_assert { + (ulimit -t 30; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) +} + +function scala_assert_thirty { + (ulimit -t 40; JAVA_OPTS="-Xmx1g" scala -i "$1" -- "$2" -e "" 2> /dev/null 1> /dev/null) +} + +# purity test + +function scala_vars { + (egrep '\bvar\b|\breturn\b|\.par\.|\.par |ListBuffer|AtomicInteger|mutable|util.control|new Array' c$out 2> /dev/null 1> /dev/null) +} + +echo -e "" >> $out +echo -e "Below is the feedback for your submission re.scala" >> $out +echo -e "" >> $out + + + +### compilation test + +echo -e "re.scala runs?" | tee -a $out + +if (scala_compile re.scala) +then + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) +else + echo -e " --> SCALA DID NOT RUN re.scala" | tee -a $out + tsts=$(( 1 )) +fi + + +# var, return, ListBuffer test +# + +if [ $tsts -eq 0 ] +then + echo -e "re.scala does not contain VARS, RETURNS etc?" | tee -a $out + + if (scala_vars re.scala) + then + echo -e " --> TEST FAILED\n" | tee -a $out + tsts=$(( 1 )) + else + echo -e " --> success" | tee -a $out + tsts=$(( 0 )) + fi +else + tsts=$(( 1 )) +fi + + + +### re1 test + +if [ $tsts -eq 0 ] +then + echo -e " nullable(ZERO) == false" | tee -a $out + echo -e " nullable(ONE) == true" | tee -a $out + echo -e " nullable(CHAR('a')) == false" | tee -a $out + echo -e " nullable(ZERO | ONE) == true" | tee -a $out + echo -e " nullable(ZERO | CHAR('a')) == false" | tee -a $out + echo -e " nullable(ONE ~ ONE) == true" | tee -a $out + echo -e " nullable(ONE ~ CHAR('a')) == false" | tee -a $out + echo -e " nullable(STAR(ZERO)) == true" | tee -a $out + + if (scala_assert "re.scala" "re_test1.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +### re2 test + +if [ $tsts -eq 0 ] +then + echo -e " der('a', ZERO | ONE) == (ZERO | ZERO)" | tee -a $out + echo -e " der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)" | tee -a $out + echo -e " der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')" | tee -a $out + echo -e " der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))" | tee -a $out + echo -e " der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))" | tee -a $out + echo -e "" | tee -a $out + echo -e " val r0 = \"a\" ~ \"b\" ~ \"c\"" | tee -a $out + echo -e " der('a', r0) == (ONE ~ \"b\") ~ \"c\"" | tee -a $out + echo -e " der('b', r0) == (ZERO ~ \"b\") ~ \"c\"" | tee -a $out + echo -e " der('c', r0) == (ZERO ~ \"b\") ~ \"c\"" | tee -a $out + echo -e "" | tee -a $out + echo -e " val r1 = (ONE ~ \"b\") ~ \"c\"" | tee -a $out + echo -e " der('a', r1) == ((ZERO ~ \"b\") | ZERO) ~ \"c\"" | tee -a $out + echo -e " der('b', r1) == ((ZERO ~ \"b\") | ONE) ~ \"c\"" | tee -a $out + echo -e " der('c', r1) == ((ZERO ~ \"b\") | ZERO) ~ \"c\"" | tee -a $out + echo -e "" | tee -a $out + echo -e " val r2 = ((ZERO ~ \"b\") | ONE) ~ \"c\"" | tee -a $out + echo -e " der('a', r2) == ((((ZERO ~ \"b\") | ZERO) ~ \"c\") | ZERO)" | tee -a $out + echo -e " der('b', r2) == ((((ZERO ~ \"b\") | ZERO) ~ \"c\") | ZERO)" | tee -a $out + echo -e " der('c', r2) == ((((ZERO ~ \"b\") | ZERO) ~ \"c\") | ONE)" | tee -a $out + + if (scala_assert "re.scala" "re_test2.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +### re3 test + +if [ $tsts -eq 0 ] +then + echo -e " simp(ZERO | ONE) == ONE" | tee -a $out + echo -e " simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)" | tee -a $out + echo -e " simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')" | tee -a $out + echo -e " simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')" | tee -a $out + echo -e " simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')" | tee -a $out + echo -e " simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO" | tee -a $out + echo -e " simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')" | tee -a $out + echo -e " simp(CHAR('a') | CHAR('a')) == CHAR('a')" | tee -a $out + echo -e " simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')" | tee -a $out + echo -e " simp(ONE | CHAR('a')) == (ONE | CHAR('a'))" | tee -a $out + echo -e " simp(ALT((CHAR('a') | ZERO) ~ ONE," | tee -a $out + echo -e " ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')" | tee -a $out + echo -e " simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO" | tee -a $out + echo -e " simp(ALT(ONE | ONE, ONE | ONE)) == ONE" | tee -a $out + echo -e " simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')" | tee -a $out + echo -e " simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE | CHAR('a'), CHAR('a') | ONE)" | tee -a $out + + if (scala_assert "re.scala" "re_test3.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +### re4 test + +if [ $tsts -eq 0 ] +then + echo -e " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" | tee -a $out + echo -e " ders((\"a\" * 5).toList,EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))" | tee -a $out + echo -e " ders(List('b'),EVIL) == ONE" | tee -a $out + echo -e " ders(List('b','b'),EVIL) == ZERO" | tee -a $out + echo -e " matcher(EVIL, \"a\" * 5 ++ \"b\") == true" | tee -a $out + echo -e " matcher(EVIL, \"a\" * 50 ++ \"b\") == true" | tee -a $out + echo -e " matcher(EVIL, \"a\" * 50) == false" | tee -a $out + echo -e " matcher(EVIL, \"b\") == true" | tee -a $out + echo -e " matcher(EVIL, \"bb\") == false" | tee -a $out + echo -e " matcher(\"abc\", \"abc\") == true" | tee -a $out + echo -e " matcher(\"abc\", \"ab\") == false" | tee -a $out + echo -e " matcher((\"ab\" | \"a\") ~ (ONE | \"bc\"), \"abc\") == true" | tee -a $out + echo -e " matcher(ONE, \"\") == true" | tee -a $out + echo -e " matcher(ZERO, \"\") == false" | tee -a $out + echo -e " matcher(ONE | CHAR('a'), \"\") == true" | tee -a $out + echo -e " matcher(ONE | CHAR('a'), \"a\") == true" | tee -a $out + + if (scala_assert "re.scala" "re_test4.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +### re5 test + + +if [ $tsts -eq 0 ] +then + echo -e " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" | tee -a $out + echo -e " size(der('a', der('a', EVIL))) == 28" | tee -a $out + echo -e " size(der('a', der('a', der('a', EVIL)))) == 58" | tee -a $out + echo -e " size(ders(\"aaaaaa\".toList, EVIL)) == 8" | tee -a $out + echo -e " size(ders((\"a\" * 50).toList, EVIL)) == 8" | tee -a $out + + if (scala_assert "re.scala" "re_test5.scala") + then + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +### re6 'power' test 1 + +sleep 5 + +if [ $tsts -eq 0 ] +then + echo -e " simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE" | tee -a $out + echo -e " ...the Iterator produces the rexp" | tee -a $out + echo -e "" | tee -a $out + echo -e " SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)" | tee -a $out + echo -e "" | tee -a $out + echo -e " where SEQ is nested 50 times." | tee -a $out + echo -e "" | tee -a $out + echo -e " simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE" | tee -a $out + echo -e " ... the Iterator produces a rexp of size 2097151" | tee -a $out + START=$(date +%s) + + if (scala_assert_thirty "re.scala" "re_test6.scala") + then + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " This test ran for $DIFF seconds" | tee -a $out + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " This test ran for $DIFF seconds" | tee -a $out + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +sleep 10 + +### re7 'power' test 2 + +if [ $tsts -eq 0 ] +then + echo -e " val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))" | tee -a $out + echo -e " matcher(EVIL, \"a\" * 1000000 ++ \"b\") == true" | tee -a $out + echo -e " matcher(EVIL, \"a\" * 1000000) == false" | tee -a $out + START=$(date +%s) + + if (scala_assert_thirty "re.scala" "re_test7.scala") + then + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " This test ran for $DIFF seconds" | tee -a $out + echo -e " --> success" | tee -a $out + marks=$(( marks + 1 )) + else + END=$(date +%s) + DIFF=$(( $END - $START )) + echo " This test ran for $DIFF seconds" | tee -a $out + echo -e " --> ONE OF THE TESTS FAILED\n" | tee -a $out + fi +fi + +sleep 10 + +## final marks +echo -e "Overall mark for Main Part 3 (Scala)" | tee -a $out +echo -e "$marks" | tee -a $out + + diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test1.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,11 @@ +import CW8c._ + +assert(nullable(ZERO) == false) +assert(nullable(ONE) == true) +assert(nullable(CHAR('a')) == false) +assert(nullable(ZERO | ONE) == true) +assert(nullable(ZERO | CHAR('a')) == false) +assert(nullable(ONE ~ ONE) == true) +assert(nullable(ONE ~ CHAR('a')) == false) +assert(nullable(STAR(ZERO)) == true) + diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test2.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test2.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,25 @@ +import CW8c._ + +assert(der('a', ZERO | ONE) == (ZERO | ZERO)) +assert(der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)) +assert(der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')) +assert(der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))) +assert(der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))) + + +val r0_urban = "a" ~ "b" ~ "c" +assert(der('a', r0_urban) == (ONE ~ "b") ~ "c") +assert(der('b', r0_urban) == (ZERO ~ "b") ~ "c") +assert(der('c', r0_urban) == (ZERO ~ "b") ~ "c") + +val r1_urban = (ONE ~ "b") ~ "c" + +assert(der('a', r1_urban) == ((ZERO ~ "b") | ZERO) ~ "c") +assert(der('b', r1_urban) == ((ZERO ~ "b") | ONE) ~ "c") +assert(der('c', r1_urban) == ((ZERO ~ "b") | ZERO) ~ "c") + +val r2_urban = ((ZERO ~ "b") | ONE) ~ "c" + +assert(der('a', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO)) +assert(der('b', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO)) +assert(der('c', r2_urban) == ((((ZERO ~ "b") | ZERO) ~ "c") | ONE)) diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test3.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test3.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,21 @@ +import CW8c._ + + +assert(simp(ZERO | ONE) == ONE) +assert(simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)) +assert(simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')) +assert(simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')) +assert(simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')) +assert(simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO) +assert(simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')) +assert(simp(CHAR('a') | CHAR('a')) == CHAR('a')) +assert(simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')) +assert(simp(ONE | CHAR('a')) == (ONE | CHAR('a'))) +assert(simp(ALT((CHAR('a') | ZERO) ~ ONE, + ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')) +assert(simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO) +assert(simp(ALT(ONE | ONE, ONE | ONE)) == ONE) +assert(simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')) +assert(simp(ALT(ONE | CHAR('a'), CHAR('a') | ONE)) == ALT(ONE | CHAR('a'), CHAR('a') | ONE)) + + diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test4.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test4.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,19 @@ +import CW8c._ + +val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +assert(ders(("a" * 5).toList, EVIL_urban) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))) +assert(ders(List('b'), EVIL_urban) == ONE) +assert(ders(List('b','b'), EVIL_urban) == ZERO) +assert(matcher(EVIL_urban, "a" * 5 ++ "b") == true) +assert(matcher(EVIL_urban, "a" * 50 ++ "b") == true) +assert(matcher(EVIL_urban, "a" * 50) == false) +assert(matcher(EVIL_urban, "b") == true) +assert(matcher(EVIL_urban, "bb") == false) +assert(matcher("abc", "abc") == true) +assert(matcher("abc", "ab") == false) +assert(matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true) +assert(matcher(ONE, "") == true) +assert(matcher(ZERO, "") == false) +assert(matcher(ONE | CHAR('a'), "") == true) +assert(matcher(ONE | CHAR('a'), "a") == true) diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test5.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test5.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,9 @@ +import CW8c._ + +val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +assert(size(der('a', der('a', EVIL_urban))) == 28) +assert(size(der('a', der('a', der('a', EVIL_urban)))) == 58) + +assert(size(ders("aaaaaa".toList, EVIL_urban)) == 8) +assert(size(ders(("a" * 50).toList, EVIL_urban)) == 8) diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test6.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test6.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,4 @@ +import CW8c._ + +assert(simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE) +assert(simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE) diff -r 4113d4d8cf62 -r 175a950470a9 main_marking3/re_test7.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/main_marking3/re_test7.scala Fri Jan 29 00:56:19 2021 +0000 @@ -0,0 +1,6 @@ +import CW8c._ + +val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +assert(matcher(EVIL_urban, "a" * 1000000) == false) +assert(matcher(EVIL_urban, "a" * 1000000 ++ "b") == true)