\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 08, King's College London, 21.~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}{s-grammar1.data}1 0.0115251 0.07973101 0.09726151 0.09320201 0.10010251 0.16997301 0.26662351 0.46118401 0.62516451 0.87247501 1.16334551 1.71152601 2.10958651 2.44360701 2.98488751 3.50326801 4.11036851 4.93394901 5.77465951 7.39123\end{filecontents}\begin{filecontents}{s-grammar2.data}1 0.012802 0.000643 0.001734 0.003555 0.009656 0.026747 0.069538 0.111669 0.1870710 0.0918911 0.1272412 0.2433713 0.5930414 1.5359415 4.0119516 10.7358217 29.51587#18 73.14163\end{filecontents}\begin{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}<1>[t]\frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] \LARGE Automata and \\[-2mm] \LARGE Formal Languages (8)\\[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<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Building a ``Web Browser''\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{"}$\\\end{tabular}}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}\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{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}The lexer cannot prevent errors like\begin{center}\bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} \end{center}or\begin{center}\bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}Parser combinators: \bigskip\begin{minipage}{1.1\textwidth}\begin{center}\mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$\end{center}\end{minipage}\bigskip\begin{itemize}\item sequencing\item alternative\item semantic action\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Alternative parser (code \bl{$p\;||\;q$})\bigskip\begin{itemize}\item apply \bl{$p$} and also \bl{$q$}; then combine the outputs\end{itemize}\begin{center}\large \bl{$p(\text{input}) \cup q(\text{input})$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Sequence parser (code \bl{$p\sim q$})\bigskip\begin{itemize}\item apply first \bl{$p$} producing a set of pairs\item then apply \bl{$q$} to the unparsed parts\item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)\end{itemize}\begin{center}\begin{tabular}{l}\large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]\large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}\end{tabular}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Function parser (code \bl{$p \Longrightarrow f$})\bigskip\begin{itemize}\item apply \bl{$p$} producing a set of pairs\item then apply the function \bl{$f$} to each first component\end{itemize}\begin{center}\begin{tabular}{l}\large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}\end{tabular}\end{center}\bigskip\bigskip\pause\bl{$f$} is the semantic action (``what to do with the parsed input'')\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Token parser:\bigskip\begin{itemize}\item if the input is\begin{center}\large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}\end{center}then return\begin{center}\large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}\end{center}or\begin{center}\large \bl{$\{\}$}\end{center}if \bl{$tok_1$} is not the right token we are looking for\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]Number-Token parser:\bigskip\begin{itemize}\item if the input is\begin{center}\large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}\end{center}then return\begin{center}\large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}\end{center}or\begin{center}\large \bl{$\{\}$}\end{center}if \bl{$tok_1$} is not the right token we are looking for\end{itemize}\pause\begin{center}list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\begin{itemize}\item if the input is\begin{center}\begin{tabular}{l}\large \bl{$num\_tok(42)::$}\\\hspace{7mm}\large \bl{$num\_tok(3) ::$}\\\hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}\end{tabular}\end{center}and the parser is \begin{center}\bl{$ntp \sim ntp$}\end{center}the successful output will be\begin{center}\large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}\end{center}\pauseNow we can form\begin{center}\bl{$(ntp \sim ntp) \Longrightarrow f$}\end{center}where \bl{$f$} is the semantic action (``what to do with the pair'')\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}Addition\begin{center}\bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}\end{center}\pauseMultiplication\begin{center}\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}\end{center}\pauseParenthesis\begin{center}\bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}\begin{itemize}\item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},then \bl{$p \sim q$} returns results of type\begin{center}\bl{$T \times S$}\end{center}\pause\item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then \bl{$q$} \alert{must} also have results of type \bl{$T$},and \bl{$p \;||\; q$} returns results of type\begin{center}\bl{$T$}\end{center}\pause\item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from\bl{$T$} to \bl{$S$}, then\bl{$p \Longrightarrow f$} returns results of type\begin{center}\bl{$S$}\end{center}\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}\begin{itemize}\item input: \alert{list of tokens}\item output: set of (output\_type, \alert{list of tokens})\end{itemize}\bigskip\pauseactually it can be any input type as long as it is a kind of sequence(for example a string)\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}\begin{itemize}\item input: \alert{string}\item output: set of (output\_type, \alert{string})\end{itemize}\bigskipbut lexers are better when whitespaces or comments need to be filtered out\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\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}\bigskipa parse is successful whenever the input has beenfully ``consumed'' (that is the second component is empty)\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]{\lstset{language=Scala}\fontsize{10}{12}\selectfont\texttt{\lstinputlisting{app7.scala}}}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]{\lstset{language=Scala}\fontsize{10}{12}\selectfont\texttt{\lstinputlisting{app7.scala}}}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]{\lstset{language=Scala}\fontsize{10}{12}\selectfont\texttt{\lstinputlisting{app8.scala}}}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[c]\frametitle{\begin{tabular}{c}Two Grammars\end{tabular}}Which languages are recognised by the following two grammars?\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}}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\begin{frame}[t]\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}\mbox{}\\[-25mm]\mbox{}\begin{center}\begin{tikzpicture}[y=.2cm, x=.009cm] %axis \draw (0,0) -- coordinate (x axis mid) (1000,0); \draw (0,0) -- coordinate (y axis mid) (0,30); %ticks \foreach \x in {0, 20, 100, 200,...,1000} \draw (\x,1pt) -- (\x,-3pt) node[anchor=north] {\small \x}; \foreach \y in {0,5,...,30} \draw (1pt,\y) -- (-3pt,\y) node[anchor=east] {\small\y}; %labels \node[below=0.6cm] at (x axis mid) {\bl{1}s}; \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};} %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}\end{tikzpicture}\end{center}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\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 --- sowe can decrease the input string/list of token by one (at the end)\end{itemize}\end{frame}}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\mode<presentation>{\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<presentation>{\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: %%% mode: latex%%% TeX-master: t%%% End: