|
1 \documentclass{article} |
|
2 \usepackage{charter} |
|
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 \usepackage{listings} |
|
7 \usepackage{xcolor} |
|
8 |
|
9 |
|
10 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
|
11 \begin{document} |
|
12 |
|
13 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
14 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
15 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
16 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
17 |
|
18 \lstdefinelanguage{scala}{ |
|
19 morekeywords={abstract,case,catch,class,def,% |
|
20 do,else,extends,false,final,finally,% |
|
21 for,if,implicit,import,match,mixin,% |
|
22 new,null,object,override,package,% |
|
23 private,protected,requires,return,sealed,% |
|
24 super,this,throw,trait,true,try,% |
|
25 type,val,var,while,with,yield}, |
|
26 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
27 sensitive=true, |
|
28 morecomment=[l]{//}, |
|
29 morecomment=[n]{/*}{*/}, |
|
30 morestring=[b]", |
|
31 morestring=[b]', |
|
32 morestring=[b]""" |
|
33 } |
|
34 |
|
35 \lstdefinelanguage{while}{ |
|
36 morekeywords={while, if, then. else, read, write}, |
|
37 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
38 sensitive=true, |
|
39 morecomment=[l]{//}, |
|
40 morecomment=[n]{/*}{*/}, |
|
41 morestring=[b]", |
|
42 morestring=[b]', |
|
43 morestring=[b]""" |
|
44 } |
|
45 |
|
46 |
|
47 \lstset{language=Scala, |
|
48 basicstyle=\ttfamily, |
|
49 keywordstyle=\color{javapurple}\bfseries, |
|
50 stringstyle=\color{javagreen}, |
|
51 commentstyle=\color{javagreen}, |
|
52 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
53 numbers=left, |
|
54 numberstyle=\tiny\color{black}, |
|
55 stepnumber=1, |
|
56 numbersep=10pt, |
|
57 tabsize=2, |
|
58 showspaces=false, |
|
59 showstringspaces=false} |
|
60 |
|
61 |
|
62 |
|
63 \section*{Coursework 2} |
|
64 |
|
65 This coursework is worth 3\% and is due on 26 November at 16:00. You are asked to implement |
|
66 a tokeniser for the WHILE language, an evaluator for boolean and arithmetic expressions and |
|
67 a WHILE program for printing prime numbers. |
|
68 |
|
69 You need to submit a document containing the answers for the questions |
|
70 below. You can do the implementation in any programming language you like, but you need |
|
71 to submit the source code with which you answered the questions. However, the coursework |
|
72 will \emph{only} be judged according to the answers. You can submit your answers |
|
73 in a txt-file or pdf.\bigskip |
|
74 |
|
75 |
|
76 \subsection*{Question 1 (marked with 1\%)} |
|
77 |
|
78 Implement a tokeniser for the WHILE language. (1) Keywords in this language |
|
79 are |
|
80 |
|
81 \begin{center} |
|
82 \texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false} |
|
83 \texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write} |
|
84 \end{center} |
|
85 |
|
86 \noindent |
|
87 (2) Operators are |
|
88 |
|
89 \begin{center} |
|
90 \texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=} |
|
91 \end{center} |
|
92 |
|
93 \noindent |
|
94 (3) Strings are enclosed into \texttt{"\ldots"}, (4) you have parentheses \texttt{(}, \texttt{\{}, \texttt{)}, and \texttt{\}}, |
|
95 (5) there are semicolons \texttt{;}, (6) whitespaces are either \texttt{" "} or \texttt{$\backslash$n}, |
|
96 (7) comments either start with $\backslash\,\backslash$ and run to the end of the corresponding line |
|
97 (\texttt{$\backslash$n}), comments can also been given by looking for $\slash\texttt{*}$ as the |
|
98 beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker. |
|
99 |
|
100 \noindent |
|
101 (8) Identifiers are letters followed by underscores \texttt{\_}, letters |
|
102 or digits. (9) There are also numbers, like \texttt{0}, \text{1}, \ldots.\medskip |
|
103 |
|
104 Once you have implemented all regular expressions for (1) - (9), then |
|
105 give the token sequence for the Fibonacci program shown below. |
|
106 |
|
107 \subsection*{Question 2 (marked with 1\%)} |
|
108 |
|
109 Implement parser combinators and an evaluate function for arithmetic and boolean |
|
110 expressions. Arithmetic operations should include $+$, $-$, $*$, $\%$ (quotient). Boolean |
|
111 operations should include $==$ (equal), $!=$ (unequal), $<$, $>$. |
|
112 |
|
113 Using the parser and evaluation function, calculate the values for |
|
114 |
|
115 \begin{itemize} |
|
116 \item \texttt{17 < 3 * 3 * 3} |
|
117 \item \texttt{(29 - 20) * 3} |
|
118 \item \texttt{79 - 20 * 3} |
|
119 \item \texttt{2 * 2 != 12 \% 3} |
|
120 \end{itemize} |
|
121 |
|
122 \subsection*{Question 3 (marked with 1\%)} |
|
123 |
|
124 Write a program in the WHILE programming language that prints out all prime numbers between |
|
125 0 and a fixed number (say 100). As a guidance have a look at the Fibonacci program |
|
126 and three nested loops program shown below. |
|
127 |
|
128 |
|
129 \begin{center} |
|
130 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
|
131 \end{center} |
|
132 |
|
133 \begin{center} |
|
134 \mbox{\lstinputlisting[language=while]{../progs/loops.while}} |
|
135 \end{center} |
|
136 |
|
137 |
|
138 \end{document} |
|
139 |
|
140 %%% Local Variables: |
|
141 %%% mode: latex |
|
142 %%% TeX-master: t |
|
143 %%% End: |