23 |
23 |
24 \noindent |
24 \noindent |
25 You can do the implementation of your compiler in any programming |
25 You can do the implementation of your compiler in any programming |
26 language you like, but you need to submit the source code with which |
26 language you like, but you need to submit the source code with which |
27 you generated the LLVM-IR files, otherwise a mark of 0\% will be |
27 you generated the LLVM-IR files, otherwise a mark of 0\% will be |
28 awarded. You should use the lexer and parser from the previous |
28 awarded. You are asked to submit the code of your compiler, but also |
29 courseworks, but you need to make some modifications to them for the |
29 the generated \texttt{.ll} files. You should use the lexer and parser |
30 `typed' fun-language. I will award up to 5\% if a lexer and a parser are |
30 from the previous courseworks, but you need to make some modifications |
31 correctly implemented. At the end, please package everything(!) in a zip-file |
31 to them for the `typed' fun-language. I will award up to 5\% if a |
32 that creates a directory with the name \texttt{YournameYourFamilyname} |
32 lexer and a parser are correctly implemented. At the end, please |
|
33 package everything(!) in a zip-file that creates a directory with the |
|
34 name |
|
35 |
|
36 \begin{center} |
|
37 \texttt{YournameYourFamilyname} |
|
38 \end{center} |
|
39 |
|
40 \noindent |
33 on my end. |
41 on my end. |
34 |
42 |
35 \subsection*{Disclaimer\alert} |
43 \subsection*{Disclaimer\alert} |
36 |
44 |
37 It should be understood that the work you submit represents your own |
45 It should be understood that the work you submit represents your own |
41 CW~4. |
49 CW~4. |
42 |
50 |
43 |
51 |
44 \subsection*{Task} |
52 \subsection*{Task} |
45 |
53 |
46 The goal is to lex and parse the Mandelbrot program shown in |
54 The main goal is to lex and parse 4 Fun-programs, including the |
47 Figure~\ref{mand} and generate corresponding code for the |
55 Mandelbrot program shown in Figure~\ref{mand}, and generate |
48 LLVM-IR. Unfortunately the calculations for the Mandelbrot set require |
56 corresponding code for the LLVM-IR. Unfortunately the calculations for |
49 floating point arithmetic and therefore we cannot be as simple-minded |
57 the Mandelbrot Set require floating point arithmetic and therefore we |
50 about types as we have been so far (remember the LLVM-IR is a |
58 cannot be as simple-minded about types as we have been so far |
51 fully-typed language and needs to know the exact types of each |
59 (remember the LLVM-IR is a fully-typed language and needs to know the |
52 expression). The idea is to deal appropriately with three types, |
60 exact types of each expression). The idea is to deal appropriately |
53 namely \texttt{Int}, \texttt{Double} and \texttt{Void} (they are |
61 with three types, namely \texttt{Int}, \texttt{Double} and |
54 represented in the LLVM-IR as \texttt{i32}, \texttt{double} and |
62 \texttt{Void} (they are represented in the LLVM-IR as \texttt{i32}, |
55 \texttt{void}). You need to extend the lexer and parser accordingly in |
63 \texttt{double} and \texttt{void}). You need to extend the lexer and |
56 order to deal with type annotations. The Fun-language includes global |
64 parser accordingly in order to deal with type annotations. The |
57 constants, such as |
65 Fun-language includes global constants, such as |
58 |
66 |
59 \begin{lstlisting}[numbers=none] |
67 \begin{lstlisting}[numbers=none] |
60 val Ymin: Double = -1.3; |
68 val Ymin: Double = -1.3; |
61 val Maxiters: Int = 1000; |
69 val Maxiters: Int = 1000; |
62 \end{lstlisting} |
70 \end{lstlisting} |
68 type \texttt{Int} or \texttt{Double}, and need to specify a return |
76 type \texttt{Int} or \texttt{Double}, and need to specify a return |
69 type, which can be \texttt{Void}, for example |
77 type, which can be \texttt{Void}, for example |
70 |
78 |
71 \begin{lstlisting}[numbers=none] |
79 \begin{lstlisting}[numbers=none] |
72 def foo(n: Int, x: Double) : Double = ... |
80 def foo(n: Int, x: Double) : Double = ... |
|
81 def id(n: Int) : Int = ... |
73 def bar() : Void = ... |
82 def bar() : Void = ... |
74 \end{lstlisting} |
83 \end{lstlisting} |
75 |
84 |
76 \noindent |
85 \noindent |
77 The idea is to record all typing information that is given |
86 The idea is to record all typing information that is given |
78 in the program, but then delay any further typing inference to |
87 in the Fun-program, but then delay any further typing inference to |
79 after the CPS-translation. That means the parser should |
88 after the CPS-translation. That means the parser should |
80 generate ASTs given by the Scala dataypes: |
89 generate ASTs given by the Scala dataypes: |
81 |
90 |
82 \begin{lstlisting}[numbers=none,language=Scala] |
91 \begin{lstlisting}[numbers=none,language=Scala] |
83 abstract class Exp |
92 abstract class Exp |
91 case class FConst(name: String, x: Float) extends Decl |
100 case class FConst(name: String, x: Float) extends Decl |
92 |
101 |
93 case class Call(name: String, args: List[Exp]) extends Exp |
102 case class Call(name: String, args: List[Exp]) extends Exp |
94 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
103 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp |
95 case class Var(s: String) extends Exp |
104 case class Var(s: String) extends Exp |
96 case class Num(i: Int) extends Exp // integer numbers |
105 case class Num(i: Int) extends Exp // integer numbers |
97 case class FNum(i: Float) extends Exp // floating numbers |
106 case class FNum(i: Float) extends Exp // floating numbers |
|
107 case class ChConst(c: Int) extends Exp // char constant |
98 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
108 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
99 case class Sequence(e1: Exp, e2: Exp) extends Exp |
109 case class Sequence(e1: Exp, e2: Exp) extends Exp |
100 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
110 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
101 \end{lstlisting} |
111 \end{lstlisting} |
102 |
112 |
118 \begin{figure}[t] |
128 \begin{figure}[t] |
119 \includegraphics[scale=0.35]{../progs/fun2/out.png} |
129 \includegraphics[scale=0.35]{../progs/fun2/out.png} |
120 \caption{Ascii output of the Mandelbrot program.\label{mand}} |
130 \caption{Ascii output of the Mandelbrot program.\label{mand}} |
121 \end{figure} |
131 \end{figure} |
122 |
132 |
|
133 Also note that the second version of the Mandelbrot program and also |
|
134 the Tower of Hanoi program uses character constants, like \texttt{'a'}, |
|
135 \texttt{'1'}, \texttt{'$\backslash$n'} and so on. When they are tokenised, |
|
136 such characters should be interpreted as the corresponding ASCII code (an |
|
137 integer), such that we can use them in calculations like \texttt{'a' + 10} |
|
138 where the result should be 107. As usual, the character \texttt{'$\backslash$n'} is the |
|
139 ASCII code 10. |
|
140 |
|
141 |
123 \subsection*{LLVM-IR} |
142 \subsection*{LLVM-IR} |
124 |
143 |
125 There are some subtleties in the LLVM-IR you need to be aware of: |
144 There are some subtleties in the LLVM-IR you need to be aware of: |
126 |
145 |
127 \begin{itemize} |
146 \begin{itemize} |
173 def compile_op(op: String) = op match { |
192 def compile_op(op: String) = op match { |
174 case "+" => "add i32 " |
193 case "+" => "add i32 " |
175 case "*" => "mul i32 " |
194 case "*" => "mul i32 " |
176 case "-" => "sub i32 " |
195 case "-" => "sub i32 " |
177 case "==" => "icmp eq i32 " |
196 case "==" => "icmp eq i32 " |
|
197 case "!=" => "icmp ne i32 " |
178 case "<=" => "icmp sle i32 " // signed less or equal |
198 case "<=" => "icmp sle i32 " // signed less or equal |
179 case "<" => "icmp slt i32 " // signed less than |
199 case "<" => "icmp slt i32 " // signed less than |
180 }\end{lstlisting} |
200 }\end{lstlisting} |
181 |
201 |
182 the corresponding operations on doubles are |
202 the corresponding operations on doubles are |
185 def compile_dop(op: String) = op match { |
205 def compile_dop(op: String) = op match { |
186 case "+" => "fadd double " |
206 case "+" => "fadd double " |
187 case "*" => "fmul double " |
207 case "*" => "fmul double " |
188 case "-" => "fsub double " |
208 case "-" => "fsub double " |
189 case "==" => "fcmp oeq double " |
209 case "==" => "fcmp oeq double " |
|
210 case "!=" => "fcmp one double " |
190 case "<=" => "fcmp ole double " |
211 case "<=" => "fcmp ole double " |
191 case "<" => "fcmp olt double " |
212 case "<" => "fcmp olt double " |
192 }\end{lstlisting} |
213 }\end{lstlisting} |
193 |
214 |
194 \item \textbf{Typing}: In order to leave the CPS-translations |
215 \item \textbf{Typing}: In order to leave the CPS-translations |
218 looking at the literature which solves the problem |
239 looking at the literature which solves the problem |
219 with much heavier machinery. |
240 with much heavier machinery. |
220 |
241 |
221 \item \textbf{Build-In Functions}: The `prelude' comes |
242 \item \textbf{Build-In Functions}: The `prelude' comes |
222 with several build-in functions: \texttt{new\_line()}, |
243 with several build-in functions: \texttt{new\_line()}, |
223 \texttt{skip}, \texttt{print\_int(n)}, \texttt{print\_space()} |
244 \texttt{skip}, \texttt{print\_int(n)}, \texttt{print\_space()}, |
224 and \texttt{print\_star()}. You can find the `prelude' for |
245 \texttt{print\_star()} and \texttt{print\_char(n)}. You can find the `prelude' for |
225 example in the file \texttt{sqr.ll}. |
246 example in the file \texttt{sqr.ll}. |
226 \end{itemize} |
247 \end{itemize} |
227 |
248 |
228 \end{document} |
249 \end{document} |
229 |
250 |