# HG changeset patch # User Christian Urban # Date 1353769107 0 # Node ID 49c0beef79a146d8555233c2b8e2c2a9c683eab2 # Parent 373cf55a3ca58718dfe68831042ce09681b0ac27 added diff -r 373cf55a3ca5 -r 49c0beef79a1 hw08.pdf Binary file hw08.pdf has changed diff -r 373cf55a3ca5 -r 49c0beef79a1 hw08.tex --- a/hw08.tex Sat Nov 24 07:08:51 2012 +0000 +++ b/hw08.tex Sat Nov 24 14:58:27 2012 +0000 @@ -21,7 +21,7 @@ & $|$ & $Id := AExp$\\ & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ -$Stmt$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ +$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ & $|$ & $Stmt$\medskip\\ $Block$ & $\rightarrow$ & $\{ Stmts \}$\\ & $|$ & $Stmt$\medskip\\ @@ -40,6 +40,8 @@ Transform this grammar into Chomsky normalform. +\item Write a program in the WHILE-language that calculates the factorial function. + \end{enumerate} \end{document} diff -r 373cf55a3ca5 -r 49c0beef79a1 slides09.tex --- a/slides09.tex Sat Nov 24 07:08:51 2012 +0000 +++ b/slides09.tex Sat Nov 24 14:58:27 2012 +0000 @@ -20,6 +20,8 @@ \usetikzlibrary{calc} \usetikzlibrary{plotmarks} \usepackage{graphicx} +\usepackage{pgfplots} + \definecolor{javared}{rgb}{0.6,0,0} % for strings \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments @@ -57,6 +59,7 @@ morestring=[b]""" } + \lstset{language=Scala, basicstyle=\ttfamily, keywordstyle=\color{javapurple}\bfseries, @@ -71,6 +74,29 @@ showspaces=false, showstringspaces=false} +\lstdefinelanguage{while}{ + morekeywords={if,then,else,while,do,true,false}, + otherkeywords={=,!=,:=,<,>}, + sensitive=true, + morecomment=[n]{/*}{*/}, +} + + +\lstset{language=While, + 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 09, King's College London, 28.~November 2012} \newcommand{\bl}[1]{\textcolor{blue}{#1}} @@ -78,48 +104,18 @@ % The data files, written on the first run. -\begin{filecontents}{s-grammar1.data} -1 0.01152 -51 0.07973 -101 0.09726 -151 0.09320 -201 0.10010 -251 0.16997 -301 0.26662 -351 0.46118 -401 0.62516 -451 0.87247 -501 1.16334 -551 1.71152 -601 2.10958 -651 2.44360 -701 2.98488 -751 3.50326 -801 4.11036 -851 4.93394 -901 5.77465 -951 7.39123 +\begin{filecontents}{compiled.data} +1 0.0207 +5000 0.0217 +10000 0.0297 +50000 0.1034 +100000 0.3873 +500000 1.27949 +1000000 5. 35424 \end{filecontents} -\begin{filecontents}{s-grammar2.data} -1 0.01280 -2 0.00064 -3 0.00173 -4 0.00355 -5 0.00965 -6 0.02674 -7 0.06953 -8 0.11166 -9 0.18707 -10 0.09189 -11 0.12724 -12 0.24337 -13 0.59304 -14 1.53594 -15 4.01195 -16 10.73582 -17 29.51587 -#18 73.14163 +\begin{filecontents}{interpreted.data} + \end{filecontents} @@ -144,45 +140,54 @@ \end{tabular} \end{center} - \end{frame}} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Building a ``Web Browser''\end{tabular}} +\frametitle{\begin{tabular}{c}While-Language\end{tabular}} -Using a lexer: assume the following regular expressions \begin{center} -\bl{\begin{tabular}{lcl} -$SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\ -$W\!O\!RD$ & $\dn$ & $SY\!M^+$\\ -$BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\ -$ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\ -$W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\ +\bl{\begin{tabular}{@{}lcl@{}} +$Stmt$ & $\rightarrow$ & $\text{skip}$\\ + & $|$ & $Id := AExp$\\ + & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ + & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\\ + & $|$ & $\alert{\text{write}\; Id}$\medskip\\ +$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ + & $|$ & $Stmt$\medskip\\ +$Block$ & $\rightarrow$ & $\{ Stmts \}$\\ + & $|$ & $Stmt$\medskip\\ +$AExp$ & $\rightarrow$ & \ldots\\ +$BExp$ & $\rightarrow$ & \ldots\\ \end{tabular}} \end{center} + \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}} +\frametitle{\begin{tabular}{c}Fibonacci Numbers\end{tabular}} + +\mbox{}\\[-18mm]\mbox{} + +{\lstset{language=While}\fontsize{10}{12}\selectfont +\texttt{\lstinputlisting{app9.while}}} -\begin{itemize} -\item the text should be formatted consistently up to a specified width, say 60 characters -\item potential linebreaks are inserted by the formatter (not the input) -\item repeated whitespaces are ``condensed'' to a single whitepace -\item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$} start/end paragraph -\item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$} start/end bold -\item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$} start/end red (cyan, etc) +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Interpreter\end{tabular}} -\end{itemize} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -497,87 +502,39 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Successful Parses\end{tabular}} - -\begin{itemize} -\item input: string -\item output: \alert{set of} (output\_type, string) -\end{itemize}\bigskip - -a parse is successful whenever the input has been -fully ``consumed'' (that is the second component is empty) - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -{\lstset{language=Scala}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{app7.scala}}} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -{\lstset{language=Scala}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{app7.scala}}} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -{\lstset{language=Scala}\fontsize{10}{12}\selectfont -\texttt{\lstinputlisting{app8.scala}}} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}} - -Which languages are recognised by the following two grammars? +\begin{frame}[t] +\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}} \begin{center} -\bl{\begin{tabular}{lcl} -$S$ & $\rightarrow$ & $1 \cdot S \cdot S$\\ - & $|$ & $\epsilon$ -\end{tabular}} -\end{center}\bigskip - -\begin{center} -\bl{\begin{tabular}{lcl} -$U$ & $\rightarrow$ & $1 \cdot U$\\ - & $|$ & $\epsilon$ -\end{tabular}} +\begin{tikzpicture} +\begin{axis}[axis x line=bottom, axis y line=left, xlabel=n, ylabel=mins] +\addplot file {compiled.data}; +\end{axis} +\end{tikzpicture} \end{center} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[t] -\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}} +\frametitle{\begin{tabular}{c}Compiled vs.~Interpreted Code\end{tabular}} \mbox{}\\[-25mm]\mbox{} \begin{center} -\begin{tikzpicture}[y=.2cm, x=.009cm] +\begin{tikzpicture}[y=.4cm, x=.00000009cm] %axis - \draw (0,0) -- coordinate (x axis mid) (1000,0); - \draw (0,0) -- coordinate (y axis mid) (0,30); + \draw (0,0) -- coordinate (x axis mid) (5,0); + \draw (0,0) -- coordinate (y axis mid) (0,5); %ticks - \foreach \x in {0, 20, 100, 200,...,1000} + \foreach \x in {0, 1000,...,10000} \draw (\x,1pt) -- (\x,-3pt) - node[anchor=north] {\small \x}; - \foreach \y in {0,5,...,30} + node[anchor=north] {\small \x{}00}; + \foreach \y in {0,0.5,1, ..., 5.5} \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\small\y}; %labels @@ -585,88 +542,29 @@ \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; %plots - \draw[color=blue] plot[mark=*, mark options={fill=white}] - file {s-grammar1.data}; - \only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] - file {s-grammar2.data};} + %\draw[color=blue] plot[mark=*, mark options={fill=white}] + % file {compiled.data}; + %\only<2->{\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] + % file {interpreted.data};} %legend - \begin{scope}[shift={(400,20)}] - \draw[color=blue] (0,0) -- - plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) - node[right]{\small unambiguous}; - \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 ambiguous};} - \end{scope} + %\begin{scope}[shift={(400,20)}] + %\draw[color=blue] (0,0) -- + % plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) + % node[right]{\small unambiguous}; + %\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 ambiguous};} + %\end{scope} \end{tikzpicture} \end{center} \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}What about Left-Recursion?\end{tabular}} - -\begin{itemize} -\item we record when we recursively called a parser\bigskip -\item whenever the is a recursion, the parser must have consumed something --- so -we can decrease the input string/list of token by one (at the end) -\end{itemize} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}While-Language\end{tabular}} -\begin{center} -\bl{\begin{tabular}{@{}lcl@{}} -$Stmt$ & $\rightarrow$ & $\text{skip}$\\ - & $|$ & $Id := AExp$\\ - & $|$ & $\text{if}\; B\!Exp \;\text{then}\; Block \;\text{else}\; Block$\\ - & $|$ & $\text{while}\; B\!Exp \;\text{do}\; Block$\medskip\\ -$Stmts$ & $\rightarrow$ & $Stmt \;\text{;}\; Stmts$\\ - & $|$ & $Stmt$\medskip\\ -$Block$ & $\rightarrow$ & $\{ Stmts \}$\\ - & $|$ & $Stmt$\medskip\\ -$AExp$ & $\rightarrow$ & \ldots\\ -$BExp$ & $\rightarrow$ & \ldots\\ -\end{tabular}} -\end{center} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}An Interpreter\end{tabular}} - -\begin{center} -\bl{\begin{tabular}{l} -$\{$\\ -\;\;$x := 5 \text{;}$\\ -\;\;$y := x * 3\text{;}$\\ -\;\;$y := x * 4\text{;}$\\ -\;\;$x := u * 3$\\ -$\}$ -\end{tabular}} -\end{center} - -\begin{itemize} -\item the interpreter has to record the value of \bl{$x$} before assigning a value to \bl{$y$}\pause -\item \bl{\text{eval}(stmt, env)} -\end{itemize} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - \end{document} %%% Local Variables: