--- a/coursework/cw02.tex Sun Oct 12 22:36:18 2014 +0100
+++ b/coursework/cw02.tex Mon Oct 13 00:09:28 2014 +0100
@@ -1,127 +1,142 @@
\documentclass{article}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
\usepackage{../langs}
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
\begin{document}
-\section*{Coursework 2}
-
-{\bf UPDATE:} There was a typo in Q1 about the regular expressions for comments:
-they should, of course, start with $\slash\slash$, as in C for example, not with
-$\backslash\backslash$. (Thanks to Bryan who pointed out this error.)\bigskip\bigskip
+\section*{Coursework 2 (Strand 1)}
\noindent
-This coursework is worth 3\% and is due on 29 November at 16:00. You are asked to
-
-\begin{enumerate}
-\item implement a tokeniser for the WHILE language,
-\item implement a parser and an evaluator for boolean and arithmetic expressions, and
-\item write a WHILE program for printing out prime numbers.
-\end{enumerate}
+This coursework is worth 5\% and is due on 3 November at 16:00. You
+are asked to implement the Sulzmann tokeniser for the WHILE language.
+You need to submit a document containing the answers for the questions
+below. 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. However, the coursework will \emph{only} be judged
+according to the answers. You can submit your answers in a txt-file or
+as pdf.
-\noindent
-You need to submit a document containing the answers for the questions
-below. 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. However, the coursework
-will \emph{only} be judged according to the answers. You can submit your answers
-in a txt-file or as pdf.\bigskip
+\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.
\subsection*{Question 1 (marked with 1\%)}
-Implement a tokeniser for the WHILE language. You first need to design the appropriate
-regular expressions for the following nine syntactic entities:
+To implement a tokeniser for the WHILE language, you first need to design
+the appropriate regular expressions for the following eight syntactic entities:
\begin{enumerate}
\item keywords are
\begin{quote}
-\texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}
-\texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}
+\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{quote}
\item operators are
\begin{quote}
-\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}
+\texttt{+},
+\texttt{-},
+\texttt{*},
+\texttt{\%},
+\texttt{/},
+\texttt{==},
+\texttt{!=},
+\texttt{>},
+\texttt{<},
+\texttt{:=},
+\texttt{\&\&},
+\texttt{||}
\end{quote}
\item strings are enclosed by \texttt{"\ldots"}
\item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}
\item there are semicolons \texttt{;}
-\item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}
-\item comments either start with $\slash\,\slash$ and run to the end of the corresponding line
-(indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by
-$\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker
+\item whitespaces are either \texttt{" "} (one or more) or \texttt{$\backslash$n}
\item identifiers are letters followed by underscores \texttt{\_\!\_}, letters
or digits
\item numbers are \texttt{0}, \text{1}, \ldots
\end{enumerate}
\noindent
-Once you have implemented all regular expressions for 1 - 9, then
-give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.
-
-\subsection*{Question 2 (marked with 1\%)}
+You can use the basic regular expressions
-Implement parser combinators and an evaluation function for arithmetic and boolean
-expressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and
-\texttt{\%} (quotient). Boolean
-operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and
-\texttt{>}.
-
-Using the parser and evaluation function, calculate the values for
+\[
+\varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*
+\]
-\begin{itemize}
-\item \texttt{17 < 3 * 3 * 3}
-\item \texttt{(29 - 20) * 3}
-\item \texttt{79 - 20 * 3}
-\item \texttt{2 * 2 != 12 \% 3}
-\end{itemize}
-
-\subsection*{Question 3 (marked with 1\%)}
-
-Write a program in the WHILE programming language that prints out all prime numbers between
-0 and a fixed number (say 100). A partial grammar of the WHILE language is given below.
+\noindent
+but also the following extended regular expressions
\begin{center}
-\begin{tabular}{@{}lcl@{}}
-\textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\
- & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
- & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
- & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
- & $|$ & \texttt{read}\;\textit{Id}\\
- & $|$ & \texttt{write}\;\textit{Id}\\
- & $|$ & \texttt{write}\;\textit{String}\medskip\\
-\textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
- & $|$ & \textit{Stmt}\medskip\\
-\textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
- & $|$ & \textit{Stmt}\medskip\\
-\textit{AExp} & $\rightarrow$ & \ldots\\
-\textit{BExp} & $\rightarrow$ & \ldots\\
+\begin{tabular}{ll}
+$[c_1 c_2 \ldots c_n]$ & a range of characters\\
+$r^+$ & one or more times $r$\\
+$r^?$ & optional $r$\\
+$r^{\{n\}}$ & n-times $r$\\
\end{tabular}
\end{center}
\noindent
-As another guidance for your program have a look at the Fibonacci program
-and ``three-nested-loops'' program shown below in Figures \ref{fib} and \ref{loop}.
+Once you have designed all regular expressions for 1 - 8, then
+give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.
+
+\subsection*{Question 2 (marked with 3\%)}
+
+Implement the Sulzmann tokeniser 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. Also add the record regular expression from the lectures 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).
+
+The functions $mkeps$ and $inj$ return values. Calculate
+the value 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 (marked with 1\%)}
+
+Extend your tokenizer from Q2 to also simplify regular expressions
+after each derivation step and rectify the computed values after each
+injection. Use this tokenizer to tokenize the programs in
+Figure~\ref{fib} and \ref{loop}.
-\begin{figure}[h]
+\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}[h]
+\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}}
+\caption{The three-nested-loops program in the WHILE language.
+Usually used for timing measurements.\label{loop}}
\end{figure}
\end{document}