equal
deleted
inserted
replaced
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
375 \mode<presentation>{ |
375 \mode<presentation>{ |
376 \begin{frame}[c] |
376 \begin{frame}[c] |
377 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
377 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
378 |
378 |
379 A (context-free) Grammar \bl{$G$} consists of |
379 A (context-free) grammar \bl{$G$} consists of |
380 |
380 |
381 \begin{itemize} |
381 \begin{itemize} |
382 \item a finite set of nonterminal symbols (upper case) |
382 \item a finite set of nonterminal symbols (upper case) |
383 \item a finite terminal symbols or tokens (lower case) |
383 \item a finite terminal symbols or tokens (lower case) |
384 \item a start symbol (which must be a nonterminal) |
384 \item a start symbol (which must be a nonterminal) |
405 \frametitle{\begin{tabular}{c}Palindromes\end{tabular}} |
405 \frametitle{\begin{tabular}{c}Palindromes\end{tabular}} |
406 |
406 |
407 \begin{center} |
407 \begin{center} |
408 \bl{\begin{tabular}{lcl} |
408 \bl{\begin{tabular}{lcl} |
409 $S$ & $\rightarrow$ & $\epsilon$ \\ |
409 $S$ & $\rightarrow$ & $\epsilon$ \\ |
410 $S$ & $\rightarrow$ & $aSa$ \\ |
410 $S$ & $\rightarrow$ & $a\cdot S\cdot a$ \\ |
411 $S$ & $\rightarrow$ & $bSb$ \\ |
411 $S$ & $\rightarrow$ & $b\cdot S\cdot b$ \\ |
412 \end{tabular}} |
412 \end{tabular}} |
413 \end{center}\pause |
413 \end{center}\pause |
414 |
414 |
415 or |
415 or |
416 |
416 |
417 \begin{center} |
417 \begin{center} |
418 \bl{\begin{tabular}{lcl} |
418 \bl{\begin{tabular}{lcl} |
419 $S$ & $\rightarrow$ & $\epsilon \;|\; aSa \;|\;bSb$ \\ |
419 $S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ |
420 \end{tabular}} |
420 \end{tabular}} |
421 \end{center} |
421 \end{center} |
422 |
422 |
423 |
423 |
424 \end{frame}} |
424 \end{frame}} |
432 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} |
432 \frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}} |
433 |
433 |
434 \begin{center} |
434 \begin{center} |
435 \bl{\begin{tabular}{lcl} |
435 \bl{\begin{tabular}{lcl} |
436 $E$ & $\rightarrow$ & $num\_token$ \\ |
436 $E$ & $\rightarrow$ & $num\_token$ \\ |
437 $E$ & $\rightarrow$ & $E + E$ \\ |
437 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
438 $E$ & $\rightarrow$ & $E - E$ \\ |
438 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
439 $E$ & $\rightarrow$ & $E * E$ \\ |
439 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
440 $E$ & $\rightarrow$ & $( E )$ |
440 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
441 \end{tabular}} |
441 \end{tabular}} |
442 \end{center}\pause |
442 \end{center}\pause |
443 |
443 |
444 \bl{\texttt{1 + 2 * 3 + 4}} |
444 \bl{\texttt{1 + 2 * 3 + 4}} |
445 |
445 |
452 \begin{frame}[c] |
452 \begin{frame}[c] |
453 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} |
453 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}} |
454 |
454 |
455 \begin{center} |
455 \begin{center} |
456 \bl{\begin{tabular}{lcl} |
456 \bl{\begin{tabular}{lcl} |
457 $E$ & $\rightarrow$ & $F \;|\; F * F$\\ |
457 $E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F$\\ |
458 $F$ & $\rightarrow$ & $T \;|\; T + T \;|\; T - T$\\ |
458 $F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\ |
459 $T$ & $\rightarrow$ & $num\_token \;|\; ( E )$\\ |
459 $T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\ |
460 \end{tabular}} |
460 \end{tabular}} |
461 \end{center} |
461 \end{center} |
462 |
462 |
463 \begin{center} |
463 \begin{center} |
464 \begin{tikzpicture}[level distance=8mm, blue] |
464 \begin{tikzpicture}[level distance=8mm, blue] |
500 |
500 |
501 |
501 |
502 \begin{center} |
502 \begin{center} |
503 \bl{\begin{tabular}{lcl} |
503 \bl{\begin{tabular}{lcl} |
504 $E$ & $\rightarrow$ & $num\_token$ \\ |
504 $E$ & $\rightarrow$ & $num\_token$ \\ |
505 $E$ & $\rightarrow$ & $E + E$ \\ |
505 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
506 $E$ & $\rightarrow$ & $E - E$ \\ |
506 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
507 $E$ & $\rightarrow$ & $E * E$ \\ |
507 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
508 $E$ & $\rightarrow$ & $( E )$ |
508 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
509 \end{tabular}} |
509 \end{tabular}} |
510 \end{center} |
510 \end{center} |
511 |
511 |
512 \bl{\texttt{1 + 2 * 3 + 4}} |
512 \bl{\texttt{1 + 2 * 3 + 4}} |
513 |
513 |
527 \end{center} |
527 \end{center} |
528 |
528 |
529 or |
529 or |
530 |
530 |
531 \begin{center} |
531 \begin{center} |
532 \bl{$A \rightarrow BC$} |
532 \bl{$A \rightarrow B\cdot C$} |
533 \end{center} |
533 \end{center} |
534 |
534 |
535 |
535 |
536 |
536 |
537 \end{frame}} |
537 \end{frame}} |
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
539 |
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
540 \mode<presentation>{ |
|
541 \begin{frame}[c] |
|
542 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} |
|
543 |
|
544 |
|
545 \begin{center} |
|
546 \bl{\begin{tabular}{@ {}lcl} |
|
547 $S$ & $\rightarrow$ & $N\cdot P$ \\ |
|
548 $P$ & $\rightarrow$ & $V\cdot N$ \\ |
|
549 $N$ & $\rightarrow$ & $N\cdot N$ \\ |
|
550 $N$ & $\rightarrow$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\ |
|
551 $E$ & $\rightarrow$ & $\texttt{trains}$ |
|
552 \end{tabular}} |
|
553 \end{center} |
|
554 |
|
555 \bl{\texttt{Jeff trains geometry students}} |
|
556 |
|
557 \end{frame}} |
|
558 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
540 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
541 \mode<presentation>{ |
560 \mode<presentation>{ |
542 \begin{frame}[c] |
561 \begin{frame}[c] |
543 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} |
562 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}} |
544 |
563 |