equal
deleted
inserted
replaced
416 \end{frame} |
416 \end{frame} |
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
417 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
418 |
418 |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
419 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
420 \begin{frame}[c] |
420 \begin{frame}[c] |
421 \frametitle{Grammars} |
421 \frametitle{CF Grammars} |
422 |
422 |
423 A (context-free) grammar \bl{$G$} consists of |
423 A \alert{\bf context-free grammar} \bl{$G$} consists of |
424 |
424 |
425 \begin{itemize} |
425 \begin{itemize} |
426 \item a finite set of nonterminal symbols (upper case) |
426 \item a finite set of nonterminal symbols (upper case) |
427 \item a finite terminal symbols or tokens (lower case) |
427 \item a finite terminal symbols or tokens (lower case) |
428 \item a start symbol (which must be a nonterminal) |
428 \item a start symbol (which must be a nonterminal) |
567 \end{frame} |
567 \end{frame} |
568 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
568 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
569 |
569 |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
571 \begin{frame}[c] |
571 \begin{frame}[c] |
572 \frametitle{Context Sensitive Grms} |
572 \frametitle{\begin{tabular}{c}Context Sensitive\\[-1mm] |
573 |
573 Grammars\end{tabular}} |
574 |
574 |
575 \begin{center} |
575 It is much harder to find out whether a string is parsed |
576 \bl{\begin{tabular}{lcl} |
576 by a context sensitive grammar: |
577 $S$ & $\Rightarrow$ & $bSAA\;|\; \epsilon$\\ |
577 |
578 $A$ & $\Rightarrow$ & $a$\\ |
578 \begin{center} |
579 $bA$ & $\Rightarrow$ & $Ab$\\ |
579 \bl{\begin{tabular}{lcl} |
|
580 $S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\ |
|
581 $A$ & $\rightarrow$ & $a$\\ |
|
582 $bA$ & $\rightarrow$ & $Ab$\\ |
580 \end{tabular}} |
583 \end{tabular}} |
581 \end{center}\pause |
584 \end{center}\pause |
582 |
585 |
583 \begin{center} |
586 \begin{center} |
584 \bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$} |
587 \bl{$S \rightarrow\ldots\rightarrow^? "ababaa"$} |
585 \end{center} |
588 \end{center} |
586 |
589 |
587 \end{frame} |
590 \end{frame} |
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
591 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
589 |
592 |