\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.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+ −
\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+ −
\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}\pause+ −
+ − Now 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}\pause+ −
+ − Multiplication+ −
+ − \begin{center}+ −
\bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}+ −
\end{center}\pause+ −
+ − Parenthesis+ −
+ − \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\pause+ −
+ − actually 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}\bigskip+ −
+ − but 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}\bigskip+ −
+ − a parse is successful whenever the input has been+ −
fully ``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 --- so+ −
we 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: + −
+ −