% !TEX program = xelatex

\documentclass{article}

\usepackage{../style}

\usepackage{../langs}

\usepackage[normalem]{ulem}

\begin{document}

\section*{Coursework 2}

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

16:00. You are asked to implement the Sulzmann \& Lu lexer for the

WHILE language. 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 need to submit your written answers as pdf---see attached

questionaire.  Code send as code. If you use Scala in your code, a

good place to start is the file \texttt{lexer.sc} and

\texttt{token.sc} uploaded to KEATS. The template file on Github is

called \texttt{cw02.sc}. Your code needs to be uploaded to Github by

the deadline.

\subsection*{Disclaimer\alert}

It should be understood that the work you submit represents

your own effort. You have not copied from anyone else

including CoPilot, ChatGPT \& Co. An

exception is the Scala code from KEATS and the code I showed

during the lectures, which you can both freely use. You can

also use your own code from the CW~1.

%But do not

%be tempted to ask Github Copilot for help or do any other

%shenanigans like this!

\subsection*{Question 1}

To implement a lexer for the WHILE language, you first

need to design the appropriate regular expressions for the

following eleven syntactic entities:

\begin{enumerate}

\item keywords are

\begin{center}

\texttt{while}, 

\texttt{if}, 

\texttt{then}, 

\texttt{else}, 

\texttt{do}, 

\texttt{for}, 

\texttt{to}, 

\texttt{true}, 

\texttt{false}, 

\texttt{read}, 

\texttt{write},

\texttt{skip}

\end{center} 

\item operators are:

\texttt{+}, 

\texttt{-}, 

\texttt{*}, 

\texttt{\%},

\texttt{/},

\texttt{==}, 

\texttt{!=}, 

\texttt{>}, 

\texttt{<},

\texttt{<=}, 

\texttt{>=},

\texttt{:=},

\texttt{\&\&},

\texttt{||}

\item letters are uppercase and lowercase

\item symbols are letters plus the characters

  \texttt{.},

  \texttt{\_},

  \texttt{>},

  \texttt{<},

  \texttt{=},

  \texttt{;},

  \texttt{,} (comma),

  \texttt{$\backslash$} and

  \texttt{:}

\item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}

\item digits are \pcode{0} to \pcode{9}

\item there are semicolons \texttt{;}

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

  \texttt{$\backslash$t} or \texttt{$\backslash$r}

\item identifiers are letters followed by underscores \texttt{\_\!\_}, letters

  or digits  

\item numbers for numbers give 

a regular expression that can recognise \pcode{0}, but not numbers 

with leading zeroes, such as \pcode{001}

\item strings are enclosed by double quotes, like \texttt{"\ldots"}, and consisting of

  symbols, digits, parentheses, whitespaces and \texttt{$\backslash$n} (note the latter is not the escaped version but \texttt{$\backslash$} followed by \texttt{n}, otherwise we would not be able to indicate in our strings when to write a newline).

\item endo-of-line-markers are \texttt{$\backslash$n} and \texttt{$\backslash$r$\backslash$n}  

\end{enumerate}

\noindent

You can use the basic regular expressions 

\[

\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*

\]

\noindent

but also the following extended regular expressions

\begin{center}

\begin{tabular}{ll}

$[c_1,c_2,\ldots,c_n]$ & a set of characters\\

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

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

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

\end{tabular}

\end{center}

\noindent

Later on you will also need the record regular expression:

\begin{center}

\begin{tabular}{ll}

$REC(x:r)$ & record regular expression\\

\end{tabular}

\end{center}

\noindent Try to design your regular expressions to be as

small as possible. For example you should use character sets

for identifiers and numbers. Feel free to use the general

character constructor \textit{CFUN} introduced in CW 1.

\subsection*{Question 2}

Implement the Sulzmann \& Lu lexer from the lectures. For

this you need to implement the functions $nullable$ and $der$

(you can use your code from CW~1), as well as $mkeps$ and

$inj$. These functions need to be appropriately extended for

the extended regular expressions from Q1. Write down in the

questionaire at the end the 

clauses for

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

