450 \frametitle{CF Grammars} |
450 \frametitle{CF Grammars} |
451 |
451 |
452 A \alert{\bf context-free grammar} \bl{$G$} consists of |
452 A \alert{\bf context-free grammar} \bl{$G$} consists of |
453 |
453 |
454 \begin{itemize} |
454 \begin{itemize} |
455 \item a finite set of nonterminal symbols (upper case) |
455 \item a finite set of nonterminal symbols ($\langle$upper case$\rangle$) |
456 \item a finite terminal symbols or tokens (lower case) |
456 \item a finite terminal symbols or tokens (lower case) |
457 \item a start symbol (which must be a nonterminal) |
457 \item a start symbol (which must be a nonterminal) |
458 \item a set of rules |
458 \item a set of rules |
459 \begin{center} |
459 \begin{center} |
460 \bl{$A \rightarrow \textit{rhs}$} |
460 \bl{$\meta{A} ::= \textit{rhs}$} |
461 \end{center} |
461 \end{center} |
462 |
462 |
463 where \bl{\textit{rhs}} are sequences involving terminals and nonterminals, |
463 where \bl{\textit{rhs}} are sequences involving terminals and nonterminals, |
464 including the empty sequence \bl{$\epsilon$}.\medskip\pause |
464 including the empty sequence \bl{$\epsilon$}.\medskip\pause |
465 |
465 |
466 We also allow rules |
466 We also allow rules |
467 \begin{center} |
467 \begin{center} |
468 \bl{$A \rightarrow \textit{rhs}_1 | \textit{rhs}_2 | \ldots$} |
468 \bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$} |
469 \end{center} |
469 \end{center} |
470 \end{itemize} |
470 \end{itemize} |
471 |
471 |
472 \end{frame} |
472 \end{frame} |
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
476 \begin{frame}[c] |
476 \begin{frame}[c] |
477 \frametitle{Palindromes} |
477 \frametitle{Palindromes} |
478 |
478 |
479 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}: |
479 A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}: |
480 |
480 |
481 \begin{center} |
481 \bl{\begin{plstx}[margin=3cm] |
482 \bl{\begin{tabular}{lcl} |
482 : \meta{S} ::= \epsilon\\ |
483 $S$ & $\rightarrow$ & $\epsilon$ \\ |
483 : \meta{S} ::= a\cdot\meta{S}\cdot a\\ |
484 $S$ & $\rightarrow$ & $a\cdot S\cdot a$ \\ |
484 : \meta{S} ::= b\cdot\meta{S}\cdot b\\ |
485 $S$ & $\rightarrow$ & $b\cdot S\cdot b$ \\ |
485 \end{plstx}}\pause |
486 \end{tabular}} |
|
487 \end{center}\pause |
|
488 |
486 |
489 or |
487 or |
490 |
488 |
491 \begin{center} |
489 \bl{\begin{plstx}[margin=2cm] |
492 \bl{\begin{tabular}{lcl} |
490 : \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\ |
493 $S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ |
491 \end{plstx}}\pause\bigskip |
494 \end{tabular}} |
|
495 \end{center}\pause\bigskip |
|
496 |
492 |
497 \small |
493 \small |
498 Can you find the grammar rules for matched parentheses? |
494 Can you find the grammar rules for matched parentheses? |
499 |
495 |
500 \end{frame} |
496 \end{frame} |
502 |
498 |
503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
499 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
504 \begin{frame}[c] |
500 \begin{frame}[c] |
505 \frametitle{Arithmetic Expressions} |
501 \frametitle{Arithmetic Expressions} |
506 |
502 |
507 \begin{center} |
503 \bl{\begin{plstx}[margin=3cm,one per line] |
508 \bl{\begin{tabular}{lcl} |
504 : \meta{E} ::= num\_token |
509 $E$ & $\rightarrow$ & $num\_token$ \\ |
505 | \meta{E} \cdot + \cdot \meta{E} |
510 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
506 | \meta{E} \cdot - \cdot \meta{E} |
511 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
507 | \meta{E} \cdot * \cdot \meta{E} |
512 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
508 | ( \cdot \meta{E} \cdot ) \\ |
513 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
509 \end{plstx}}\pause |
514 \end{tabular}} |
|
515 \end{center}\pause |
|
516 |
510 |
517 \bl{\texttt{1 + 2 * 3 + 4}} |
511 \bl{\texttt{1 + 2 * 3 + 4}} |
518 |
512 |
519 \end{frame} |
513 \end{frame} |
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
522 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
523 \begin{frame}[c] |
517 \begin{frame}[c] |
524 \frametitle{A CFG Derivation} |
518 \frametitle{A CFG Derivation} |
525 |
519 |
526 \begin{enumerate} |
520 \begin{enumerate} |
527 \item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip |
521 \item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip |
528 \item Replace any nonterminal \bl{$X$} in the string by the |
522 \item Replace any nonterminal \bl{\meta{X}} in the string by the |
529 right-hand side of some production \bl{$X \rightarrow \textit{rhs}$}\bigskip |
523 right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip |
530 \item Repeat 2 until there are no nonterminals |
524 \item Repeat 2 until there are no nonterminals |
531 \end{enumerate} |
525 \end{enumerate} |
532 |
526 |
533 \begin{center} |
527 \begin{center} |
534 \bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} |
528 \bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} |
535 \end{center} |
529 \end{center} |
536 |
530 |
537 \end{frame} |
531 \end{frame} |
538 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
539 |
533 |
540 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
541 \begin{frame}[c] |
535 \begin{frame}[t] |
542 \frametitle{Example Derivation} |
536 \frametitle{Example Derivation} |
543 |
537 |
544 \begin{center} |
538 \bl{\begin{plstx}[margin=2cm] |
545 \bl{\begin{tabular}{lcl} |
539 : \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\ |
546 $S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ |
540 \end{plstx}}\bigskip |
547 \end{tabular}} |
|
548 \end{center}\bigskip |
|
549 |
541 |
550 \begin{center} |
542 \begin{center} |
551 \begin{tabular}{lcl} |
543 \begin{tabular}{lcl} |
552 \bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\ |
544 \bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\ |
553 & \bl{$\rightarrow$} & \bl{$abSba$}\\ |
545 & \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\ |
554 & \bl{$\rightarrow$} & \bl{$abaSaba$}\\ |
546 & \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\ |
555 & \bl{$\rightarrow$} & \bl{$abaaba$}\\ |
547 & \bl{$\rightarrow$} & \bl{$abaaba$}\\ |
556 |
548 |
557 |
549 |
558 \end{tabular} |
550 \end{tabular} |
559 \end{center} |
551 \end{center} |
560 |
552 |
561 \end{frame} |
553 \end{frame} |
562 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
554 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
563 |
555 |
564 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
556 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
565 \begin{frame}[c] |
557 \begin{frame}[t] |
566 \frametitle{Example Derivation} |
558 \frametitle{Example Derivation} |
567 |
559 |
568 \begin{center} |
560 \bl{\begin{plstx}[margin=3cm,one per line] |
569 \bl{\begin{tabular}{lcl} |
561 : \meta{E} ::= num\_token |
570 $E$ & $\rightarrow$ & $num\_token$ \\ |
562 | \meta{E} \cdot + \cdot \meta{E} |
571 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
563 | \meta{E} \cdot - \cdot \meta{E} |
572 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
564 | \meta{E} \cdot * \cdot \meta{E} |
573 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
565 | ( \cdot \meta{E} \cdot ) \\ |
574 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
566 \end{plstx}} |
575 \end{tabular}} |
567 |
576 \end{center}\bigskip |
568 \small |
577 |
|
578 |
|
579 \begin{center} |
569 \begin{center} |
580 \begin{tabular}{@{}c@{}c@{}} |
570 \begin{tabular}{@{}c@{}c@{}} |
581 \begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} |
571 \begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}} |
582 \bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\ |
572 \bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\ |
583 & \bl{$\rightarrow$} & \bl{$E+E*E$}\\ |
573 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\ |
584 & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ |
574 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\ |
585 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ |
575 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ |
586 \end{tabular} &\pause |
576 \end{tabular} &\pause |
587 \begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} |
577 \begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l} |
588 \bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\ |
578 \bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\ |
589 & \bl{$\rightarrow$} & \bl{$E+E+E$}\\ |
579 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\ |
590 & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ |
580 & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\ |
591 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ |
581 & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ |
592 \end{tabular} |
582 \end{tabular} |
593 \end{tabular} |
583 \end{tabular} |
594 \end{center} |
584 \end{center} |
595 |
585 |
596 \end{frame} |
586 \end{frame} |
602 Grammars\end{tabular}} |
592 Grammars\end{tabular}} |
603 |
593 |
604 It is much harder to find out whether a string is parsed |
594 It is much harder to find out whether a string is parsed |
605 by a context sensitive grammar: |
595 by a context sensitive grammar: |
606 |
596 |
607 \begin{center} |
597 \bl{\begin{plstx}[margin=2cm] |
608 \bl{\begin{tabular}{lcl} |
598 : \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\ |
609 $S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\ |
599 : \meta{A} ::= a\\ |
610 $A$ & $\rightarrow$ & $a$\\ |
600 : b\meta{A} ::= \meta{A}b\\ |
611 $bA$ & $\rightarrow$ & $Ab$\\ |
601 \end{plstx}}\pause |
612 \end{tabular}} |
602 |
613 \end{center}\pause |
603 \begin{center} |
614 |
604 \bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$} |
615 \begin{center} |
|
616 \bl{$S \rightarrow\ldots\rightarrow^? "ababaa"$} |
|
617 \end{center} |
605 \end{center} |
618 |
606 |
619 \end{frame} |
607 \end{frame} |
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
608 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
621 |
609 |
622 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
610 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
623 \begin{frame}[c] |
611 \begin{frame}[c] |
624 \frametitle{Language of a CFG} |
612 \frametitle{Language of a CFG} |
625 |
613 |
626 Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. |
614 Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}. |
627 Then the language \bl{$L(G)$} is: |
615 Then the language \bl{$L(G)$} is: |
628 |
616 |
629 \begin{center} |
617 \begin{center} |
630 \bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$} |
618 \bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$} |
631 \end{center}\pause |
619 \end{center}\pause |
632 |
620 |
633 \begin{itemize} |
621 \begin{itemize} |
634 \item Terminals, because there are no rules for replacing them. |
622 \item Terminals, because there are no rules for replacing them. |
635 \item Once generated, terminals are ``permanent''. |
623 \item Once generated, terminals are ``permanent''. |
639 |
627 |
640 \end{frame} |
628 \end{frame} |
641 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
642 |
630 |
643 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
644 \begin{frame}[c] |
632 \begin{frame}[t] |
645 \frametitle{Parse Trees} |
633 \frametitle{Parse Trees} |
646 |
634 \mbox{}\\[-16mm] |
647 \begin{center} |
635 |
648 \bl{\begin{tabular}{lcl} |
636 \bl{\begin{plstx}: \meta{E} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{F}\\ |
649 $E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F$\\ |
637 : \meta{F} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{T} | \meta{T} \cdot - \cdot \meta{T}\\ |
650 $F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\ |
638 : \meta{T} ::= num\_token | ( \cdot \meta{E} \cdot )\\ |
651 $T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\ |
639 \end{plstx}} |
652 \end{tabular}} |
640 |
653 \end{center} |
641 \begin{center}\small |
654 |
|
655 \begin{center} |
|
656 \begin{tikzpicture}[level distance=8mm, blue] |
642 \begin{tikzpicture}[level distance=8mm, blue] |
657 \node {$E$} |
643 \node {$\meta{E}$} |
658 child {node {$F$} |
644 child {node {$\meta{F}$} |
659 child {node {$T$} |
645 child {node {$\meta{T}$} |
660 child {node {(\,$E$\,)} |
646 child {node {(\,$\meta{E}$\,)} |
661 child {node{$F$ *{} $F$} |
647 child {node{$\meta{F}$ *{} $\meta{F}$} |
662 child {node {$T$} child {node {2}}} |
648 child {node {$\meta{T}$} child {node {2}}} |
663 child {node {$T$} child {node {3}}} |
649 child {node {$\meta{T}$} child {node {3}}} |
664 } |
650 } |
665 } |
651 } |
666 } |
652 } |
667 child {node {+}} |
653 child {node {+}} |
668 child {node {$T$} |
654 child {node {$\meta{T}$} |
669 child {node {(\,$E$\,)} |
655 child {node {(\,$\meta{E}$\,)} |
670 child {node {$F$} |
656 child {node {$\meta{F}$} |
671 child {node {$T$ +{} $T$} |
657 child {node {$\meta{T}$ +{} $\meta{T}$} |
672 child {node {3}} |
658 child {node {3}} |
673 child {node {4}} |
659 child {node {4}} |
674 } |
660 } |
675 }} |
661 }} |
676 }}; |
662 }}; |
683 |
669 |
684 \end{frame} |
670 \end{frame} |
685 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
671 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
686 |
672 |
687 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
688 \begin{frame}[c] |
674 \begin{frame}[t] |
689 \frametitle{Arithmetic Expressions} |
675 \frametitle{Arithmetic Expressions} |
690 |
676 |
691 \begin{center} |
677 \bl{\begin{plstx}[margin=3cm,one per line] |
692 \bl{\begin{tabular}{lcl} |
678 : \meta{E} ::= num\_token |
693 $E$ & $\rightarrow$ & $num\_token$ \\ |
679 | \meta{E} \cdot + \cdot \meta{E} |
694 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
680 | \meta{E} \cdot - \cdot \meta{E} |
695 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
681 | \meta{E} \cdot * \cdot \meta{E} |
696 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
682 | ( \cdot \meta{E} \cdot ) \\ |
697 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
683 \end{plstx}}\pause\bigskip |
698 \end{tabular}} |
684 |
699 \end{center}\pause\bigskip |
685 A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such |
700 |
686 that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$} |
701 A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$E$} such |
687 |
702 that \bl{$E \rightarrow^+ E\cdot \ldots$} |
688 \end{frame} |
703 |
689 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
704 \end{frame} |
690 |
705 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
706 |
692 \begin{frame}[t] |
707 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
708 \begin{frame}[c] |
|
709 \frametitle{Ambiguous Grammars} |
693 \frametitle{Ambiguous Grammars} |
710 |
694 |
711 A grammar is \alert{\bf ambiguous} if there is a string that |
695 A grammar is \alert{\bf ambiguous} if there is a string that |
712 has at least two different parse trees. |
696 has at least two different parse trees. |
713 |
697 |
714 |
698 \bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= num\_token |
715 \begin{center} |
699 | \meta{E} \cdot + \cdot \meta{E} |
716 \bl{\begin{tabular}{lcl} |
700 | \meta{E} \cdot - \cdot \meta{E} |
717 $E$ & $\rightarrow$ & $num\_token$ \\ |
701 | \meta{E} \cdot * \cdot \meta{E} |
718 $E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ |
702 | ( \cdot \meta{E} \cdot ) \\ |
719 $E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ |
703 \end{plstx}} |
720 $E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ |
704 |
721 $E$ & $\rightarrow$ & $( \cdot E \cdot )$ |
|
722 \end{tabular}} |
|
723 \end{center} |
|
724 |
705 |
725 \bl{\texttt{1 + 2 * 3 + 4}} |
706 \bl{\texttt{1 + 2 * 3 + 4}} |
726 |
707 |
727 \end{frame} |
708 \end{frame} |
728 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
709 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |