afl-material: comparison slides/slides07.tex

equal deleted inserted replaced

-:fab34204d08e
+:9471a0325773
 	numbersep=10pt,
 	tabsize=2,
 	showspaces=false,
 	showstringspaces=false}
+\setmonofont{Consolas}
 % beamer stuff
 \renewcommand{\slidecaption}{AFL 07, King's College London, 13.~November 2013}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}
 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
 $N$ & $\rightarrow$ & $N \cdot N \;|\; 0 \;|\; 1 \;|\: \ldots \;|\; 9$
 \end{tabular}}
 \end{center}
-Unfortunately left-recursive (and ambiguous).\medskip\\
+Unfortunately it is left-recursive (and ambiguous).\medskip\\
 A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
 \bigskip\pause
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \bl{\begin{tabular}{lcl}
 $N$ & $\rightarrow$ &  $N \cdot N \;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
 \end{tabular}}
 \end{center}
-A non-left-recursive, non-ambiguous grammar for numbers
+A non-left-recursive, non-ambiguous grammar for numbers:
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $N$ & $\rightarrow$ &  $0 \cdot N \;|\;1 \cdot N \;|\;\ldots\;|\; 0 \;|\; 1 \;|\; \ldots \;|\; 9$\\
 \end{tabular}}
 \bl{\begin{tabular}{lcl}
 $E$ & $\rightarrow$ &  $E \cdot + \cdot E \;|\;E \cdot * \cdot E \;|\;( \cdot E \cdot ) \;|\;N$ \\
 \end{tabular}}
 \end{center}
-Decide how many precedence levels, say\medskip\\
+Decide on how many precedence levels, say\medskip\\
 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
 \begin{center}
 \bl{\begin{tabular}{lcl}
 $E_{low}$ & $\rightarrow$ & $E_{med} \cdot + \cdot E_{low} \;|\; E_{med}$ \\
 \small
 \begin{center}
 \begin{tabular}{ccc}
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\
+\\
+\\
+\\
+\\
+\\
 \end{tabular}} &
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+\\
 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
+\\
+$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\
 \end{tabular}}
 \end{tabular}
 \end{center}
+\pause\normalsize
+\begin{center}
+\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
+\end{tabular}}
+\end{center}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
+If grammar is in Chomsky normalform \ldots
-\begin{center}
-\bl{\begin{tabular}{@ {}lcl}
+\begin{center}
+\bl{\begin{tabular}{@ {}lcl@ {}}
 $S$ & $\rightarrow$ &  $N\cdot P$ \\
 $P$ & $\rightarrow$ &  $V\cdot N$ \\
 $N$ & $\rightarrow$ &  $N\cdot N$ \\
 $N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
 $V$ & $\rightarrow$ &  $\texttt{trains}$
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
 \begin{itemize}
+\item fastest possible algorithm for recognition problem
 \item runtime is \bl{$O(n^3)$}\bigskip
 \item grammars need to be transferred into CNF
 \end{itemize}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
+Recall that languages are sets of strings.
+\begin{center}
+\begin{tikzpicture}
+[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
+\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
+\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
+\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
+\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
+\draw (0,-1.4) node [rect] {regular languages};
+\end{tikzpicture}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Context Sensitive Grms\end{tabular}}
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\Rightarrow$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $\Rightarrow$ & $a$\\
+$bA$ & $\Rightarrow$ & $Ab$\\
+\end{tabular}}
+\end{center}\pause
+\begin{center}
+\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
+\begin{center}
+\begin{tabular}{@{}lcl@{}}
+\textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\
+& $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
+& $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
+& $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
+& $|$ & \texttt{read}\;\textit{Id}\\
+& $|$ & \texttt{write}\;\textit{Id}\\
+& $|$ & \texttt{write}\;\textit{String}\medskip\\
+\textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
+& $|$ & \textit{Stmt}\medskip\\
+\textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
+& $|$ & \textit{Stmt}\medskip\\
+\textit{AExp} & $\rightarrow$ & \ldots\\
+\textit{BExp} & $\rightarrow$ & \ldots\\
+\end{tabular}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

changeset 187	9471a0325773
parent 186	fab34204d08e
child 188	12ef150273ce