diff -r a7071c2a9446 -r dc2f5eb33a9a slides/slides05.tex --- a/slides/slides05.tex Sun Oct 20 15:24:22 2019 +0100 +++ b/slides/slides05.tex Wed Oct 23 21:39:11 2019 +0100 @@ -1,4 +1,5 @@ +% !TEX program = xelatex \documentclass[dvipsnames,14pt,t]{beamer} \usepackage{../slides} \usepackage{../graphics} @@ -30,30 +31,15 @@ \normalsize \begin{center} \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - Office: & N\liningnums{7.07} (North Wing, Bush House)\\ - Slides: & KEATS (also home work is there)\\ + Email: & christian.urban at kcl.ac.uk\\ + Office Hours: & Thursdays 12 -- 14\\ + Location: & N7.07 (North Wing, Bush House)\\ + Slides \& Progs: & KEATS (also homework is there)\\ \end{tabular} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% \begin{frame}[c] -% \frametitle{Survey: Thanks!} -% \small - -% \begin{itemize} -% \item {\bf My Voice} ``could be a bit louder'' -% \item {\bf Writing} ``sometimes a bit difficult to read'' -% \item {\bf Recording} ``video caps of blackboard'' -% \item ``It's all great'' -% \end{itemize} - -% \end{frame} -% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -83,7 +69,7 @@ & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ & \bl{$\mid$} & \bl{$Left(v)$} \\ & \bl{$\mid$} & \bl{$Right(v)$} \\ - & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\ + & \bl{$\mid$} & \bl{$Stars [v_1,\ldots\,v_n]$} \\ \end{tabular} \end{column} \end{columns} @@ -299,7 +285,7 @@ \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ - \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & + \bl{$env(Stars [v_1,\ldots ,v_n])$} & \bl{$\dn$} & \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ \end{tabular} @@ -372,93 +358,110 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Coursework: PLs (16)} +\frametitle{Coursework: Submissions} \begin{itemize} -\item Java (16) -\item C++, C, C\# (14) -\item JavaScript (10) -\item Scala (9) -\item Python (9) -\item PHP (6) -\item Haskell (3) -\item Ruby (4) -\item Bash, Perl, Powershell (2) -\item TypeScript (1) -\item R (1) -\item Coconut (1) -\item Pascal (1) -\end{itemize} +\item Scala (29) +\item Haskell (1) +\item Kotlin (1) +\item Rust (1) +\end{itemize}\bigskip +Please get in contact if you intend to do CW Strand 2. \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Coursework: Nullable} - -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} - \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ - \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ - -\end{tabular} -\end{center} - -\end{frame} +%\begin{frame}[c] +%\frametitle{Coursework: PLs (16)} +% +%\begin{itemize} +%\item Java (16) +%\item C++, C, C\# (14) +%\item JavaScript (10) +%\item Scala (9) +%\item Python (9) +%\item PHP (6) +%\item Haskell (3) +%\item Ruby (4) +%\item Bash, Perl, Powershell (2) +%\item TypeScript (1) +%\item R (1) +%\item Coconut (1) +%\item Pascal (1) +%\end{itemize} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -%%\frametitle{Coursework: der} - -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} - \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ - \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ - \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ - \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & - \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ - \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & - \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ - & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ - \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & - \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ - - \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & - \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ - \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ - \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else - \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ - \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ -\end{tabular} -\end{center} - -\end{frame} +%\begin{frame}[c] +%\frametitle{Coursework: Nullable} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ +% \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ +% +%\end{tabular} +%\end{center} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Coursework: CFUN} +%\begin{frame}[c] +%%%\frametitle{Coursework: der} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} +% \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ +% \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\ +% \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ +% & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\ +% \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & +% \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\ +% +% \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & +% \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ +% \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\ +% \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else +% \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\ +% \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ +%\end{tabular} +%\end{center} +% +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} - \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ - \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & - \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ - \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ - \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ - \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ -\end{tabular} -\end{center} - -\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[c] +%\frametitle{Coursework: CFUN} +% +%\begin{center} +%\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} +% \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ +% \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & +% \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ +% \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ +% \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ +% \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ +%\end{tabular} +%\end{center} +% +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -571,8 +574,8 @@ A \alert{\bf context-free grammar} \bl{$G$} consists of \begin{itemize} -\item a finite set of nonterminal symbols ($\langle$upper case$\rangle$) -\item a finite terminal symbols or tokens (lower case) +\item a finite set of nonterminal symbols (e.g.~$\meta{A}$ upper case) +\item a finite set terminal symbols or tokens (lower case) \item a start symbol (which must be a nonterminal) \item a set of rules \begin{center} @@ -709,8 +712,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\begin{tabular}{c}Context Sensitive\\[-1mm] - Grammars\end{tabular}} +\frametitle{Context Sensitive Grammars} It is much harder to find out whether a string is parsed by a context sensitive grammar: @@ -1036,9 +1038,9 @@ \begin{itemize} \item input: \alert{string} \item output: set of (output\_type, \alert{string}) -\end{itemize}\bigskip +\end{itemize}\bigskip\bigskip -but lexers are better when whitespaces or comments need to be +but using lexers is better because whitespaces or comments can be filtered out; then input is a sequence of tokens \end{frame}