195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   196 \mode<presentation>{

   197 \begin{frame}[c]

   198 \frametitle{\begin{tabular}{c}Interpreting a List of Tokens\end{tabular}}

   199 

   200 The lexer cannot prevent errors like

   201 

   202 \begin{center}

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

   204 \end{center}

   205 

   206 or

   207 

   208 \begin{center}

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

   210 \end{center}

   211 

   212 

   213 \end{frame}}

   214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   215 

   216 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   217 \mode<presentation>{

   218 \begin{frame}[c]

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

   220 

   221 Parser combinators: \bigskip

   222 

   223 \begin{minipage}{1.1\textwidth}

   224 \begin{center}

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

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

   227 \end{center}

   228 \end{minipage}\bigskip

   229 

   230 \begin{itemize}

   231 \item sequencing

   232 \item alternative

   233 \item semantic action

   234 \end{itemize}

   235 

   236 \end{frame}}

   237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   238 

   239 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   240 \mode<presentation>{

   241 \begin{frame}[c]

   242 

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

   244 

   245 \begin{itemize}

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

   247 \end{itemize}

   248 

   249 \begin{center}

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

   251 \end{center}

   252 

   253 

   254 \end{frame}}

   255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   256 

   257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   258 \mode<presentation>{

   259 \begin{frame}[c]

   260 

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

   262 

   263 \begin{itemize}

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

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

   266 \item then combine the results:\\ \mbox{}\;\;((output$_1$, output$_2$), unparsed part)

   267 \end{itemize}

   268 

   269 \begin{center}

   270 \begin{tabular}{l}

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

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

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

   274 \end{tabular}

   275 \end{center}

   276 

   277 

   278 \end{frame}}

   279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   280 

   281 

   282 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   283 \mode<presentation>{

   284 \begin{frame}[c]

   285 

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

   287 

   288 \begin{itemize}

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

   290 \item then apply the function \bl{$f$} to each first component

   291 \end{itemize}

   292 

   293 \begin{center}

   294 \begin{tabular}{l}

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

   296 \end{tabular}

   297 \end{center}\bigskip\bigskip\pause

   298 

   299 \bl{$f$} is the semantic action (``what to do with the parsed input'')

   300 

   301 \end{frame}}

   302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   303 

   304 

   305 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   306 \mode<presentation>{

   307 \begin{frame}[c]

   308 

   309 Token parser:\bigskip

   310 

   311 \begin{itemize}

   312 \item if the input is

   313 

   314 \begin{center}

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

   316 \end{center}

   317 

   318 then return

   319 

   320 \begin{center}

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

   322 \end{center}

   323 

   324 or

   325 

   326 \begin{center}

   327 \large \bl{$\{\}$}

   328 \end{center}

   329 

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

   331 \end{itemize}

   332 

   333 

   334 

   335 \end{frame}}

   336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   337 

   338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   339 \mode<presentation>{

   340 \begin{frame}[c]

   341 

   342 Number-Token parser:\bigskip

   343 

   344 \begin{itemize}

   345 \item if the input is

   346 

   347 \begin{center}

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

   349 \end{center}

   350 

   351 then return

   352 

   353 \begin{center}

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

   355 \end{center}

   356 

   357 or

   358 

   359 \begin{center}

   360 \large \bl{$\{\}$}

   361 \end{center}

   362 

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

   364 \end{itemize}\pause

   365 

   366 \begin{center}

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

   368 \end{center}

   369 

   370 \end{frame}}

   371 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   372 

   373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   374 \mode<presentation>{

   375 \begin{frame}[c]

   376 

   377 \begin{itemize}

   378 \item if the input is

   379 

   380 \begin{center}

   381 \begin{tabular}{l}

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

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

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

   385 \end{tabular}

   386 \end{center}

   387 

   388 and the parser is 

   389 

   390 \begin{center}

   391 \bl{$ntp \sim ntp$}

   392 \end{center}

   393 

   394 the successful output will be

   395 

   396 \begin{center}

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

   398 \end{center}\pause

   399 

   400 Now we can form

   401 \begin{center}

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

   403 \end{center}

   404 

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

   406 

   407 \end{itemize}

   408 

   409 \end{frame}}

   410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 

   411 

   412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   413 \mode<presentation>{

   414 \begin{frame}[c]

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

   416 

   417 Addition

   418 

   419 \begin{center}

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

   421 \end{center}\pause

   422 

   423 Multiplication

   424 

   425 \begin{center}

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

   427 \end{center}\pause

   428 

   429 Parenthesis

   430 

   431 \begin{center}

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

   433 \end{center}

   434 

   435 \end{frame}}

   436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   437 

   438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   439 \mode<presentation>{

   440 \begin{frame}[c]

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

   442 

   443 \begin{itemize}

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

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

   446 

   447 \begin{center}

   448 \bl{$T \times S$}

   449 \end{center}\pause

   450 

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

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

   453 

   454 \begin{center}

   455 \bl{$T$}

   456 \end{center}\pause

   457 

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

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

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

   461 

   462 \begin{center}

   463 \bl{$S$}

   464 \end{center}

   465 

   466 \end{itemize}

   467 

   468 \end{frame}}

   469 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   470 

   471 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   472 \mode<presentation>{

   473 \begin{frame}[c]

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

   475 

   476 \begin{itemize}

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

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

   479 \end{itemize}\bigskip\pause

   480 

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

   482 (for example a string)

   483 

   484 \end{frame}}

   485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

   486 

   487 

   488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   489 \mode<presentation>{

   490 \begin{frame}[c]

   491 \frametitle{\begin{tabular}{c}Scannerless Parsers\end{tabular}}

   492 

   493 \begin{itemize}

   494 \item input: \alert{string}

   495 \item output: set of (output\_type, \alert{string})

   496 \end{itemize}\bigskip

   497 

   498 but lexers are better when whitespaces or comments need to be filtered out

   499 

   500 \end{frame}}

   501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%