57 |
57 |
58 \noindent You can assume that $n$ and $m$ are greater or equal than |
58 \noindent You can assume that $n$ and $m$ are greater or equal than |
59 $0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip |
59 $0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip |
60 |
60 |
61 \noindent {\bf Important!} Your implementation should have explicit |
61 \noindent {\bf Important!} Your implementation should have explicit |
62 cases for the basic regular expressions, but also explicit cases for |
62 cases for the basic regular expressions, but also for explicit cases for |
63 the extended regular expressions. That means do not treat the extended |
63 the extended regular expressions. That means do not treat the extended |
64 regular expressions by just translating them into the basic ones. See |
64 regular expressions by just translating them into the basic ones. See |
65 also Question 2, where you are asked to explicitly give the rules for |
65 also Question 2, where you are asked to explicitly give the rules for |
66 \textit{nullable} and \textit{der} for the extended regular |
66 \textit{nullable} and \textit{der} for the extended regular |
67 expressions.\newpage |
67 expressions.\newpage |
170 \noindent |
170 \noindent |
171 Does your matcher produce the expected results? |
171 Does your matcher produce the expected results? |
172 |
172 |
173 \subsection*{Question 3} |
173 \subsection*{Question 3} |
174 |
174 |
175 There are a number of explicit regular expressions that deal with single or several |
175 As you can see, there are a number of explicit regular expressions |
176 characters, for example: |
176 that deal with single or several characters, for example: |
177 |
177 |
178 \begin{center} |
178 \begin{center} |
179 \begin{tabular}{ll} |
179 \begin{tabular}{ll} |
180 $c$ & match a single character\\ |
180 $c$ & matches a single character\\ |
181 $[c_1,c_2,\ldots,c_n]$ & match a set of characters---for character ranges\\ |
181 $[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\ |
182 $\textit{ALL}$ & match any character |
182 $\textit{ALL}$ & matches any character |
183 \end{tabular} |
183 \end{tabular} |
184 \end{center} |
184 \end{center} |
185 |
185 |
186 \noindent |
186 \noindent |
187 the latter is useful for matching any string (for example |
187 the latter is useful for matching any string (for example |
188 $\textit{ALL}^*$). In order to avoid having an explicit constructor |
188 by using $\textit{ALL}^*$). In order to avoid having an explicit constructor |
189 for each case, we can generalise all such cases and introduce a single |
189 for each case, we can generalise all these cases and introduce a single |
190 constructor $\textit{CFUN}(f)$ where $f$ is a function from characters |
190 constructor $\textit{CFUN}(f)$ where $f$ is a function from characters |
191 to a boolean. Implement |
191 to a boolean. The idea is that the function $f$ determines which character(s) |
|
192 are matched, namely those where $f$ returns \texttt{true}. |
|
193 In this question implement \textit{CFUN} and define |
192 |
194 |
193 \begin{center} |
195 \begin{center} |
194 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
196 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
195 $\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\ |
197 $\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\ |
196 $\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$ |
198 $\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$ |
197 \end{tabular} |
199 \end{tabular} |
198 \end{center} |
200 \end{center} |
199 |
201 |
200 \noindent in your matcher and then give definitions for |
202 \noindent in your matcher and then also give definitions for |
201 |
203 |
202 \begin{center} |
204 \begin{center} |
203 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
205 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
204 $c$ & $\dn$ & $\textit{CFUN}(?)$\\ |
206 $c$ & $\dn$ & $\textit{CFUN}(?)$\\ |
205 $[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\ |
207 $[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\ |