$mkeps([c_1,c_2,\ldots,c_n])$  & $\dn$ & $?$\\

$mkeps(r^+)$                   & $\dn$ & $?$\\

$mkeps(r^?)$                   & $\dn$ & $?$\\

$mkeps(r^{\{n\}})$             & $\dn$ & $?$\medskip\\

$inj\, ([c_1,c_2,\ldots,c_n])\,c\,\ldots$  & $\dn$ & $?$\\

$inj\, (r^+)\,c\,\ldots$                   & $\dn$ & $?$\\

$inj\, (r^?)\,c\,\ldots$                   & $\dn$ & $?$\\

$inj\, (r^{\{n\}})\,c\,\ldots$             & $\dn$ & $?$\\

\end{tabular}

\end{center}

\noindent where $inj$ takes three arguments: a regular

expression, a character and a value. Test your lexer code

with at least the two small examples below:

\begin{center}

\begin{tabular}{ll}

regex: & string:\smallskip\\

$a^{\{3\}}$ & $aaa$\\

$(a + \ONE)^{\{3\}}$ & $aa$

\end{tabular}

\end{center}

\noindent Both strings should be successfully lexed by the

respective regular expression, that means the lexer returns 

in both examples a value.

Also add the record regular expression from the

lectures to your lexer and implement a function, say

\pcode{env}, that returns all assignments from a value (such

that you can extract easily the tokens from a value).\medskip 

\noindent

Finally give \textbf{all} the tokens for your regular expressions from Q1 and the

string

\begin{center}

\code{"read n;"}

\end{center} 

\noindent

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

\subsection*{Question 3}

Extend your lexer from Q2 to also simplify regular expressions after

each derivation step and rectify the computed values after each

injection. Use this lexer to tokenize six WHILE programs some of which

are given in Figures~\ref{fib} -- \ref{collatz}. You can find these programms also on

Github under the \texttt{cw2} directory. Give the tokens of these

programs where whitespaces and comments are

filtered out. Make sure you can tokenise \textbf{exactly} these

programs.\bigskip

\begin{figure}[h]

\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/fib.while}}

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

\end{figure}

\begin{figure}[h]

\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/loops.while}}

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

(Usually used for timing measurements.)\label{loop}}

\end{figure}

\begin{figure}[h]

\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/factors.while}}

\caption{A program that calculates factors for numbers in the WHILE

  language.\label{factors}}

\end{figure}

\begin{figure}[h]

\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../cwtests/cw02/collatz2.while}}

\caption{A program that calculates the Collatz series for numbers

  between 1 and 100.\label{collatz}}

\end{figure}

\clearpage

\newpage

\section*{Answers}

\mbox{}

\noindent

\textbf{Question 2:}\\ (Use mathematical notation, such as $r^+$, rather than code, such as \code{PLUS(r)})

\begin{center}

  \def\arraystretch{1.6}  

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

$mkeps([c_1,c_2,\ldots,c_n])$  & $\dn$ & \uline{\hspace{8cm}}\\

$mkeps(r^+)$                   & $\dn$ & \uline{\hspace{8cm}}\\

$mkeps(r^?)$                   & $\dn$ & \uline{\hspace{8cm}}\\

$mkeps(r^{\{n\}})$             & $\dn$ & \uline{\hspace{8cm}}\bigskip\\

$inj\, ([c_1,c_2,\ldots,c_n])\,c\,\ldots$  & $\dn$ & \uline{\hspace{8cm}}\\

$inj\, (r^+)\,c\,\ldots$                   & $\dn$ & \uline{\hspace{8cm}}\\

$inj\, (r^?)\,c\,\ldots$                   & $\dn$ & \uline{\hspace{8cm}}\\

$inj\, (r^{\{n\}})\,c\,\ldots$             & $\dn$ & \uline{\hspace{8cm}}\\

\end{tabular}

\end{center}\bigskip

\noindent

Tokens for \code{"read n;"}\\

\noindent

\uline{\hfill}\medskip

\noindent

\uline{\hfill}\medskip

\noindent

\uline{\hfill}\medskip

\noindent

\uline{\hfill}\medskip

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: