--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic9.java Wed Nov 28 23:45:37 2018 +0000
@@ -0,0 +1,48 @@
+// A case of catastrophic backtracking in Java 9+
+//------------------------------------------------
+//
+// It is actually not too bad in comparison what Python
+// and Java 8 are to compute. But it is still pretty
+// bad, even in Java 9, considering that the the basic
+// part of the CW improves on this by a factor of 100
+// (...if implemented correctly).
+//
+// regexp: (a*)*b
+// strings: aa....aaa
+//
+// compile with: javac catastrophic9.java
+// call with: java catastrophic9
+//
+//
+
+import java.util.regex.*;
+
+public class catastrophic9 {
+ public static void main(String[] args) {
+
+ //we always run all the tests twice -> to warmup of the JVM
+ for (int runs = 0; runs < 2; runs++) {
+
+ Pattern pattern = Pattern.compile("(a*)*b");
+
+ // Run from 5 to 28 characters
+ for (int length = 0; length < 50000; length += 5000) {
+
+ // Build input of specified length
+ String input = "";
+ for (int i = 0; i < length; i++) { input += "a"; }
+
+ // Measure the average duration of two calls...
+ long start = System.nanoTime();
+ for (int i = 0; i < 2; i++) {
+ pattern.matcher(input).find();
+ }
+
+ // Print out time
+ System.out.println(length + " a's : "
+ + ((System.nanoTime() - start) / 2000000000d)
+ + " secs");
+ }
+ }
+ }
+}
--- a/progs/compile_arr.scala Tue Nov 27 07:53:57 2018 +0000
+++ b/progs/compile_arr.scala Wed Nov 28 23:45:37 2018 +0000
@@ -12,12 +12,15 @@
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
case class While(b: BExp, bl: Block) extends Stmt
case class Assign(s: String, a: AExp) extends Stmt
+case class AssignA(s: String, a1: AExp, a2: AExp) extends Stmt
case class Write(s: String) extends Stmt // writes out a variable
+case class Array(s: String, n: Int) extends Stmt
// arithmetic expressions
case class Var(s: String) extends AExp
case class Num(i: Int) extends AExp
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
+case class Ref(s: String, a1: AExp) extends AExp
// boolean expressions
case object True extends BExp
@@ -136,6 +139,24 @@
case Write(x) =>
(List("iload " + env(x) + "\n" +
"invokestatic XXX/XXX/write(I)V\n"), env)
+ case Array(s, n) => {
+ val index = if (env.isDefinedAt(s)) throw new Exception("Array already defined") else
+ env.keys.size.toString
+ (List("ldc " ++ n.toString ++ "\n",
+ "newarray int \n",
+ "astore " ++ index ++ "\n"), env + (s -> index))
+ }
+ case AssignA(s, a1, a2) => {
+ val index = if (env.isDefinedAt(s)) env(s) else
+ throw new Exception("Array not yet defined")
+ (List("aload " + index) ++
+ compile_aexp(a1, env) ++
+ compile_aexp(a2, env) ++
+ List("iastore"), env)
+
+ compile_aexp(a, env) ++
+ List("istore " + index + "\n"), env + (x -> index))
+ }
}
// compilation of a block (i.e. list of instructions)
@@ -217,6 +238,12 @@
compile_run(fib_test, "fib")
+val arr_test =
+ List(Assign("x", Num(0)),
+ Array("a", 10))
+
+compile_block(arr_test, Map())._1.mkString
+compile_run(arr_test, "arr")
val arr_test =
--- a/progs/fib.j Tue Nov 27 07:53:57 2018 +0000
+++ b/progs/fib.j Wed Nov 28 23:45:37 2018 +0000
@@ -13,44 +13,11 @@
.limit stack 2
getstatic java/lang/System/out Ljava/io/PrintStream;
iload 0
- invokevirtual java/io/PrintStream/println(I)V
+ i2c
+ invokevirtual java/io/PrintStream/print(C)V
return
.end method
-.method public static read()I
- .limit locals 10
- .limit stack 10
-
- ldc 0
- istore 1 ; this will hold our final integer
-Label1:
- getstatic java/lang/System/in Ljava/io/InputStream;
- invokevirtual java/io/InputStream/read()I
- istore 2
- iload 2
- ldc 10 ; the newline delimiter
- isub
- ifeq Label2
- iload 2
- ldc 32 ; the space delimiter
- isub
- ifeq Label2
-
- iload 2
- ldc 48 ; we have our digit in ASCII, have to subtract it from 48
- isub
- ldc 10
- iload 1
- imul
- iadd
- istore 1
- goto Label1
-Label2:
- ;when we come here we have our integer computed in local variable 1
- iload 1
- ireturn
-.end method
-
.method public static main([Ljava/lang/String;)V
.limit locals 200
.limit stack 200
Binary file slides/slides09.pdf has changed
--- a/slides/slides09.tex Tue Nov 27 07:53:57 2018 +0000
+++ b/slides/slides09.tex Wed Nov 28 23:45:37 2018 +0000
@@ -509,19 +509,23 @@
\begin{center}
\begin{tabular}{c}
- \bl{\infer{\mbox{}}{A\;\texttt{skip}\;A}}\qquad
- \bl{\infer{vars(a) \subseteq A}{A\;\;(\texttt{x\,:=\,a})\;\;\{x\}\cup A}}
+ \bl{\infer{\mbox{}}{A\triangleright\texttt{skip}\triangleright{}A}}\qquad
+ \bl{\infer{vars(a) \subseteq A}{A\triangleright
+ (\texttt{x\,:=\,a})\triangleright\{x\}\cup A}}
\medskip\\\pause
- \bl{\infer{A_1\;s_1\;A_2\quad A_2\;s_2\;A_3}{A_1\;(s_1 ; s_2)\;A_3}}
+ \bl{\infer{A_1\triangleright{}s_1\triangleright{}A_2
+ \quad A_2\triangleright{}s_2\triangleright{}A_3}
+ {A_1\triangleright{}(s_1 ; s_2)\triangleright{}A_3}}
\medskip\\\pause
- \bl{\infer{vars(b)\subseteq A\quad A\;s_1\;A_1\quad A\;s_2\;A_2}
- {A\;(\texttt{if}\;b\;\texttt{then}\;s_1\;\texttt{else}\;s_2)\;A_1\cap A_2}}
+ \bl{\infer{vars(b)\subseteq A\quad A\triangleright{}s_1\triangleright{}A_1
+ \quad A\triangleright{}s_2\triangleright{}A_2}
+ {A\triangleright(\texttt{if}\;b\;\texttt{then}\;s_1\;\texttt{else}\;s_2)\triangleright{}A_1\cap A_2}}
\medskip\\\pause
- \bl{\infer{vars(b)\subseteq A\quad A\;s\;A'}
- {A\;(\texttt{while}\;b\;\texttt{do}\;s)\;A}}\pause
+ \bl{\infer{vars(b)\subseteq A\quad A\triangleright{}s\triangleright{}A'}
+ {A\triangleright(\texttt{while}\;b\;\texttt{do}\;s)\triangleright{}A}}\pause
\end{tabular}
\end{center}
@@ -622,6 +626,25 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{frame}[c]
+\frametitle{Next Week}
+
+\begin{itemize}
+\item Revision Lecture\medskip
+\item How many strings are in $\bl{L(a^*)}$?\pause\medskip
+\item How many strings are in $\bl{L((a + b)^*)}$?\\ Are there more than
+ in $\bl{L(a^*)}$?
+\end{itemize}
+
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
\end{document}
%%% Local Variables: