7 \section*{Coursework 3} |
7 \section*{Coursework 3} |
8 |
8 |
9 \noindent |
9 \noindent |
10 This coursework is worth 5\% and is due on 28 November at 16:00. You |
10 This coursework is worth 5\% and is due on 28 November at 16:00. You |
11 are asked to implement a parser for the WHILE language and also |
11 are asked to implement a parser for the WHILE language and also |
12 an iterpreter. |
12 an interpreter. You should use the lexer from the previous |
|
13 coursework for the parser. |
13 |
14 |
14 |
15 |
15 |
16 |
16 \subsection*{Question 1 (marked with 1\%)} |
17 \subsection*{Question 1 (marked with 1\%)} |
17 |
18 |
18 You need to lex and parse WHILE programs and submit the assembler |
19 Design a grammar for the WHILE language and give the grammar |
19 instructions for the Fibonacci program and for the program you submitted |
20 rules. The main categories of non-terminal will be: |
20 in Coursework 2 in Question 3. The latter should be so modified that |
21 |
21 a user can input the upper bound on the console (in the original question |
22 \begin{itemize} |
22 it was fixed to 100). |
23 \item arithmetic expressions (with the operations from the |
|
24 previous coursework, such as \pcode{+}, \pcode{*} and so on) |
|
25 \item boolean expressions (such as \pcode{<}, \pcode{!=} and |
|
26 so on) |
|
27 \item single statements (such as \pcode{skip}, assignments, \pcode{if}s, |
|
28 \pcode{while}-loops and so on) |
|
29 \item compound statements separated by semicolons |
|
30 \item blocks which are enclosed in curly parentheses |
|
31 \end{itemize} |
23 |
32 |
24 \subsection*{Question 2 (marked with 2\%)} |
33 \subsection*{Question 2 (marked with 2\%)} |
25 |
34 |
|
35 You should implement a parser based on parser combinators |
|
36 for the WHILE language. Be careful that the parser takes |
|
37 as input a stream of token generated by the tokenizer from |
|
38 the previous courswork. Your parser should be able to handle |
|
39 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
|
40 |
|
41 Give the parse tree for the statement: |
|
42 |
|
43 \begin{center} |
|
44 \code{if (a < b) then skip else a := a * b + 1} |
|
45 \end{center} |
|
46 |
|
47 A (possibly incomplete) datatype for parse trees in Scala would |
|
48 look as in Figure~\ref{trees}. |
|
49 |
|
50 \begin{figure} |
|
51 \begin{lstlisting}[language=Scala] |
|
52 abstract class Stmt |
|
53 abstract class AExp |
|
54 abstract class BExp |
|
55 |
|
56 type Block = List[Stmt] |
|
57 |
|
58 case object Skip extends Stmt |
|
59 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
|
60 case class While(b: BExp, bl: Block) extends Stmt |
|
61 case class Assign(s: String, a: AExp) extends Stmt |
|
62 |
|
63 case class Var(s: String) extends AExp |
|
64 case class Num(i: Int) extends AExp |
|
65 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
|
66 |
|
67 case object True extends BExp |
|
68 case object False extends BExp |
|
69 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
|
70 \end{lstlisting} |
|
71 \caption{The datatype for parse trees in Scala.} |
|
72 \end{figure} |
26 |
73 |
27 \subsection*{Question 3 (marked with 2\%)} |
74 \subsection*{Question 3 (marked with 2\%)} |
28 |
75 |
|
76 Implement an interpreter for the WHILE language you |
|
77 designed and parsed above. |
29 |
78 |
30 |
79 |
|
80 |
|
81 \begin{figure}[p] |
|
82 \begin{center} |
|
83 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
|
84 \end{center} |
|
85 \caption{Fibonacci program in the WHILE language.\label{fib}} |
|
86 \end{figure} |
|
87 |
|
88 \begin{figure}[p] |
|
89 \begin{center} |
|
90 \mbox{\lstinputlisting[language=while]{../progs/loops.while}} |
|
91 \end{center} |
|
92 \caption{The three-nested-loops program in the WHILE language. |
|
93 Usually used for timing measurements.\label{loop}} |
|
94 \end{figure} |
31 |
95 |
32 \end{document} |
96 \end{document} |
33 |
97 |
34 %%% Local Variables: |
98 %%% Local Variables: |
35 %%% mode: latex |
99 %%% mode: latex |