154 \frametitle{\begin{tabular}{c}Building a Web Browser\end{tabular}}

   155 

   156 Using a lexer: assume the following regular expressions

   157 

   158 \begin{center}

   159 \bl{\begin{tabular}{lcl}

   160 $SY\!M$ & $\dn$ & $(\text{a}..\text{zA}..\text{Z0}..\text{9}..)$\\

   161 $W\!O\!RD$ & $\dn$ & $SY\!M^+$\\

   162 $BT\!AG$ & $\dn$ & $<\!W\!O\!RD\!>$\\

   163 $ET\!AG$ & $\dn$ & $<\!/W\!O\!RD\!>$\\

   164 $W\!HIT\!E$ & $\dn$ & $\texttt{" "} + \texttt{"}\slash{}n\texttt{"}$\\

   165 \end{tabular}}

   166 \end{center}

   167 

   168 \end{frame}}

   169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   170 

   171 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   172 \mode<presentation>{

   173 \begin{frame}[c]

   174 \frametitle{\begin{tabular}{c}Interpreting a List of Token\end{tabular}}

   175 

   176 \begin{itemize}

   177 \item text should be formatted consistently up to a specified width, say 60 characters 

   178 \item potential linebreaks are inserted by the formatter

   179 \item repeated whitespaces are ``condensed'' to a single whitepace

   180 \item \bl{$<\!p\!>$} \bl{$<\!\slash{}p\!>$}  start/end paragraph

   181 \item \bl{$<\!b\!>$} \bl{$<\!\slash{}b\!>$}  start/end bold

   182 \item \bl{$<\!red\!>$} \bl{$<\!\slash{}red\!>$}  start/end red (cyan, etc)

   183 

   184 

   185 \end{itemize}

   186 

   187 \end{frame}}

   188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   189 

   190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   191 \mode<presentation>{

   192 \begin{frame}[c]

   193 \frametitle{\begin{tabular}{c}Interpreting a List of Token\end{tabular}}

   194 

   195 The lexer cannot prevent errors like

   196 

   197 \begin{center}

   198 \bl{$<\!b\!>$} \ldots \bl{$<\!p\!>$} \ldots \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!\slash{}p\!>$} 

   199 \end{center}

   200 

   201 or

   202 

   203 \begin{center}

   204 \bl{$<\!\slash{}b\!>$} \ldots \bl{$<\!b\!>$}

   205 \end{center}

   206 

   207 

   208 \end{frame}}

   209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   210 

   211 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   212 \mode<presentation>{

   213 \begin{frame}[c]

   214 \frametitle{\begin{tabular}{c}Parser Combinators\end{tabular}}

   215 

   216 Parser combinators: \bigskip

   217 

   218 \begin{minipage}{1.1\textwidth}

   219 \begin{center}

   220 \mbox{}\hspace{-12mm}\mbox{}$\underbrace{\text{list of tokens}}_{\text{input}}$ \bl{$\Rightarrow$} 

   221 $\underbrace{\text{set of (parsed input, unparsed input)}}_{\text{output}}$

   222 \end{center}

   223 \end{minipage}\bigskip

   224 

   225 \begin{itemize}

   226 \item sequencing

   227 \item alternative

   228 \item semantic action

   229 \end{itemize}

   230 

   231 \end{frame}}

   232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   233 

   234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   235 \mode<presentation>{

   236 \begin{frame}[c]

   237 

   238 Alternative parser (code \bl{$p\;||\;q$})\bigskip

   239 

   240 \begin{itemize}

   241 \item apply \bl{$p$} and also \bl{$q$}; then combine the outputs

   242 \end{itemize}

   243 

   244 \begin{center}

   245 \large \bl{$p(\text{input}) \cup q(\text{input})$}

   246 \end{center}

   247 

   248 

   249 \end{frame}}

   250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   251 

   252 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   253 \mode<presentation>{

   254 \begin{frame}[c]

   255 

   256 Sequence parser (code \bl{$p\sim q$})\bigskip

   257 

   258 \begin{itemize}

   259 \item apply \bl{$p$} first producing a set of pairs

   260 \item then apply \bl{$q$} to the unparsed parts

   261 \item the combine the results:\\ \mbox{}\;\;((input$_1$, input$_2$), unparsed part)

   262 \end{itemize}

   263 

   264 \begin{center}

   265 \begin{tabular}{l}

   266 \large \bl{$\{((o_1, o_2), u_2) \;|\;$}\\[2mm] 

   267 \large\mbox{}\hspace{15mm} \bl{$(o_1, u_1) \in p(\text{input}) \wedge$}\\[2mm]

   268 \large\mbox{}\hspace{15mm} \bl{$(o_2, u_2) \in q(u_1)\}$}

   269 \end{tabular}

   270 \end{center}

   271 

   272 

   273 \end{frame}}

   274 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   275 

   276 

   277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   278 \mode<presentation>{

   279 \begin{frame}[c]

   280 

   281 Function parser (code \bl{$p \Longrightarrow f$})\bigskip

   282 

   283 \begin{itemize}

   284 \item apply \bl{$p$} producing a set of pairs

   285 \item then apply the function \bl{$f$} to each fist component

   286 \end{itemize}

   287 

   288 \begin{center}

   289 \begin{tabular}{l}

   290 \large \bl{$\{(f(o_1), u_1) \;|\; (o_1, u_1) \in p(\text{input})\}$}

   291 \end{tabular}

   292 \end{center}

   293 

   294 

   295 \end{frame}}

   296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   297 

   298 

   299 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   300 \mode<presentation>{

   301 \begin{frame}[c]

   302 

   303 Token parser:\bigskip

   304 

   305 \begin{itemize}

   306 \item if the input is

   307 

   308 \begin{center}

   309 \large \bl{$tok_1:: tok_2 :: \ldots :: tok_n$}

   310 \end{center}

   311 

   312 then return

   313 

   314 \begin{center}

   315 \large \bl{$\{(tok_1,\; tok_2 :: \ldots :: tok_n)\}$}

   316 \end{center}

   317 

   318 or

   319 

   320 \begin{center}

   321 \large \bl{$\{\}$}

   322 \end{center}

   323 

   324 if \bl{$tok_1$} is not the right token we are looking for

   325 \end{itemize}

   326 

   327 

   328 

   329 \end{frame}}

   330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   331 

   332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   333 \mode<presentation>{

   334 \begin{frame}[c]

   335 

   336 Number-Token parser:\bigskip

   337 

   338 \begin{itemize}

   339 \item if the input is

   340 

   341 \begin{center}

   342 \large \bl{$num\_tok(42):: tok_2 :: \ldots :: tok_n$}

   343 \end{center}

   344 

   345 then return

   346 

   347 \begin{center}

   348 \large \bl{$\{(42,\; tok_2 :: \ldots :: tok_n)\}$}

   349 \end{center}

   350 

   351 or

   352 

   353 \begin{center}

   354 \large \bl{$\{\}$}

   355 \end{center}

   356 

   357 if \bl{$tok_1$} is not the right token we are looking for

   358 \end{itemize}\pause

   359 

   360 \begin{center}

   361 list of tokens \bl{$\Rightarrow$} set of (\alert{int}, list of tokens)

   362 \end{center}

   363 

   364 \end{frame}}

   365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   366 

   367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   368 \mode<presentation>{

   369 \begin{frame}[c]

   370 

   371 \begin{itemize}

   372 \item if the input is

   373 

   374 \begin{center}

   375 \begin{tabular}{l}

   376 \large \bl{$num\_tok(42)::$}\\

   377 \hspace{7mm}\large \bl{$num\_tok(3) ::$}\\

   378 \hspace{14mm}\large \bl{$tok_3 :: \ldots :: tok_n$}

   379 \end{tabular}

   380 \end{center}

   381 

   382 and the parser is 

   383 

   384 \begin{center}

   385 \bl{$ntp \sim ntp$}

   386 \end{center}

   387 

   388 the successful output will be

   389 

   390 \begin{center}

   391 \large \bl{$\{((42, 3),\; tok_2 :: \ldots :: tok_n)\}$}

   392 \end{center}\pause

   393 

   394 Now we can form

   395 \begin{center}

   396 \bl{$(ntp \sim ntp) \Longrightarrow f$}

   397 \end{center}

   398 

   399 where \bl{$f$} is the semantic action (what to do with the pair)

   400 

   401 \end{itemize}

   402 

   403 \end{frame}}

   404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   405 

   406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   407 \mode<presentation>{

   408 \begin{frame}[c]

   409 \frametitle{\begin{tabular}{c}Semantic Actions\end{tabular}}

   410 

   411 Addition

   412 

   413 \begin{center}

   414 \bl{$T \sim + \sim E \Longrightarrow \underbrace{f((x,y), z) \Rightarrow x + z}_{\text{semantic action}}$}

   415 \end{center}\pause

   416 

   417 Multiplication

   418 

   419 \begin{center}

   420 \bl{$F \sim * \sim T \Longrightarrow f((x,y), z) \Rightarrow x * z$}

   421 \end{center}\pause

   422 

   423 Parenthesis

   424 

   425 \begin{center}

   426 \bl{$\text{(} \sim E \sim \text{)} \Longrightarrow f((x,y), z) \Rightarrow y$}

   427 \end{center}

   428 

   429 \end{frame}}

   430 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   431 

   432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   433 \mode<presentation>{

   434 \begin{frame}[c]

   435 \frametitle{\begin{tabular}{c}Types of Parsers\end{tabular}}

   436 

   437 \begin{itemize}

   438 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},

   439 then \bl{$p \sim q$} returns results of type

   440 

   441 \begin{center}

   442 \bl{$T \times S$}

   443 \end{center}\pause

   444 

   445 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},

   446 and \bl{$p \;||\; q$} returns results of type

   447 

   448 \begin{center}

   449 \bl{$T$}

   450 \end{center}\pause

   451 

   452 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from

   453 \bl{$T$} to \bl{$S$}, then

   454 \bl{$p \Longrightarrow f$} returns results of type

   455 

   456 \begin{center}

   457 \bl{$S$}

   458 \end{center}

   459 

   460 \end{itemize}

   461 

   462 \end{frame}}

   463 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   464 

   465 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   466 \mode<presentation>{

   467 \begin{frame}[c]

   468 \frametitle{\begin{tabular}{c}Input Types of Parsers\end{tabular}}

   469 

   470 \begin{itemize}

   471 \item input: \alert{list of tokens}

   472 \item output: set of (output\_type, \alert{list of tokens})

   473 \end{itemize}\bigskip\pause

   474 

   475 actually it can be any input type as long as it is a kind of sequence

   476 (for example a string)

   477 

   478 \end{frame}}

   479 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   480 

   481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   482 \mode<presentation>{

   483 \begin{frame}[c]

   484 {\lstset{language=Scala}\fontsize{10}{12}\selectfont

   485 \texttt{\lstinputlisting{app7.scala}}}

   486 \end{frame}}

   487 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   488 

   489 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   490 \mode<presentation>{

   491 \begin{frame}[c]

   492 {\lstset{language=Scala}\fontsize{10}{12}\selectfont

   493 \texttt{\lstinputlisting{app7.scala}}}

   494 \end{frame}}

   495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   496 

   497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   498 \mode<presentation>{

   499 \begin{frame}[c]

   500 {\lstset{language=Scala}\fontsize{10}{12}\selectfont

   501 \texttt{\lstinputlisting{app8.scala}}}

   502 \end{frame}}

   503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   504 

   505 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   506 \mode<presentation>{

   507 \begin{frame}[c]