630
|
1 |
% !TEX program = xelatex
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
2 |
\documentclass{article}
|
299
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../style}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
\usepackage{../langs}
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
\section*{Coursework 3}
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
9 |
|
722
|
10 |
|
|
11 |
|
750
|
12 |
\noindent This coursework is worth 10\% and is due on \cwTHREE{} at
|
877
|
13 |
16:00. You are asked to implement a parser for the WHILE language and
|
748
|
14 |
also an interpreter. You can do the implementation in any programming
|
|
15 |
language you like, but you need to submit the source code with which
|
|
16 |
you answered the questions, otherwise a mark of 0\% will be
|
|
17 |
awarded. You should use the lexer from the previous coursework for the
|
|
18 |
parser. Please package everything(!) in a zip-file that creates a
|
|
19 |
directory with the name \texttt{YournameYourFamilyname} on my end.
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
20 |
|
750
|
21 |
\subsection*{Disclaimer\alert}
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
|
750
|
23 |
It should be understood that the work you submit represents your own
|
|
24 |
effort. You have not copied from anyone else. An exception is the
|
|
25 |
Scala code I showed during the lectures or uploaded to KEATS, which
|
|
26 |
you can both use. You can also use your own code from the CW~1 and
|
886
|
27 |
CW~2. But do not
|
|
28 |
be tempted to ask Github Copilot for help or do any other
|
|
29 |
shenanigans like this!
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
30 |
|
299
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
\subsection*{Question 1}
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
Design a grammar for the WHILE language and give the grammar
|
544
|
35 |
rules. The main categories of non-terminals should be:
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
\item arithmetic expressions (with the operations from the
|
682
|
39 |
previous coursework, that is \pcode{+}, \pcode{-}, \pcode{*},
|
|
40 |
\pcode{/} and \pcode{\%})
|
|
41 |
\item boolean expressions (with the operations \pcode{==}, \pcode{<}, \pcode{>},
|
686
|
42 |
\code{>=}, \code{<=},
|
682
|
43 |
\code{!=}, \pcode{&&}, \pcode{||}, \pcode{true} and \pcode{false})
|
|
44 |
\item single statements (that is \pcode{skip}, assignments, \pcode{if}s,
|
|
45 |
\pcode{while}-loops, \pcode{read} and \pcode{write})
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
\item compound statements separated by semicolons
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
\item blocks which are enclosed in curly parentheses
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
\end{itemize}
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
|
683
|
50 |
\noindent
|
|
51 |
Make sure the grammar is not left-recursive.
|
|
52 |
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\subsection*{Question 2}
|
201
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
|
684
|
55 |
You should implement a parser for the WHILE language using parser
|
|
56 |
combinators. Be careful that the parser takes as input a stream, or
|
750
|
57 |
list, of \emph{tokens} generated by the tokenizer from the previous
|
684
|
58 |
coursework. For this you might want to filter out whitespaces and
|
|
59 |
comments. Your parser should be able to handle the WHILE programs in
|
801
|
60 |
Figures~\ref{fib} -- \ref{collatz}. In addition give the
|
901
|
61 |
parse tree according to your grammar for the statement:
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
\begin{lstlisting}[language=While,numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
if (a < b) then skip else a := a * b + 1
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
\end{lstlisting}
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
\noindent
|
901
|
68 |
The output of the parser is an abstract syntax tree (AST).
|
|
69 |
A (possibly incomplete) datatype for ASTs of the WHILE language
|
|
70 |
is shown in Figure~\ref{trees}.
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
|
750
|
72 |
\begin{figure}[p]
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
\begin{lstlisting}[language=Scala]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
abstract class Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
abstract class AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
abstract class BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
type Block = List[Stmt]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
case object Skip extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
case class While(b: BExp, bl: Block) extends Stmt
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
case class Assign(s: String, a: AExp) extends Stmt
|
750
|
84 |
case class Read(s: String) extends Stmt
|
|
85 |
case class WriteVar(s: String) extends Stmt
|
|
86 |
case class WriteStr(s: String) extends Stmt
|
|
87 |
// for printing variables and strings
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
case class Var(s: String) extends AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
case class Num(i: Int) extends AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
case class Aop(o: String, a1: AExp, a2: AExp) extends AExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
case object True extends BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
case object False extends BExp
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
case class Bop(o: String, a1: AExp, a2: AExp) extends BExp
|
682
|
96 |
case class Lop(o: String, b1: BExp, b2: BExp) extends BExp
|
750
|
97 |
// logical operations: and, or
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\end{lstlisting}
|
901
|
99 |
\caption{The datatype for abstract syntax trees in Scala.\label{trees}}
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
\end{figure}
|
201
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
|
419
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
\subsection*{Question 3}
|
205
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
Implement an interpreter for the WHILE language you designed
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
and parsed in Question 1 and 2. This interpreter should take
|
901
|
106 |
as input an AST. However be careful because, programs
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
contain variables and variable assignments. This means
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
you need to maintain a kind of memory, or environment,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
where you can look up a value of a variable and also
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
store a new value if it is assigned. Therefore an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
evaluation function (interpreter) needs to look roughly as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
follows
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
\begin{lstlisting}[numbers=none]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
eval_stmt(stmt, env)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
\end{lstlisting}
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
where \pcode{stmt} corresponds to the parse tree
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
of the program and \pcode{env} is an environment
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
acting as a store for variable values.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
Consider the Fibonacci program in Figure~\ref{fib}.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
At the beginning of the program this store will be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
empty, but needs to be extended in line 3 and 4 where
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
the variables \pcode{minus1} and \pcode{minus2}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
are assigned values. These values need to be reassigned in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
lines 7 and 8. The program should be interpreted
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
according to straightforward rules: for example an
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
if-statement will ``run'' the if-branch if the boolean
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
evaluates to \pcode{true}, otherwise the else-branch.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
Loops should be run as long as the boolean is \pcode{true}.
|
750
|
132 |
Programs you should be able to run are shown in
|
|
133 |
Figures \ref{fib} -- \ref{collatz}.
|
684
|
134 |
|
|
135 |
|
301
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
Give some time measurements for your interpreter
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
and the loop program in Figure~\ref{loop}. For example
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
how long does your interpreter take when \pcode{start}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
is initialised with 100, 500 and so on. How far can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
140 |
you scale this value if you are willing to wait, say
|
473
|
141 |
1 Minute?
|
202
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
142 |
|
750
|
143 |
\begin{figure}[h]
|
860
|
144 |
\lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/fib.while}
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
145 |
\caption{Fibonacci program in the WHILE language.\label{fib}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
\end{figure}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
147 |
|
750
|
148 |
\begin{figure}[h]
|
860
|
149 |
\lstinputlisting[language=while,xleftmargin=20mm]{../cwtests/cw03/loops.while}
|
300
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
150 |
\caption{The three-nested-loops program in the WHILE language.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
Usually used for timing measurements.\label{loop}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
\end{figure}
|
214
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
|
750
|
154 |
\begin{figure}[h]
|
860
|
155 |
\lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/primes.while}
|
750
|
156 |
\caption{Prime number program.\label{primes}}
|
|
157 |
\end{figure}
|
|
158 |
|
|
159 |
|
684
|
160 |
\begin{figure}[p]
|
860
|
161 |
\lstinputlisting[language=while,xleftmargin=0mm]{../cwtests/cw03/collatz2.while}
|
750
|
162 |
\caption{Collatz series program.\label{collatz}}
|
684
|
163 |
\end{figure}
|
|
164 |
|
200
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
165 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
166 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
167 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
168 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
169 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
170 |
%%% End:
|