--- a/cws/build.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/cws/build.sc Sun Sep 17 19:12:57 2023 +0100
@@ -1,10 +1,10 @@
#!/usr/bin/env amm
val files = Seq("cw01.tex",
- "cw02.tex",
- "cw03.tex",
- "cw04.tex",
- "cw05.tex")
+ "cw02.tex",
+ "cw03.tex",
+ "cw04.tex",
+ "cw05.tex")
val pdf_files = files.map(s => s.stripSuffix("tex") ++ "pdf")
@@ -13,8 +13,8 @@
def make() = {
for (f <- files) {
println(s"Processing $f ...")
- os.proc("xelatex", f).call(stdout = os.Inherit, stdin = os.Inherit)
- os.proc("xelatex", f).call(stdout = os.Inherit, stdin = os.Inherit)
+ os.proc("lualatex", f).call(stdout = os.Inherit, stdin = os.Inherit)
+ os.proc("lualatex", f).call(stdout = os.Inherit, stdin = os.Inherit)
}
}
Binary file cws/cw01.pdf has changed
Binary file cws/cw02.pdf has changed
Binary file cws/cw03.pdf has changed
Binary file cws/cw04.pdf has changed
Binary file cws/cw05.pdf has changed
--- a/cws/upload Fri Sep 15 10:49:33 2023 +0100
+++ b/cws/upload Sun Sep 17 19:12:57 2023 +0100
@@ -8,5 +8,10 @@
done
-scp $fls k1192855@bastion:public_html/cfl/cws/
+scp $fls k1192855@bastion:public_html/cfl/cws
+
+#hg commit -m "updated jars"
+
+# prevent PDF from being copied
+###gs -o output.pdf -dNoOutputFonts -sDEVICE=pdfwrite main_cw01.pdf
--- a/progs/matcher/re1.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/progs/matcher/re1.sc Sun Sep 17 19:12:57 2023 +0100
@@ -1,6 +1,6 @@
// A simple matcher for basic regular expressions
//
-// Call the test cases with X = {1,2,3}
+// Call the testcases with X = {1,2,3}
//
// amm re1.sc testX
//
@@ -19,9 +19,9 @@
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
case class STAR(r: Rexp) extends Rexp // star
+
// nullable function: tests whether a regular
-// expression can recognise the empty string
-
+// expression can recognise the empty string
def nullable(r: Rexp) : Boolean = r match {
case ZERO => false
case ONE => true
@@ -54,13 +54,12 @@
nullable(ders(s.toList, r))
+// some examples from the homework
val r = SEQ(CHAR('b'), CHAR('c'))
matcher(r, "ac")
-// some examples from the homework
-
-val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
+val r1 = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
der('a', r)
der('b', r)
der('c', r)
@@ -71,6 +70,9 @@
der('z', der('y', der('x', r2)))
+// Test Cases
+//============
+
// the optional regular expression (one or zero times)
def OPT(r: Rexp) = ALT(r, ONE) // r + 1
@@ -81,10 +83,6 @@
case n => SEQ(r, NTIMES(r, n - 1))
}
-
-// Test Cases
-//============
-
// the evil regular expression (a?){n} a{n}
def EVIL1(n: Int) =
SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
--- a/progs/matcher/re2.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/progs/matcher/re2.sc Sun Sep 17 19:12:57 2023 +0100
@@ -1,6 +1,8 @@
-// A Version with an explicit n-times regular expression;
+// A Version of the matcher with an explicit
+// n-times regular expression
+//
// this keeps the size of the regular expression in the
-// EVIL1 test-case quite small
+// EVIL1 testcase small
//
// call the test cases with X = {1,2}
//
@@ -31,7 +33,6 @@
case NTIMES(r, n) => if (n == 0) true else nullable(r)
}
-
def der(c: Char, r: Rexp) : Rexp = r match {
case ZERO => ZERO
case ONE => ZERO
@@ -54,13 +55,13 @@
nullable(ders(s.toList, r))
+// Test Cases
+
// 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
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
@@ -90,7 +91,7 @@
def test2() = {
println("Test (a*)* b")
- for (i <- 0 to 30 by 2) {
+ for (i <- 0 to 22 by 2) {
println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f")
}
}
--- a/progs/matcher/re3.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/progs/matcher/re3.sc Sun Sep 17 19:12:57 2023 +0100
@@ -1,4 +1,6 @@
-// A version with simplification of derivatives;
+// A version of the matcher with simplification
+// of derivatives
+//
// this keeps the regular expressions small, which
// is good for the run-time
//
@@ -48,6 +50,7 @@
if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
}
+// simplification
def simp(r: Rexp) : Rexp = r match {
case ALT(r1, r2) => (simp(r1), simp(r2)) match {
case (ZERO, r2s) => r2s
@@ -64,26 +67,23 @@
case r => r
}
-
-
// 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)))
}
-
// the main matcher function
def matcher(r: Rexp, s: String) : Boolean =
nullable(ders(s.toList, r))
+// Test Cases
+//============
+
// one or zero
def OPT(r: Rexp) = ALT(r, ONE)
-
-// Test Cases
-
// 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'))
--- a/progs/parser-combinators/comb1.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/progs/parser-combinators/comb1.sc Sun Sep 17 19:12:57 2023 +0100
@@ -89,12 +89,12 @@
extension [I, T](p: Parser[I, T])(using I => Seq[_]) {
def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)
def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
- def mapp[S](f: => T => S) = new MapParser[I, T, S](p, f)
+ def map[S](f: => T => S) = new MapParser[I, T, S](p, f)
}
def toU(s: String) = s.map(_.toUpper)
-(p"ELSE").mapp(toU(_)).parse("ELSEifthen")
+(p"ELSE").map(toU(_)).parse("ELSEifthen")
// these implicits allow us to use an infix notation for
// sequences and alternatives; we also can write the usual
@@ -109,8 +109,8 @@
// A parser for palindromes (just returns them as string)
lazy val Pal : Parser[String, String] = {
- (p"a" ~ Pal ~ p"a").mapp{ case ((x, y), z) => s"$x$y$z" } ||
- (p"b" ~ Pal ~ p"b").mapp{ case ((x, y), z) => s"$x$y$z" } ||
+ (p"a" ~ Pal ~ p"a").map{ case ((x, y), z) => s"$x$y$z" } ||
+ (p"b" ~ Pal ~ p"b").map{ case ((x, y), z) => s"$x$y$z" } ||
p"a" || p"b" || p""
}
@@ -126,7 +126,7 @@
//
// (transforms '(' -> '{' , ')' -> '}' )
lazy val P : Parser[String, String] = {
- (p"(" ~ P ~ p")" ~ P).mapp{ case (((_, x), _), y) => "{" + x + "}" + y } ||
+ (p"(" ~ P ~ p")" ~ P).map{ case (((_, x), _), y) => "{" + x + "}" + y } ||
p""
}
@@ -224,32 +224,32 @@
// a problem with the arithmetic expression parser: it
// gets very slow with deeply nested parentheses
-println("Runtime problem")
+println("A runtime problem")
println(E.parse("1"))
println(E.parse("(1)"))
println(E.parse("((1))"))
println(E.parse("(((1)))"))
println(E.parse("((((1))))"))
-//println(E.parse("((((((1))))))"))
-//println(E.parse("(((((((1)))))))"))
+println(E.parse("((((((1))))))"))
+println(E.parse("(((((((1)))))))"))
//println(E.parse("((((((((1))))))))"))
-// faster because of merge
+// faster because of merge in the +/- case
lazy val E2: Parser[String, Int] = {
- (T2 ~ (p"+" || p"-") ~ E2).mapp[Int]{ case ((x, y), z) => if (y == "+") x + z else x - z} || T2 }
+ (T2 ~ (p"+" || p"-") ~ E2).map[Int]{ case ((x, y), z) => if (y == "+") x + z else x - z} || T2 }
lazy val T2: Parser[String, Int] = {
- (F2 ~ p"*" ~ T2).mapp[Int]{ case ((x, _), z) => x * z } || F2 }
+ (F2 ~ p"*" ~ T2).map[Int]{ case ((x, _), z) => x * z } || F2 }
lazy val F2: Parser[String, Int] = {
- (p"(" ~ E2 ~ p")").mapp[Int]{ case ((_, y), _) => y } || NumParserInt }
+ (p"(" ~ E2 ~ p")").map[Int]{ case ((_, y), _) => y } || NumParserInt }
-println("Runtime problem")
+println("mitigated by merging clauses")
println(E2.parse("1"))
println(E2.parse("(1)"))
println(E2.parse("((1))"))
println(E2.parse("(((1)))"))
println(E2.parse("((((1))))"))
-//println(E2.parse("((((((1))))))"))
-//println(E2.parse("(((((((1)))))))"))
-//println(E2.parse("((((((((1))))))))"))
\ No newline at end of file
+println(E2.parse("((((((1))))))"))
+println(E2.parse("(((((((1)))))))"))
+println(E2.parse("((((((((1))))))))"))
\ No newline at end of file
--- a/progs/parser-combinators/comb2.sc Fri Sep 15 10:49:33 2023 +0100
+++ b/progs/parser-combinators/comb2.sc Sun Sep 17 19:12:57 2023 +0100
@@ -43,7 +43,7 @@
}
// map parser
-class MapParser[I, T, S](p: => Parser[I, T],
+class maparser[I, T, S](p: => Parser[I, T],
f: T => S)(using I => Seq[_]) extends Parser[I, S] {
def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)
}
@@ -93,7 +93,7 @@
extension [I, T](p: Parser[I, T])(using I => Seq[_]) {
def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)
def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
- def mapp[S](f: => T => S) = new MapParser[I, T, S](p, f)
+ def map[S](f: => T => S) = new maparser[I, T, S](p, f)
}
@@ -125,47 +125,47 @@
// arithmetic expressions
lazy val AExp: Parser[String, AExp] =
- (Te ~ p"+" ~ AExp).mapp[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } ||
- (Te ~ p"-" ~ AExp).mapp[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te
+ (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } ||
+ (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te
lazy val Te: Parser[String, AExp] =
- (Fa ~ p"*" ~ Te).mapp[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } ||
- (Fa ~ p"/" ~ Te).mapp[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa
+ (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } ||
+ (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa
lazy val Fa: Parser[String, AExp] =
- (p"(" ~ AExp ~ p")").mapp{ case _ ~ y ~ _ => y } ||
- IdParser.mapp(Var) ||
- NumParser.mapp(Num)
+ (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } ||
+ IdParser.map(Var) ||
+ NumParser.map(Num)
// boolean expressions with some simple nesting
lazy val BExp: Parser[String, BExp] =
- (AExp ~ p"==" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } ||
- (AExp ~ p"!=" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } ||
- (AExp ~ p"<" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } ||
- (AExp ~ p">" ~ AExp).mapp[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } ||
- (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).mapp[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } ||
- (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).mapp[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } ||
- (p"true".mapp[BExp]{ _ => True }) ||
- (p"false".mapp[BExp]{ _ => False }) ||
- (p"(" ~ BExp ~ p")").mapp[BExp]{ case _ ~ x ~ _ => x }
+ (AExp ~ p"==" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } ||
+ (AExp ~ p"!=" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } ||
+ (AExp ~ p"<" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } ||
+ (AExp ~ p">" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } ||
+ (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } ||
+ (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } ||
+ (p"true".map[BExp]{ _ => True }) ||
+ (p"false".map[BExp]{ _ => False }) ||
+ (p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ x ~ _ => x }
// a single statement
lazy val Stmt: Parser[String, Stmt] =
- ((p"skip".mapp[Stmt]{_ => Skip }) ||
- (IdParser ~ p":=" ~ AExp).mapp[Stmt]{ case x ~ _ ~ z => Assign(x, z) } ||
- (p"write(" ~ IdParser ~ p")").mapp[Stmt]{ case _ ~ y ~ _ => Write(y) } ||
+ ((p"skip".map[Stmt]{_ => Skip }) ||
+ (IdParser ~ p":=" ~ AExp).map[Stmt]{ case x ~ _ ~ z => Assign(x, z) } ||
+ (p"write(" ~ IdParser ~ p")").map[Stmt]{ case _ ~ y ~ _ => Write(y) } ||
(p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block)
- .mapp[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } ||
- (p"while" ~ BExp ~ p"do" ~ Block).mapp[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) })
+ .map[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } ||
+ (p"while" ~ BExp ~ p"do" ~ Block).map[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) })
// statements
lazy val Stmts: Parser[String, Block] =
- (Stmt ~ p";" ~ Stmts).mapp[Block]{ case x ~ _ ~ z => x :: z } ||
- (Stmt.mapp[Block]{ s => List(s) })
+ (Stmt ~ p";" ~ Stmts).map[Block]{ case x ~ _ ~ z => x :: z } ||
+ (Stmt.map[Block]{ s => List(s) })
// blocks (enclosed in curly braces)
lazy val Block: Parser[String, Block] =
- ((p"{" ~ Stmts ~ p"}").mapp{ case _ ~ y ~ _ => y } ||
- (Stmt.mapp(s => List(s))))
+ ((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } ||
+ (Stmt.map(s => List(s))))
// Examples