2 \usepackage{hyperref}

     2 \usepackage{../style}

     3 \usepackage{amssymb}

     4 \usepackage{amsmath}

    10 \section*{Coursework 2}

     7 \section*{Coursework 2 (Strand 1)}

    11 

    12 {\bf UPDATE:} There was a typo in Q1 about the regular expressions for comments:

    13 they should, of course, start with $\slash\slash$, as in C for example, not with 

    14 $\backslash\backslash$. (Thanks to Bryan who pointed out this error.)\bigskip\bigskip

    17 This coursework is worth 3\% and is due on 29 November at 16:00. You are asked to 

    10 This coursework is worth 5\% and is due on 3 November at 16:00. You

    11 are asked to implement the Sulzmann tokeniser for the WHILE language.

    12 You need to submit a document containing the answers for the questions

    13 below. You can do the implementation in any programming language you

    14 like, but you need to submit the source code with which you answered

    15 the questions. However, the coursework will \emph{only} be judged

    16 according to the answers. You can submit your answers in a txt-file or

    17 as pdf.

    19 \begin{enumerate}

    19 \subsection*{Disclaimer}

    20 \item implement a tokeniser for the WHILE language,

    21 \item implement a parser and an evaluator for boolean and arithmetic expressions, and

    22 \item write a WHILE program for printing out prime numbers.

    23 \end{enumerate}

    25 \noindent

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

    26 You need to submit a document containing the answers for the questions 

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

    27 below. You can do the implementation in any programming language you like, but you need 

    23 Scala code I showed during the lectures, which you can use.

    28 to submit the source code with which you answered the questions. However, the coursework 

    24 You can also use your own code from the CW~1.

    29 will \emph{only} be judged according to the answers. You can submit your answers

    30 in a txt-file or as pdf.\bigskip

    31 

    35 Implement a tokeniser for the WHILE language. You first need to design the appropriate

    28 To implement a tokeniser for the WHILE language, you first need to design 

    36 regular expressions for the following nine syntactic entities:

    29 the appropriate regular expressions for the following eight syntactic entities:

    42 \texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}

    35 \texttt{while}, 

    43 \texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}

    36 \texttt{if}, 

    37 \texttt{then}, 

    38 \texttt{else}, 

    39 \texttt{do}, 

    40 \texttt{for}, 

    41 \texttt{to}, 

    42 \texttt{true}, 

    43 \texttt{false}, 

    44 \texttt{read}, 

    45 \texttt{write},

    46 \texttt{skip}

    49 \texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}

    52 \texttt{+}, 

    53 \texttt{-}, 

    54 \texttt{*}, 

    55 \texttt{\%},

    56 \texttt{/},

    57 \texttt{==}, 

    58 \texttt{!=}, 

    59 \texttt{>}, 

    60 \texttt{<}, 

    61 \texttt{:=},

    62 \texttt{\&\&},

    63 \texttt{||}

    55 \item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}

    69 \item whitespaces are either \texttt{" "} (one or more) or \texttt{$\backslash$n}

    56 \item comments either start with $\slash\,\slash$ and run to the end of the corresponding line 

    57 (indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by

    58 $\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker

    65 Once you have implemented all regular expressions for 1 - 9, then

    76 You can use the basic regular expressions 

    66 give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.

    68 \subsection*{Question 2 (marked with 1\%)}

    78 \[

    79 \varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*

    80 \]

    70 Implement parser combinators and an evaluation function for arithmetic and boolean

    82 \noindent

    71 expressions.  Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and 

    83 but also the following extended regular expressions

    72 \texttt{\%} (quotient). Boolean

    73 operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and  

    74 \texttt{>}.

    75  

    76 Using the parser and evaluation function, calculate the values for

    77 

    78 \begin{itemize}

    79 \item \texttt{17 < 3 * 3 * 3}

    80 \item \texttt{(29 - 20) * 3}

    81 \item \texttt{79 - 20 * 3}

    82 \item \texttt{2 * 2 != 12 \% 3}

    83 \end{itemize} 

    84  

    85 \subsection*{Question 3 (marked with 1\%)}

    86 

    87 Write a program in the WHILE programming language that prints out all prime numbers between

    88 0 and a fixed number (say 100). A partial grammar of the WHILE language is given below. 

    91 \begin{tabular}{@{}lcl@{}}

    86 \begin{tabular}{ll}

    92 \textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\

    87 $[c_1 c_2 \ldots c_n]$ & a range of characters\\

    93               & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\

    88 $r^+$ & one or more times $r$\\

    94               & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\

    89 $r^?$ & optional $r$\\

    95               & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\

    90 $r^{\{n\}}$ & n-times $r$\\

    96               & $|$ & \texttt{read}\;\textit{Id}\\

    97               & $|$ & \texttt{write}\;\textit{Id}\\

    98               & $|$ & \texttt{write}\;\textit{String}\medskip\\

    99 \textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\

   100               & $|$ & \textit{Stmt}\medskip\\

   101 \textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\

   102                 & $|$ & \textit{Stmt}\medskip\\

   103 \textit{AExp} & $\rightarrow$ & \ldots\\

   104 \textit{BExp} & $\rightarrow$ & \ldots\\

   109 As another guidance for your program have a look at the Fibonacci program

    95 Once you have designed all regular expressions for 1 - 8, then

   110 and ``three-nested-loops'' program shown below in Figures \ref{fib} and \ref{loop}. 

    96 give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.

    97 

    98 \subsection*{Question 2 (marked with 3\%)}

    99 

   100 Implement the Sulzmann tokeniser from the lectures. For this you need

   101 to implement the functions $nullable$ and $der$ (you can use your code

   102 from CW 1), as well as $mkeps$ and $inj$. These functions need to be

   103 appropriately extended for the extended regular expressions from

   104 Q1. Also add the record regular expression from the lectures and

   105 implement a function, say \pcode{env}, that returns all assignments

   106 from a value (such that you can extract easily the tokens from a

   107 value). 

   108 

   109 The functions $mkeps$ and $inj$ return values. Calculate

   110 the value for your regular expressions from Q1 and the string

   111 

   112 \begin{center}

   113 \code{"read n;"}

   114 \end{center} 

   115 

   116 \noindent

   117 and use your \pcode{env} function to give the token sequence.

   118 

   119 \subsection*{Question 3 (marked with 1\%)}

   120 

   121 Extend your tokenizer from Q2 to also simplify regular expressions

   122 after each derivation step and rectify the computed values after each

   123 injection. Use this tokenizer to tokenize the programs in

   124 Figure~\ref{fib} and \ref{loop}.

   113 \begin{figure}[h]

   127 \begin{figure}[p]

   120 \begin{figure}[h]

   134 \begin{figure}[p]

   124 \caption{The three-nested-loops program in the WHILE language. Usually used for timing measurements.\label{loop}}

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

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