2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../langs} |
3 \usepackage{../langs} |
4 |
4 |
5 \begin{document} |
5 \begin{document} |
6 |
6 |
7 \section*{Coursework 3 (Strand 1)} |
7 \section*{Coursework 3} |
8 |
8 |
9 \noindent This coursework is worth 5\% and is due on 27 |
9 \noindent This coursework is worth 5\% and is due on 24 |
10 November at 16:00. You are asked to implement a parser for the |
10 November at 16:00. You are asked to implement a parser for the |
11 WHILE language and also an interpreter. You can do the |
11 WHILE language and also an interpreter. 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 should |
14 questions, otherwise a mark of 0\% will be awarded. You should |
21 exception is the Scala code I showed during the lectures, |
21 exception is the Scala code I showed during the lectures, |
22 which you can use. You can also use your own code from the |
22 which you can use. You can also use your own code from the |
23 CW~1 and CW~2. |
23 CW~1 and CW~2. |
24 |
24 |
25 |
25 |
26 \subsection*{Question 1 (marked with 1\%)} |
26 \subsection*{Question 1} |
27 |
27 |
28 Design a grammar for the WHILE language and give the grammar |
28 Design a grammar for the WHILE language and give the grammar |
29 rules. The main categories of non-terminal should be: |
29 rules. The main categories of non-terminal should be: |
30 |
30 |
31 \begin{itemize} |
31 \begin{itemize} |
32 \item arithmetic expressions (with the operations from the |
32 \item arithmetic expressions (with the operations from the |
33 previous coursework, such as \pcode{+}, \pcode{*} and so on) |
33 previous coursework, such as \pcode{+}, \pcode{*} and so on) |
37 \pcode{while}-loops and so on) |
37 \pcode{while}-loops and so on) |
38 \item compound statements separated by semicolons |
38 \item compound statements separated by semicolons |
39 \item blocks which are enclosed in curly parentheses |
39 \item blocks which are enclosed in curly parentheses |
40 \end{itemize} |
40 \end{itemize} |
41 |
41 |
42 \subsection*{Question 2 (marked with 2\%)} |
42 \subsection*{Question 2} |
43 |
43 |
44 You should implement a parser for the WHILE language using |
44 You should implement a parser for the WHILE language using |
45 parser combinators. Be careful that the parser takes as input |
45 parser combinators. Be careful that the parser takes as input |
46 a stream, or list, of tokens generated by the tokenizer from |
46 a stream, or list, of tokens generated by the tokenizer from |
47 the previous coursework. For this you might filter out |
47 the previous coursework. For this you might want to filter out |
48 whitespaces and comments. Your parser should be able to handle |
48 whitespaces and comments. Your parser should be able to handle |
49 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
49 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
50 In addition give the parse tree for the statement: |
50 In addition give the parse tree for the statement: |
51 |
51 |
52 \begin{lstlisting}[language=While,numbers=none] |
52 \begin{lstlisting}[language=While,numbers=none] |
79 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
79 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
80 \end{lstlisting} |
80 \end{lstlisting} |
81 \caption{The datatype for parse trees in Scala.\label{trees}} |
81 \caption{The datatype for parse trees in Scala.\label{trees}} |
82 \end{figure} |
82 \end{figure} |
83 |
83 |
84 \subsection*{Question 3 (marked with 2\%)} |
84 \subsection*{Question 3} |
85 |
85 |
86 Implement an interpreter for the WHILE language you designed |
86 Implement an interpreter for the WHILE language you designed |
87 and parsed in Question 1 and 2. This interpreter should take |
87 and parsed in Question 1 and 2. This interpreter should take |
88 as input a parse tree. However be careful because programs |
88 as input a parse tree. However be careful because, programs |
89 contain variables and variable assignments. This means |
89 contain variables and variable assignments. This means |
90 you need to maintain a kind of memory, or environment, |
90 you need to maintain a kind of memory, or environment, |
91 where you can look up a value of a variable and also |
91 where you can look up a value of a variable and also |
92 store a new value if it is assigned. Therefore an |
92 store a new value if it is assigned. Therefore an |
93 evaluation function (interpreter) needs to look roughly as |
93 evaluation function (interpreter) needs to look roughly as |