# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1570184490 -3600
# Node ID 180600c04da245f41334236015f8895b060cbbf4
# Parent  2abd285c66d1ad617850ccf86601f3257064832d
updated

diff -r 2abd285c66d1 -r 180600c04da2 hws/hw03.pdf
Binary file hws/hw03.pdf has changed
diff -r 2abd285c66d1 -r 180600c04da2 hws/hw03.tex
--- a/hws/hw03.tex	Thu Oct 03 11:12:00 2019 +0100
+++ b/hws/hw03.tex	Fri Oct 04 11:21:30 2019 +0100
@@ -9,6 +9,10 @@
 \HEADER
 
 \begin{enumerate}
+\item The regular expression matchers in Java, Python and Ruby can be
+  very slow with some (basic) regular expressions. What is the main
+  reason for this inefficient computation?
+  
 \item What is a regular language? Are there alternative ways
       to define this notion? If yes, give an explanation why
       they define the same notion.
@@ -27,14 +31,14 @@
     r_1 \cdot r_2 \;|\; r^*$ 
   \end{center}
 
-\item Define the function \textit{zeroable} which takes a
-      regular expression as argument and returns a boolean.
-      The function should satisfy the following property:
-
-  \begin{center}
-    $\textit{zeroable(r)} \;\text{if and only if}\; 
-    L(r) = \{\}$
-  \end{center}
+%\item Define the function \textit{zeroable} which takes a
+%      regular expression as argument and returns a boolean.
+%      The function should satisfy the following property:
+%
+%  \begin{center}
+%    $\textit{zeroable(r)} \;\text{if and only if}\; 
+%    L(r) = \{\}$
+%  \end{center}
 
 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two
   states, say $Q_0$ and $Q_1$.  The starting state is $Q_0$ and the
diff -r 2abd285c66d1 -r 180600c04da2 hws/hw06.pdf
Binary file hws/hw06.pdf has changed
diff -r 2abd285c66d1 -r 180600c04da2 hws/hw06.tex
--- a/hws/hw06.tex	Thu Oct 03 11:12:00 2019 +0100
+++ b/hws/hw06.tex	Fri Oct 04 11:21:30 2019 +0100
@@ -69,6 +69,14 @@
 there are several values for how these regular expressions can
 recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case
 \emph{all} the values and indicate which one is the POSIX value.
+
+\item Parsing combinators consist of atomic parsers, alternative
+  parsers, sequence parsers and semantic actions.  What is the purpose
+  of (1) atomic parsers and of (2) semantic actions?
+
+
+
+
 \item \POSTSCRIPT        
 \end{enumerate}
 
diff -r 2abd285c66d1 -r 180600c04da2 hws/hw09.pdf
Binary file hws/hw09.pdf has changed
diff -r 2abd285c66d1 -r 180600c04da2 hws/hw09.tex
--- a/hws/hw09.tex	Thu Oct 03 11:12:00 2019 +0100
+++ b/hws/hw09.tex	Fri Oct 04 11:21:30 2019 +0100
@@ -33,18 +33,18 @@
   Give the arithmetic expression that produced this code.  Make sure
   you give all necessary parentheses.
 
-\item Describe what the following three JVM instructions do!
+\item Describe what the following JVM instructions do!
 
-\begin{lstlisting}[language=JVMIS,numbers=none]
+  
+\begin{lstlisting}[language=JVMIS2,numbers=none]
+ldc 3    
 iload 3
 istore 1
 ifeq label
+if_icmpge label
 \end{lstlisting}
 
 
-\item Early in the module, we saw that the regular expression matchers
-  in Java, Python and Ruby are very slow with some (basic) regular
-  expressions. What is the main reason for this ineffcient computation?
 
 \item \POSTSCRIPT  
 
diff -r 2abd285c66d1 -r 180600c04da2 langs.sty
--- a/langs.sty	Thu Oct 03 11:12:00 2019 +0100
+++ b/langs.sty	Fri Oct 04 11:21:30 2019 +0100
@@ -64,6 +64,10 @@
 }[keywords,comments,strings]
 
 
+\lstdefinelanguage{JVMIS2}{
+  morekeywords={ldc,iload,istore,ifeq,if_icmpge},
+}[keywords]
+
 
 \newcommand{\code}[1]{{\lstinline{#1}}}
 \newcommand{\pcode}[1]{\mbox{\lstset{language={},keywordstyle=\color{black}}\lstinline!#1!}}
diff -r 2abd285c66d1 -r 180600c04da2 progs/re1.scala
--- a/progs/re1.scala	Thu Oct 03 11:12:00 2019 +0100
+++ b/progs/re1.scala	Fri Oct 04 11:21:30 2019 +0100
@@ -139,3 +139,16 @@
 for (i <- 0 to 200 by 10) {
   println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f")
 }
+
+
+
+
+//////////////////////////////////////
+def concat(A: Set[String], B: Set[String]) : Set[String] =
+  for (s1 <- A; s2 <- B) yield s1 ++ s2
+  
+
+val A = Set("foo", "bar")
+val B = Set("a", "b")
+
+
diff -r 2abd285c66d1 -r 180600c04da2 progs/re3.scala
--- a/progs/re3.scala	Thu Oct 03 11:12:00 2019 +0100
+++ b/progs/re3.scala	Fri Oct 04 11:21:30 2019 +0100
@@ -1,6 +1,6 @@
 // A version with simplification of derivatives;
 // this keeps the regular expressions small, which
-// is good for run-time
+// is good for the run-time
  
 
 abstract class Rexp
@@ -65,7 +65,8 @@
 
 
 // the main matcher function
-def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
+def matcher(r: Rexp, s: String) : Boolean = 
+  nullable(ders(s.toList, r))
 
 
 // one or zero