59 \end{center} |
59 \end{center} |
60 |
60 |
61 \end{frame} |
61 \end{frame} |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
62 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
63 |
63 |
|
64 |
64 \begin{frame}[t,fragile] |
65 \begin{frame}[t,fragile] |
65 \begin{mybox3}{} |
66 \begin{minipage}{1.1\textwidth} |
66 In CW2, be careful with the order of defining regular expressions: |
67 \begin{mybox3}{} |
67 |
68 Why the hell did we bother for 4 long weeks with a worse-than-cubic |
68 \begin{verbatim} |
69 lexing algorithm for regular expressions, given the CYK-algorithm |
69 val COMMENT : Rexp = ... ~ EOL |
70 can decide in cubic time whether a string is matched by a context |
70 val EOL : Rexp = "\r\n" | "\n" |
71 free grammar? Is the lecturer insane? |
71 \end{verbatim} |
72 \end{mybox3} |
72 \end{mybox3} |
73 \end{minipage}\bigskip |
73 \end{frame} |
74 |
74 |
75 \begin{itemize} |
|
76 \item Yes, if we are only after string matching. But we are after lexing where |
|
77 we need POSIX matching |
|
78 and calculate POSIX values. You cannot do this with any of the CFG-algorithms. |
|
79 \item Also it is not so easy to include extended regular expressions like $\sim{}r$ |
|
80 and $r^{\{n\}}$. |
|
81 \end{itemize} |
|
82 \end{frame} |
75 |
83 |
76 \begin{frame}[t,fragile] |
84 \begin{frame}[t,fragile] |
77 \begin{mybox3}{} |
85 \begin{minipage}{1.1\textwidth} |
78 In CW2, what is the derivative of RECD? |
86 \begin{mybox3}{} |
79 |
87 Why the hell did we bother for 4 long weeks with a lexing algorithm |
80 \begin{center} |
88 generating tokens, given the lecturer explains the parsing algorithm using |
81 \bl{$der\;c\;RECD(l, r) \;\;\dn\;\; ???$} |
89 strings as input? Has the lecturer gone insane? |
82 \end{center} |
90 \end{mybox3} |
83 \end{mybox3} |
91 \end{minipage}\bigskip |
84 \end{frame} |
92 |
85 |
93 \end{frame} |
|
94 |
|
95 |
|
96 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
97 %\begin{frame}[t,fragile] |
|
98 %\begin{mybox3}{} |
|
99 % In CW2, be careful with the order of defining regular expressions: |
|
100 % |
|
101 %\begin{verbatim} |
|
102 %val COMMENT : Rexp = ... ~ EOL |
|
103 %val EOL : Rexp = "\r\n" | "\n" |
|
104 %\end{verbatim} |
|
105 %\end{mybox3} |
|
106 %\end{frame} |
|
107 % |
|
108 % |
|
109 %\begin{frame}[t,fragile] |
|
110 %\begin{mybox3}{} |
|
111 % In CW2, what is the derivative of RECD? |
|
112 % |
|
113 %\begin{center} |
|
114 %\bl{$der\;c\;RECD(l, r) \;\;\dn\;\; ???$} |
|
115 %\end{center} |
|
116 %\end{mybox3} |
|
117 %\end{frame} |
|
118 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
86 |
119 |
87 |
120 |
88 |
121 |
89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
90 \begin{frame}[c] |
123 \begin{frame}[c] |