178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\usepackage{hyperref}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
3 |
\usepackage{amssymb}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
\usepackage{amsmath}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
5 |
\usepackage{../langs}
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
10 |
\section*{Coursework 2}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
11 |
|
198
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
{\bf UPDATE:} There was a typo in Q1 about the regular expressions for comments:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
they should, of course, start with $\slash\slash$, as in C for example, not with
|
199
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
$\backslash\backslash$. (Thanks to Bryan who pointed out this error.)\bigskip\bigskip
|
198
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
\noindent
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
This coursework is worth 3\% and is due on 29 November at 16:00. You are asked to
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
18 |
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
\item implement a tokeniser for the WHILE language,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
\item implement a parser and an evaluator for boolean and arithmetic expressions, and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\item write a WHILE program for printing out prime numbers.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
\noindent
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
26 |
You need to submit a document containing the answers for the questions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
27 |
below. You can do the implementation in any programming language you like, but you need
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
28 |
to submit the source code with which you answered the questions. However, the coursework
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
29 |
will \emph{only} be judged according to the answers. You can submit your answers
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
in a txt-file or as pdf.\bigskip
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
31 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
32 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
\subsection*{Question 1 (marked with 1\%)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
Implement a tokeniser for the WHILE language. You first need to design the appropriate
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
regular expressions for the following nine syntactic entities:
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
\item keywords are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
\begin{quote}
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
\texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
\texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write}
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
\item operators are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
\begin{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
\texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
\end{quote}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
\item strings are enclosed by \texttt{"\ldots"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
\item there are semicolons \texttt{;}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\item whitespaces are either \texttt{" "} or \texttt{$\backslash$n}
|
198
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
\item comments either start with $\slash\,\slash$ and run to the end of the corresponding line
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
(indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
$\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
\item identifiers are letters followed by underscores \texttt{\_\!\_}, letters
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
or digits
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
\item numbers are \texttt{0}, \text{1}, \ldots
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
\end{enumerate}
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
\noindent
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
Once you have implemented all regular expressions for 1 - 9, then
|
181
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
give the token sequence for the Fibonacci program shown below in Fig.~\ref{fib}.
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
\subsection*{Question 2 (marked with 1\%)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
69 |
|
180
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
Implement parser combinators and an evaluation function for arithmetic and boolean
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
expressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\texttt{\%} (quotient). Boolean
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
\texttt{>}.
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
76 |
Using the parser and evaluation function, calculate the values for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
79 |
\item \texttt{17 < 3 * 3 * 3}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
80 |
\item \texttt{(29 - 20) * 3}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
81 |
\item \texttt{79 - 20 * 3}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
82 |
\item \texttt{2 * 2 != 12 \% 3}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
83 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
84 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
85 |
\subsection*{Question 3 (marked with 1\%)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
86 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
87 |
Write a program in the WHILE programming language that prints out all prime numbers between
|
182
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
0 and a fixed number (say 100). A partial grammar of the WHILE language is given below.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
\begin{tabular}{@{}lcl@{}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
\textit{Stmt} & $\rightarrow$ & $\texttt{skip}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
& $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
& $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
& $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
& $|$ & \texttt{read}\;\textit{Id}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
& $|$ & \texttt{write}\;\textit{Id}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
& $|$ & \texttt{write}\;\textit{String}\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
\textit{Stmts} & $\rightarrow$ & \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
& $|$ & \textit{Stmt}\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
\textit{Block} & $\rightarrow$ & \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
& $|$ & \textit{Stmt}\medskip\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
\textit{AExp} & $\rightarrow$ & \ldots\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
\textit{BExp} & $\rightarrow$ & \ldots\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
As another guidance for your program have a look at the Fibonacci program
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
and ``three-nested-loops'' program shown below in Figures \ref{fib} and \ref{loop}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
112 |
|
181
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
\begin{figure}[h]
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
114 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
115 |
\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
116 |
\end{center}
|
181
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
\caption{Fibonacci program in the WHILE language.\label{fib}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
\end{figure}
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
119 |
|
181
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
\begin{figure}[h]
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
121 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
122 |
\mbox{\lstinputlisting[language=while]{../progs/loops.while}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
123 |
\end{center}
|
181
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
\caption{The three-nested-loops program in the WHILE language. Usually used for timing measurements.\label{loop}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
\end{figure}
|
178
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
126 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
127 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
128 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
129 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
130 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
131 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
132 |
%%% End:
|