diff -r d91a1748a9be -r 4a5876f321ae slides/slides05.tex --- a/slides/slides05.tex Thu Oct 13 13:13:27 2016 +0100 +++ b/slides/slides05.tex Sat Oct 15 14:27:01 2016 +0100 @@ -452,12 +452,12 @@ A \alert{\bf context-free grammar} \bl{$G$} consists of \begin{itemize} -\item a finite set of nonterminal symbols (upper case) +\item a finite set of nonterminal symbols ($\langle$upper case$\rangle$) \item a finite terminal symbols or tokens (lower case) \item a start symbol (which must be a nonterminal) \item a set of rules \begin{center} -\bl{$A \rightarrow \textit{rhs}$} +\bl{$\meta{A} ::= \textit{rhs}$} \end{center} where \bl{\textit{rhs}} are sequences involving terminals and nonterminals, @@ -465,7 +465,7 @@ We also allow rules \begin{center} -\bl{$A \rightarrow \textit{rhs}_1 | \textit{rhs}_2 | \ldots$} +\bl{$\meta{A} ::= \textit{rhs}_1 | \textit{rhs}_2 | \ldots$} \end{center} \end{itemize} @@ -478,21 +478,17 @@ A grammar for palindromes over the alphabet~\bl{$\{a,b\}$}: -\begin{center} -\bl{\begin{tabular}{lcl} -$S$ & $\rightarrow$ & $\epsilon$ \\ -$S$ & $\rightarrow$ & $a\cdot S\cdot a$ \\ -$S$ & $\rightarrow$ & $b\cdot S\cdot b$ \\ -\end{tabular}} -\end{center}\pause +\bl{\begin{plstx}[margin=3cm] +: \meta{S} ::= \epsilon\\ +: \meta{S} ::= a\cdot\meta{S}\cdot a\\ +: \meta{S} ::= b\cdot\meta{S}\cdot b\\ +\end{plstx}}\pause or -\begin{center} -\bl{\begin{tabular}{lcl} -$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ -\end{tabular}} -\end{center}\pause\bigskip +\bl{\begin{plstx}[margin=2cm] +: \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\ +\end{plstx}}\pause\bigskip \small Can you find the grammar rules for matched parentheses? @@ -504,15 +500,13 @@ \begin{frame}[c] \frametitle{Arithmetic Expressions} -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center}\pause +\bl{\begin{plstx}[margin=3cm,one per line] +: \meta{E} ::= num\_token + | \meta{E} \cdot + \cdot \meta{E} + | \meta{E} \cdot - \cdot \meta{E} + | \meta{E} \cdot * \cdot \meta{E} + | ( \cdot \meta{E} \cdot ) \\ +\end{plstx}}\pause \bl{\texttt{1 + 2 * 3 + 4}} @@ -524,34 +518,32 @@ \frametitle{A CFG Derivation} \begin{enumerate} -\item Begin with a string containing only the start symbol, say \bl{$S$}\bigskip -\item Replace any nonterminal \bl{$X$} in the string by the -right-hand side of some production \bl{$X \rightarrow \textit{rhs}$}\bigskip +\item Begin with a string containing only the start symbol, say \bl{\meta{S}}\bigskip +\item Replace any nonterminal \bl{\meta{X}} in the string by the +right-hand side of some production \bl{$\meta{X} ::= \textit{rhs}$}\bigskip \item Repeat 2 until there are no nonterminals \end{enumerate} \begin{center} -\bl{$S \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} +\bl{$\meta{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots $} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Example Derivation} -\begin{center} -\bl{\begin{tabular}{lcl} -$S$ & $\rightarrow$ & $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\ -\end{tabular}} -\end{center}\bigskip +\bl{\begin{plstx}[margin=2cm] +: \meta{S} ::= \epsilon | a\cdot \meta{S}\cdot a | b\cdot \meta{S}\cdot b \\ +\end{plstx}}\bigskip \begin{center} \begin{tabular}{lcl} -\bl{$S$} & \bl{$\rightarrow$} & \bl{$aSa$}\\ - & \bl{$\rightarrow$} & \bl{$abSba$}\\ - & \bl{$\rightarrow$} & \bl{$abaSaba$}\\ +\bl{\meta{S}} & \bl{$\rightarrow$} & \bl{$a\meta{S}a$}\\ + & \bl{$\rightarrow$} & \bl{$ab\meta{S}ba$}\\ + & \bl{$\rightarrow$} & \bl{$aba\meta{S}aba$}\\ & \bl{$\rightarrow$} & \bl{$abaaba$}\\ @@ -562,33 +554,31 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Example Derivation} -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center}\bigskip +\bl{\begin{plstx}[margin=3cm,one per line] +: \meta{E} ::= num\_token + | \meta{E} \cdot + \cdot \meta{E} + | \meta{E} \cdot - \cdot \meta{E} + | \meta{E} \cdot * \cdot \meta{E} + | ( \cdot \meta{E} \cdot ) \\ +\end{plstx}} - +\small \begin{center} \begin{tabular}{@{}c@{}c@{}} -\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} -\bl{$E$} & \bl{$\rightarrow$} & \bl{$E*E$}\\ - & \bl{$\rightarrow$} & \bl{$E+E*E$}\\ - & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ +\begin{tabular}{@{\hspace{-2mm}}l@{\hspace{1mm}}l@{\hspace{1mm}}l@{\hspace{4mm}}} +\bl{\meta{E}} & \bl{$\rightarrow$} & \bl{$\meta{E}*\meta{E}$}\\ + & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}$}\\ + & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\ & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ \end{tabular} &\pause -\begin{tabular}{l@{\hspace{1mm}}l@{\hspace{1mm}}l} -\bl{$E$} & \bl{$\rightarrow$} & \bl{$E+E$}\\ - & \bl{$\rightarrow$} & \bl{$E+E+E$}\\ - & \bl{$\rightarrow$} & \bl{$E+E*E+E$}\\ - & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ +\begin{tabular}{@{}l@{\hspace{0mm}}l@{\hspace{1mm}}l} +\bl{$\meta{E}$} & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}$}\\ + & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}+\meta{E}$}\\ + & \bl{$\rightarrow$} & \bl{$\meta{E}+\meta{E}*\meta{E}+\meta{E}$}\\ + & \bl{$\rightarrow^+$} & \bl{$1+2*3+4$}\\ \end{tabular} \end{tabular} \end{center} @@ -604,16 +594,14 @@ It is much harder to find out whether a string is parsed by a context sensitive grammar: -\begin{center} -\bl{\begin{tabular}{lcl} -$S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\ -$A$ & $\rightarrow$ & $a$\\ -$bA$ & $\rightarrow$ & $Ab$\\ -\end{tabular}} -\end{center}\pause +\bl{\begin{plstx}[margin=2cm] +: \meta{S} ::= b\meta{S}\meta{A}\meta{A} | \epsilon\\ +: \meta{A} ::= a\\ +: b\meta{A} ::= \meta{A}b\\ +\end{plstx}}\pause \begin{center} -\bl{$S \rightarrow\ldots\rightarrow^? "ababaa"$} +\bl{$\meta{S} \rightarrow\ldots\rightarrow^? ababaa$} \end{center} \end{frame} @@ -623,11 +611,11 @@ \begin{frame}[c] \frametitle{Language of a CFG} -Let \bl{$G$} be a context-free grammar with start symbol \bl{$S$}. +Let \bl{$G$} be a context-free grammar with start symbol \bl{\meta{S}}. Then the language \bl{$L(G)$} is: \begin{center} -\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge S \rightarrow^* c_1\ldots c_n \}$} +\bl{$\{c_1\ldots c_n \;|\; \forall i.\; c_i \in T \wedge \meta{S} \rightarrow^* c_1\ldots c_n \}$} \end{center}\pause \begin{itemize} @@ -641,34 +629,32 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Parse Trees} +\mbox{}\\[-16mm] + +\bl{\begin{plstx}: \meta{E} ::= \meta{F} | \meta{F} \cdot * \cdot \meta{F}\\ +: \meta{F} ::= \meta{T} | \meta{T} \cdot + \cdot \meta{T} | \meta{T} \cdot - \cdot \meta{T}\\ +: \meta{T} ::= num\_token | ( \cdot \meta{E} \cdot )\\ +\end{plstx}} -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $F \;|\; F \cdot * \cdot F$\\ -$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\ -$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\ -\end{tabular}} -\end{center} - -\begin{center} +\begin{center}\small \begin{tikzpicture}[level distance=8mm, blue] - \node {$E$} - child {node {$F$} - child {node {$T$} - child {node {(\,$E$\,)} - child {node{$F$ *{} $F$} - child {node {$T$} child {node {2}}} - child {node {$T$} child {node {3}}} + \node {$\meta{E}$} + child {node {$\meta{F}$} + child {node {$\meta{T}$} + child {node {(\,$\meta{E}$\,)} + child {node{$\meta{F}$ *{} $\meta{F}$} + child {node {$\meta{T}$} child {node {2}}} + child {node {$\meta{T}$} child {node {3}}} } } } child {node {+}} - child {node {$T$} - child {node {(\,$E$\,)} - child {node {$F$} - child {node {$T$ +{} $T$} + child {node {$\meta{T}$} + child {node {(\,$\meta{E}$\,)} + child {node {$\meta{F}$} + child {node {$\meta{T}$ +{} $\meta{T}$} child {node {3}} child {node {4}} } @@ -685,42 +671,37 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Arithmetic Expressions} -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center}\pause\bigskip +\bl{\begin{plstx}[margin=3cm,one per line] +: \meta{E} ::= num\_token + | \meta{E} \cdot + \cdot \meta{E} + | \meta{E} \cdot - \cdot \meta{E} + | \meta{E} \cdot * \cdot \meta{E} + | ( \cdot \meta{E} \cdot ) \\ +\end{plstx}}\pause\bigskip -A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$E$} such -that \bl{$E \rightarrow^+ E\cdot \ldots$} +A CFG is \alert{\bf left-recursive} if it has a nonterminal \bl{$\meta{E}$} such +that \bl{$\meta{E} \rightarrow^+ \meta{E}\cdot \ldots$} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +\begin{frame}[t] \frametitle{Ambiguous Grammars} A grammar is \alert{\bf ambiguous} if there is a string that has at least two different parse trees. +\bl{\begin{plstx}[margin=3cm,one per line]: \meta{E} ::= num\_token + | \meta{E} \cdot + \cdot \meta{E} + | \meta{E} \cdot - \cdot \meta{E} + | \meta{E} \cdot * \cdot \meta{E} + | ( \cdot \meta{E} \cdot ) \\ +\end{plstx}} -\begin{center} -\bl{\begin{tabular}{lcl} -$E$ & $\rightarrow$ & $num\_token$ \\ -$E$ & $\rightarrow$ & $E \cdot + \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot - \cdot E$ \\ -$E$ & $\rightarrow$ & $E \cdot * \cdot E$ \\ -$E$ & $\rightarrow$ & $( \cdot E \cdot )$ -\end{tabular}} -\end{center} \bl{\texttt{1 + 2 * 3 + 4}}