diff -r 36799f7b9702 -r 5990e03b2ba8 slides/slides06.tex --- a/slides/slides06.tex Fri Oct 31 19:26:11 2025 +0000 +++ b/slides/slides06.tex Sat Nov 01 04:59:23 2025 +0000 @@ -61,28 +61,61 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \begin{frame}[t,fragile] -\begin{mybox3}{} - In CW2, be careful with the order of defining regular expressions: +\begin{minipage}{1.1\textwidth} + \begin{mybox3}{} + Why the hell did we bother for 4 long weeks with a worse-than-cubic + lexing algorithm for regular expressions, given the CYK-algorithm + can decide in cubic time whether a string is matched by a context + free grammar? Is the lecturer insane? + \end{mybox3} +\end{minipage}\bigskip -\begin{verbatim} -val COMMENT : Rexp = ... ~ EOL -val EOL : Rexp = "\r\n" | "\n" -\end{verbatim} -\end{mybox3} +\begin{itemize} +\item Yes, if we are only after string matching. But we are after lexing where + we need POSIX matching + and calculate POSIX values. You cannot do this with any of the CFG-algorithms. +\item Also it is not so easy to include extended regular expressions like $\sim{}r$ +and $r^{\{n\}}$. +\end{itemize} +\end{frame} + +\begin{frame}[t,fragile] +\begin{minipage}{1.1\textwidth} + \begin{mybox3}{} + Why the hell did we bother for 4 long weeks with a lexing algorithm + generating tokens, given the lecturer explains the parsing algorithm using + strings as input? Has the lecturer gone insane? + \end{mybox3} +\end{minipage}\bigskip + \end{frame} -\begin{frame}[t,fragile] -\begin{mybox3}{} - In CW2, what is the derivative of RECD? - -\begin{center} -\bl{$der\;c\;RECD(l, r) \;\;\dn\;\; ???$} -\end{center} -\end{mybox3} -\end{frame} - +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%\begin{frame}[t,fragile] +%\begin{mybox3}{} +% In CW2, be careful with the order of defining regular expressions: +% +%\begin{verbatim} +%val COMMENT : Rexp = ... ~ EOL +%val EOL : Rexp = "\r\n" | "\n" +%\end{verbatim} +%\end{mybox3} +%\end{frame} +% +% +%\begin{frame}[t,fragile] +%\begin{mybox3}{} +% In CW2, what is the derivative of RECD? +% +%\begin{center} +%\bl{$der\;c\;RECD(l, r) \;\;\dn\;\; ???$} +%\end{center} +%\end{mybox3} +%\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%