diff -r b5b5583a3a08 -r 6acabeecdf75 slides/slides04.tex --- a/slides/slides04.tex Thu Jul 30 13:50:54 2020 +0100 +++ b/slides/slides04.tex Sat Aug 15 14:18:37 2020 +0100 @@ -1,5 +1,5 @@ % !TEX program = xelatex -\documentclass[dvipsnames,14pt,t]{beamer} +\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} \usepackage{../slides} \usepackage{../graphics} \usepackage{../langs} @@ -27,126 +27,38 @@ \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Compilers and \\[-2mm] - \LARGE Formal Languages (4)\\[3mm] + \LARGE Formal Languages\\[3mm] \end{tabular}} \normalsize \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Office Hours: & Thursdays 12 -- 14\\ - Location: & N7.07 (North Wing, Bush House)\\ + %Office Hours: & Thursdays 12 -- 14\\ + %Location: & N7.07 (North Wing, Bush House)\\ Slides \& Progs: & KEATS (also homework is there)\\ \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 \\ + \cellcolor{blue!50} + 4 Lexing, Tokenising & 9 Optimisations \\ + 5 Grammars, Parsing & 10 LLVM \\ \hline + \end{tabular}% + }; + \end{tikzpicture} + \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] - \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; - \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) - (q1) edge[bend left] node[above] {\alert{$b$}} (q0) - (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) - (q1) edge node[above] {\alert{$a$}} (q2) - (q2) edge [loop right] node {\alert{$a$}} () - (q0) edge [loop below] node {\alert{$b$}} () - ; -\end{tikzpicture} -\end{center}\bigskip - -\begin{center} -\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ -\end{tabular} -\end{center} - - -Arden's Lemma: -\begin{center} -If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -\end{center} - -\only<2-6>{\small -\begin{textblock}{6}(1,0.8) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<3-6>{\small -\begin{textblock}{6}(2,4.15) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<4-6>{\small -\begin{textblock}{6}(3,7.55) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<5-6>{\small -\begin{textblock}{6}(4,10.9) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<6>{\small -\begin{textblock}{6}(5,13.4) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - - -\only<7->{\small -\begin{textblock}{6}(6,11.5) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{Finally:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -192,251 +104,7 @@ \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Regexps and Automata} - -\begin{center} -\begin{tikzpicture} -\node (rexp) {\bl{\bf Regexps}}; -\node (nfa) [right=of rexp] {\bl{\bf NFAs}}; -\node (dfa) [right=of nfa] {\bl{\bf DFAs}}; -\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}}; -\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] - {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa); -\path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] - {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa); -\path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa); -%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp); -\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp); - -\end{tikzpicture}\\ -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} - -\begin{tikzpicture} -\begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, - enlargelimits=false, - xtick={0,5,...,30}, - xmax=30, - ymax=35, - ytick={0,5,...,30}, - scaled ticks=false, - axis lines=left, - width=10cm, - height=7cm, - legend entries={Python,Ruby,my NFA}, - legend pos=north west, - legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; -\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; -\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; -\end{axis} -\end{tikzpicture} - -The punchline is that many existing libraries do depth-first search -in NFAs (backtracking). - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{DFA to Rexp} - -% \begin{center} -% \begin{tikzpicture}[scale=2,>=stealth',very thick, -% every state/.style={minimum size=0pt, -% draw=blue!50,very thick,fill=blue!20},] -% \node[state, initial] (q0) at ( 0,1) {$q_0$}; -% \node[state] (q1) at ( 1,1) {$q_1$}; -% \node[state, accepting] (q2) at ( 2,1) {$q_2$}; -% \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) -% (q1) edge[bend left] node[above] {\alert{$b$}} (q0) -% (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) -% (q1) edge node[above] {\alert{$a$}} (q2) -% (q2) edge [loop right] node {\alert{$a$}} () -% (q0) edge [loop below] node {\alert{$b$}} (); -% \end{tikzpicture} -% \end{center}\bigskip - -% \begin{center} -% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} -% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ -% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ -% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ - -% \end{tabular} -% \end{center} - -% Arden's Lemma: -% \begin{center} -% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -% \end{center} - - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{DFA Minimisation} - -% \begin{enumerate} -% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} -% \item Mark all pairs that accepting and non-accepting states -% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether -% \begin{center} -% \bl{$(\delta(q, c), \delta(p,c))$} -% \end{center} -% are marked. If yes, then also mark \bl{$(q, p)$}. -% \item Repeat last step until no change. -% \item All unmarked pairs can be merged. -% \end{enumerate} - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] - -% \begin{center} -% \begin{tabular}{@{\hspace{-8mm}}cc@{}} -% \begin{tikzpicture}[>=stealth',very thick,auto, -% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -% \node[state,initial] (q_0) {$q_0$}; -% \node[state] (q_1) [right=of q_0] {$q_1$}; -% \node[state] (q_2) [below right=of q_0] {$q_2$}; -% \node[state] (q_3) [right=of q_2] {$q_3$}; -% \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; -% \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); -% \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); -% \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); -% \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); -% \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); -% \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); -% \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); -% \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); -% \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); -% \end{tikzpicture} -% & -% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] -% \draw (0,0) -- (4,0); -% \draw (0,1) -- (4,1); -% \draw (0,2) -- (3,2); -% \draw (0,3) -- (2,3); -% \draw (0,4) -- (1,4); - -% \draw (0,0) -- (0, 4); -% \draw (1,0) -- (1, 4); -% \draw (2,0) -- (2, 3); -% \draw (3,0) -- (3, 2); -% \draw (4,0) -- (4, 1); - -% \draw (0.5,-0.5) node {$q_0$}; -% \draw (1.5,-0.5) node {$q_1$}; -% \draw (2.5,-0.5) node {$q_2$}; -% \draw (3.5,-0.5) node {$q_3$}; - -% \draw (-0.5, 3.5) node {$q_1$}; -% \draw (-0.5, 2.5) node {$q_2$}; -% \draw (-0.5, 1.5) node {$q_3$}; -% \draw (-0.5, 0.5) node {$q_4$}; - -% \draw (0.5,0.5) node {\large$\star$}; -% \draw (1.5,0.5) node {\large$\star$}; -% \draw (2.5,0.5) node {\large$\star$}; -% \draw (3.5,0.5) node {\large$\star$}; -% \draw (0.5,1.5) node {\large$\star$}; -% \draw (2.5,1.5) node {\large$\star$}; -% \draw (0.5,3.5) node {\large$\star$}; -% \draw (1.5,2.5) node {\large$\star$}; -% \end{tikzpicture}} -% \end{tabular} -% \end{center} - - -% \mbox{}\\[-20mm]\mbox{} - -% \begin{center} -% \begin{tikzpicture}[>=stealth',very thick,auto, -% every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] -% \node[state,initial] (q_02) {$q_{0, 2}$}; -% \node[state] (q_13) [right=of q_02] {$q_{1, 3}$}; -% \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$}; -% \path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13); -% \path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02); -% \path[->] (q_02) edge [loop below] node {\alert{$b$}} (); -% \path[->] (q_13) edge node [above] {\alert{$a$}} (q_4); -% \path[->] (q_4) edge [loop above] node {\alert{$a, b$}} (); -% \end{tikzpicture}\\ -% minimal automaton -% \end{center} - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Regular Languages} - -Two equivalent definitions:\bigskip - -\begin{quote}\rm A language is \alert{regular} iff there exists a -regular expression that recognises all its strings. -\end{quote} - -\begin{quote}\rm A language is \alert{regular} iff there exists an -automaton that recognises all its strings. -\end{quote}\bigskip\bigskip - - -\small -for example \bl{$a^nb^n$} is not regular -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Negation} - -Regular languages are closed under negation:\bigskip - -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt, - draw=blue!50,very thick,fill=blue!20}] - \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};} - \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};} - \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} - \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} - \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} - \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};} - \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) - (q1) edge[bend left] node[above] {\alert{$b$}} (q0) - (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) - (q1) edge node[above] {\alert{$a$}} (q2) - (q2) edge [loop right] node {\alert{$a$}} () - (q0) edge [loop below] node {\alert{$b$}} (); -\end{tikzpicture} -\end{center}\bigskip\bigskip - -But requires that the automaton is \alert{completed}! - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -449,7 +117,7 @@ rectangle,rounded corners=3mm, very thick,draw=black!50, minimum height=18mm, minimum width=20mm, - top color=white,bottom color=black!20}] + top color=white,bottom color=black!20,drop shadow}] \node at (3.05, 1.8) {\Large\bf Write a compiler}; @@ -509,7 +177,7 @@ \begin{frame}[c] \frametitle{Lexing: Test Case} -\mbox{\lstinputlisting[language=While]{../progs/fib.while}} +??%\mbox{\lstinputlisting[language=While]{../progs/fib.while}} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -1474,6 +1142,416 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Last Week\\[-2mm] + Regexes and Values\end{tabular}} + +Regular expressions and their corresponding values: + +\begin{center} +\begin{columns} +\begin{column}{3cm} +\begin{tabular}{@{}rrl@{}} + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ + & \bl{$\mid$} & \bl{$\ONE$} \\ + & \bl{$\mid$} & \bl{$c$} \\ + & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ + & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ + \\ + & \bl{$\mid$} & \bl{$r^*$} \\ + \end{tabular} +\end{column} +\begin{column}{3cm} +\begin{tabular}{@{\hspace{-7mm}}rrl@{}} + \bl{$v$} & \bl{$::=$} & \\ + & & \bl{$Empty$} \\ + & \bl{$\mid$} & \bl{$Char(c)$} \\ + & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ + & \bl{$\mid$} & \bl{$Left(v)$} \\ + & \bl{$\mid$} & \bl{$Right(v)$} \\ + & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\ + \end{tabular} +\end{column} +\end{columns} +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{textblock}{10}(3,5) +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\node (r1) {\bl{$r_1$}}; +\node (r2) [right=of r1] {\bl{$r_2$}}; +\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; +\node (r3) [right=of r2] {\bl{$r_3$}}; +\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; +\node (r4) [right=of r3] {\bl{$r_4$}}; +\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; +\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; +\node (v4) [below=of r4] {\bl{$v_4$}}; +\draw[->,line width=1mm] (r4) -- (v4); +\node (v3) [left=of v4] {\bl{$v_3$}}; +\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; +\node (v2) [left=of v3] {\bl{$v_2$}}; +\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; +\node (v1) [left=of v2] {\bl{$v_1$}}; +\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; +\draw[->,line width=0.5mm] (r3) -- (v3); +\draw[->,line width=0.5mm] (r2) -- (v2); +\draw[->,line width=0.5mm] (r1) -- (v1); +\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; +\end{tikzpicture} +\end{textblock} + +\begin{textblock}{6}(1,0.8) +\begin{bubble}[6cm] +\small +\begin{tabular}{ll} +\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ +\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(1,11.4) +\begin{bubble}[7.6cm] +\small +\begin{tabular}{ll} +\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\ +\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\ +\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\ +\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\ +\end{tabular} +\end{bubble} +\end{textblock} + +\begin{textblock}{6}(12,11.4) +\begin{bubble}[2cm] +\small +\begin{tabular}{ll} +\bl{$|v_1|$}: & \bl{$abc$}\\ +\bl{$|v_2|$}: & \bl{$bc$}\\ +\bl{$|v_3|$}: & \bl{$c$}\\ +\bl{$|v_4|$}: & \bl{$[]$} +\end{tabular} +\end{bubble} +\end{textblock} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Simplification} + +\begin{itemize} +\item If we simplify after the derivative, then we are builing the +value for the simplified regular expression, but \emph{not} for the original +regular expression. +\end{itemize} + +\begin{center} +\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] +\node (r1) {\bl{$r_1$}}; +\node (r2) [right=of r1] {\bl{$r_2$}}; +\draw[->,line width=1mm] (r1) -- (r2) node[above,midway] {\bl{$der\,a$}}; +\node (r3) [right=of r2] {\bl{$r_3$}}; +\draw[->,line width=1mm] (r2) -- (r3) node[above,midway] {\bl{$der\,b$}}; +\node (r4) [right=of r3] {\bl{$r_4$}}; +\draw[->,line width=1mm] (r3) -- (r4) node[above,midway] {\bl{$der\,c$}}; +\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}}; +\node (v4) [below=of r4] {\bl{$v_4$}}; +\draw[->,line width=1mm] (r4) -- (v4); +\node (v3) [left=of v4] {\bl{$v_3$}}; +\draw[->,line width=1mm] (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}}; +\node (v2) [left=of v3] {\bl{$v_2$}}; +\draw[->,line width=1mm] (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}}; +\node (v1) [left=of v2] {\bl{$v_1$}}; +\draw[->,line width=1mm] (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}}; +\draw[->,line width=0.5mm] (r3) -- (v3); +\draw[->,line width=0.5mm] (r2) -- (v2); +\draw[->,line width=0.5mm] (r1) -- (v1); +\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; +\end{tikzpicture} +\end{center} + +\small +\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$} +$\mapsto$ +\bl{$(b \cdot c) + \ONE$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] + +% \begin{center} +% \bl{$\only<1>{(b \cdot c)}% +% \only<2-3>{(\underline{b \cdot c})}% +% \only<1-3>{+}% +% \only<1>{(\ZERO + \ONE)}% +% \only<2-3>{(\underline{\ZERO + \ONE})}$}% +% \only<4->{% +% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% +% } +% $\mapsto$ +% \bl{$(b \cdot c) + \ONE$} +% \end{center}\bigskip + +% \onslide<3->{% +% \begin{center} +% \begin{tabular}{lcl} +% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ +% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} +% \end{tabular} +% \end{center}} + +% \only<4>{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(f_{s1}(v'))$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(f_{s2}(v'))$}\\ +% \end{tabular} +% \end{center}}% +% \only<5->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(v')$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(Right(v'))$}\\ +% \end{tabular} +% \end{center}}% + +% \only<6->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}} +% \bl{$\textit{mkeps}$} simplified case: & +% \bl{$\textit{Right}(\textit{Empty})$}\\ +% rectified case: & +% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} +% \end{tabular} +% \end{center}}% + +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Records} + +\begin{itemize} +\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause + +\item \bl{$nullable(x:r) \dn nullable(r)$} +\item \bl{$der\,c\,(x:r) \dn der\,c\,r$} +\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} +\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} +\end{itemize}\bigskip\bigskip\pause + +\small +for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Environments} + +Obtaining the ``recorded'' parts of a value: + +\begin{center} +\begin{tabular}{lcl} + \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ + \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ + \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ + \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ + \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ + \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & + \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ + \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{While Tokens} + +\begin{center} +\begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}} +\pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ + & & \phantom{(}\pcode{("i" : ID)} +\\ + & & \phantom{(}\pcode{("o" : OP)} + \\ + & & \phantom{(}\pcode{("n" : NUM)} + \\ + & & \phantom{(}\pcode{("s" : SEMI)} +\\ + & & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ + & & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ + & & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$} +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] + +\consolas +\begin{center} +\code{"if true then then 42 else +"} +\end{center} + +\only<1>{ +\small\begin{tabular}{l} +KEYWORD(if),\\ +WHITESPACE,\\ +IDENT(true),\\ +WHITESPACE,\\ +KEYWORD(then),\\ +WHITESPACE,\\ +KEYWORD(then),\\ +WHITESPACE,\\ +NUM(42),\\ +WHITESPACE,\\ +KEYWORD(else),\\ +WHITESPACE,\\ +OP(+) +\end{tabular}} + +\only<2>{ +\small\begin{tabular}{l} +KEYWORD(if),\\ +IDENT(true),\\ +KEYWORD(then),\\ +KEYWORD(then),\\ +NUM(42),\\ +KEYWORD(else),\\ +OP(+) +\end{tabular}} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: PLs (16)} +% +%\begin{itemize} +%\item Java (16) +%\item C++, C, C\# (14) +%\item JavaScript (10) +%\item Scala (9) +%\item Python (9) +%\item PHP (6) +%\item Haskell (3) +%\item Ruby (4) +%\item Bash, Perl, Powershell (2) +%\item TypeScript (1) +%\item R (1) +%\item Coconut (1) +%\item Pascal (1) +%\end{itemize} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: Nullable} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ +% +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%%%\frametitle{Coursework: der} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} +% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ +% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ +% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ +% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ +% +% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & +% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ +% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ +% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else +% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ +% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: CFUN} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ +% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & +% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ +% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ +% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ +% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document} %%% Local Variables: