# HG changeset patch # User cu # Date 1508886359 -3600 # Node ID 68fab15cd6fb1408e0562b9fcffd7a8c73d8ddc1 # Parent 2a62f0845f98132c42992d0bbd89738ded181d16 updated diff -r 2a62f0845f98 -r 68fab15cd6fb slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 2a62f0845f98 -r 68fab15cd6fb slides/slides05.tex --- a/slides/slides05.tex Fri Oct 20 11:29:48 2017 +0100 +++ b/slides/slides05.tex Wed Oct 25 00:05:59 2017 +0100 @@ -37,20 +37,20 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Survey: Thanks!} -\small +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{Survey: Thanks!} +% \small -\begin{itemize} -\item {\bf My Voice} ``could be a bit louder'' -\item {\bf Writing} ``sometimes a bit difficult to read'' -\item {\bf Recording} ``video caps of blackboard'' -\item ``It's all great'' -\end{itemize} +% \begin{itemize} +% \item {\bf My Voice} ``could be a bit louder'' +% \item {\bf Writing} ``sometimes a bit difficult to read'' +% \item {\bf Recording} ``video caps of blackboard'' +% \item ``It's all great'' +% \end{itemize} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -203,67 +203,67 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[t] -\begin{center} -\bl{$\only<1>{(b \cdot c)}% - \only<2-3>{(\underline{b \cdot c})}% - \only<1-3>{+}% - \only<1>{(\ZERO + \ONE)}% - \only<2-3>{(\underline{\ZERO + \ONE})}$}% -\only<4->{% -\bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% -} -$\mapsto$ -\bl{$(b \cdot c) + \ONE$} -\end{center}\bigskip +% \begin{center} +% \bl{$\only<1>{(b \cdot c)}% +% \only<2-3>{(\underline{b \cdot c})}% +% \only<1-3>{+}% +% \only<1>{(\ZERO + \ONE)}% +% \only<2-3>{(\underline{\ZERO + \ONE})}$}% +% \only<4->{% +% \bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% +% } +% $\mapsto$ +% \bl{$(b \cdot c) + \ONE$} +% \end{center}\bigskip -\onslide<3->{% -\begin{center} -\begin{tabular}{lcl} -\bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ -\bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} -\end{tabular} -\end{center}} +% \onslide<3->{% +% \begin{center} +% \begin{tabular}{lcl} +% \bl{$f_{s1}$} & \bl{$=$} & \bl{$\lambda v.v$}\\ +% \bl{$f_{s2}$} & \bl{$=$} & \bl{$\lambda v. \textit{Right}(v)$} +% \end{tabular} +% \end{center}} -\only<4>{% -\begin{center} -\begin{tabular}{@{}l@{\hspace{1mm}}l@{}} -\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ -\quad \bl{$\lambda v.\,$} - case \bl{$v = Left(v')$}: - & return \bl{$Left(f_{s1}(v'))$}\\ -\quad \phantom{$\lambda v.\,$} - case \bl{$v = Right(v')$}: - & return \bl{$Right(f_{s2}(v'))$}\\ -\end{tabular} -\end{center}}% -\only<5->{% -\begin{center} -\begin{tabular}{@{}l@{\hspace{1mm}}l@{}} -\only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ -\quad \bl{$\lambda v.\,$} - case \bl{$v = Left(v')$}: - & return \bl{$Left(v')$}\\ -\quad \phantom{$\lambda v.\,$} - case \bl{$v = Right(v')$}: - & return \bl{$Right(Right(v'))$}\\ -\end{tabular} -\end{center}}% +% \only<4>{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(f_{s1}(v'))$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(f_{s2}(v'))$}\\ +% \end{tabular} +% \end{center}}% +% \only<5->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{1mm}}l@{}} +% \only<5->{\phantom{\bl{$f_{alt}(f_{s1}, f_{s2}) \dn$}}}\\ +% \quad \bl{$\lambda v.\,$} +% case \bl{$v = Left(v')$}: +% & return \bl{$Left(v')$}\\ +% \quad \phantom{$\lambda v.\,$} +% case \bl{$v = Right(v')$}: +% & return \bl{$Right(Right(v'))$}\\ +% \end{tabular} +% \end{center}}% -\only<6->{% -\begin{center} -\begin{tabular}{@{}l@{\hspace{4mm}}l@{}} -\bl{$\textit{mkeps}$} simplified case: & -\bl{$\textit{Right}(\textit{Empty})$}\\ -rectified case: & -\bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} -\end{tabular} -\end{center}}% +% \only<6->{% +% \begin{center} +% \begin{tabular}{@{}l@{\hspace{4mm}}l@{}} +% \bl{$\textit{mkeps}$} simplified case: & +% \bl{$\textit{Right}(\textit{Empty})$}\\ +% rectified case: & +% \bl{$\textit{Right}(\textit{Right}(\textit{Empty}))$} +% \end{tabular} +% \end{center}}% -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -371,51 +371,110 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Two Rules} - -\begin{itemize} -\item Longest match rule (``maximal munch rule''): The -longest initial substring matched by any regular expression is taken -as next token.\bigskip +\frametitle{Coursework: Nullable} -\item Rule priority: -For a particular longest initial substring, the first regular -expression that can match determines the token. - -\end{itemize} - -%\url{http://www.technologyreview.com/tr10/?year=2011} - -%finite deterministic automata/ nondeterministic automaton - -%\item problem with infix operations, for example i-12 - +\begin{center} +\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} + \bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^{\{n\}})$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^{\{n..\}})$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^{\{..n\}})$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(r^{\{n..m\}})$} & \bl{$\dn$} & $?$\\ + \bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\\ + +\end{tabular} +\end{center} \end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{Coursework} +%%\frametitle{Coursework: der} \begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -\bl{$nullable([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ -\bl{$nullable(r^+)$} & \bl{$\dn$} & $?$\\ -\bl{$nullable(r^?)$} & \bl{$\dn$} & $?$\\ -\bl{$nullable(r^{\{n,m\}})$} & \bl{$\dn$} & $?$\\ -\bl{$nullable(\sim{}r)$} & \bl{$\dn$} & $?$\medskip\\ -\bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ -\bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ -\bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ -\bl{$der\, c\, (r^{\{n,m\}})$} & \bl{$\dn$} & $?$\\ -\bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ +\begin{tabular}{@ {}l@ {\hspace{1mm}}c@ {\hspace{1mm}}l@ {}} + \bl{$der\, c\, ([c_1 c_2 \ldots c_n])$} & \bl{$\dn$} & $?$\\ + \bl{$der\, c\, (r^+)$} & \bl{$\dn$} & $?$\\ + \bl{$der\, c\, (r^?)$} & \bl{$\dn$} & $?$\\ + \bl{$der\, c\, (r^{\{n\}})$} & \bl{$\dn$} & + \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{n-1\}}$}\\ + \bl{$der\, c\, (r^{\{n..\}})$} & \bl{$\dn$} & + \bl{$if\;n=0\;then (der\,c\,r)\cdot r^*$}\\ + & & \bl{$\phantom{if\;n=0\;}else \;(der\,c\,r)\cdot r^{\{n-1..\}}$}\\ + \bl{$der\, c\, (r^{\{..n\}})$} & \bl{$\dn$} & + \bl{$if\;n=0\;then\;\ZERO\;else\;(der\,c\,r)\cdot r^{\{..n-1\}}$}\\ + + \bl{$der\, c\, (r^{\{n..m\}})$} & \bl{$\dn$} & + \bl{$if\;n = 0 \wedge m = 0\;then\;\ZERO\; else$}\\ + \multicolumn{3}{l}{\bl{$if\;n = 0 \wedge m > 0\;then\;(der\,c\,r)\cdot r^{\{..m-1\}}$}}\\ + \multicolumn{3}{l}{\bl{$\phantom{if\;n = 0 \wedge m > 0\;}else + \;(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}}\\ + \bl{$der\, c\, (\sim{}r)$} & \bl{$\dn$} & $?$\\ \end{tabular} \end{center} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Coursework: CFUN} + +\begin{center} +\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} + \bl{$nullable(CFUN(\_))$} & \bl{$\dn$} & \bl{$false$}\\ + \bl{$der\,c\,(CFUN(f))$} & \bl{$\dn$} & + \bl{$if\;f(c)\;then\;\ONE\;else\;\ZERO$}\bigskip\\ + \bl{$CHAR(c)$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;c=d)$}\\ + \bl{$CSET([c_1,\ldots,c_n])$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;d\in [c_1,\ldots,c_n])$}\\ + \bl{$ALL$} & \bl{$\dn$} & \bl{$CFUN(\lambda{}d.\;true)$}\\ +\end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] +\frametitle{Lexer, Parser} +\mbox{}\\[-16mm]\mbox{} + +\begin{center} + \begin{tikzpicture}[scale=1, + node/.style={ + rectangle,rounded corners=3mm, + very thick,draw=black!50, + minimum height=18mm, minimum width=20mm, + top color=white,bottom color=black!20}] + \node (0) at (-2.3,0) {}; + + \node (A) at (0,0) [node] {}; + \node [below right] at (A.north west) {lexer}; + + \node (B) at (3,0) [node] {}; + \node [below right=1mm] at (B.north west) + {\mbox{}\hspace{-1mm}parser}; + + \node (C) at (6,0) [node] {}; + \node [below right] at (C.north west) + {\mbox{}\hspace{-1mm}code gen}; + + \node (1) at (8.4,0) {}; + + \draw [->,line width=4mm] (0) -- (A); + \draw [->,line width=4mm] (A) -- (B); + \draw [->,line width=4mm] (B) -- (C); + \draw [->,line width=4mm] (C) -- (1); + \end{tikzpicture} + \end{center} + +Today a parser. + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -811,7 +870,7 @@ \begin{itemize} \item apply first \bl{$p$} producing a set of pairs -\item then apply \bl{$q$} to the unparsed parts +\item then apply \bl{$q$} to the unparsed part \item then combine the results:\medskip \begin{center} ((output$_1$, output$_2$), unparsed part)