60 |
60 |
61 |
61 |
62 |
62 |
63 \section*{Coursework 2} |
63 \section*{Coursework 2} |
64 |
64 |
65 This coursework is worth 3\% and is due on 26 November at 16:00. You are asked to implement |
65 This coursework is worth 3\% and is due on 27 November at 16:00. You are asked to |
66 a tokeniser for the WHILE language, an evaluator for boolean and arithmetic expressions and |
|
67 a WHILE program for printing prime numbers. |
|
68 |
66 |
|
67 \begin{enumerate} |
|
68 \item implement a tokeniser for the WHILE language, |
|
69 \item implement a parser and an evaluator for boolean and arithmetic expressions, and |
|
70 \item write a WHILE program for printing out prime numbers. |
|
71 \end{enumerate} |
|
72 |
|
73 \noindent |
69 You need to submit a document containing the answers for the questions |
74 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 |
75 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 |
76 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 |
77 will \emph{only} be judged according to the answers. You can submit your answers |
73 in a txt-file or pdf.\bigskip |
78 in a txt-file or as pdf.\bigskip |
74 |
79 |
75 |
80 |
76 \subsection*{Question 1 (marked with 1\%)} |
81 \subsection*{Question 1 (marked with 1\%)} |
77 |
82 |
78 Implement a tokeniser for the WHILE language. (1) Keywords in this language |
83 Implement a tokeniser for the WHILE language. You first need to design the appropriate |
79 are |
84 regular expressions for the following nine syntactic entities: |
80 |
85 |
81 \begin{center} |
86 \begin{enumerate} |
|
87 \item keywords are |
|
88 |
|
89 \begin{quote} |
82 \texttt{while}, \texttt{if}, \texttt{then}, \texttt{else}, \texttt{do}, \texttt{for}, \texttt{to}, \texttt{true}, \texttt{false} |
90 \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} |
91 \texttt{andalso}, \texttt{orelse}, \texttt{read}, \texttt{write} |
84 \end{center} |
92 \end{quote} |
|
93 |
|
94 \item operators are |
|
95 |
|
96 \begin{quote} |
|
97 \texttt{+}, \texttt{-}, \texttt{*}, \texttt{\%}, \texttt{==}, \texttt{!=}, \texttt{>}, \texttt{<}, \texttt{:=} |
|
98 \end{quote} |
|
99 |
|
100 \item strings are enclosed by \texttt{"\ldots"} |
|
101 \item parentheses are \texttt{(}, \texttt{\{}, \texttt{)} and \texttt{\}} |
|
102 \item there are semicolons \texttt{;} |
|
103 \item whitespaces are either \texttt{" "} or \texttt{$\backslash$n} |
|
104 \item comments either start with $\backslash\,\backslash$ and run to the end of the corresponding line |
|
105 (indicated by \texttt{$\backslash$n}), or they can also run over several lines but then need to be enclosed by |
|
106 $\slash\texttt{*}$ as the beginning marker and $\texttt{*}\slash{}$\smallskip as the end marker |
|
107 \item identifiers are letters followed by underscores \texttt{\_\!\_}, letters |
|
108 or digits |
|
109 \item numbers are \texttt{0}, \text{1}, \ldots |
|
110 \end{enumerate} |
85 |
111 |
86 \noindent |
112 \noindent |
87 (2) Operators are |
113 Once you have implemented all regular expressions for 1 - 9, then |
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 in \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. |
114 give the token sequence for the Fibonacci program shown below. |
106 |
115 |
107 \subsection*{Question 2 (marked with 1\%)} |
116 \subsection*{Question 2 (marked with 1\%)} |
108 |
117 |
109 Implement parser combinators and an evaluate function for arithmetic and boolean |
118 Implement parser combinators and an evaluation function for arithmetic and boolean |
110 expressions. Arithmetic operations should include $+$, $-$, $*$, $\%$ (quotient). Boolean |
119 expressions. Arithmetic operations should include \texttt{+}, \texttt{-}, \texttt{*} and |
111 operations should include $==$ (equal), $!=$ (unequal), $<$, $>$. |
120 \texttt{\%} (quotient). Boolean |
|
121 operations should include \texttt{==} (equal), \texttt{!=} (unequal), \texttt{<} and |
|
122 \texttt{>}. |
112 |
123 |
113 Using the parser and evaluation function, calculate the values for |
124 Using the parser and evaluation function, calculate the values for |
114 |
125 |
115 \begin{itemize} |
126 \begin{itemize} |
116 \item \texttt{17 < 3 * 3 * 3} |
127 \item \texttt{17 < 3 * 3 * 3} |