4 |
4 |
5 \begin{document} |
5 \begin{document} |
6 |
6 |
7 \section*{Coursework 2 (Strand 1)} |
7 \section*{Coursework 2 (Strand 1)} |
8 |
8 |
9 \noindent This coursework is worth 5\% and is due on 4 |
9 \noindent This coursework is worth 5\% and is due on 3 |
10 November at 16:00. You are asked to implement the Sulzmann \& |
10 November at 16:00. You are asked to implement the Sulzmann \& |
11 Lu lexer for the WHILE language. You can do the |
11 Lu lexer for the WHILE language. You can do the |
12 implementation in any programming language you like, but you |
12 implementation in any programming language you like, but you |
13 need to submit the source code with which you answered the |
13 need to submit the source code with which you answered the |
14 questions, otherwise a mark of 0\% will be awarded. You can |
14 questions, otherwise a mark of 0\% will be awarded. You can |
86 \noindent |
86 \noindent |
87 but also the following extended regular expressions |
87 but also the following extended regular expressions |
88 |
88 |
89 \begin{center} |
89 \begin{center} |
90 \begin{tabular}{ll} |
90 \begin{tabular}{ll} |
91 $[c_1 c_2 \ldots c_n]$ & a range of characters\\ |
91 $[c_1,c_2,\ldots,c_n]$ & a set of characters\\ |
92 $r^+$ & one or more times $r$\\ |
92 $r^+$ & one or more times $r$\\ |
93 $r^?$ & optional $r$\\ |
93 $r^?$ & optional $r$\\ |
94 $r^{\{n\}}$ & n-times $r$\\ |
94 $r^{\{n\}}$ & n-times $r$\\ |
95 \end{tabular} |
95 \end{tabular} |
96 \end{center} |
96 \end{center} |
97 |
97 |
98 \noindent |
98 \noindent |
99 Later on you will also need the record regular expressions: |
99 Later on you will also need the record regular expression: |
100 |
100 |
101 \begin{center} |
101 \begin{center} |
102 \begin{tabular}{ll} |
102 \begin{tabular}{ll} |
103 $REC(x:r)$ & record regular expression\\ |
103 $REC(x:r)$ & record regular expression\\ |
104 \end{tabular} |
104 \end{tabular} |
105 \end{center} |
105 \end{center} |
106 |
106 |
107 \noindent Try to design your regular expressions to be as |
107 \noindent Try to design your regular expressions to be as |
108 small as possible. For example you should use character ranges |
108 small as possible. For example you should use character sets |
109 for identifiers and numbers. |
109 for identifiers and numbers. Feel free to use the general |
|
110 character constructor \textit{CFUN} introduced in CW 1. |
110 |
111 |
111 \subsection*{Question 2} |
112 \subsection*{Question 2} |
112 |
113 |
113 Implement the Sulzmann \& Lu lexer from the lectures. For |
114 Implement the Sulzmann \& Lu lexer from the lectures. For |
114 this you need to implement the functions $nullable$ and $der$ |
115 this you need to implement the functions $nullable$ and $der$ |
117 the extended regular expressions from Q1. Write down the |
118 the extended regular expressions from Q1. Write down the |
118 clauses for |
119 clauses for |
119 |
120 |
120 \begin{center} |
121 \begin{center} |
121 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
122 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
122 $mkeps([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\ |
123 $mkeps([c_1,c_2,\ldots,c_n])$ & $\dn$ & $?$\\ |
123 $mkeps(r^+)$ & $\dn$ & $?$\\ |
124 $mkeps(r^+)$ & $\dn$ & $?$\\ |
124 $mkeps(r^?)$ & $\dn$ & $?$\\ |
125 $mkeps(r^?)$ & $\dn$ & $?$\\ |
125 $mkeps(r^{\{n\}})$ & $\dn$ & $?$\medskip\\ |
126 $mkeps(r^{\{n\}})$ & $\dn$ & $?$\medskip\\ |
126 $inj\, ([c_1 c_2 \ldots c_n])\,c\,\ldots$ & $\dn$ & $?$\\ |
127 $inj\, ([c_1,c_2,\ldots,c_n])\,c\,\ldots$ & $\dn$ & $?$\\ |
127 $inj\, (r^+)\,c\,\ldots$ & $\dn$ & $?$\\ |
128 $inj\, (r^+)\,c\,\ldots$ & $\dn$ & $?$\\ |
128 $inj\, (r^?)\,c\,\ldots$ & $\dn$ & $?$\\ |
129 $inj\, (r^?)\,c\,\ldots$ & $\dn$ & $?$\\ |
129 $inj\, (r^{\{n\}})\,c\,\ldots$ & $\dn$ & $?$\\ |
130 $inj\, (r^{\{n\}})\,c\,\ldots$ & $\dn$ & $?$\\ |
130 \end{tabular} |
131 \end{tabular} |
131 \end{center} |
132 \end{center} |
173 Figure~\ref{fib} and \ref{loop}. Give the tokens of these |
174 Figure~\ref{fib} and \ref{loop}. Give the tokens of these |
174 programs where whitespaces are filtered out. |
175 programs where whitespaces are filtered out. |
175 |
176 |
176 |
177 |
177 \begin{figure}[p] |
178 \begin{figure}[p] |
178 \begin{center} |
|
179 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
179 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
180 \end{center} |
|
181 \caption{Fibonacci program in the WHILE language.\label{fib}} |
180 \caption{Fibonacci program in the WHILE language.\label{fib}} |
182 \end{figure} |
181 \end{figure} |
183 |
182 |
184 \begin{figure}[p] |
183 \begin{figure}[p] |
185 \begin{center} |
|
186 \mbox{\lstinputlisting[language=while]{../progs/loops.while}} |
184 \mbox{\lstinputlisting[language=while]{../progs/loops.while}} |
187 \end{center} |
|
188 \caption{The three-nested-loops program in the WHILE language. |
185 \caption{The three-nested-loops program in the WHILE language. |
189 Usually used for timing measurements.\label{loop}} |
186 Usually used for timing measurements.\label{loop}} |
190 \end{figure} |
187 \end{figure} |
191 |
188 |
192 \end{document} |
189 \end{document} |