56 combinators. Be careful that the parser takes as input a stream, or |
56 combinators. Be careful that the parser takes as input a stream, or |
57 list, of \emph{tokens} generated by the tokenizer from the previous |
57 list, of \emph{tokens} generated by the tokenizer from the previous |
58 coursework. For this you might want to filter out whitespaces and |
58 coursework. For this you might want to filter out whitespaces and |
59 comments. Your parser should be able to handle the WHILE programs in |
59 comments. Your parser should be able to handle the WHILE programs in |
60 Figures~\ref{fib} -- \ref{collatz}. In addition give the |
60 Figures~\ref{fib} -- \ref{collatz}. In addition give the |
61 parse tree for the statement: |
61 parse tree according to your grammar for the statement: |
62 |
62 |
63 \begin{lstlisting}[language=While,numbers=none] |
63 \begin{lstlisting}[language=While,numbers=none] |
64 if (a < b) then skip else a := a * b + 1 |
64 if (a < b) then skip else a := a * b + 1 |
65 \end{lstlisting} |
65 \end{lstlisting} |
66 |
66 |
67 \noindent |
67 \noindent |
68 A (possibly incomplete) datatype for parse trees in Scala is shown |
68 The output of the parser is an abstract syntax tree (AST). |
69 in Figure~\ref{trees}. |
69 A (possibly incomplete) datatype for ASTs of the WHILE language |
|
70 is shown in Figure~\ref{trees}. |
70 |
71 |
71 \begin{figure}[p] |
72 \begin{figure}[p] |
72 \begin{lstlisting}[language=Scala] |
73 \begin{lstlisting}[language=Scala] |
73 abstract class Stmt |
74 abstract class Stmt |
74 abstract class AExp |
75 abstract class AExp |
93 case object False extends BExp |
94 case object False extends BExp |
94 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
95 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
95 case class Lop(o: String, b1: BExp, b2: BExp) extends BExp |
96 case class Lop(o: String, b1: BExp, b2: BExp) extends BExp |
96 // logical operations: and, or |
97 // logical operations: and, or |
97 \end{lstlisting} |
98 \end{lstlisting} |
98 \caption{The datatype for parse trees in Scala.\label{trees}} |
99 \caption{The datatype for abstract syntax trees in Scala.\label{trees}} |
99 \end{figure} |
100 \end{figure} |
100 |
101 |
101 \subsection*{Question 3} |
102 \subsection*{Question 3} |
102 |
103 |
103 Implement an interpreter for the WHILE language you designed |
104 Implement an interpreter for the WHILE language you designed |
104 and parsed in Question 1 and 2. This interpreter should take |
105 and parsed in Question 1 and 2. This interpreter should take |
105 as input a parse tree. However be careful because, programs |
106 as input an AST. However be careful because, programs |
106 contain variables and variable assignments. This means |
107 contain variables and variable assignments. This means |
107 you need to maintain a kind of memory, or environment, |
108 you need to maintain a kind of memory, or environment, |
108 where you can look up a value of a variable and also |
109 where you can look up a value of a variable and also |
109 store a new value if it is assigned. Therefore an |
110 store a new value if it is assigned. Therefore an |
110 evaluation function (interpreter) needs to look roughly as |
111 evaluation function (interpreter) needs to look roughly as |