# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1573077162 0
# Node ID 612976492d2593c2f77c462b69eff21703bc8bd2
# Parent  9efdee02c95e06ac7bba20477c75c9a346b28db8
updated

diff -r 9efdee02c95e -r 612976492d25 coursework/cw03.pdf
Binary file coursework/cw03.pdf has changed
diff -r 9efdee02c95e -r 612976492d25 coursework/cw03.tex
--- a/coursework/cw03.tex	Wed Nov 06 17:09:58 2019 +0000
+++ b/coursework/cw03.tex	Wed Nov 06 21:52:42 2019 +0000
@@ -31,11 +31,12 @@
 
 \begin{itemize}
 \item arithmetic expressions (with the operations from the
-  previous coursework, such as \pcode{+}, \pcode{*} and so on)
-\item boolean expressions (such as \pcode{<}, \code{!=} and 
-  so on)
-\item single statements (such as \pcode{skip}, assignments, \pcode{if}s,
-  \pcode{while}-loops and so on)
+  previous coursework, that is \pcode{+}, \pcode{-}, \pcode{*},
+  \pcode{/} and \pcode{\%})
+\item boolean expressions (with the operations \pcode{==}, \pcode{<}, \pcode{>},
+  \code{!=}, \pcode{&&}, \pcode{||}, \pcode{true} and \pcode{false})
+\item single statements (that is \pcode{skip}, assignments, \pcode{if}s,
+  \pcode{while}-loops, \pcode{read} and \pcode{write})
 \item compound statements separated by semicolons
 \item blocks which are enclosed in curly parentheses
 \end{itemize}
@@ -78,6 +79,7 @@
 case object True extends BExp
 case object False extends BExp
 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
+case class Lop(o: String, b1: BExp, b2: BExp) extends BExp
 \end{lstlisting}
 \caption{The datatype for parse trees in Scala.\label{trees}}
 \end{figure}
diff -r 9efdee02c95e -r 612976492d25 handouts/ho05.pdf
Binary file handouts/ho05.pdf has changed
diff -r 9efdee02c95e -r 612976492d25 handouts/ho05.tex
--- a/handouts/ho05.tex	Wed Nov 06 17:09:58 2019 +0000
+++ b/handouts/ho05.tex	Wed Nov 06 21:52:42 2019 +0000
@@ -17,7 +17,7 @@
 While regular expressions are very useful for lexing and for recognising
 many patterns in strings (like email addresses), they have their
 limitations. For example there is no regular expression that can
-recognise the language $a^nb^n$ (where you have strings with $n$ $a$'s
+recognise the language $a^nb^n$ (where you have strings starting with $n$ $a$'s
 followed by the same amount of $b$'s). Another example for which there
 exists no regular expression is the language of well-parenthesised
 expressions. In languages like Lisp, which use parentheses rather
@@ -66,7 +66,7 @@
 the ``words'' appear in. For example ambiguity issues like
 
 \begin{center}
-\tt Time flies like an arrow; fruit flies like bananas.
+\tt Time flies like an arrow. Fruit flies like bananas.
 \end{center}  
 
 \noindent
@@ -466,14 +466,14 @@
 The following grammar is in Chomsky normalform:
 
 \begin{plstx}[margin=1cm]
-  : \meta{S\/} ::= \meta{N}\cdot \meta{P}\\
-  : \meta{P\/} ::= \meta{V}\cdot \meta{N}\\
-  : \meta{N\/} ::= \meta{N}\cdot \meta{N}\\
-  : \meta{N\/} ::= \meta{A}\cdot \meta{N}\\
-  : \meta{N\/} ::= \texttt{student} | \texttt{trainer} | \texttt{team} 
-                   | \texttt{trains}\\
-  : \meta{V\/} ::= \texttt{trains} | \texttt{team}\\
-  : \meta{A\/} ::= \texttt{The} | \texttt{the}\\
+  : \meta{S} ::= \meta{N}\cdot \meta{P}\\
+  : \meta{P} ::= \meta{V}\cdot \meta{N}\\
+  : \meta{N} ::= \meta{N}\cdot \meta{N}\\
+  : \meta{N} ::= \meta{A}\cdot \meta{N}\\
+  : \meta{N} ::= \texttt{student} | \texttt{trainer} | \texttt{team} 
+                | \texttt{trains}\\
+  : \meta{V} ::= \texttt{trains} | \texttt{team}\\
+  : \meta{A} ::= \texttt{The} | \texttt{the}\\
 \end{plstx}
 
 \noindent
@@ -493,7 +493,48 @@
 is recognised by the grammar. The CYK algorithm starts with the
 following triangular data structure.
 
-TBD
+\begin{figure}[t]
+\begin{center}
+  \begin{tikzpicture}[scale=0.8,line width=0.8mm]
+  \draw (-2,0) -- (4,0);
+  \draw (-2,1) -- (4,1);
+  \draw (-2,2) -- (3,2);
+  \draw (-2,3) -- (2,3);
+  \draw (-2,4) -- (1,4);
+  \draw (-2,5) -- (0,5);
+  \draw (-2,6) -- (-1,6);
+  
+  \draw (0,0) -- (0, 5);
+  \draw (1,0) -- (1, 4);
+  \draw (2,0) -- (2, 3);
+  \draw (3,0) -- (3, 2);
+  \draw (4,0) -- (4, 1);
+  \draw (-1,0) -- (-1, 6);
+  \draw (-2,0) -- (-2, 6);
+  
+  \draw (-1.5,-0.5) node {\footnotesize{}\texttt{The}}; 
+  \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trainer}}; 
+  \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{trains}}; 
+  \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{the}}; 
+  \draw ( 2.5,-0.5) node {\footnotesize{}\texttt{student}}; 
+  \draw ( 3.5,-1.0) node {\footnotesize{}\texttt{team}};
+  
+  \draw (-1.5,0.5) node {$A$}; 
+  \draw (-0.5,0.5) node {$N$}; 
+  \draw ( 0.5,0.5) node {$N,V$}; 
+  \draw ( 1.5,0.5) node {$A$}; 
+  \draw ( 2.5,0.5) node {$N$}; 
+  \draw ( 3.5,0.5) node {$N,V$};
+
+  \draw (-2.4, 5.5) node {$1$}; 
+  \draw (-2.4, 4.5) node {$2$}; 
+  \draw (-2.4, 3.5) node {$3$}; 
+  \draw (-2.4, 2.5) node {$4$}; 
+  \draw (-2.4, 1.5) node {$5$}; 
+  \draw (-2.4, 0.5) node {$6$}; 
+  \end{tikzpicture}
+  \end{center}
+\end{figure}
 
 \end{document}