376 \end{tikzpicture} |
376 \end{tikzpicture} |
377 \end{textblock} |
377 \end{textblock} |
378 |
378 |
379 \end{frame}} |
379 \end{frame}} |
380 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
380 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
381 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
382 \mode<presentation>{ |
|
383 \begin{frame}[c] |
|
384 |
|
385 \begin{tikzpicture}[scale=1] |
|
386 |
|
387 \draw[line width=1mm] (-.3, 0) rectangle (1.5,2); |
|
388 \draw (4.2,1) node {Code Gen}; |
|
389 \draw (0.6,1.7) node {\footnotesize Parser}; |
|
390 \draw (-2.7,1.7) node {\footnotesize Lexer}; |
|
391 |
|
392 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
|
393 |
|
394 \draw[white] (1.7,1) node (X) {}; |
|
395 \draw[white] (3.2,1) node (Y) {}; |
|
396 \draw[red, ->, line width = 2mm] (X) -- (Y); |
|
397 |
|
398 \draw[red, <-, line width = 2mm] (-0.6,1) -- (-1.6,1); |
|
399 \draw[red, <-, line width = 2mm] (-3.8,1) -- (-4.8,1); |
|
400 \end{tikzpicture} |
|
401 |
|
402 |
|
403 \end{frame}} |
|
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
381 |
405 |
382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
383 |
407 |
384 \mode<presentation>{ |
408 \mode<presentation>{ |
385 \begin{frame}[t] |
409 \begin{frame}[t] |
450 |
474 |
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
452 \mode<presentation>{ |
476 \mode<presentation>{ |
453 \begin{frame}[c] |
477 \begin{frame}[c] |
454 |
478 |
455 \begin{tikzpicture}[scale=1] |
479 |
456 |
480 There is one small problem with the tokenizer. How should we |
457 \draw[line width=1mm] (-.3, 0) rectangle (1.5,2); |
481 tokenize: |
458 \draw (4.2,1) node {Code Gen}; |
482 |
459 \draw (0.6,1.7) node {\footnotesize Parser}; |
483 \begin{center} |
460 \draw (-2.7,1.7) node {\footnotesize Lexer}; |
484 {\consolas "x - 3"} |
461 |
485 \end{center} |
462 \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2); |
486 |
463 |
487 \consolas |
464 \draw[white] (1.7,1) node (X) {}; |
488 \begin{tabular}{@{}l} |
465 \draw[white] (3.2,1) node (Y) {}; |
489 OP:\\ |
466 \draw[red, ->, line width = 2mm] (X) -- (Y); |
490 \hspace{5mm}\texttt{"+"}, \texttt{"-"}\\ |
467 |
491 NUM:\\ |
468 \draw[red, <-, line width = 2mm] (-0.6,1) -- (-1.6,1); |
492 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\ |
469 \draw[red, <-, line width = 2mm] (-3.8,1) -- (-4.8,1); |
493 NUMBER:\\ |
470 \end{tikzpicture} |
494 \hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\ |
|
495 \end{tabular} |
471 |
496 |
472 |
497 |
473 \end{frame}} |
498 \end{frame}} |
474 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
499 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
475 |
|
476 |
500 |
477 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
478 \mode<presentation>{ |
502 \mode<presentation>{ |
479 \begin{frame}[c] |
503 \begin{frame}[c] |
480 \frametitle{\begin{tabular}{c}Two Rules\end{tabular}} |
504 \frametitle{\begin{tabular}{c}Two Rules\end{tabular}} |
534 \bl{$zeroable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\ |
558 \bl{$zeroable (c)$} & \bl{$\dn$} & \bl{$f\!alse$}\\ |
535 \bl{$zeroable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$} \\ |
559 \bl{$zeroable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$} \\ |
536 \bl{$zeroable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$} \\ |
560 \bl{$zeroable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$} \\ |
537 \bl{$zeroable (r^*)$} & \bl{$\dn$} & \bl{$f\!alse$} \\ |
561 \bl{$zeroable (r^*)$} & \bl{$\dn$} & \bl{$f\!alse$} \\ |
538 \end{tabular} |
562 \end{tabular} |
539 \end{center} |
563 \end{center}\bigskip\pause |
540 |
564 |
|
565 \begin{center} |
|
566 \bl{$zeroable(r) \Leftrightarrow L(r) = \varnothing$} |
|
567 \end{center} |
541 |
568 |
542 \end{frame}} |
569 \end{frame}} |
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
571 |
|
572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
573 \mode<presentation>{ |
|
574 \begin{frame}[c] |
|
575 |
|
576 \begin{itemize} |
|
577 \item The star-case in our proof about the matcher needs the following lemma |
|
578 \begin{center} |
|
579 \bl{$Der\,c\,A^* = (Der c A)\,@\, A^*$} |
|
580 \end{center} |
|
581 \end{itemize}\bigskip\bigskip |
|
582 |
|
583 \begin{itemize} |
|
584 \item If \bl{\texttt{""} $\in A$}, then\\ \bl{$Der\,c\,(A @ B) = (Der\,c\,A) @ B \cup (Der\,c\,B)$}\medskip |
|
585 \item If \bl{\texttt{""} $\not\in A$}, then\\ \bl{$Der\,c\,(A @ B) = (Der\,c\,A) @ B$} |
|
586 |
|
587 \end{itemize} |
|
588 |
|
589 \end{frame}} |
|
590 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
591 |
544 |
592 |
545 \newcommand{\qq}{\mbox{\texttt{"}}} |
593 \newcommand{\qq}{\mbox{\texttt{"}}} |
546 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
594 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
547 \mode<presentation>{ |
595 \mode<presentation>{ |
548 \begin{frame}[c] |
596 \begin{frame}[c] |