Mercurial Mercurial > hg > afl-material / comparison
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/slides06.tex
changeset 531 f6e937ed0332
parent 500 c502933be072
child 597 ce8419e3915c
equal deleted inserted replaced
530:cec95ad3a837 531:f6e937ed0332 
    36 \end{frame}
 
    36 \end{frame}
 
    37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
    37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
    38 
    38 
    39 
    39 
    40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    41 \begin{frame}[c]
 
    41 % \begin{frame}[c]
 
    42 \small
 
    42 % \small
 
    43 \mbox{}\\[5mm]
 
    43 % \mbox{}\\[5mm]
 
    44 %\begin{textblock}{10}(3,5)
 
    44 % %\begin{textblock}{10}(3,5)
 
    45 \begin{tikzpicture}[scale=1.5,
 
    45 % \begin{tikzpicture}[scale=1.5,
 
    46                     node distance=1cm,
 
    46 %                     node distance=1cm,
 
    47                     every node/.style={minimum size=7mm}]
 
    47 %                     every node/.style={minimum size=7mm}]
 
    48 \node (r1)  {\bl{$r_1$}};
 
    48 % \node (r1)  {\bl{$r_1$}};
 
    49 \node (r2) [right=of r1] {\bl{$r_2$}};
 
    49 % \node (r2) [right=of r1] {\bl{$r_2$}};
 
    50 \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
 
    50 % \draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
 
    51 \node (r3) [right=of r2] {\bl{$r_3$}};
 
    51 % \node (r3) [right=of r2] {\bl{$r_3$}};
 
    52 \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
 
    52 % \draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
 
    53 \node (r4) [right=of r3] {\bl{$r_4$}};
 
    53 % \node (r4) [right=of r3] {\bl{$r_4$}};
 
    54 \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
 
    54 % \draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
 
    55 \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
 
    55 % \draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
 
    56 \node (v4) [below=of r4] {\bl{$v_4$}};
 
    56 % \node (v4) [below=of r4] {\bl{$v_4$}};
 
    57 \draw[->,line width=1mm]  (r4) -- (v4);
 
    57 % \draw[->,line width=1mm]  (r4) -- (v4);
 
    58 \node (v3) [left=of v4] {\bl{$v_3$}};
 
    58 % \node (v3) [left=of v4] {\bl{$v_3$}};
 
    59 \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
 
    59 % \draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
 
    60 \node (v2) [left=of v3] {\bl{$v_2$}};
 
    60 % \node (v2) [left=of v3] {\bl{$v_2$}};
 
    61 \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
 
    61 % \draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
 
    62 \node (v1) [left=of v2] {\bl{$v_1$}};
 
    62 % \node (v1) [left=of v2] {\bl{$v_1$}};
 
    63 \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
 
    63 % \draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
 
    64 \draw[->,line width=0.5mm]  (r3) -- (v3);
 
    64 % \draw[->,line width=0.5mm]  (r3) -- (v3);
 
    65 \draw[->,line width=0.5mm]  (r2) -- (v2);
 
    65 % \draw[->,line width=0.5mm]  (r2) -- (v2);
 
    66 \draw[->,line width=0.5mm]  (r1) -- (v1);
 
    66 % \draw[->,line width=0.5mm]  (r1) -- (v1);
 
    67 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
 
    67 % \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
 
    68 \end{tikzpicture}
 
    68 % \end{tikzpicture}
 
    69 %\end{textblock}
 
    69 % %\end{textblock}
 
    70 
    70 
    71 \begin{center}
 
    71 % \begin{center}
 
    72 \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
 
    72 % \begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
 
    73   \\[-10mm]
 
    73 %   \\[-10mm]
 
    74   \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$}  & \bl{$Char\,c$}\\
 
    74 %   \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$}  & \bl{$Char\,c$}\\
 
    75   \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\
 
    75 %   \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\
 
    76   \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\
 
    76 %   \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\
 
    77   \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
 
    77 %   \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
 
    78   \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
 
    78 %   \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
 
    79   \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
 
    79 %   \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
 
    80   \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$}  & \bl{$inj\,r\,c\,v\,::\,vs$}\\
 
    80 %   \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$}  & \bl{$inj\,r\,c\,v\,::\,vs$}\\
 
    81 \end{tabular}
 
    81 % \end{tabular}
 
    82 \end{center}
 
    82 % \end{center}
 
    83 
    83 
    84 \end{frame}
 
    84 % \end{frame}
 
    85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
    85 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
    86 
    86 
    87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    88 \begin{frame}[c]
 
    88 \begin{frame}[c]
 
    89 \frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
 
    89 \frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
 
    90 
    90 
   104 \end{center}
 
   104 \end{center}
 
   105 
   105 
   106 \end{frame}
 
   106 \end{frame}
 
   107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
   108 
   108 
   109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   109    
   110 \begin{frame}[c]
 
       
   111 \frametitle{Two Grammars}
 
       
   112 
       
   113 Which languages are recognised by the following two grammars?
 
       
   114 
       
   115 \begin{center}
 
       
   116 \bl{\begin{tabular}{lcl}
 
       
   117 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
 
       
   118         & $|$ & $\epsilon$
 
       
   119 \end{tabular}}
 
       
   120 \end{center}\bigskip
 
       
   121 
       
   122 \begin{center}
 
       
   123 \bl{\begin{tabular}{lcl}
 
       
   124 $U$ & $\rightarrow$ &  $1 \cdot U$\\
 
       
   125         & $|$ & $\epsilon$
 
       
   126 \end{tabular}}
 
       
   127 \end{center}
 
       
   128 
       
   129 \end{frame}
 
       
   130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
       
   131 
   110 
   132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   133 \begin{frame}[c]
 
   112 \begin{frame}[c]
 
   134 
   113 
   135 Atomic parsers, for example
 
   114 Atomic parsers, for example
 
   206 \end{center}
 
   185 \end{center}
 
   207 
   186 
   208 \end{frame}
 
   187 \end{frame}
 
   209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
   188 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
   210 
   189 
       
   190 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
       
   191 \begin{frame}[c]
 
       
   192 \frametitle{Types of Parsers}
 
       
   193 
       
   194 \begin{itemize}
 
       
   195 \item {\bf Sequencing}: if \bl{$p$} returns results of type \bl{$T$}, and \bl{$q$} results of type \bl{$S$},
 
       
   196 then \bl{$p \sim q$} returns results of type
 
       
   197 
       
   198 \begin{center}
 
       
   199 \bl{$T \times S$}
 
       
   200 \end{center}\pause
 
       
   201 
       
   202 \item {\bf Alternative}: if \bl{$p$} returns results of type \bl{$T$} then  \bl{$q$} \alert{must} also have results of type \bl{$T$},
 
       
   203 and \bl{$p \;||\; q$} returns results of type
 
       
   204 
       
   205 \begin{center}
 
       
   206 \bl{$T$}
 
       
   207 \end{center}\pause
 
       
   208 
       
   209 \item {\bf Semantic Action}: if \bl{$p$} returns results of type \bl{$T$} and \bl{$f$} is a function from
 
       
   210 \bl{$T$} to \bl{$S$}, then
 
       
   211 \bl{$p \Rightarrow f$} returns results of type
 
       
   212 
       
   213 \begin{center}
 
       
   214 \bl{$S$}
 
       
   215 \end{center}
 
       
   216 
       
   217 \end{itemize}
 
       
   218 
       
   219 \end{frame}
 
       
   220 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
       
   221 
       
   222 
       
   223 
       
   224 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
       
   225 \begin{frame}[c]
 
       
   226 \frametitle{Two Grammars}
 
       
   227 
       
   228 Which languages are recognised by the following two grammars?
 
       
   229 
       
   230 \begin{center}
 
       
   231 \bl{\begin{tabular}{lcl}
 
       
   232 $S$ & $\rightarrow$ &  $1 \cdot S \cdot S$\\
 
       
   233         & $|$ & $\epsilon$
 
       
   234 \end{tabular}}
 
       
   235 \end{center}\bigskip
 
       
   236 
       
   237 \begin{center}
 
       
   238 \bl{\begin{tabular}{lcl}
 
       
   239 $U$ & $\rightarrow$ &  $1 \cdot U$\\
 
       
   240         & $|$ & $\epsilon$
 
       
   241 \end{tabular}}
 
       
   242 \end{center}
 
       
   243 
       
   244 \end{frame}
 
       
   245 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   211 
   246 
   212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   247 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
   213 \begin{frame}[t]
 
   248 \begin{frame}[t]
 
   214 \frametitle{Ambiguous Grammars}
 
   249 \frametitle{Ambiguous Grammars}
 
   215 
   250
afl-material