# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1383307024 0
# Node ID 7cfb7a6f7c9909abb5d27763c7b2492ece954237
# Parent  47b5c91eff470b2dbb2ae7c96b675dd42d44d2ef
added slides

diff -r 47b5c91eff47 -r 7cfb7a6f7c99 handouts/ho05.tex
--- a/handouts/ho05.tex	Wed Oct 30 15:14:14 2013 +0000
+++ b/handouts/ho05.tex	Fri Nov 01 11:57:04 2013 +0000
@@ -24,7 +24,7 @@
 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
-
+  
 \lstdefinelanguage{scala}{
   morekeywords={abstract,case,catch,class,def,%
     do,else,extends,false,final,finally,%
diff -r 47b5c91eff47 -r 7cfb7a6f7c99 handouts/ho06.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/ho06.tex	Fri Nov 01 11:57:04 2013 +0000
@@ -0,0 +1,183 @@
+\documentclass{article}
+\usepackage{charter}
+\usepackage{hyperref}
+\usepackage{amssymb}
+\usepackage{amsmath}
+\usepackage[T1]{fontenc}
+\usepackage{listings}
+\usepackage{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows}
+\usetikzlibrary{automata}
+\usetikzlibrary{shapes}
+\usetikzlibrary{shadows}
+\usetikzlibrary{positioning}
+\usetikzlibrary{calc}
+\usetikzlibrary{fit}
+\usetikzlibrary{backgrounds}
+\usepackage{fontspec}
+\setmonofont{Consolas}
+
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
+
+\definecolor{javared}{rgb}{0.6,0,0} % for strings
+\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
+\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
+\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
+
+\lstdefinelanguage{scala}{
+  morekeywords={abstract,case,catch,class,def,%
+    do,else,extends,false,final,finally,%
+    for,if,implicit,import,match,mixin,%
+    new,null,object,override,package,%
+    private,protected,requires,return,sealed,%
+    super,this,throw,trait,true,try,%
+    type,val,var,while,with,yield},
+  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+  sensitive=true,
+  morecomment=[l]{//},
+  morecomment=[n]{/*}{*/},
+  morestring=[b]",
+  morestring=[b]',
+  morestring=[b]"""
+}
+
+\lstdefinelanguage{while}{
+  morekeywords={while, if, then. else, read, write},
+  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
+  sensitive=true,
+  morecomment=[l]{//},
+  morecomment=[n]{/*}{*/},
+  morestring=[b]",
+  morestring=[b]',
+  morestring=[b]"""
+}
+
+
+\lstset{language=Scala,
+	basicstyle=\ttfamily,
+	keywordstyle=\color{javapurple}\bfseries,
+	stringstyle=\color{javagreen},
+	commentstyle=\color{javagreen},
+	morecomment=[s][\color{javadocblue}]{/**}{*/},
+	numbers=left,
+	numberstyle=\tiny\color{black},
+	stepnumber=1,
+	numbersep=10pt,
+	tabsize=2,
+	showspaces=false,
+	showstringspaces=false}
+	
+\newcommand\grid[1]{%
+\begin{tikzpicture}[baseline=(char.base)]
+  \path[use as bounding box]
+    (0,0) rectangle (1em,1em);
+  \draw[red!50, fill=red!20]
+    (0,0) rectangle (1em,1em);
+  \node[inner sep=1pt,anchor=base west]
+    (char) at (0em,\gridraiseamount) {#1};
+\end{tikzpicture}}
+\newcommand\gridraiseamount{0.12em}
+
+\makeatletter
+\newcommand\Grid[1]{%
+  \@tfor\z:=#1\do{\grid{\z}}}
+\makeatother	
+
+\newcommand\Vspace[1][.3em]{%
+  \mbox{\kern.06em\vrle height.3ex}%
+  \vbox{\hrule width#1}%
+  \hbox{\vrule height.3ex}}
+
+\def\VS{\Vspace[0.6em]}
+	
+\begin{document}
+
+\section*{Handout 6}
+
+While regular expressions are very useful for lexing and for recognising
+many patterns (like email addresses), they have their limitations. For
+example there is no regular expression that can recognise the language 
+$a^nb^n$. Another example is the language of well-parenthesised 
+expressions.  In languages like Lisp, which use parentheses rather
+extensively, it might be of interest whether the following two expressions
+are well-parenthesised (the left one is, the right one is not):
+
+\begin{center}
+$(((()()))())$  \hspace{10mm} $(((()()))()))$
+\end{center}
+
+In order to solve such recognition problems, we need more powerful 
+techniques than regular expressions. We will in particular look at \emph{context-free
+languages}. They include the regular languages as the picture below shows:
+
+
+\begin{center}
+\begin{tikzpicture}
+[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
+
+\draw (0,0) node [rect, text depth=30mm, text width=46mm] {all languages};
+\draw (0,-0.4) node [rect, text depth=20mm, text width=44mm] {decidable languages};
+\draw (0,-0.65) node [rect, text depth=13mm] {context sensitive languages};
+\draw (0,-0.84) node [rect, text depth=7mm, text width=35mm] {context-free languages};
+\draw (0,-1.05) node [rect] {regular languages};
+\end{tikzpicture}
+\end{center}
+
+\noindent
+Context-free languages play an important role in `day-to-day' text processing and in
+programming languages. Context-free languages are usually specified by grammars.
+For example a grammar for well-parenthesised  expressions is
+
+\begin{center}
+$P \;\;\rightarrow\;\; ( \cdot  P \cdot ) \cdot P \;|\; \epsilon$
+\end{center}
+ 
+\noindent
+In general grammars consist of finitely many rules built up from terminal symbols (usually lower-case letters)
+and non-terminal symbols (upper-case letters).  Rules have the shape
+
+\begin{center}
+$NT \;\;\rightarrow\;\; \textit{rhs}$
+\end{center}
+ 
+\noindent
+where on the left-hand side is a single non-terminal and on the right a string consisting
+of both terminals and non-terminals including the $\epsilon$-symbol for indicating the
+empty string. We use the convention  to separate components on
+the right hand-side by using the $\cdot$ symbol, as in the grammar for well-parenthesised  expressions.
+We also use the convention to use $|$ as a shorthand notation for several rules. For example
+
+\begin{center}
+$NT \;\;\rightarrow\;\; \textit{rhs}_1 \;|\; \textit{rhs}_2$
+\end{center}
+
+\noindent
+means that the non-terminal $NT$ can be replaced by either $\textit{rhs}_1$ or $\textit{rhs}_2$.
+If there are more than one non-terminal on the left-hand side of the rules, then we need to indicate
+what is the \emph{starting} symbol of the grammar. For example the grammar for arithmetic expressions
+can be given as follows
+
+\begin{center}
+\begin{tabular}{lcl}
+$E$ & $\rightarrow$ &  $N$ \\
+$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\
+$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\
+$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\
+$E$ & $\rightarrow$ &  $( \cdot E \cdot )$\\
+$N$ & $\rightarrow$ & $\epsilon \;|\; 0 \cdot N \;|\; 1 \cdot N \;|\: \ldots \;|\; 9 \cdot N$ 
+\end{tabular}
+\end{center}
+
+\noindent
+where $E$ is the starting symbol. A \emph{derivation} for a grammar
+starts with the staring symbol of the grammar and in each step replaces one
+non-terminal by a right-hand side of a rule.
+
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex  
+%%% TeX-master: t
+%%% End: 
diff -r 47b5c91eff47 -r 7cfb7a6f7c99 progs/comb2.scala
--- a/progs/comb2.scala	Wed Oct 30 15:14:14 2013 +0000
+++ b/progs/comb2.scala	Fri Nov 01 11:57:04 2013 +0000
@@ -111,14 +111,14 @@
 }
 
 lazy val AExp: Parser[String, AExp] = 
-  ((Te ~ "+" ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||
-   (Te ~ "-" ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || Te)  
+  ((Te ~ "+" ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z):AExp } ||
+   (Te ~ "-" ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z):AExp } || Te)  
 lazy val Te: Parser[String, AExp] = 
-  (Fa ~ "*" ~ Te) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || Fa
+  (Fa ~ "*" ~ Te) ==> { case ((x, y), z) => Aop("*", x, z):AExp } || Fa
 lazy val Fa: Parser[String, AExp] = 
   (("(" ~ AExp ~ ")") ==> { case ((x, y), z) => y } || 
-   IdParser ==> ((s:String) => Var(s) :AExp) || 
-   NumParser ==> ((i:Int) => Num(i) :AExp))
+   IdParser ==> Var || 
+   NumParser ==> Num)
 
 // boolean expressions
 lazy val BExp: Parser[String, BExp] = 
diff -r 47b5c91eff47 -r 7cfb7a6f7c99 slides/slides07.pdf
Binary file slides/slides07.pdf has changed
diff -r 47b5c91eff47 -r 7cfb7a6f7c99 slides/slides07.tex
--- a/slides/slides07.tex	Wed Oct 30 15:14:14 2013 +0000
+++ b/slides/slides07.tex	Fri Nov 01 11:57:04 2013 +0000
@@ -1,7 +1,7 @@
 \documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplainculight}
-\usepackage[T1]{fontenc}
-\usepackage[latin1]{inputenc}
+\usepackage{beamerthemeplaincu}
+%\usepackage[T1]{fontenc}
+%\usepackage[latin1]{inputenc}
 \usepackage{mathpartir}
 \usepackage[absolute,overlay]{textpos}
 \usepackage{ifthen}
@@ -72,7 +72,7 @@
 	showstringspaces=false}
 
 % beamer stuff 
-\renewcommand{\slidecaption}{AFL 07, King's College London, 14.~November 2012}
+\renewcommand{\slidecaption}{AFL 07, King's College London, 13.~November 2013}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 
@@ -238,7 +238,7 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
+  Office: & S1.27 (1st floor Strand Building)\\
   Slides: & KEATS (also home work is there)\\
   \end{tabular}
   \end{center}
@@ -248,113 +248,6 @@
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.3cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (30,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,5,...,30}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
-		file {re2.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-    
-	%legend
-	\begin{scope}[shift={(4,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Python};
-	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Ruby (Daniel Baldwin)};
-         \draw[yshift=\baselineskip, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V1};	
-	 \draw[yshift=2\baselineskip, color=green] (0,0) -- 
-		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V2 with simplifications};
-	\end{scope}
-\end{tikzpicture}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-
-\begin{tikzpicture}[y=.7cm, x=.0009cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (10000,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,6);
-    	%ticks
-    	\foreach \x in {0,2000,...,10000}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,1,...,6}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-internal.data};
-	\only<1->{	 
-         \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re3.data};}
-    
-	%legend
-	\begin{scope}[shift={(2000,4)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Scala Internal};
-        \only<1->{
-	\draw[yshift=\baselineskip, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V3 with explicit $\_\{\_\}$};}
-	\end{scope}
-\end{tikzpicture}
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
-  \\[-8mm]
-  \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$}  & \bl{if nullable r$_1$}\\
-  & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ 
-  & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\
-  \bl{der c (r$\{n\}$)} & \bl{$\dn$} & \bl{if $n = 0$ then $\varnothing$}\\
-  & & \bl{else (der c r) $\cdot$ r$\{n - 1\}$}
-  \end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-
 \newcommand{\qq}{\mbox{\texttt{"}}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
@@ -392,7 +285,8 @@
 
 \begin{enumerate}
 \item Begin with a string with only the start symbol \bl{$S$}\bigskip
-\item Replace any non-terminal \bl{$X$} in the string by the
right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip
+\item Replace any non-terminal \bl{$X$} in the string by the
+right-hand side of some production \bl{$X \rightarrow \text{rhs}$}\bigskip
 \item Repeat 2 until there are no non-terminals
 \end{enumerate}