95 |
95 |
96 \section*{Coursework 9 (Scala)} |
96 \section*{Coursework 9 (Scala)} |
97 |
97 |
98 This coursework is worth 10\%. It is about a regular expression |
98 This coursework is worth 10\%. It is about a regular expression |
99 matcher and the shunting yard algorithm by Dijkstra. The first part is |
99 matcher and the shunting yard algorithm by Dijkstra. The first part is |
100 due on 6 December at 11pm; the second, more advanced part, is due on |
100 due on \cwNINE{} at 11pm; the second, more advanced part, is due on |
101 20 December at 11pm. In the first part, you are asked to implement a |
101 \cwNINEa{} at 11pm. In the first part, you are asked to implement a |
102 regular expression matcher based on derivatives of regular |
102 regular expression matcher based on derivatives of regular |
103 expressions. The background is that regular expression matching in |
103 expressions. The background is that ``out-of-the-box'' regular |
104 languages like Java, JavaScript and Python can sometimes be excruciatingly |
104 expression matching in mainstream languages like Java, JavaScript and |
105 slow. The advanced part is about the shunting yard algorithm that |
105 Python can sometimes be excruciatingly slow. You are supposed to implement |
106 transforms the usual infix notation of arithmetic expressions into the |
106 an regular expression macther that is much, much faster. The advanced part is |
107 postfix notation, which is for example used in compilers.\bigskip |
107 about the shunting yard algorithm that transforms the usual infix |
|
108 notation of arithmetic expressions into the postfix notation, which is |
|
109 for example used in compilers.\bigskip |
108 |
110 |
109 \IMPORTANT{} |
111 \IMPORTANT{} |
110 |
112 |
111 \noindent |
113 \noindent |
112 Also note that the running time of each part will be restricted to a |
114 Also note that the running time of each part will be restricted to a |