1 % !TEX program = xelatex

     2 \documentclass{article}

     3 \usepackage{../style}

     4 \usepackage{../langs}

     5 

     6 \begin{document}

     7 

     8 \section*{Coursework 3}

     9 

    10 

    11 

    12 \noindent This coursework is worth 10\% and is due on \cwTHREE{} at

    13 18:00. You are asked to implement a parser for the WHILE language and

    14 also an interpreter. You can do the implementation in any programming

    15 language you like, but you need to submit the source code with which

    16 you answered the questions, otherwise a mark of 0\% will be

    17 awarded. You should use the lexer from the previous coursework for the

    18 parser.  Please package everything(!) in a zip-file that creates a

    19 directory with the name \texttt{YournameYourFamilyname} on my end.

    20 

    21 \subsection*{Disclaimer\alert}

    22 

    23 It should be understood that the work you submit represents your own

    24 effort. You have not copied from anyone else. An exception is the

    25 Scala code I showed during the lectures or uploaded to KEATS, which

    26 you can both use. You can also use your own code from the CW~1 and

    27 CW~2.

    28 

    29 

    30 \subsection*{Question 1}

    31 

    32 Design a grammar for the WHILE language and give the grammar

    33 rules. The main categories of non-terminals should be:

    34 

    35 \begin{itemize}

    36 \item arithmetic expressions (with the operations from the

    37   previous coursework, that is \pcode{+}, \pcode{-}, \pcode{*},

    38   \pcode{/} and \pcode{\%})

    39 \item boolean expressions (with the operations \pcode{==}, \pcode{<}, \pcode{>},

    40   \code{>=}, \code{<=}, 

    41   \code{!=}, \pcode{&&}, \pcode{||}, \pcode{true} and \pcode{false})

    42 \item single statements (that is \pcode{skip}, assignments, \pcode{if}s,

    43   \pcode{while}-loops, \pcode{read} and \pcode{write})

    44 \item compound statements separated by semicolons

    45 \item blocks which are enclosed in curly parentheses

    46 \end{itemize}

    47 

    48 \noindent

    49 Make sure the grammar is not left-recursive.

    50 

    51 \subsection*{Question 2}

    52 

    53 You should implement a parser for the WHILE language using parser

    54 combinators. Be careful that the parser takes as input a stream, or

    55 list, of \emph{tokens} generated by the tokenizer from the previous

    56 coursework. For this you might want to filter out whitespaces and

    57 comments. Your parser should be able to handle the WHILE programs in

    58 Figures~\ref{fib}, \ref{loop} and \ref{primes}.  In addition give the

    59 parse tree for the statement:

    60 

    61 \begin{lstlisting}[language=While,numbers=none]

    62 if (a < b) then skip else a := a * b + 1

    63 \end{lstlisting}

    64 

    65 \noindent

    66 A (possibly incomplete) datatype for parse trees in Scala is shown

    67 in Figure~\ref{trees}.

    68 

    69 \begin{figure}[p]

    70 \begin{lstlisting}[language=Scala]

    71 abstract class Stmt

    72 abstract class AExp

    73 abstract class BExp 

    74 

    75 type Block = List[Stmt]

    76 

    77 case object Skip extends Stmt

    78 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt

    79 case class While(b: BExp, bl: Block) extends Stmt

    80 case class Assign(s: String, a: AExp) extends Stmt

    81 case class Read(s: String) extends Stmt

    82 case class WriteVar(s: String) extends Stmt  

    83 case class WriteStr(s: String) extends Stmt 

    84                       // for printing variables and strings

    85 

    86 case class Var(s: String) extends AExp

    87 case class Num(i: Int) extends AExp

    88 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp

    89 

    90 case object True extends BExp

    91 case object False extends BExp

    92 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp

    93 case class Lop(o: String, b1: BExp, b2: BExp) extends BExp

    94                      // logical operations: and, or

    95 \end{lstlisting}

    96 \caption{The datatype for parse trees in Scala.\label{trees}}

    97 \end{figure}

    98 

    99 \subsection*{Question 3}

   100 

   101 Implement an interpreter for the WHILE language you designed

   102 and parsed in Question 1 and 2. This interpreter should take

   103 as input a parse tree. However be careful because, programs

   104 contain variables and variable assignments. This means

   105 you need to maintain a kind of memory, or environment,

   106 where you can look up a value of a variable and also

   107 store a new value if it is assigned. Therefore an

   108 evaluation function (interpreter) needs to look roughly as 

   109 follows 

   110 

   111 \begin{lstlisting}[numbers=none]

   112 eval_stmt(stmt, env)

   113 \end{lstlisting}

   114 

   115 \noindent 

   116 where \pcode{stmt} corresponds to the parse tree

   117 of the program and \pcode{env} is an environment

   118 acting as a store for variable values. 

   119 Consider the Fibonacci program in Figure~\ref{fib}.

   120 At the beginning of the program this store will be 

   121 empty, but needs to be extended in line 3 and 4 where 

   122 the variables \pcode{minus1} and \pcode{minus2}

   123 are assigned values. These values need to be reassigned in

   124 lines 7 and 8. The program should  be interpreted

   125 according to straightforward rules: for example an

   126 if-statement will ``run'' the if-branch if the boolean

   127 evaluates to \pcode{true}, otherwise the else-branch.

   128 Loops should be run as long as the boolean is \pcode{true}.

   129 Programs you should be able to run are shown in

   130 Figures \ref{fib} -- \ref{collatz}.

   131 

   132 

   133 Give some time measurements for your interpreter

   134 and the loop program in Figure~\ref{loop}. For example

   135 how long does your interpreter take when \pcode{start}

   136 is initialised with 100, 500 and so on. How far can

   137 you scale this value if you are willing to wait, say

   138 1 Minute?

   139 

   140 \begin{figure}[h]

   141 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/fib.while}

   142 \caption{Fibonacci program in the WHILE language.\label{fib}}

   143 \end{figure}

   144 

   145 \begin{figure}[h]

   146 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/loops.while}

   147 \caption{The three-nested-loops program in the WHILE language. 

   148 Usually used for timing measurements.\label{loop}}

   149 \end{figure}

   150 

   151 \begin{figure}[h]

   152 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/primes.while}

   153 \caption{Prime number program.\label{primes}}

   154 \end{figure}

   155 

   156 

   157 \begin{figure}[p]

   158 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/collatz2.while}

   159 \caption{Collatz series program.\label{collatz}}

   160 \end{figure}

   161 

   162 \end{document}

   163 

   164 %%% Local Variables: 

   165 %%% mode: latex

   166 %%% TeX-master: t

   167 %%% End: