# HG changeset patch # User Christian Urban # Date 1543448737 0 # Node ID 7a12053567d4497c04ebba4a5d5af0d9b19331d5 # Parent 060f33b5661d9f45b4bc923105dc2f9781e439ac updated diff -r 060f33b5661d -r 7a12053567d4 progs/catastrophic9.java --- /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"); + } + } + } +} diff -r 060f33b5661d -r 7a12053567d4 progs/compile_arr.scala --- 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 = diff -r 060f33b5661d -r 7a12053567d4 progs/fib.j --- 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 diff -r 060f33b5661d -r 7a12053567d4 slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 060f33b5661d -r 7a12053567d4 slides/slides09.tex --- 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: