5 |
5 |
6 \begin{document} |
6 \begin{document} |
7 |
7 |
8 \section*{Coursework 3} |
8 \section*{Coursework 3} |
9 |
9 |
10 TODO: Testcases for expressions |
|
11 \url{https://github.com/ArashPartow/math-parser-benchmark-project} |
|
12 |
10 |
13 |
11 |
14 \noindent This coursework is worth 5\% and is due on \cwTHREE{} at |
12 \noindent This coursework is worth 10\% and is due on \cwTHREE{} at |
15 18:00. You are asked to implement a parser for the WHILE language and |
13 18:00. You are asked to implement a parser for the WHILE language and |
16 also an interpreter. You can do the implementation in any programming |
14 also an interpreter. You can do the implementation in any programming |
17 language you like, but you need to submit the source code with which |
15 language you like, but you need to submit the source code with which |
18 you answered the questions, otherwise a mark of 0\% will be |
16 you answered the questions, otherwise a mark of 0\% will be |
19 awarded. You should use the lexer from the previous coursework for the |
17 awarded. You should use the lexer from the previous coursework for the |
20 parser. Please package everything(!) in a zip-file that creates a |
18 parser. Please package everything(!) in a zip-file that creates a |
21 directory with the name \texttt{YournameYourFamilyname} on my end. |
19 directory with the name \texttt{YournameYourFamilyname} on my end. |
22 |
20 |
23 \subsection*{Disclaimer} |
21 \subsection*{Disclaimer\alert} |
24 |
22 |
25 It should be understood that the work you submit represents |
23 It should be understood that the work you submit represents your own |
26 your own effort. You have not copied from anyone else. An |
24 effort. You have not copied from anyone else. An exception is the |
27 exception is the Scala code I showed during the lectures, |
25 Scala code I showed during the lectures or uploaded to KEATS, which |
28 which you can use. You can also use your own code from the |
26 you can both use. You can also use your own code from the CW~1 and |
29 CW~1 and CW~2. |
27 CW~2. |
30 |
28 |
31 |
29 |
32 \subsection*{Question 1} |
30 \subsection*{Question 1} |
33 |
31 |
34 Design a grammar for the WHILE language and give the grammar |
32 Design a grammar for the WHILE language and give the grammar |
52 |
50 |
53 \subsection*{Question 2} |
51 \subsection*{Question 2} |
54 |
52 |
55 You should implement a parser for the WHILE language using parser |
53 You should implement a parser for the WHILE language using parser |
56 combinators. Be careful that the parser takes as input a stream, or |
54 combinators. Be careful that the parser takes as input a stream, or |
57 list, of tokens generated by the tokenizer from the previous |
55 list, of \emph{tokens} generated by the tokenizer from the previous |
58 coursework. For this you might want to filter out whitespaces and |
56 coursework. For this you might want to filter out whitespaces and |
59 comments. Your parser should be able to handle the WHILE programs in |
57 comments. Your parser should be able to handle the WHILE programs in |
60 Figures~\ref{fib}, \ref{loop} and \ref{primes} (if your lexer cannot |
58 Figures~\ref{fib}, \ref{loop} and \ref{primes}. In addition give the |
61 deal with comments you can delete them from the prime number program). |
59 parse tree for the statement: |
62 In addition give the parse tree for the statement: |
|
63 |
60 |
64 \begin{lstlisting}[language=While,numbers=none] |
61 \begin{lstlisting}[language=While,numbers=none] |
65 if (a < b) then skip else a := a * b + 1 |
62 if (a < b) then skip else a := a * b + 1 |
66 \end{lstlisting} |
63 \end{lstlisting} |
67 |
64 |
68 \noindent |
65 \noindent |
69 A (possibly incomplete) datatype for parse trees in Scala would |
66 A (possibly incomplete) datatype for parse trees in Scala is shown |
70 look as in Figure~\ref{trees}. |
67 in Figure~\ref{trees}. |
71 |
68 |
72 \begin{figure} |
69 \begin{figure}[p] |
73 \begin{lstlisting}[language=Scala] |
70 \begin{lstlisting}[language=Scala] |
74 abstract class Stmt |
71 abstract class Stmt |
75 abstract class AExp |
72 abstract class AExp |
76 abstract class BExp |
73 abstract class BExp |
77 |
74 |
79 |
76 |
80 case object Skip extends Stmt |
77 case object Skip extends Stmt |
81 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
78 case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt |
82 case class While(b: BExp, bl: Block) extends Stmt |
79 case class While(b: BExp, bl: Block) extends Stmt |
83 case class Assign(s: String, a: AExp) extends Stmt |
80 case class Assign(s: String, a: AExp) extends Stmt |
|
81 case class Read(s: String) extends Stmt |
|
82 case class WriteVar(s: String) extends Stmt |
|
83 case class WriteStr(s: String) extends Stmt |
|
84 // for printing variables and strings |
84 |
85 |
85 case class Var(s: String) extends AExp |
86 case class Var(s: String) extends AExp |
86 case class Num(i: Int) extends AExp |
87 case class Num(i: Int) extends AExp |
87 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
88 case class Aop(o: String, a1: AExp, a2: AExp) extends AExp |
88 |
89 |
89 case object True extends BExp |
90 case object True extends BExp |
90 case object False extends BExp |
91 case object False extends BExp |
91 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
92 case class Bop(o: String, a1: AExp, a2: AExp) extends BExp |
92 case class Lop(o: String, b1: BExp, b2: BExp) extends BExp |
93 case class Lop(o: String, b1: BExp, b2: BExp) extends BExp |
|
94 // logical operations: and, or |
93 \end{lstlisting} |
95 \end{lstlisting} |
94 \caption{The datatype for parse trees in Scala.\label{trees}} |
96 \caption{The datatype for parse trees in Scala.\label{trees}} |
95 \end{figure} |
97 \end{figure} |
96 |
98 |
97 \subsection*{Question 3} |
99 \subsection*{Question 3} |
122 lines 7 and 8. The program should be interpreted |
124 lines 7 and 8. The program should be interpreted |
123 according to straightforward rules: for example an |
125 according to straightforward rules: for example an |
124 if-statement will ``run'' the if-branch if the boolean |
126 if-statement will ``run'' the if-branch if the boolean |
125 evaluates to \pcode{true}, otherwise the else-branch. |
127 evaluates to \pcode{true}, otherwise the else-branch. |
126 Loops should be run as long as the boolean is \pcode{true}. |
128 Loops should be run as long as the boolean is \pcode{true}. |
127 |
129 Programs you should be able to run are shown in |
|
130 Figures \ref{fib} -- \ref{collatz}. |
128 |
131 |
129 |
132 |
130 Give some time measurements for your interpreter |
133 Give some time measurements for your interpreter |
131 and the loop program in Figure~\ref{loop}. For example |
134 and the loop program in Figure~\ref{loop}. For example |
132 how long does your interpreter take when \pcode{start} |
135 how long does your interpreter take when \pcode{start} |
133 is initialised with 100, 500 and so on. How far can |
136 is initialised with 100, 500 and so on. How far can |
134 you scale this value if you are willing to wait, say |
137 you scale this value if you are willing to wait, say |
135 1 Minute? |
138 1 Minute? |
136 |
139 |
137 \begin{figure}[p] |
140 \begin{figure}[h] |
138 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/fib.while} |
141 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/fib.while} |
139 \caption{Fibonacci program in the WHILE language.\label{fib}} |
142 \caption{Fibonacci program in the WHILE language.\label{fib}} |
140 \end{figure} |
143 \end{figure} |
141 |
144 |
142 \begin{figure}[p] |
145 \begin{figure}[h] |
143 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/loops.while} |
146 \lstinputlisting[language=while,xleftmargin=20mm]{../progs/while-tests/loops.while} |
144 \caption{The three-nested-loops program in the WHILE language. |
147 \caption{The three-nested-loops program in the WHILE language. |
145 Usually used for timing measurements.\label{loop}} |
148 Usually used for timing measurements.\label{loop}} |
146 \end{figure} |
149 \end{figure} |
147 |
150 |
|
151 \begin{figure}[h] |
|
152 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/primes.while} |
|
153 \caption{Prime number program.\label{primes}} |
|
154 \end{figure} |
|
155 |
|
156 |
148 \begin{figure}[p] |
157 \begin{figure}[p] |
149 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/primes.while} |
158 \lstinputlisting[language=while,xleftmargin=0mm]{../progs/while-tests/collatz2.while} |
150 \caption{Prime number program.\label{primes}} |
159 \caption{Collatz series program.\label{collatz}} |
151 \end{figure} |
160 \end{figure} |
152 |
161 |
153 \end{document} |
162 \end{document} |
154 |
163 |
155 %%% Local Variables: |
164 %%% Local Variables: |