1063 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

  1064 

  1065 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1066 \begin{frame}[t]

  1067 \frametitle{Rectification Example}

  1068 

  1069 \begin{center}

  1070 \bl{$\only<1>{(b \cdot c)}%

  1071      \only<2-3>{(\underline{b \cdot c})}%

  1072      \only<1-3>{+}% 

  1073      \only<1>{(\ZERO + \ONE)}%

  1074      \only<2-3>{(\underline{\ZERO + \ONE})}$}%

  1075 \only<4->{%

  1076 \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}%

  1077 }

  1078 $\mapsto$

  1079 \bl{$(b \cdot c) + \ONE$}

  1080 \end{center}\bigskip

  1081 

  1082 \onslide<3->{%

  1083 \begin{center}

  1084 \begin{tabular}{lcl}

  1085 \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\

  1086 \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$}

  1087 \end{tabular}

  1088 \end{center}}

  1089 

  1090 \only<4>{%

  1091 \begin{center}

  1092 \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}

  1093 \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\

  1094 \quad \bl{$\lambda v.\,$} 

  1095         case \bl{$v = Left(v')$}: 

  1096       & return \bl{$Left(f_{s1}(v'))$}\\

  1097 \quad \phantom{$\lambda v.\,$} 

  1098         case \bl{$v = Right(v')$}: 

  1099       & return \bl{$Right(f_{s2}(v'))$}\\ 

  1100 \end{tabular}

  1101 \end{center}}%

  1102 \only<5->{%

  1103 \begin{center}

  1104 \begin{tabular}{@{}l@{\hspace{1mm}}l@{}}

  1105 \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\

  1106 \quad \bl{$\lambda v.\,$} 

  1107         case \bl{$v = Left(v')$}: 

  1108       & return \bl{$Left(v')$}\\

  1109 \quad \phantom{$\lambda v.\,$} 

  1110         case \bl{$v = Right(v')$}: 

  1111       & return \bl{$Right(Right(v'))$}\\ 

  1112 \end{tabular}

  1113 \end{center}}%

  1114 

  1115 \only<6->{%

  1116 \begin{center}

  1117 \begin{tabular}{@{}l@{\hspace{4mm}}l@{}}

  1118 \bl{$\textit{mkeps}$} simplified case: &

  1119 \bl{$\textit{Right}(\textit{Empty})$}\\

  1120 rectified case: &

  1121 \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$}

  1122 \end{tabular}

  1123 \end{center}}%

  1124 

  1125 \end{frame}

  1126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1170 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1171 \begin{frame}[c]

  1172 \frametitle{Environments}

  1173 

  1174 Obtaining the ``recorded'' parts of a value: 

  1175 

  1176 \begin{center}

  1177 \begin{tabular}{lcl}

  1178   \bl{$env(Empty)$}     & \bl{$\dn$} & \bl{$[]$}\\

  1179   \bl{$env(Char(c))$}   & \bl{$\dn$} & \bl{$[]$}\\

  1180   \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\

  1181   \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\

  1182   \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\

  1183   \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & 

  1184      \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\

  1185   \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\

  1186 \end{tabular}

  1187 \end{center}

  1188 

  1189 \end{frame}

  1190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1191 

  1192 

  1193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1194 \begin{frame}[c]

  1195 \frametitle{While Tokens}

  1196 

  1197 \begin{center}

  1198 \begin{tabular}{@{}r@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}

  1199 \pcode{WHILE\_REGS} & $\dn$ & \raisebox{-1mm}{\large(}\pcode{("k" : KEYWORD)} +\\ 

  1200                   &       & \phantom{(}\pcode{("i" : ID)} +\\ 

  1201                   &       & \phantom{(}\pcode{("o" : OP)} + \\

  1202                   &       & \phantom{(}\pcode{("n" : NUM)} + \\

  1203                   &       & \phantom{(}\pcode{("s" : SEMI)} +\\ 

  1204                   &       & \phantom{(}\pcode{("p" : (LPAREN + RPAREN))} +\\ 

  1205                   &       & \phantom{(}\pcode{("b" : (BEGIN + END))} +\\ 

  1206                   &       & \phantom{(}\pcode{("w" : WHITESPACE)}\raisebox{-1mm}{\large)$^*$}

  1207 \end{tabular}

  1208 \end{center}

  1209 

  1210 \end{frame}

  1211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

  1212 

  1213 

  1214 

  1215 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1216 \begin{frame}[t]

  1217 

  1218 \consolas

  1219 \begin{center}

  1220 \code{"if true then then 42 else +"}

  1221 \end{center}

  1222 

  1223 \only<1>{

  1224 \small\begin{tabular}{l}

  1225 KEYWORD(if),\\ 

  1226 WHITESPACE,\\ 

  1227 IDENT(true),\\ 

  1228 WHITESPACE,\\ 

  1229 KEYWORD(then),\\ 

  1230 WHITESPACE,\\ 

  1231 KEYWORD(then),\\ 

  1232 WHITESPACE,\\ 

  1233 NUM(42),\\ 

  1234 WHITESPACE,\\ 

  1235 KEYWORD(else),\\ 

  1236 WHITESPACE,\\ 

  1237 OP(+)

  1238 \end{tabular}}

  1239 

  1240 \only<2>{

  1241 \small\begin{tabular}{l}

  1242 KEYWORD(if),\\ 

  1243 IDENT(true),\\ 

  1244 KEYWORD(then),\\ 

  1245 KEYWORD(then),\\ 

  1246 NUM(42),\\ 

  1247 KEYWORD(else),\\ 

  1248 OP(+)

  1249 \end{tabular}}

  1250 

  1251 \end{frame}

  1252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1253 

  1254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1255 \begin{frame}[c]

  1256 \frametitle{Two Rules}

  1257 

  1258 \begin{itemize}

  1259 \item Longest match rule (``maximal munch rule''): The 

  1260 longest initial substring matched by any regular expression is taken

  1261 as next token.\bigskip

  1262 

  1263 \item Rule priority:

  1264 For a particular longest initial substring, the first regular

  1265 expression that can match determines the token.

  1266 

  1267 \end{itemize}

  1268 

  1269 %\url{http://www.technologyreview.com/tr10/?year=2011}

  1270   

  1271 %finite deterministic automata/ nondeterministic automaton

  1272 

  1273 %\item problem with infix operations, for example i-12

  1274 

  1275 

  1276 \end{frame}

  1277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

  1278 

  1279