Mercurial Mercurial > hg > afl-material / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
slides/slides05.tex
changeset 582 d236e75e1d55
parent 550 71fc4a7a7039
child 583 200d2a3eb1b1
equal deleted inserted replaced
581:19de761b69e9 582:d236e75e1d55 
       
     1 
     1 \documentclass[dvipsnames,14pt,t]{beamer}
 
     2 \documentclass[dvipsnames,14pt,t]{beamer}
 
     2 \usepackage{../slides}
 
     3 \usepackage{../slides}
 
     3 \usepackage{../graphics}
 
     4 \usepackage{../graphics}
 
     4 \usepackage{../langs}
 
     5 \usepackage{../langs}
 
     5 \usepackage{../data}
 
     6 \usepackage{../data}
 
    28 
    29 
    29   \normalsize
 
    30   \normalsize
 
    30   \begin{center}
 
    31   \begin{center}
 
    31   \begin{tabular}{ll}
 
    32   \begin{tabular}{ll}
 
    32   Email:  & christian.urban at kcl.ac.uk\\
 
    33   Email:  & christian.urban at kcl.ac.uk\\
 
    33   Office: & N7.07 (North Wing, Bush House)\\
 
    34   Office: & N\liningnums{7.07} (North Wing, Bush House)\\
 
    34   Slides: & KEATS (also home work is there)\\
 
    35   Slides: & KEATS (also home work is there)\\
 
    35   \end{tabular}
 
    36   \end{tabular}
 
    36   \end{center}
 
    37   \end{center}
 
    37 \end{frame}
 
    38 \end{frame}
 
    38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
    39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
   369 \end{frame}
 
   370 \end{frame}
 
   370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   371 
   372 
   372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   373 \begin{frame}[c]
 
   374 \begin{frame}[c]
 
       
   375 \frametitle{Coursework: PLs (16)}
 
       
   376 
       
   377 \begin{itemize}
 
       
   378 \item Java (16)
 
       
   379 \item C++, C, C\# (14)
 
       
   380 \item JavaScript (10)
 
       
   381 \item Scala (9)
 
       
   382 \item Python (9)  
       
   383 \item PHP (6)
 
       
   384 \item Haskell (3)
 
       
   385 \item Ruby (4)
 
       
   386 \item Bash, Perl, Powershell (2)
 
       
   387 \item TypeScript (1)
 
       
   388 \item R (1)
 
       
   389 \item Coconut (1)  
       
   390 \item Pascal (1)
 
       
   391 \end{itemize}  
       
   392 
       
   393 \end{frame}
 
       
   394 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
       
   395 
       
   396 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
       
   397 \begin{frame}[c]
 
   374 \frametitle{Coursework: Nullable}
 
   398 \frametitle{Coursework: Nullable}
 
   375 
   399 
   376 \begin{center}
 
   400 \begin{center}
 
   377 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
 
   401 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
 
   378   \bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 
   402   \bl{$nullable([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 
   398 \begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
 
   422 \begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}}
 
   399   \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 
   423   \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$}  & \bl{$\dn$} & $?$\\
 
   400   \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\
 
   424   \bl{$der\, c\, (r^+)$}                   & \bl{$\dn$} & $?$\\
 
   401   \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\
 
   425   \bl{$der\, c\, (r^?)$}                   & \bl{$\dn$} & $?$\\
 
   402   \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &
 
   426   \bl{$der\, c\, (r^{\{n\}})$}              & \bl{$\dn$} &
 
   403      \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-1\}}$}\\
 
   427      \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-\liningnums{1}\}}$}\\
 
   404   \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &
 
   428   \bl{$der\, c\, (r^{\{n..\}})$}            & \bl{$\dn$} &
 
   405      \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
 
   429      \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\
 
   406   & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-1..\}}$}\\
 
   430   & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..\}}$}\\
 
   407   \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &
 
   431   \bl{$der\, c\, (r^{\{..n\}})$}            & \bl{$\dn$} &
 
   408      \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-1\}}$}\\
 
   432      \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-\liningnums{1}\}}$}\\
 
   409   
   433   
   410   \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &
 
   434   \bl{$der\, c\, (r^{\{n..m\}})$}          & \bl{$\dn$} &
 
   411      \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
 
   435      \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\
 
   412   \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-1\}}$}}\\
 
   436   \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-\liningnums{1}\}}$}}\\
 
   413   \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
 
   437   \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else
 
   414           \;(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}}\\
 
   438           \;(der\,c\,r)\cdot r^{\{n-\liningnums{1}..m-\liningnums{1}\}}$}}\\
 
   415   \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\
 
   439   \bl{$der\, c\, (\sim{}r)$}              & \bl{$\dn$} & $?$\\
 
   416 \end{tabular}
 
   440 \end{tabular}
 
   417 \end{center}
 
   441 \end{center}
 
   418 
   442 
   419 \end{frame}
 
   443 \end{frame}
 
   434 \end{tabular}
 
   458 \end{tabular}
 
   435 \end{center}
 
   459 \end{center}
 
   436 
   460 
   437 \end{frame}
 
   461 \end{frame}
 
   438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   439 
   463  
   440 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   441 \begin{frame}[t]
 
   465 \begin{frame}[t]
 
   442 \frametitle{Lexer, Parser}
 
   466 \frametitle{Lexer, Parser}
 
   443 \mbox{}\\[-16mm]\mbox{}
 
   467 \mbox{}\\[-16mm]\mbox{}
 
   444 
   468 
   566 
   590 
   567 \end{frame}
 
   591 \end{frame}
 
   568 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   592 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   569 
   593 
   570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   594 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   571 \begin{frame}[c]
 
   595 \begin{frame}[t]
 
   572 \frametitle{Palindromes}
 
   596 \frametitle{Palindromes}
 
   573 
   597 
   574 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
 
   598 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}:
 
   575 
   599 
   576 \bl{\begin{plstx}[margin=3cm]
 
   600 \bl{\begin{plstx}[margin=3cm]
 
   614 
   638 
   615 \begin{enumerate}
 
   639 \begin{enumerate}
 
   616 \item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
 
   640 \item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip
 
   617 \item Replace any nonterminal \bl{\meta{X}} in the string by the
 
   641 \item Replace any nonterminal \bl{\meta{X}} in the string by the
 
   618 right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
 
   642 right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip
 
   619 \item Repeat 2 until there are no nonterminals
 
   643 \item Repeat 2 until there are no nonterminals left
 
   620 \end{enumerate}
 
   644 \end{enumerate}
 
   621 
   645 
   622 \begin{center}
 
   646 \begin{center}
 
   623 \bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}
 
   647 \bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots  \rightarrow \ldots  \rightarrow \ldots $}
 
   624 \end{center}
 
   648 \end{center}
 
   724 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   725 
   749 
   726 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   727 \begin{frame}[t]
 
   751 \begin{frame}[t]
 
   728 \frametitle{Parse Trees}
 
   752 \frametitle{Parse Trees}
 
   729 \mbox{}\\[-16mm]
 
   753 \mbox{}\\[-12mm]
 
   730 
   754 
   731 \bl{\begin{plstx}: \meta{E} ::= \meta{F} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\
 
   755 \bl{\begin{plstx}: \meta{E} ::= \meta{F} | \meta{T} \cdot + \cdot \meta{E} |  \meta{T} \cdot - \cdot \meta{E}\\
 
   732 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
 
   756 : \meta{T} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{T}\\
 
   733 : \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\
 
   757 : \meta{F} ::= num\_token | ( \cdot \meta{E} \cdot )\\
 
   734 \end{plstx}}
 
   758 \end{plstx}}
 
   803 \end{frame}
 
   827 \end{frame}
 
   804 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   828 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   805 
   829 
   806 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   830 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   807 \begin{frame}[c]
 
   831 \begin{frame}[c]
 
   808 \frametitle{Dangling Else}
 
   832 \frametitle{`Dangling' Else}
 
   809 
   833 
   810 Another ambiguous grammar:\bigskip
 
   834 Another ambiguous grammar:\bigskip
 
   811 
   835 
   812 \begin{center}
 
   836 \begin{center}
 
   813 \bl{\begin{tabular}{lcl}
 
   837 \bl{\begin{tabular}{lcl}
 
   936 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
 
   960 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}
 
   937 
   961 
   938 Addition
 
   962 Addition
 
   939 
   963 
   940 \begin{center}
 
   964 \begin{center}
 
   941 \bl{$T \sim + \sim E \Rightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
 
   965 \bl{$\meta{T} \sim + \sim \meta{E} \Rightarrow \underbrace{f\,((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}
 
   942 \end{center}\pause
 
   966 \end{center}\pause
 
   943 
   967 
   944 Multiplication
 
   968 Multiplication
 
   945 
   969 
   946 \begin{center}
 
   970 \begin{center}
 
   947 \bl{$F \sim * \sim T \Rightarrow f((x,y), z) \Rightarrow x * z$}
 
   971 \bl{$\meta{F} \sim * \sim \meta{T} \Rightarrow f\,((x,y), z) \Rightarrow x * z$}
 
   948 \end{center}\pause
 
   972 \end{center}\pause
 
   949 
   973 
   950 Parenthesis
 
   974 Parenthesis
 
   951 
   975 
   952 \begin{center}
 
   976 \begin{center}
 
   953 \bl{$\text{(} \sim E \sim \text{)} \Rightarrow f((x,y), z) \Rightarrow y$}
 
   977 \bl{$\text{(} \sim \meta{E} \sim \text{)} \Rightarrow f\,((x,y), z) \Rightarrow y$}
 
   954 \end{center}
 
   978 \end{center}
 
   955 
   979 
   956 \end{frame}}
 
   980 \end{frame}}
 
   957 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   981 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   958 
   982 
  1060 
  1084 
  1061 Which languages are recognised by the following two grammars?
 
  1085 Which languages are recognised by the following two grammars?
 
  1062 
  1086 
  1063 \begin{center}
 
  1087 \begin{center}
 
  1064 \bl{\begin{tabular}{lcl}
 
  1088 \bl{\begin{tabular}{lcl}
 
  1065 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
 
  1089 $\meta{S}$ & $\rightarrow$ &  $1 \cdot \meta{S} \cdot \meta{S}$\\
 
  1066         & $|$ & $\epsilon$
 
  1090         & $|$ & $\epsilon$
 
  1067 \end{tabular}}
 
  1091 \end{tabular}}
 
  1068 \end{center}\bigskip
 
  1092 \end{center}\bigskip
 
  1069 
  1093 
  1070 \begin{center}
 
  1094 \begin{center}
 
  1071 \bl{\begin{tabular}{lcl}
 
  1095 \bl{\begin{tabular}{lcl}
 
  1072 $U$ & $\rightarrow$ &  $1 \cdot U$\\
 
  1096 $\meta{U}$ & $\rightarrow$ &  $1 \cdot \meta{U}$\\
 
  1073         & $|$ & $\epsilon$
 
  1097         & $|$ & $\epsilon$
 
  1074 \end{tabular}}
 
  1098 \end{tabular}}
 
  1075 \end{center}
 
  1099 \end{center}
 
  1076 
  1100 
  1077 \end{frame}
 
  1101 \end{frame}
 
  1197 \end{frame}}
 
  1221 \end{frame}}
 
  1198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
  1222 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
  1199 
  1223 
  1200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
  1224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
  1201 \begin{frame}[c]
 
  1225 \begin{frame}[c]
 
  1202 \frametitle{\begin{tabular}{c}Test Program\end{tabular}}
 
  1226 \frametitle{Test Program}
 
  1203 
  1227 
  1204 \mbox{}\\[-18mm]\mbox{}
 
  1228 \mbox{}\\[-18mm]\mbox{}
 
  1205 
  1229 
  1206 {\lstset{language=While}%%\fontsize{10}{12}\selectfont
 
  1230 {\lstset{language=While}%%\fontsize{10}{12}\selectfont
 
  1207 \texttt{\lstinputlisting{../progs/loops.while}}}
 
  1231 \texttt{\lstinputlisting{../progs/loops.while}}}
afl-material