15 |
15 |
16 |
16 |
17 \subsection*{Question 1 (marked with 1\%)} |
17 \subsection*{Question 1 (marked with 1\%)} |
18 |
18 |
19 Design a grammar for the WHILE language and give the grammar |
19 Design a grammar for the WHILE language and give the grammar |
20 rules. The main categories of non-terminal will be: |
20 rules. The main categories of non-terminal should be: |
21 |
21 |
22 \begin{itemize} |
22 \begin{itemize} |
23 \item arithmetic expressions (with the operations from the |
23 \item arithmetic expressions (with the operations from the |
24 previous coursework, such as \pcode{+}, \pcode{*} and so on) |
24 previous coursework, such as \pcode{+}, \pcode{*} and so on) |
25 \item boolean expressions (such as \pcode{<}, \pcode{!=} and |
25 \item boolean expressions (such as \pcode{<}, \code{!=} and |
26 so on) |
26 so on) |
27 \item single statements (such as \pcode{skip}, assignments, \pcode{if}s, |
27 \item single statements (such as \pcode{skip}, assignments, \pcode{if}s, |
28 \pcode{while}-loops and so on) |
28 \pcode{while}-loops and so on) |
29 \item compound statements separated by semicolons |
29 \item compound statements separated by semicolons |
30 \item blocks which are enclosed in curly parentheses |
30 \item blocks which are enclosed in curly parentheses |
31 \end{itemize} |
31 \end{itemize} |
32 |
32 |
33 \subsection*{Question 2 (marked with 2\%)} |
33 \subsection*{Question 2 (marked with 2\%)} |
34 |
34 |
35 You should implement a parser based on parser combinators |
35 You should implement a parser for the WHILE language using |
36 for the WHILE language. Be careful that the parser takes |
36 parser combinators. Be careful that the parser takes as input |
37 as input a stream of token generated by the tokenizer from |
37 a stream, or list, of tokens generated by the tokenizer from |
38 the previous courswork. Your parser should be able to handle |
38 the previous coursework. Your parser should be able to handle |
39 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
39 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
|
40 In addition give the parse tree for the statement: |
40 |
41 |
41 Give the parse tree for the statement: |
42 \begin{lstlisting}[language=While,numbers=none] |
|
43 if (a < b) then skip else a := a * b + 1 |
|
44 \end{lstlisting} |
42 |
45 |
43 \begin{center} |
46 \noindent |
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 |
47 A (possibly incomplete) datatype for parse trees in Scala would |
48 look as in Figure~\ref{trees}. |
48 look as in Figure~\ref{trees}. |
49 |
49 |
50 \begin{figure} |
50 \begin{figure} |
51 \begin{lstlisting}[language=Scala] |
51 \begin{lstlisting}[language=Scala] |
66 |
66 |
67 case object True extends BExp |
67 case object True extends BExp |
68 case object False extends BExp |
68 case object False extends BExp |
69 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
69 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
70 \end{lstlisting} |
70 \end{lstlisting} |
71 \caption{The datatype for parse trees in Scala.} |
71 \caption{The datatype for parse trees in Scala.\label{trees}} |
72 \end{figure} |
72 \end{figure} |
73 |
73 |
74 \subsection*{Question 3 (marked with 2\%)} |
74 \subsection*{Question 3 (marked with 2\%)} |
75 |
75 |
76 Implement an interpreter for the WHILE language you |
76 Implement an interpreter for the WHILE language you designed |
77 designed and parsed above. |
77 and parsed in Question 1 and 2. This interpreter should take |
|
78 as input a parse tree. However be careful because programs |
|
79 contain variables and variable assignments. This means |
|
80 you need to maintain a kind of memory, or environment, |
|
81 where you can look up a value of a variable and also |
|
82 store a new value if it is assigned. Therefore an |
|
83 evaluation function (interpreter) needs to look roughly as |
|
84 follows |
78 |
85 |
|
86 \begin{lstlisting}[numbers=none] |
|
87 eval_stmt(stmt, env) |
|
88 \end{lstlisting} |
79 |
89 |
|
90 \noindent |
|
91 where \pcode{stmt} corresponds to the parse tree |
|
92 of the program and \pcode{env} is an environment |
|
93 acting as a store for variable values. |
|
94 Consider the Fibonacci program in Figure~\ref{fib}. |
|
95 At the beginning of the program this store will be |
|
96 empty, but needs to be extended in line 3 and 4 where |
|
97 the variables \pcode{minus1} and \pcode{minus2} |
|
98 are assigned values. These values need to be reassigned in |
|
99 lines 7 and 8. The program should be interpreted |
|
100 according to straightforward rules: for example an |
|
101 if-statement will ``run'' the if-branch if the boolean |
|
102 evaluates to \pcode{true}, otherwise the else-branch. |
|
103 Loops should be run as long as the boolean is \pcode{true}. |
|
104 |
|
105 Give some time measurements for your interpreter |
|
106 and the loop program in Figure~\ref{loop}. For example |
|
107 how long does your interpreter take when \pcode{start} |
|
108 is initialised with 100, 500 and so on. How far can |
|
109 you scale this value if you are willing to wait, say |
|
110 1 Minute. |
80 |
111 |
81 \begin{figure}[p] |
112 \begin{figure}[p] |
82 \begin{center} |
113 \begin{center} |
83 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
114 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
84 \end{center} |
115 \end{center} |