Mercurial Mercurial > hg > afl-material / diff
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
slides/slides05.tex
changeset 451 4a5876f321ae
parent 445 e7d0157f0471
child 462 fb5e1ef58049 
--- 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}}
afl-material