% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\usepackage{../langs}
\usepackage{../data}
\usepackage{../grammar}
\hfuzz=220pt
\pgfplotsset{compat=1.11}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
\renewcommand{\slidecaption}{CFL 05, King's College London}
\usepackage{tcolorbox}
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
\LARGE Formal Languages\\[-5mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office Hour: & Fridays 12 -- 14\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\end{tabular}
\end{center}
\begin{center}
\begin{tikzpicture}
\node[drop shadow,fill=white,inner sep=0pt]
{\footnotesize\rowcolors{1}{capri!10}{white}
\begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
1 Introduction, Languages & 6 While-Language \\
2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
3 Automata, Regular Languages & 8 Compiling Functional Languages \\
4 Lexing, Tokenising & 9 Optimisations \\
\cellcolor{blue!50}
5 Grammars, Parsing & 10 LLVM \\ \hline
\end{tabular}%
};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
% \frametitle{Coursework 1: Submissions}
%
% \begin{itemize}
% \item Scala (29)
% \item Haskell (1)
% \item Kotlin (1)
% \item Rust (1)
% \end{itemize}\bigskip\bigskip
%
% \small
% Please get in contact if you intend to do CW Strand 2. No zips please.
% Give definitions also on paper if asked. BTW, simp
% can stay unchanged. Use \texttt{ders} for CW2, not \texttt{ders2}!
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}<1-10>[c]
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Coursework 1: Submissions}
\begin{itemize}
\item Scala (162)
\item Ocaml (1)
\item Java (1) \ldots uses new features of Java 21
\item Rust (6)
\end{itemize}\bigskip\bigskip
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Parser}
\mbox{}\\[-16mm]\mbox{}
\begin{center}
\begin{tikzpicture}[scale=1,
node/.style={
rectangle,rounded corners=3mm,
very thick,draw=black!50,
minimum height=18mm, minimum width=20mm,
top color=white,bottom color=black!20,drop shadow}]
\node (0) at (-2.3,0) {};
\node (A) at (0,0) [node] {};
\node [below right] at (A.north west) {lexer};
\node (B) at (3,0) [node] {};
\node [below right=1mm] at (B.north west)
{\mbox{}\hspace{-1mm}parser};
\node (C) at (6,0) [node] {};
\node [below right] at (C.north west)
{\mbox{}\hspace{-1mm}code gen};
\node (1) at (8.4,0) {};
\draw [->,line width=4mm] (0) -- (A);
\draw [->,line width=4mm] (A) -- (B);
\draw [->,line width=4mm] (B) -- (C);
\draw [->,line width=4mm] (C) -- (1);
\end{tikzpicture}
\end{center}
\only<2>{
\begin{textblock}{1}(3,6)
\begin{bubble}[8.5cm]
\normalsize
parser input: a sequence of tokens\smallskip\\
{\small\hspace{5mm}\code{key(read) lpar id(n) rpar semi}}\smallskip\\
parser output: an abstract syntax tree\smallskip\\
\footnotesize
\hspace{2cm}\begin{tikzpicture}
\node {\code{read}}
child {node {\code{lpar}}}
child {node {\code{n}}}
child {node {\code{rpar}}};
\end{tikzpicture}
\end{bubble}
\end{textblock}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{What Parsing is Not}
Usually parsing does not check semantic correctness, e.g.
\begin{itemize}
\item whether a function is not used before it
is defined
\item whether a function has the correct number of arguments
or are of correct type
\item whether a variable can be declared twice in a scope
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=1.5,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20}]
\node[state,initial] (q0) at (0,2) {$q_0$};
\node[state,accepting] (q1) at (2,2) {$q_1$};
\node[state] (q2) at (0,0) {$q_2$};
\node[state] (q3) at (2,0) {$q_3$};
\path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
(q1) edge[bend left] node[above] {\alert{$a$}} (q0)
(q2) edge[bend left] node[above] {\alert{$a$}} (q3)
(q3) edge[bend left] node[above] {\alert{$a$}} (q2)
(q0) edge[bend left] node[right] {\alert{$b$}} (q2)
(q2) edge[bend left] node[left] {\alert{$b$}} (q0)
(q1) edge[bend left] node[right] {\alert{$b$}} (q3)
(q3) edge[bend left] node[left] {\alert{$b$}} (q1);
\end{tikzpicture}
\end{center}
\hfill{}Which language?
\end{frame}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Languages}
While regular expressions are very useful for lexing, there is
no regular expression that can recognise the language
\bl{$a^nb^n$}.\bigskip
\begin{center}
\bl{$(((()()))())$} \;\;vs.\;\; \bl{$(((()()))()))$}
\end{center}\bigskip\bigskip
\small
\noindent So we cannot find out with regular expressions
whether parentheses are matched or unmatched. Also regular
expressions are not recursive, e.g.~\bl{$(1 + 2) + 3$}.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Hierarchy of Languages}
\begin{center}
\begin{tikzpicture}
[rect/.style={draw=black!50,
top color=white,
bottom color=black!20,
rectangle,
very thick,
rounded corners}, scale=1.2]
\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
\draw (0,-1.4) node [rect] {regular languages};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\LARGE
\begin{center}
Time flies like an arrow.\\
Fruit flies like bananas.
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CFGs}
A \alert{\bf context-free grammar} \bl{$G$} consists of
\begin{itemize}
\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case)
\item a finite set terminal symbols or tokens (lower case)
\item a start symbol (which must be a nonterminal)
\item a set of rules
\begin{center}
\bl{$\meta{A} ::= \textit{rhs}$}
\end{center}
where \bl{\textit{rhs}} are sequences involving terminals and nonterminals,
including the empty sequence \bl{$\epsilon$}.\medskip\pause
We also allow rules
\begin{center}
\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$}
\end{center}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Palindromes}
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
\only<1>{%
\bl{\begin{plstx}[margin=1cm]
: \meta{S} ::= a\cdot\meta{S}\cdot a\\
: \meta{S} ::= b\cdot\meta{S}\cdot b\\
: \meta{S} ::= a\\
: \meta{S} ::= b\\
: \meta{S} ::= \epsilon\\
\end{plstx}}}
%
\only<2>{%
\bl{\begin{plstx}[margin=1cm]
: \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a | b | \epsilon\\
\end{plstx}}}
%\small
%Can you find the grammar rules for matched parentheses?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Arithmetic Expressions}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}\pause
\bl{\texttt{1 + 2 * 3 + 4}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{A CFG Derivation}
\begin{enumerate}
\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
\item Replace any nonterminal \bl{\meta{X}} in the string by the
right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
\item Repeat 2 until there are no nonterminals left
\end{enumerate}
\begin{center}
\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Example Derivation}
\bl{\begin{plstx}[margin=2cm]
: \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\
\end{plstx}}\bigskip
\begin{center}
\begin{tabular}{lcl}
\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\
& \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\
& \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\
& \bl{$\rightarrow$} & \bl{$abaaba$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Example Derivation}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= 0 \mid 1 \mid 2 \mid ... \mid 9
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}
\small
\begin{center}
\begin{tabular}{@{}c@{}c@{}}
\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}}
\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
\end{tabular} &\pause
\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l}
\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\
& \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\
\end{tabular}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Language of a CFG}
Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}.
Then the language \bl{$L(G)$} is:
\begin{center}
\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$}
\end{center}\pause
\begin{itemize}
\item Terminals, because there are no rules for replacing them.
\item Once generated, terminals are ``permanent''.
\item Terminals ought to be tokens of the language\\
(but can also be strings).
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Parse Trees}
\mbox{}\\[-12mm]
\bl{\begin{plstx}: \meta{E} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{E} | \meta{T} \cdot - \cdot \meta{E}\\
: \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
: \meta{F} ::= 0 ... 9 | ( \cdot \meta{E} \cdot )\\
\end{plstx}}
\begin{textblock}{5}(6, 5)
\small
\begin{tikzpicture}[level distance=10mm, blue]
\node {$\meta{E}$}
child {node {$\meta{T}$}
child {node {$\meta{F}$} child {node {1}}}
}
child {node {+}}
child {node {$\meta{E}$}
child[sibling distance=10mm] {node {$\meta{T}$}
child {node {$\meta{F}$} child {node {2}}}
child {node {*}}
child {node {$\meta{T}$} child {node {$\meta{F}$} child {node {3}}}}
}
child {node {+}}
child {node {$\meta{E}$} child {node {$\meta{T}$}
child {node {$\meta{F}$} child {node {4}}}}}
}
;
\end{tikzpicture}
\end{textblock}
\begin{textblock}{5}(1, 10)
\bl{\texttt{1 + 2 * 3 + 4}}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Arithmetic Expressions}
\bl{\begin{plstx}[margin=3cm,one per line]
: \meta{E} ::= 0..9
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}\pause\bigskip
A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such
that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Ambiguous Grammars}
A grammar is \alert{\bf ambiguous} if there is a string that
has at least two different parse trees.
\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= 0 ... 9
| \meta{E} \cdot + \cdot \meta{E}
| \meta{E} \cdot - \cdot \meta{E}
| \meta{E} \cdot * \cdot \meta{E}
| ( \cdot \meta{E} \cdot ) \\
\end{plstx}}
\bl{\texttt{1 + 2 * 3 + 4}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{`Dangling' Else}
Another ambiguous grammar:\bigskip
\begin{center}
\bl{\begin{tabular}{lcl}
$E$ & $\rightarrow$ & if $E$ then $E$\\
& $|$ & if $E$ then $E$ else $E$ \\
& $|$ & \ldots
\end{tabular}}
\end{center}\bigskip
\bl{\texttt{if a then if x then y else c}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}
Suppose the grammar:
\begin{center}
\bl{\begin{tabular}{@ {}lcl@ {}}
$\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{CYK Algorithm}
\begin{center}
\begin{tikzpicture}[scale=1,line width=0.8mm]
\draw (-2,0) -- (2,0);
\draw (-2,1) -- (2,1);
\draw (-2,2) -- (1,2);
\draw (-2,3) -- (0,3);
\draw (-2,4) -- (-1,4);
\draw (0,0) -- (0, 3);
\draw (1,0) -- (1, 2);
\draw (2,0) -- (2, 1);
\draw (-1,0) -- (-1, 4);
\draw (-2,0) -- (-2, 4);
\draw (-1.5,-0.5) node {\footnotesize{}\texttt{Jeff}};
\draw (-0.5,-1.0) node {\footnotesize{}\texttt{trains}};
\draw ( 0.5,-0.5) node {\footnotesize{}\texttt{geometry}};
\draw ( 1.5,-1.0) node {\footnotesize{}\texttt{students}};
\draw (-1.5,0.5) node {$N$};
\draw (-0.5,0.5) node {$N,V$};
\draw ( 0.5,0.5) node {$N$};
\draw ( 1.5,0.5) node {$N$};
\draw (-2.4, 3.5) node {$1$};
\draw (-2.4, 2.5) node {$2$};
\draw (-2.4, 1.5) node {$3$};
\draw (-2.4, 0.5) node {$4$};
\end{tikzpicture}
\end{center}
\begin{textblock}{5}(10,10)
\small\bl{\begin{tabular}{@ {}lcl@ {}}
$\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{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Chomsky Normal Form}
A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
\bl{\begin{plstx}[margin=0cm]
: \meta{S} ::= a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b | a\cdot a | b\cdot b | a | b \\
\end{plstx}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\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 transformed into CNF
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
\begin{mybox3}{}\it
"The C++ grammar is ambiguous, context-dependent and potentially
requires infinite lookahead to resolve some ambiguities."
\end{mybox3}\bigskip
\hfill from the \href{http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.pdf}{PhD thesis} by Willink (2001)
\small
\begin{center}
\begin{lstlisting}[language={},numbers=none]
int(x), y, *const z;
int(x), y, new int;
\end{lstlisting}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Context Sensitive Grammars}
It is much harder to find out whether a string is parsed
by a context sensitive grammar:
\bl{\begin{plstx}[margin=2cm]
: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\
: \meta{A} ::= a\\
: b\meta{A} ::= \meta{A}b\\
\end{plstx}}\pause
\begin{center}
\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t,fragile]
\begin{mybox3}{}
For CW2, please include '$\backslash$' as a symbol in strings, because
the collatz program contains
\begin{lstlisting}[language=Scala, numbers=none]
write "\n";\end{lstlisting}
\end{mybox3}
\end{frame}
\begin{frame}[t]
\begin{mybox3}{}
val (r1s, f1s) = simp(r1)\\
val (r2s, f2s) = simp(r2)\\
how are the
first rectification functions f1s and f2s made? could you maybe
show an example?
\end{mybox3}
\end{frame}
\begin{frame}<1-24>[c]
\end{frame}
\begin{frame}[t]
\begin{minipage}{1.2\textwidth}
\begin{mybox3}{}\small
\textbf{Questions regarding CFL CW1}
Dear Dr Urban
Regarding CW1, I am stuck on finding the nullable and derivative rules for some important regexes.\smallskip
The NOT Regex nullable rule: I am not sure how to approach this, I am inclined to simply put this as the negation of the nullable function on the input regex (e.g !nullable(r)). However I have found instances where negating a nullable does not make it un-nullable. For example the negation of r* can still match regex ab (which is not nullable). So I would like some actual clarification, pointers and help in this area.\smallskip
The NOT Regex derivation rule: again I am dumbfounded here, I am inclined to think that I should derive the regex and then negate that derivation. But none of this ever works. Please provide some helpful information so I can solve this.
\end{mybox3}
\end{minipage}
\end{frame}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: