44 \noindent |
44 \noindent |
45 Make sure the grammar is not left-recursive. |
45 Make sure the grammar is not left-recursive. |
46 |
46 |
47 \subsection*{Question 2} |
47 \subsection*{Question 2} |
48 |
48 |
49 You should implement a parser for the WHILE language using |
49 You should implement a parser for the WHILE language using parser |
50 parser combinators. Be careful that the parser takes as input |
50 combinators. Be careful that the parser takes as input a stream, or |
51 a stream, or list, of tokens generated by the tokenizer from |
51 list, of tokens generated by the tokenizer from the previous |
52 the previous coursework. For this you might want to filter out |
52 coursework. For this you might want to filter out whitespaces and |
53 whitespaces and comments. Your parser should be able to handle |
53 comments. Your parser should be able to handle the WHILE programs in |
54 the WHILE programs in Figures~\ref{fib} and \ref{loop}. |
54 Figures~\ref{fib}, \ref{loop} and \ref{primes} (if your lexer cannot |
|
55 deal with comments you can delete them from the prime number program). |
55 In addition give the parse tree for the statement: |
56 In addition give the parse tree for the statement: |
56 |
57 |
57 \begin{lstlisting}[language=While,numbers=none] |
58 \begin{lstlisting}[language=While,numbers=none] |
58 if (a < b) then skip else a := a * b + 1 |
59 if (a < b) then skip else a := a * b + 1 |
59 \end{lstlisting} |
60 \end{lstlisting} |
116 according to straightforward rules: for example an |
117 according to straightforward rules: for example an |
117 if-statement will ``run'' the if-branch if the boolean |
118 if-statement will ``run'' the if-branch if the boolean |
118 evaluates to \pcode{true}, otherwise the else-branch. |
119 evaluates to \pcode{true}, otherwise the else-branch. |
119 Loops should be run as long as the boolean is \pcode{true}. |
120 Loops should be run as long as the boolean is \pcode{true}. |
120 |
121 |
|
122 |
|
123 |
121 Give some time measurements for your interpreter |
124 Give some time measurements for your interpreter |
122 and the loop program in Figure~\ref{loop}. For example |
125 and the loop program in Figure~\ref{loop}. For example |
123 how long does your interpreter take when \pcode{start} |
126 how long does your interpreter take when \pcode{start} |
124 is initialised with 100, 500 and so on. How far can |
127 is initialised with 100, 500 and so on. How far can |
125 you scale this value if you are willing to wait, say |
128 you scale this value if you are willing to wait, say |
126 1 Minute? |
129 1 Minute? |
127 |
130 |
128 \begin{figure}[p] |
131 \begin{figure}[p] |
129 \begin{center} |
132 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/fib.while} |
130 \mbox{\lstinputlisting[language=while]{../progs/fib.while}} |
|
131 \end{center} |
|
132 \caption{Fibonacci program in the WHILE language.\label{fib}} |
133 \caption{Fibonacci program in the WHILE language.\label{fib}} |
133 \end{figure} |
134 \end{figure} |
134 |
135 |
135 \begin{figure}[p] |
136 \begin{figure}[p] |
136 \begin{center} |
137 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/loops.while} |
137 \mbox{\lstinputlisting[language=while]{../progs/loops.while}} |
|
138 \end{center} |
|
139 \caption{The three-nested-loops program in the WHILE language. |
138 \caption{The three-nested-loops program in the WHILE language. |
140 Usually used for timing measurements.\label{loop}} |
139 Usually used for timing measurements.\label{loop}} |
|
140 \end{figure} |
|
141 |
|
142 \begin{figure}[p] |
|
143 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/primes.while} |
|
144 \caption{Prime number program.\label{primes}} |
141 \end{figure} |
145 \end{figure} |
142 |
146 |
143 \end{document} |
147 \end{document} |
144 |
148 |
145 %%% Local Variables: |
149 %%% Local Variables: |