% !TEX program = xelatex+ −
\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../langs}+ −
+ −
\begin{document}+ −
+ −
\section*{Coursework 3}+ −
+ −
\noindent This coursework is worth 5\% and is due on 22 + −
November at 18:00. You are asked to implement a parser for the+ −
WHILE language and also an interpreter. You can do the+ −
implementation in any programming language you like, but you+ −
need to submit the source code with which you answered the+ −
questions, otherwise a mark of 0\% will be awarded. You should+ −
use the lexer from the previous coursework for the parser. + −
+ −
\subsection*{Disclaimer}+ −
+ −
It should be understood that the work you submit represents+ −
your own effort. You have not copied from anyone else. An+ −
exception is the Scala code I showed during the lectures,+ −
which you can use. You can also use your own code from the+ −
CW~1 and CW~2.+ −
+ −
+ −
\subsection*{Question 1}+ −
+ −
Design a grammar for the WHILE language and give the grammar+ −
rules. The main categories of non-terminals should be:+ −
+ −
\begin{itemize}+ −
\item arithmetic expressions (with the operations from the+ −
previous coursework, that is \pcode{+}, \pcode{-}, \pcode{*},+ −
\pcode{/} and \pcode{\%})+ −
\item boolean expressions (with the operations \pcode{==}, \pcode{<}, \pcode{>},+ −
\code{!=}, \pcode{&&}, \pcode{||}, \pcode{true} and \pcode{false})+ −
\item single statements (that is \pcode{skip}, assignments, \pcode{if}s,+ −
\pcode{while}-loops, \pcode{read} and \pcode{write})+ −
\item compound statements separated by semicolons+ −
\item blocks which are enclosed in curly parentheses+ −
\end{itemize}+ −
+ −
\noindent+ −
Make sure the grammar is not left-recursive.+ −
+ −
\subsection*{Question 2}+ −
+ −
You should implement a parser for the WHILE language using+ −
parser combinators. Be careful that the parser takes as input+ −
a stream, or list, of tokens generated by the tokenizer from+ −
the previous coursework. For this you might want to filter out + −
whitespaces and comments. Your parser should be able to handle+ −
the WHILE programs in Figures~\ref{fib} and \ref{loop}.+ −
In addition give the parse tree for the statement:+ −
+ −
\begin{lstlisting}[language=While,numbers=none]+ −
if (a < b) then skip else a := a * b + 1+ −
\end{lstlisting}+ −
+ −
\noindent+ −
A (possibly incomplete) datatype for parse trees in Scala would+ −
look as in Figure~\ref{trees}.+ −
+ −
\begin{figure}+ −
\begin{lstlisting}[language=Scala]+ −
abstract class Stmt+ −
abstract class AExp+ −
abstract class BExp + −
+ −
type Block = List[Stmt]+ −
+ −
case object Skip extends Stmt+ −
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt+ −
case class While(b: BExp, bl: Block) extends Stmt+ −
case class Assign(s: String, a: AExp) extends Stmt+ −
+ −
case class Var(s: String) extends AExp+ −
case class Num(i: Int) extends AExp+ −
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp+ −
+ −
case object True extends BExp+ −
case object False extends BExp+ −
case class Bop(o: String, a1: AExp, a2: AExp) extends BExp+ −
case class Lop(o: String, b1: BExp, b2: BExp) extends BExp+ −
\end{lstlisting}+ −
\caption{The datatype for parse trees in Scala.\label{trees}}+ −
\end{figure}+ −
+ −
\subsection*{Question 3}+ −
+ −
Implement an interpreter for the WHILE language you designed+ −
and parsed in Question 1 and 2. This interpreter should take+ −
as input a parse tree. However be careful because, programs+ −
contain variables and variable assignments. This means+ −
you need to maintain a kind of memory, or environment,+ −
where you can look up a value of a variable and also+ −
store a new value if it is assigned. Therefore an+ −
evaluation function (interpreter) needs to look roughly as + −
follows + −
+ −
\begin{lstlisting}[numbers=none]+ −
eval_stmt(stmt, env)+ −
\end{lstlisting}+ −
+ −
\noindent + −
where \pcode{stmt} corresponds to the parse tree+ −
of the program and \pcode{env} is an environment+ −
acting as a store for variable values. + −
Consider the Fibonacci program in Figure~\ref{fib}.+ −
At the beginning of the program this store will be + −
empty, but needs to be extended in line 3 and 4 where + −
the variables \pcode{minus1} and \pcode{minus2}+ −
are assigned values. These values need to be reassigned in+ −
lines 7 and 8. The program should be interpreted+ −
according to straightforward rules: for example an+ −
if-statement will ``run'' the if-branch if the boolean+ −
evaluates to \pcode{true}, otherwise the else-branch.+ −
Loops should be run as long as the boolean is \pcode{true}.+ −
+ −
Give some time measurements for your interpreter+ −
and the loop program in Figure~\ref{loop}. For example+ −
how long does your interpreter take when \pcode{start}+ −
is initialised with 100, 500 and so on. How far can+ −
you scale this value if you are willing to wait, say+ −
1 Minute?+ −
+ −
\begin{figure}[p]+ −
\begin{center}+ −
\mbox{\lstinputlisting[language=while]{../progs/fib.while}}+ −
\end{center}+ −
\caption{Fibonacci program in the WHILE language.\label{fib}}+ −
\end{figure}+ −
+ −
\begin{figure}[p]+ −
\begin{center}+ −
\mbox{\lstinputlisting[language=while]{../progs/loops.while}}+ −
\end{center}+ −
\caption{The three-nested-loops program in the WHILE language. + −
Usually used for timing measurements.\label{loop}}+ −
\end{figure}+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −