diff -r e85600529ca5 -r 4794759139ea slides07.tex --- a/slides07.tex Sat Jun 15 09:11:11 2013 -0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,542 +0,0 @@ -\documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplainculight} -\usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} -\usepackage{mathpartir} -\usepackage[absolute,overlay]{textpos} -\usepackage{ifthen} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{calc} -\usepackage{ulem} -\usepackage{courier} -\usepackage{listings} -\renewcommand{\uline}[1]{#1} -\usetikzlibrary{arrows} -\usetikzlibrary{automata} -\usetikzlibrary{shapes} -\usetikzlibrary{shadows} -\usetikzlibrary{positioning} -\usetikzlibrary{calc} -\usetikzlibrary{plotmarks} -\usepackage{graphicx} - -\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} - -\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]""" -} - -\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} - -% beamer stuff -\renewcommand{\slidecaption}{AFL 07, King's College London, 14.~November 2012} -\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 -5 0.029 -10 0.029 -15 0.032 -16 0.042 -17 0.042 -18 0.055 -19 0.084 -20 0.136 -21 0.248 -22 0.464 -23 0.899 -24 1.773 -25 3.505 -26 6.993 -27 14.503 -28 29.307 -#29 58.886 -\end{filecontents} - -\begin{filecontents}{re-ruby.data} -1 0.00006 -2 0.00003 -3 0.00001 -4 0.00001 -5 0.00001 -6 0.00002 -7 0.00002 -8 0.00004 -9 0.00007 -10 0.00013 -11 0.00026 -12 0.00055 -13 0.00106 -14 0.00196 -15 0.00378 -16 0.00764 -17 0.01606 -18 0.03094 -19 0.06508 -20 0.12420 -21 0.25393 -22 0.51449 -23 1.02174 -24 2.05998 -25 4.22514 -26 8.42479 -27 16.88678 -28 34.79653 -\end{filecontents} - -\begin{filecontents}{re1.data} -1 0.00179 -2 0.00011 -3 0.00014 -4 0.00026 -5 0.00050 -6 0.00095 -7 0.00190 -8 0.00287 -9 0.00779 -10 0.01399 -11 0.01894 -12 0.03666 -13 0.07994 -14 0.08944 -15 0.02377 -16 0.07392 -17 0.22798 -18 0.65310 -19 2.11360 -20 6.31606 -21 21.46013 -\end{filecontents} - -\begin{filecontents}{re2.data} -1 0.00240 -2 0.00013 -3 0.00020 -4 0.00030 -5 0.00049 -6 0.00083 -7 0.00146 -8 0.00228 -9 0.00351 -10 0.00640 -11 0.01217 -12 0.02565 -13 0.01382 -14 0.02423 -15 0.05065 -16 0.06522 -17 0.02140 -18 0.05176 -19 0.18254 -20 0.51898 -21 1.39631 -22 2.69501 -23 8.07952 -\end{filecontents} - -\begin{filecontents}{re-internal.data} -1 0.00069 -301 0.00700 -601 0.00297 -901 0.00470 -1201 0.01301 -1501 0.01175 -1801 0.01761 -2101 0.01787 -2401 0.02717 -2701 0.03932 -3001 0.03470 -3301 0.04349 -3601 0.05411 -3901 0.06181 -4201 0.07119 -4501 0.08578 -\end{filecontents} - -\begin{filecontents}{re3.data} -1 0.001605 -501 0.131066 -1001 0.057885 -1501 0.136875 -2001 0.176238 -2501 0.254363 -3001 0.37262 -3501 0.500946 -4001 0.638384 -4501 0.816605 -5001 1.00491 -5501 1.232505 -6001 1.525672 -6501 1.757502 -7001 2.092784 -7501 2.429224 -8001 2.803037 -8501 3.463045 -9001 3.609 -9501 4.081504 -10001 4.54569 -\end{filecontents} -\begin{document} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] -\frametitle{% - \begin{tabular}{@ {}c@ {}} - \\[-3mm] - \LARGE Automata and \\[-2mm] - \LARGE Formal Languages (7)\\[3mm] - \end{tabular}} - - \normalsize - \begin{center} - \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - Of$\!$fice: & S1.27 (1st floor Strand Building)\\ - Slides: & KEATS (also home work is there)\\ - \end{tabular} - \end{center} - - -\end{frame}} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}CFGs\end{tabular}} - -A \alert{context-free} grammar (CFG) \bl{$G$} consists of: - -\begin{itemize} -\item a finite set of nonterminal symbols (upper case) -\item a finite terminal symbols or tokens (lower case) -\item a start symbol (which must be a nonterminal) -\item a set of rules -\begin{center} -\bl{$A \rightarrow \text{rhs}$} -\end{center} - -where \bl{rhs} are sequences involving terminals and nonterminals (can also be empty).\medskip\pause - -We can also allow rules -\begin{center} -\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$} -\end{center} -\end{itemize} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}A CFG Derivation\end{tabular}} - -\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 Repeat 2 until there are no non-terminals -\end{enumerate} - -\begin{center} -\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Language of a CFG\end{tabular}} - -Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. -Then the language \bl{$L(G)$} is: - -\begin{center} -\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$} -\end{center}\pause - -\begin{itemize} -\item Terminals are so-called because there are no rules for replacing them -\item Once generated, terminals are ``permanent'' -\item Terminals ought to be tokens of the language (at least in this course) -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center}\pause\bigskip - -A CFG is \alert{left-recursive} if it has a nonterminal \bl{$E$} such -that \bl{$E \rightarrow^+ E\cdot \ldots$} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F$\\ -$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\ -$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\ -\end{tabular}} -\end{center} - -\begin{center} -\begin{tikzpicture}[level distance=8mm, blue] - \node {$E$} - child {node {$F$} - child {node {$T$} - child {node {(\,$E$\,)} - child {node{$F$ *{} $F$} - child {node {$T$} child {node {2}}} - child {node {$T$} child {node {3}}} - } - } - } - child {node {+}} - child {node {$T$} - child {node {(\,$E$\,)} - child {node {$F$} - child {node {$T$ +{} $T$} - child {node {3}} - child {node {4}} - } - }} - }}; -\end{tikzpicture} -\end{center} - -\begin{textblock}{5}(1, 6.5) -\bl{\texttt{(2*3)+(3+4)}} -\end{textblock} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} - -A CFG is \alert{ambiguous} if there is a string that has at least parse trees. - - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center} - -\bl{\texttt{1 + 2 * 3 + 4}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Dangling Else\end{tabular}} - -Another ambiguous grammar:\bigskip - -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & if $E$ then $E$\\ - & $|$ & if $E$ then $E$ else $E$ \\ - & $|$ & id -\end{tabular}} -\end{center}\bigskip - -\bl{\texttt{if a then if x then y else c}} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -\end{document} - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: -