--- a/LINKS	Fri Nov 02 00:24:28 2018 +0000
+++ b/LINKS	Tue Nov 06 00:48:53 2018 +0000
@@ -35,6 +35,11 @@
 Basic as a DSL in Scala
 https://github.com/fogus/baysick/blob/master/src/main/scala/fogus/baysick/Baysick.scala
 
+
+============================
+Arihmetic with regexes
+
+http://www.drregex.com/2018/11/how-to-match-b-c-where-abc-beast-reborn.html
 ============================
 Static analysis lecture notes
 https://cs.au.dk/~amoeller/spa/spa.pdf

Binary file slides/slides06.pdf has changed

--- a/slides/slides06.tex	Fri Nov 02 00:24:28 2018 +0000
+++ b/slides/slides06.tex	Tue Nov 06 00:48:53 2018 +0000
@@ -3,7 +3,7 @@
 \usepackage{../graphics}
 \usepackage{../langs}
 \usepackage{../data}
-
+\usepackage{../grammar}
 
 % beamer stuff 
 \renewcommand{\slidecaption}{CFL 06, King's College London}
@@ -28,7 +28,7 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Office: & N7.07 (North Wing, Bush House)\\
+  Office: & N\liningnums{7.07} (North Wing, Bush House)\\
   Slides: & KEATS (also home work is there)\\
   \end{tabular}
   \end{center}
@@ -118,7 +118,7 @@
 \end{center}\bigskip
 
 \begin{itemize}
-\item you consume one or more token from the\\ 
+\item you consume one or more tokens from the\\ 
   input (stream)
 \item also works for characters and strings
 \end{itemize}
@@ -227,19 +227,13 @@
 
 Which languages are recognised by the following two grammars?
 
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
-        & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}\bigskip
+\bl{\begin{plstx}[margin=3cm]
+: \meta{S} ::= \liningnums{1}\cdot\meta{S}\cdot \meta{S} | \epsilon\\
+\end{plstx}}
 
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$U$ & $\rightarrow$ &  $1 \cdot U$\\
-        & $|$ & $\epsilon$
-\end{tabular}}
-\end{center}
+\bl{\begin{plstx}[margin=3cm]
+: \meta{U} ::= \liningnums{1}\cdot\meta{U} | \epsilon\\
+\end{plstx}}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -277,62 +271,55 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}
+\frametitle{Arithmetic Expressions}
 
 A grammar for arithmetic expressions and numbers:
 
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$ 
-\end{tabular}}
-\end{center}
+\bl{\begin{plstx}[margin=1cm]
+    : \meta{E} ::= \meta{E} \cdot + \cdot \meta{E}
+    | \meta{E} \cdot * \cdot \meta{E}
+    | ( \cdot \meta{E} \cdot )  | \meta{N}\\
+    : \meta{N} ::= \meta{N} \cdot \meta{N} |
+    0 | 1 | \ldots | 9\\
+\end{plstx}}
 
 Unfortunately it is left-recursive (and ambiguous).\medskip\\
-A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
-\bigskip\pause
+A problem for \alert{recursive descent parsers} (e.g.~parser
+combinators).  \bigskip\pause
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Numbers\end{tabular}}
-
-
+\frametitle{Numbers}
 
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
+\bl{\begin{plstx}[margin=1cm]
+    : \meta{N} ::= \meta{N} \cdot \meta{N} |
+    0 | 1 | \ldots | 9\\
+\end{plstx}}
 
 A non-left-recursive, non-ambiguous grammar for numbers:
 
-\begin{center}
-\bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
-\end{tabular}}
-\end{center}
+\bl{\begin{plstx}[margin=1cm]
+    : \meta{N} ::= 0 \cdot \meta{N} | 1 \cdot \meta{N} | \ldots |
+    0 | 1 | \ldots | 9\\
+\end{plstx}}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Removing Left-Recursion\end{tabular}}
+\frametitle{Removing Left-Recursion}
 
 The rule for numbers is directly left-recursive:
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 
+$\meta{N}$ & $::=$ & $\meta{N} \cdot \meta{N} \;|\; 0 \;|\; 1\;\;\;\;(\ldots)$ 
 \end{tabular}}
 \end{center}
 
@@ -341,81 +328,79 @@
 \begin{center}
 \begin{tabular}{ccc}
 \bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $N \cdot \alpha$\\
+$\meta{N}$ & $::=$ & $\meta{N} \cdot \alpha$\\
  &  $\;|\;$ & $\beta$\\
  \\ 
 \end{tabular}} 
 & {\Large$\Rightarrow$} &
 \bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $\beta \cdot N'$\\
-$N'$ & $\rightarrow$ & $\alpha \cdot N'$\\
+$\meta{N}$ & $::=$ & $\beta \cdot \meta{N}'$\\
+$\meta{N}'$ & $::=$ & $\alpha \cdot \meta{N}'$\\
  &  $\;|\;$ & $\epsilon$ 
 \end{tabular}}
 \end{tabular}
 \end{center}\pause
 
-Which means
+Which means in this case:
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1 \cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N' \;|\; \epsilon$\\
+$\meta{N}$ & $\rightarrow$ & $0 \cdot \meta{N}' \;|\; 1 \cdot \meta{N}'$\\
+$\meta{N}'$ & $\rightarrow$ & $\meta{N} \cdot \meta{N}' \;|\; \epsilon$\\
 \end{tabular}}
 \end{center}
 
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Operator Precedences\end{tabular}}
+\frametitle{Operator Precedences}
 
 
 To disambiguate
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
+$\meta{E}$ & $::=$ &  $\meta{E} \cdot + \cdot \meta{E} \;|\;\meta{E} \cdot * \cdot \meta{E} \;|\;( \cdot \meta{E} \cdot ) \;|\;\meta{N}$ \\
 \end{tabular}}
 \end{center}
 
 Decide on how many precedence levels, say\medskip\\
