--- a/data.sty Mon Feb 22 22:09:31 2016 +0000
+++ b/data.sty Tue Mar 22 17:09:24 2016 +0000
@@ -207,7 +207,6 @@
\end{filecontents}
\begin{filecontents}{interpreted.data}
-%1 0.00503
200 1.005863
400 7.8296765
500 15.43106
@@ -219,7 +218,7 @@
\end{filecontents}
\begin{filecontents}{interpreted2.data}
-%1 0.00503
+0 0
200 1.005863
400 7.8296765
600 27.2321885
@@ -230,6 +229,7 @@
\end{filecontents}
\begin{filecontents}{compiled2.data}
+0 0
200 0.222058
400 0.215204
600 0.202031
--- a/handouts/ho01.tex Mon Feb 22 22:09:31 2016 +0000
+++ b/handouts/ho01.tex Tue Mar 22 17:09:24 2016 +0000
@@ -5,6 +5,9 @@
\usepackage{../data}
%%http://regexcrossword.com/challenges/cities/puzzles/1
+%%https://jex.im/regulex/
+%%https://www.reddit.com/r/ProgrammingLanguages/comments/42dlem/mona_compiler_development_part_2_parsing/
+%%https://www.reddit.com/r/ProgrammingLanguages/comments/43wlkq/formal_grammar_for_csh_tsch_sh_or_bash/
\begin{document}
\fnote{\copyright{} Christian Urban, 2014, 2015}
Binary file handouts/ho02.pdf has changed
Binary file handouts/notation.pdf has changed
--- a/handouts/notation.tex Mon Feb 22 22:09:31 2016 +0000
+++ b/handouts/notation.tex Tue Mar 22 17:09:24 2016 +0000
@@ -8,8 +8,8 @@
\section*{A Crash-Course on Notation}
-There are innumerable books available about automata and
-formal languages. Unfortunately, they often use their own
+There are innumerable books available about compiler, automata
+and formal languages. Unfortunately, they often use their own
notational conventions and their own symbols. This handout is
meant to clarify some of the notation I will use.
@@ -190,7 +190,7 @@
\noindent but using the big union notation is more concise.
An important notion in this module are \defn{languages}, which
-are sets of strings. The main goal for us will be how to
+are sets of strings. One of the main goals for us will be how to
(formally) specify languages and to find out whether a string
is in a language or not.\footnote{You might wish to ponder
whether this is in general a hard or easy problem, where
Binary file handouts/scala-ho.pdf has changed
--- a/handouts/scala-ho.tex Mon Feb 22 22:09:31 2016 +0000
+++ b/handouts/scala-ho.tex Tue Mar 22 17:09:24 2016 +0000
@@ -54,9 +54,8 @@
\begin{lstlisting}[language={},numbers=none,basicstyle=\ttfamily\small]
$ scala
-Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM).
-Type in expressions to have them evaluated.
-Type :help for more information.
+Welcome to Scala version 2.11.8 (Java HotSpot(TM) 64-Bit Server VM).
+Type in expressions for evaluation. Or try :help.
scala>
\end{lstlisting}
@@ -133,12 +132,12 @@
\begin{center}
\begin{tabular}{r@{\hspace{2mm}}r@{\hspace{2mm}}l@{\hspace{13mm}}l}
- $r$ & $::=$ & $\varnothing$ & null\\
- & $\mid$ & $\epsilon$ & empty string\\
- & $\mid$ & $c$ & single character\\
- & $\mid$ & $r_1 \cdot r_2$ & sequence\\
- & $\mid$ & $r_1 + r_2$ & alternative / choice\\
- & $\mid$ & $r^*$ & star (zero or more)\\
+ $r$ & $::=$ & $\ZERO$ & null\\
+ & $\mid$ & $\ONE$ & empty string\\
+ & $\mid$ & $c$ & single character\\
+ & $\mid$ & $r_1 \cdot r_2$ & sequence\\
+ & $\mid$ & $r_1 + r_2$ & alternative / choice\\
+ & $\mid$ & $r^\star$ & star (zero or more)\\
\end{tabular}
\end{center}
@@ -155,19 +154,19 @@
actually very simple: It first requires an \emph{abstract
class}, say, \code{Rexp}. This will act as the type for
regular expressions. Second, it requires a case for each
-clause in the grammar. The cases for $\varnothing$ and
-$\epsilon$ do not have any arguments, while in all the other
-cases we do have arguments. For example the character regular
-expression needs to take as an argument the character it is
-supposed to recognise. In Scala, the cases without arguments
-are called \emph{case objects}, whereas the ones with
-arguments are \emph{case classes}. The corresponding Scala
-code is as follows:
+clause in the grammar. The cases for $\ZERO$ and $\ONE$ do not
+have any arguments, while in all the other cases we do have
+arguments. For example the character regular expression needs
+to take as an argument the character it is supposed to
+recognise. In Scala, the cases without arguments are called
+\emph{case objects}, whereas the ones with arguments are
+\emph{case classes}. The corresponding Scala code is as
+follows:
\begin{lstlisting}[numbers=none]
abstract class Rexp
-case object NULL extends Rexp
-case object EMPTY extends Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
case class CHAR (c: Char) extends Rexp
case class SEQ (r1: Rexp, r2: Rexp) extends Rexp
case class ALT (r1: Rexp, r2: Rexp) extends Rexp
@@ -202,20 +201,19 @@
omit such ``tricks'' here.
Note that Scala in its response says the variable \code{r} is
-of type \lstinline[emph={ALT}]!ALT!, not \code{Rexp}. This
-might be a bit unexpected, but can be explained as follows:
-Scala always tries to find the most general type that is
-needed for a variable or expression, but does not
-``over-generalise''. In our definition the type \code{Rexp} is
-more general than \lstinline[emph={ALT}]!ALT!, since it is the
-abstract class. But in this case there is no need to give
-\code{r} the more general type of \code{Rexp}. This is
-different if you want to form a list of regular expressions,
-for example
+of type \code{ALT}, not \code{Rexp}. This might be a bit
+unexpected, but can be explained as follows: Scala always
+tries to find the most general type that is needed for a
+variable or expression, but does not ``over-generalise''. In
+our definition the type \code{Rexp} is more general than
+\code{Rexp}, since it is the abstract class. But in this case
+there is no need to give \code{r} the more general type of
+\code{Rexp}. This is different if you want
+to form a list of regular expressions, for example
\begin{lstlisting}[numbers=none]
-scala> val ls = List(ALT(CHAR('a'), CHAR('b')), NULL)
-ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), NULL)
+scala> val ls = List(ALT(CHAR('a'), CHAR('b')), ZERO)
+ls: List[Rexp] = List(ALT(CHAR(a),CHAR(b)), ZERO)
\end{lstlisting}
\noindent In this case, Scala needs to assign a common type to
@@ -301,8 +299,8 @@
\begin{center}
\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
-$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+$rev(\ZERO)$ & $\dn$ & $\ZERO$\\
+$rev(\ONE)$ & $\dn$ & $\ONE$\\
$rev(c)$ & $\dn$ & $c$\\
$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
--- a/slides/compiled.data Mon Feb 22 22:09:31 2016 +0000
+++ b/slides/compiled.data Tue Mar 22 17:09:24 2016 +0000
@@ -1,6 +1,6 @@
%% LaTeX2e file `compiled.data'
%% generated by the `filecontents' environment
-%% from source `slides01' on 2013/12/01.
+%% from source `annonce' on 2016/02/23.
%%
%1 0.234146
%5000 0.227539
--- a/slides/compiled2.data Mon Feb 22 22:09:31 2016 +0000
+++ b/slides/compiled2.data Tue Mar 22 17:09:24 2016 +0000
@@ -1,7 +1,8 @@
%% LaTeX2e file `compiled2.data'
%% generated by the `filecontents' environment
-%% from source `slides01' on 2013/12/01.
+%% from source `annonce' on 2016/02/23.
%%
+0 0
200 0.222058
400 0.215204
600 0.202031
--- a/slides/interpreted.data Mon Feb 22 22:09:31 2016 +0000
+++ b/slides/interpreted.data Tue Mar 22 17:09:24 2016 +0000
@@ -1,8 +1,7 @@
%% LaTeX2e file `interpreted.data'
%% generated by the `filecontents' environment
-%% from source `slides01' on 2013/12/01.
+%% from source `annonce' on 2016/02/23.
%%
-%1 0.00503
200 1.005863
400 7.8296765
500 15.43106
--- a/slides/interpreted2.data Mon Feb 22 22:09:31 2016 +0000
+++ b/slides/interpreted2.data Tue Mar 22 17:09:24 2016 +0000
@@ -1,8 +1,8 @@
%% LaTeX2e file `interpreted2.data'
%% generated by the `filecontents' environment
-%% from source `slides01' on 2013/12/01.
+%% from source `annonce' on 2016/02/23.
%%
-%1 0.00503
+0 0
200 1.005863
400 7.8296765
600 27.2321885
--- a/slides/slides02.tex Mon Feb 22 22:09:31 2016 +0000
+++ b/slides/slides02.tex Tue Mar 22 17:09:24 2016 +0000
@@ -12,7 +12,7 @@
numbers=none,
xleftmargin=0mm}
-\pgfplotsset{compat=1.11}
+\pgfplotsset{compat=1.12}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
Binary file slides/slides08.pdf has changed
--- a/style.sty Mon Feb 22 22:09:31 2016 +0000
+++ b/style.sty Tue Mar 22 17:09:24 2016 +0000
@@ -9,6 +9,11 @@
\definecolor{darkblue}{rgb}{0,0,0.6}
\usepackage[colorlinks=true,urlcolor=darkblue,linkcolor=darkblue]{hyperref}
+%%% fo regular expressions
+\newcommand{\ZERO}{\mbox{\bf 0}}
+\newcommand{\ONE}{\mbox{\bf 1}}
+
+
%%% for trees
%% http://anorien.csc.warwick.ac.uk/mirrors/CTAN/graphics/pgf/contrib/forest/forest.pdf