10 |
10 |
11 |
11 |
12 |
12 |
13 \noindent This coursework is worth 10\% and is due on \cwTHREE{} at |
13 \noindent This coursework is worth 10\% and is due on \cwTHREE{} at |
14 16:00. You are asked to implement a parser for the WHILE language and |
14 16:00. You are asked to implement a parser for the WHILE language and |
15 also an interpreter. The parser needs to use parser combinators. |
15 also an interpreter. The parser needs to use parser combinators. You |
16 You can do the implementation in any programming |
16 can do the implementation in any programming language you like, but |
17 language you like, but you need to submit the source code with which |
17 you need to submit the source code with which you answered the |
18 you answered the questions, otherwise a mark of 0\% will be |
18 questions, otherwise a mark of 0\% will be awarded. If you use Scala |
19 awarded. You should use the lexer from the previous coursework for the |
19 in your code, a good place to start is the file \texttt{comb1.sc} and |
20 parser. Please submit your code to Github by the deadline. |
20 \texttt{comb2.sc} uploaded to KEATS. Feel free to use the ``hack'' |
|
21 explained during the lectures. This might make your grammar |
|
22 simpler. However, make sure you understand the code involved in the |
|
23 ``hack'' because if you just do ``mix-and-match'' you will receive |
|
24 strange errors. The main function that will be tested is called |
|
25 \texttt{eval} and \texttt{Stmts.parse\_all}. The latter expects a list |
|
26 of tokens as input and generates an AST. The former expects an AST and |
|
27 ``runs'' the program. The marks will be distributed such that 6 marks |
|
28 are given for the correct grammar (and parsers); 4 marks for the correct |
|
29 \texttt{eval} function. You should use the lexer from CW2 for the |
|
30 parser - you potentially need to make additions for CW2. |
21 |
31 |
22 \subsection*{Disclaimer\alert} |
32 \subsection*{Disclaimer\alert} |
23 |
33 |
24 It should be understood that the work you submit represents your own |
34 It should be understood that the work you submit represents your own |
25 effort. You have not copied from anyone else. An exception is the |
35 effort. You have not copied from anyone else. An exception is the |
26 Scala code I showed during the lectures or uploaded to KEATS, which |
36 Scala code I showed during the lectures or uploaded to KEATS, which |
27 you can both use. You can also use your own code from the CW~1 and |
37 you can both use. You can also use your own code from the CW~1 and |
28 CW~2. But do not |
38 CW~2. But do not |
29 be tempted to ask Github Copilot for help or do any other |
39 be tempted to ask Github Copilot for help or do any other |
30 shenanigans like this! |
40 shenanigans like this! |
|
41 |
|
42 \subsection*{Syntax Error in Template File cw03.sc\alert} |
|
43 |
|
44 Apologies, there is a small syntax error in the template file where a variable |
|
45 needs to be called \texttt{tks} instead of \texttt{tk}. The code |
|
46 in question is at the end of \texttt{cw03.sc} and should be like |
|
47 this (see lines 5, 6 and 8): |
|
48 |
|
49 \begin{lstlisting}[language=Scala,numbers=left] |
|
50 @main |
|
51 def test(file: String) = { |
|
52 val contents = os.read(os.pwd / "examples" / file) |
|
53 println(s"Lex $file: ") |
|
54 val tks = tokenise(contents) |
|
55 println(tks.mkString(",")) |
|
56 println(s"Parse $file: ") |
|
57 val ast = Stmts.parse_all(tks).head |
|
58 println(ast) |
|
59 println(s"Eval $file: ") |
|
60 println(eval(ast)) |
|
61 } |
|
62 \end{lstlisting} |
|
63 |
31 |
64 |
32 |
65 |
33 \subsection*{Question 1} |
66 \subsection*{Question 1} |
34 |
67 |
35 Design a grammar for the WHILE language and give the grammar |
68 Design a grammar for the WHILE language and give the grammar |
52 Make sure the grammar is not left-recursive. |
85 Make sure the grammar is not left-recursive. |
53 |
86 |
54 \subsection*{Question 2} |
87 \subsection*{Question 2} |
55 |
88 |
56 You should implement a parser for the WHILE language using parser |
89 You should implement a parser for the WHILE language using parser |
57 combinators. Be careful that the parser takes as input a stream, or |
90 combinators. Be careful that the parser takes as input a list of |
58 list, of \emph{tokens} generated by the tokenizer from the previous |
91 \emph{tokens} generated by the tokenizer from the previous |
59 coursework. For this you might want to filter out whitespaces and |
92 coursework. For this you might want to filter out whitespaces and |
60 comments. Your parser should be able to handle the WHILE programs in |
93 comments. Your parser should be able to handle the WHILE programs in |
61 Figures~\ref{fib} -- \ref{collatz}. In addition give the |
94 the \texttt{examples} directory. The output of the parser is an |
62 parse tree according to your grammar for the statement: |
95 abstract syntax tree (AST). A (possibly incomplete) datatype for ASTs |
63 |
96 of the WHILE language is shown in Figure~\ref{trees}. |
64 \begin{lstlisting}[language=While,numbers=none] |
|
65 if (a < b) then skip else a := a * b + 1 |
|
66 \end{lstlisting} |
|
67 |
|
68 \noindent |
|
69 The output of the parser is an abstract syntax tree (AST). |
|
70 A (possibly incomplete) datatype for ASTs of the WHILE language |
|
71 is shown in Figure~\ref{trees}. |
|
72 |
97 |
73 \begin{figure}[p] |
98 \begin{figure}[p] |
74 \begin{lstlisting}[language=Scala] |
99 \begin{lstlisting}[language=Scala] |
75 abstract class Stmt |
100 abstract class Stmt |
76 abstract class AExp |
101 abstract class AExp |
131 evaluates to \pcode{true}, otherwise the else-branch. |
156 evaluates to \pcode{true}, otherwise the else-branch. |
132 Loops should be run as long as the boolean is \pcode{true}. |
157 Loops should be run as long as the boolean is \pcode{true}. |
133 Note also that some programs contain a read-statement, |
158 Note also that some programs contain a read-statement, |
134 which means you need to read and integer from the commandline |
159 which means you need to read and integer from the commandline |
135 and store the value in the corresponding variable. |
160 and store the value in the corresponding variable. |
136 Programs you should be able to run are shown in |
161 Programs you should be able to run are given in the |
137 Figures \ref{fib} -- \ref{collatz}. The output |
162 \texttt{examples} directory. The output |
138 of the \texttt{primes.while} should look as follows: |
163 of the \texttt{primes.while} should look as follows: |
139 |
164 |
140 \begin{figure}[h] |
165 \begin{figure}[h] |
141 {\small |
166 {\small |
142 \begin{lstlisting}[numbers=none] |
167 \begin{lstlisting}[numbers=none] |
168 Map(end -> 100, n -> 100, f -> 4, tmp -> 1) |
193 Map(end -> 100, n -> 100, f -> 4, tmp -> 1) |
169 \end{lstlisting}} |
194 \end{lstlisting}} |
170 \caption{Sample output for the file \texttt{primes.while}.\label{fib}} |
195 \caption{Sample output for the file \texttt{primes.while}.\label{fib}} |
171 \end{figure} |
196 \end{figure} |
172 |
197 |
173 \noindent |
|
174 Give some time measurements for your interpreter |
|
175 and the loop program in Figure~\ref{loop}. For example |
|
176 how long does your interpreter take when \pcode{start} |
|
177 is initialised with 100, 500 and so on. How far can |
|
178 you scale this value if you are willing to wait, say |
|
179 1 Minute? |
|
180 |
|
181 \clearpage |
|
182 |
|
183 \begin{figure}[h] |
|
184 \lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/fib.while} |
|
185 \caption{Fibonacci program in the WHILE language.\label{fib}} |
|
186 \end{figure} |
|
187 |
|
188 \begin{figure}[h] |
|
189 \lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/loops.while} |
|
190 \caption{The three-nested-loops program in the WHILE language. |
|
191 Usually used for timing measurements.\label{loop}} |
|
192 \end{figure} |
|
193 |
|
194 \begin{figure}[h] |
|
195 \lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/primes.while} |
|
196 \caption{Prime number program.\label{primes}} |
|
197 \end{figure} |
|
198 |
|
199 |
|
200 \begin{figure}[p] |
|
201 \lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/collatz2.while} |
|
202 \caption{Collatz series program.\label{collatz}} |
|
203 \end{figure} |
|
204 |
|
205 \clearpage |
|
206 \newpage |
|
207 \section*{Answers} |
|
208 |
|
209 \mbox{} |
|
210 |
|
211 \noindent |
|
212 \textbf{Name:}\uline{\hfill}\bigskip |
|
213 |
|
214 |
|
215 |
|
216 \noindent |
|
217 \textbf{Question 1 (Grammar):}\\ |
|
218 |
|
219 \mbox{}\\[9cm] |
|
220 |
|
221 \newpage |
|
222 \noindent |
|
223 \textbf{Question 2 (Parse Tree):}\\ |
|
224 |
|
225 \mbox{}\\[8cm] |
|
226 |
|
227 |
|
228 \noindent |
|
229 \textbf{Question 3 (Timings):}\\ |
|
230 |
|
231 \begin{center} |
|
232 \def\arraystretch{1.5} |
|
233 \begin{tabular}{l|l} |
|
234 n & secs\\ |
|
235 \hline |
|
236 100 & \\ |
|
237 500 & \\ |
|
238 700 & \\ |
|
239 1000 & \\ |
|
240 \\ |
|
241 \\ |
|
242 \\ |
|
243 \\ |
|
244 \end{tabular} |
|
245 \end{center} |
|
246 |
198 |
247 \end{document} |
199 \end{document} |
248 |
200 |
249 %%% Local Variables: |
201 %%% Local Variables: |
250 %%% mode: latex |
202 %%% mode: latex |