-\hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
+highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
-$E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\
-$E_{med}$ & $\rightarrow$ & $E_{hi} \cdot * \cdot E_{med} \;|\; E_{hi}$\\
-$E_{hi}$ & $\rightarrow$ &  $( \cdot E_{low} \cdot ) \;|\;N$ \\
+$\meta{E}_{low}$ & $::=$ & $\meta{E}_{med} \cdot + \cdot \meta{E}_{low} \;|\; \meta{E}_{med}$ \\
+$\meta{E}_{med}$ & $::=$ & $\meta{E}_{hi} \cdot * \cdot \meta{E}_{med} \;|\; \meta{E}_{hi}$\\
+$\meta{E}_{hi}$ & $::=$ &  $( \cdot \meta{E}_{low} \cdot ) \;|\;\meta{N}$ \\
 \end{tabular}}
 \end{center}\pause
 
 \small What happens with \bl{$1 + 3  + 4$}?
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}
+\frametitle{Chomsky Normal Form}
 
 All rules must be of the form
 
 \begin{center}
-\bl{$A \rightarrow a$}
+\bl{$\meta{A} ::= a$}
 \end{center}
 
 or
 
 \begin{center}
-\bl{$A \rightarrow B\cdot C$}
+\bl{$\meta{A} ::= \meta{B}\cdot \meta{C}$}
 \end{center}
 
 No rule can contain \bl{$\epsilon$}.
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -423,17 +408,17 @@
 \frametitle{\begin{tabular}{c}$\epsilon$-Removal\end{tabular}}
 
 \begin{enumerate}
-\item If \bl{$A\rightarrow \alpha \cdot B \cdot \beta$} and \bl{$B \rightarrow \epsilon$} are in the grammar,
-then add \bl{$A\rightarrow \alpha \cdot \beta$} (iterate if necessary).
-\item Throw out all \bl{$B \rightarrow \epsilon$}.
+\item If \bl{$A::= \alpha \cdot B \cdot \beta$} and \bl{$B ::= \epsilon$} are in the grammar,
+then add \bl{$A::= \alpha \cdot \beta$} (iterate if necessary).
+\item Throw out all \bl{$B ::= \epsilon$}.
 \end{enumerate}
 
 \small
 \begin{center}
 \begin{tabular}{ccc}
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\
+$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'$\\
+$N'$ & $::=$ & $N \cdot N'\;|\;\epsilon$\\
 \\ 
 \\
 \\
@@ -442,11 +427,11 @@
 \end{tabular}} &
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
 \\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
+$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+$N'$ & $::=$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
 \\
-$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\
+$N$ & $::=$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+$N'$ & $::=$ & $N \cdot N'\;|\;N$\\
 \end{tabular}}
 \end{tabular}
 \end{center}
@@ -454,7 +439,7 @@
 \pause\normalsize
 \begin{center}
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
+$N$ & $::=$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
 \end{tabular}}
 
 \end{center}
@@ -464,39 +449,38 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
+\frametitle{CYK Algorithm}
 
 If grammar is in Chomsky normalform \ldots
 
 \begin{center}
 \bl{\begin{tabular}{@ {}lcl@ {}}
-$S$ & $\rightarrow$ &  $N\cdot P$ \\
-$P$ & $\rightarrow$ &  $V\cdot N$ \\
-$N$ & $\rightarrow$ &  $N\cdot N$ \\
-$N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
-$V$ & $\rightarrow$ &  $\texttt{trains}$ 
+$\meta{S}$ & $::=$ &  $\meta{N}\cdot \meta{P}$ \\
+$\meta{P}$ & $::=$ &  $\meta{V}\cdot \meta{N}$ \\
+$\meta{N}$ & $::=$ &  $\meta{N}\cdot \meta{N}$ \\
+$\meta{N}$ & $::=$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
+$\meta{V}$ & $::=$ &  $\texttt{trains}$ 
 \end{tabular}}
 \end{center}
 
 \bl{\texttt{Jeff trains geometry students}}
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
+\frametitle{CYK Algorithm}
 
 
 \begin{itemize}
 \item fastest possible algorithm for recognition problem
 \item runtime is \bl{$O(n^3)$}\bigskip
-\item grammars need to be transferred into CNF
+\item grammars need to be transformed into CNF
 \end{itemize}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -545,19 +529,19 @@
 
 \begin{center}
 \bl{\begin{tabular}{@{}lcl@{}}
-\textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\
+\textit{Stmt} & $::=$ &  $\texttt{skip}$\\
               & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
               & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
               & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
               & $|$ & \texttt{read}\;\textit{Id}\\
               & $|$ & \texttt{write}\;\textit{Id}\\
               & $|$ & \texttt{write}\;\textit{String}\medskip\\
-\textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
+\textit{Stmts} & $::=$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
               & $|$ & \textit{Stmt}\medskip\\
-\textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
+\textit{Block} & $::=$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
                 & $|$ & \textit{Stmt}\medskip\\
-\textit{AExp} & $\rightarrow$ & \ldots\\
-\textit{BExp} & $\rightarrow$ & \ldots\\
+\textit{AExp} & $::=$ & \ldots\\
+\textit{BExp} & $::=$ & \ldots\\
 \end{tabular}}
 \end{center}
 \end{frame}