# HG changeset patch # User Christian Urban # Date 1383049462 0 # Node ID e60c4a9ba340789692fc82f26e267c6349c69c9a # Parent cfba674a8fdfcc3e1ceb2c8c7ef077b97bb7cdac added slides diff -r cfba674a8fdf -r e60c4a9ba340 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r cfba674a8fdf -r e60c4a9ba340 slides/slides06.tex --- a/slides/slides06.tex Mon Oct 28 13:19:44 2013 +0000 +++ b/slides/slides06.tex Tue Oct 29 12:24:22 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} @@ -20,25 +20,18 @@ \usetikzlibrary{calc} \usetikzlibrary{plotmarks} \usepackage{graphicx} +\setmonofont{Consolas} \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 -\lstset{language=Java, - 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} +\makeatletter +\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} +\@empty\z@\@empty +\makeatother + \lstdefinelanguage{scala}{ morekeywords={abstract,case,catch,class,def,% @@ -57,6 +50,18 @@ 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, @@ -70,13 +75,13 @@ tabsize=2, showspaces=false, showstringspaces=false} + % beamer stuff -\renewcommand{\slidecaption}{AFL 06, King's College London, 31.~October 2012} +\renewcommand{\slidecaption}{AFL 06, King's College London, 30.~October 2013} \newcommand{\bl}[1]{\textcolor{blue}{#1}} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions - % The data files, written on the first run. \begin{filecontents}{re-python.data} 1 0.029 @@ -207,7 +212,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} @@ -216,159 +221,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -``I hate coding. I do not want to look at code.'' - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -``I am appalled. You do not show code anymore.'' - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}ReDoS\end{tabular}} - -\begin{itemize} -\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice\bigskip -\item ``Regular Expressions Will Stab You in the Back''\bigskip -\item Evil regular expressions\medskip -\begin{itemize} -\item \bl{$(a?\{n\})a\{n\}$} -\item \bl{$(a^+)^+$} -\item \bl{$([a-zA-Z]^+)^*$} -\item \bl{$(a + aa)^+$} -\item \bl{$(a + a?)^+$} -\end{itemize} -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regexp Matching\end{tabular}} - -Given a regular expression - -\begin{enumerate} -\item you might convert it into a DFA (subset construction) -\item you might try all possible paths in an NFA via backtracking -\item you might try all paths in an NFA in parallel -\item you might try to convert the DFA ``lazily'' -\end{enumerate}\bigskip - -Often No~2 is implemented (sometimes there are even good reasons for doing this). - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$} in Python\end{tabular}} - -\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}; - \only<2->{ - \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] - file {re1.data};} - \only<3->{ - \draw[color=green] plot[mark=square*, mark options={fill=white} ] - file {re2.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}; - \only<2->{\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};} - \only<3->{ - \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{ -\begin{frame}[c] - - -\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<2->{ - \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<2->{ - \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} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - \newcommand{\qq}{\mbox{\texttt{"}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%