89 \begin{frame}[c] |
89 \begin{frame}[c] |
90 \frametitle{Fun Grammar} |
90 \frametitle{Fun Grammar} |
91 \bl{ |
91 \bl{ |
92 \begin{plstx}[rhs style=] |
92 \begin{plstx}[rhs style=] |
93 : \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}} |
93 : \meta{Exp} ::= \meta{Var} | \meta{Num}{\hspace{3cm}} |
94 | \meta{Exp} + \meta{Exp} | ... | (\meta{ExP}) |
94 | \meta{Exp} + \meta{Exp} | ... | (\meta{Exp}) |
95 | \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp} |
95 | \code{if} \meta{BExp} \code{then} \meta{Exp} \code{else} \meta{Exp} |
96 | \code{write} \meta{Exp} {\hspace{3cm}} |
96 | \code{write} \meta{Exp} {\hspace{3cm}} |
97 | \meta{Exp} ; \meta{Exp} |
97 | \meta{Exp} ; \meta{Exp} |
98 | \textit{FunName} (\meta{Exp}, ..., \meta{Exp})\\ |
98 | \textit{FunName} (\meta{Exp}, ... , \meta{Exp})\\ |
99 : \meta{BExp} ::= ...\\ |
99 : \meta{BExp} ::= ...\\ |
100 : \meta{Decl} ::= \meta{Def} ; \meta{Decl} |
100 : \meta{Decl} ::= \meta{Def} ; \meta{Decl} |
101 | \meta{Exp}\\ |
101 | \meta{Exp}\\ |
102 : \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ..., $x_2$)\\ |
102 : \meta{Def} ::= \code{def} \textit{FunName} ($\hspace{0.4mm}x_1$, ... , $x_n$) = \meta{Exp}\\ |
103 \end{plstx}} |
103 \end{plstx}} |
104 |
104 |
105 |
105 |
106 |
106 |
107 \end{frame} |
107 \end{frame} |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 |
109 |
110 |
|
111 |
|
112 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
113 \begin{frame}[c, fragile] |
111 \begin{frame}[c, fragile] |
114 \frametitle{Abstract Syntax Tree} |
112 \frametitle{Abstract Syntax Trees} |
115 |
113 |
116 \footnotesize |
114 \footnotesize |
117 \begin{textblock}{13}(0.3,2) |
115 \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm] |
118 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
119 abstract class Exp |
116 abstract class Exp |
120 abstract class BExp |
117 abstract class BExp |
121 abstract class Decl |
118 abstract class Decl |
122 |
119 |
123 case class |
120 case class |
132 case class Num(i: Int) extends Exp |
129 case class Num(i: Int) extends Exp |
133 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
130 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp |
134 case class Sequ(e1: Exp, e2: Exp) extends Exp |
131 case class Sequ(e1: Exp, e2: Exp) extends Exp |
135 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
132 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp |
136 \end{lstlisting} |
133 \end{lstlisting} |
137 \end{textblock} |
|
138 |
134 |
139 \end{frame} |
135 \end{frame} |
140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
136 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
141 |
137 |
142 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
143 \begin{frame}[c, fragile] |
139 \begin{frame}[c] |
144 \frametitle{Mathematical Functions} |
140 \frametitle{Arithmetic Functions} |
145 |
141 |
146 Compilation of some mathematical functions: |
142 Compilation of some aritmetic functions: |
147 |
143 |
148 \begin{center} |
144 \begin{center} |
149 \begin{tabular}{lcl} |
145 \begin{tabular}{lcl} |
150 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
146 \texttt{Aop("+", a1, a2)} & $\Rightarrow$ & \texttt{...iadd}\\ |
151 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
147 \texttt{Aop("-", a1, a2)} & $\Rightarrow$ & \texttt{...isub}\\ |
157 |
153 |
158 \end{frame} |
154 \end{frame} |
159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
160 |
156 |
161 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
162 \begin{frame}[c, fragile] |
158 \begin{frame}[c] |
163 \frametitle{Boolean Expressions} |
159 \frametitle{Boolean Expressions} |
164 |
160 |
165 Compilation of boolean expressions: |
161 Compilation of Boolean expressions: |
166 |
162 |
167 \begin{center} |
163 \begin{center} |
168 \begin{tikzpicture}[node distance=2mm and 4mm, |
164 \begin{tikzpicture}[node distance=2mm and 4mm, |
169 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
165 block/.style={rectangle, minimum size=1cm, draw=black, line width=1mm}, |
170 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
166 point/.style={rectangle, inner sep=0mm, minimum size=0mm, fill=red}, |
198 |
194 |
199 \end{frame} |
195 \end{frame} |
200 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
201 |
197 |
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
203 \begin{frame}[t, fragile] |
199 \begin{frame}[c, fragile] |
204 \frametitle{Sequences} |
200 \frametitle{Sequences} |
205 |
201 |
206 Compiling \texttt{arg1 ; arg2}: |
202 Compiling \texttt{arg1 ; arg2}:\bigskip |
207 |
203 |
208 |
204 |
209 \begin{textblock}{7}(2,5)\footnotesize |
205 \begin{lstlisting}[language=JVMIS, numbers=none] |
210 \begin{minipage}{6cm} |
|
211 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
212 ...arg1... |
206 ...arg1... |
213 pop |
207 pop |
214 ...arg1... |
208 ...arg1... |
215 \end{lstlisting} |
209 \end{lstlisting} |
216 \end{minipage} |
|
217 \end{textblock} |
|
218 |
|
219 |
210 |
220 \end{frame} |
211 \end{frame} |
221 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
222 |
213 |
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
224 \begin{frame}[t, fragile] |
215 \begin{frame}[c, fragile] |
225 \frametitle{Write} |
216 \frametitle{Write} |
226 |
217 |
227 Compiling \texttt{write(arg)}: |
218 Compiling call to \texttt{write(arg)}:\bigskip |
228 |
219 |
229 |
220 |
230 \begin{textblock}{7}(2,4)\footnotesize |
221 \begin{lstlisting}[language=JVMIS, numbers=none] |
231 \begin{minipage}{6cm} |
|
232 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
233 ...arg... |
222 ...arg... |
234 dup |
223 dup |
235 invokestatic XXX/XXX/write(I)V |
224 invokestatic XXX/XXX/write(I)V |
236 \end{lstlisting} |
225 \end{lstlisting}\bigskip |
237 \end{minipage} |
226 |
238 \end{textblock} |
227 \small |
239 |
228 needs a helper function |
240 |
229 |
241 |
|
242 \begin{textblock}{7}(2,8)\footnotesize |
|
243 \begin{minipage}{6cm} |
|
244 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
|
245 case Write(a1) => { |
|
246 compile_exp(a1, env) ++ |
|
247 List("dup\n", |
|
248 "invokestatic XXX/XXX/write(I)V\n") |
|
249 } |
|
250 \end{lstlisting} |
|
251 \end{minipage} |
|
252 \end{textblock} |
|
253 |
|
254 \end{frame} |
230 \end{frame} |
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
231 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
256 |
232 |
257 |
233 |
258 |
234 |
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
235 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
260 \begin{frame}[c, fragile] |
236 \begin{frame}[c, fragile] |
261 \frametitle{Functions} |
237 \frametitle{Function Definitions} |
262 |
238 |
263 \begin{textblock}{7}(1,2)\footnotesize |
239 \footnotesize |
264 \begin{minipage}{6cm} |
240 \begin{lstlisting}[language=JVMIS, |
265 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
241 xleftmargin=2mm, |
|
242 numbers=none] |
266 .method public static write(I)V |
243 .method public static write(I)V |
267 .limit locals 5 |
244 .limit locals 1 |
268 .limit stack 5 |
245 .limit stack 2 |
|
246 getstatic java/lang/System/out Ljava/io/PrintStream; |
269 iload 0 |
247 iload 0 |
270 getstatic java/lang/System/out Ljava/io/PrintStream; |
|
271 swap |
|
272 invokevirtual java/io/PrintStream/println(I)V |
248 invokevirtual java/io/PrintStream/println(I)V |
273 return |
249 return |
274 .end method |
250 .end method |
275 \end{lstlisting} |
251 \end{lstlisting}\bigskip |
276 \end{minipage} |
252 |
277 \end{textblock} |
253 \small We will need for definitions\footnotesize\medskip |
278 |
254 |
279 |
255 \begin{lstlisting}[language=JVMIS, |
280 \begin{textblock}{10}(1,9.8) |
256 xleftmargin=2mm, |
281 \small We will need for definitions\\[-8mm]\mbox{}\footnotesize |
257 numbers=none] |
282 \begin{center} |
|
283 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
|
284 .method public static f (I...I)I |
258 .method public static f (I...I)I |
285 .limit locals ?? |
259 .limit locals ?? |
286 .limit stack ?? |
260 .limit stack ?? |
287 ?? |
261 ?? |
288 .end method |
262 .end method |
289 \end{lstlisting} |
263 \end{lstlisting} |
290 \end{center} |
|
291 \end{textblock} |
|
292 |
264 |
293 \end{frame} |
265 \end{frame} |
294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
295 |
267 |
296 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
300 \begin{center} |
272 \begin{center} |
301 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
273 \begin{lstlisting}[language=Scala,basicstyle=\ttfamily, numbers=none] |
302 def max_stack_exp(e: Exp): Int = e match { |
274 def max_stack_exp(e: Exp): Int = e match { |
303 case Call(_, args) => args.map(max_stack_exp).sum |
275 case Call(_, args) => args.map(max_stack_exp).sum |
304 case If(a, e1, e2) => max_stack_bexp(a) + |
276 case If(a, e1, e2) => max_stack_bexp(a) + |
305 (List(max_stack_exp(e1), max_stack_exp(e1)).max) |
277 (List(max_stack_exp(e1), max_stack_exp(e1)).max) |
306 case Write(e) => max_stack_exp(e) + 1 |
278 case Write(e) => max_stack_exp(e) + 1 |
307 case Var(_) => 1 |
279 case Var(_) => 1 |
308 case Num(_) => 1 |
280 case Num(_) => 1 |
309 case Aop(_, a1, a2) => |
281 case Aop(_, a1, a2) => |
310 max_stack_exp(a1) + max_stack_exp(a2) |
282 max_stack_exp(a1) + max_stack_exp(a2) |
311 case Sequ(e1, e2) => |
283 case Sequ(e1, e2) => |
312 List(max_stack_exp(e1), max_stack_exp(e2)).max |
284 List(max_stack_exp(e1), max_stack_exp(e2)).max |
313 } |
285 } |
314 |
286 |
315 def max_stack_bexp(e: BExp): Int = e match { |
287 def max_stack_bexp(e: BExp): Int = e match { |
316 case Bop(_, a1, a2) => |
288 case Bop(_, a1, a2) => |
317 max_stack_exp(a1) + max_stack_exp(a2) |
289 max_stack_exp(a1) + max_stack_exp(a2) |
318 } |
290 } |
319 \end{lstlisting} |
291 \end{lstlisting} |
320 \end{center} |
292 \end{center} |
321 |
293 |
322 \end{frame} |
294 \end{frame} |
323 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
295 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
324 |
296 |
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
297 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 \begin{frame}[fragile] |
298 \begin{frame}[fragile] |
327 \frametitle{Successor} |
299 \frametitle{Successor Function} |
328 |
300 |
329 \begin{textblock}{7}(1,2.5)\footnotesize |
301 \begin{textblock}{7}(1,2.5)\footnotesize |
330 \begin{minipage}{6cm} |
302 \begin{minipage}{6cm} |
331 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
303 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
332 .method public static suc(I)I |
304 .method public static suc(I)I |
355 \end{frame} |
327 \end{frame} |
356 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
328 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
357 |
329 |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
359 \begin{frame}[fragile] |
331 \begin{frame}[fragile] |
360 \frametitle{Addition} |
332 \frametitle{Addition Function} |
361 |
333 |
362 \begin{textblock}{7}(1,1.5)\footnotesize |
334 \begin{textblock}{7}(1,1.9)\footnotesize |
363 \begin{minipage}{6cm} |
335 \begin{minipage}{6cm} |
364 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
336 \begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none] |
365 .method public static add(II)I |
337 .method public static add(II)I |
366 .limit locals 2 |
338 .limit locals 2 |
367 .limit stack 6 |
339 .limit stack 6 |
368 iload 0 |
340 iload 0 |
369 ldc 0 |
341 ldc 0 |
370 if_icmpne If_else_2 |
342 if_icmpne If_else |
371 iload 1 |
343 iload 1 |
372 goto If_end_3 |
344 goto If_end |
373 If_else_2: |
345 If_else: |
374 iload 0 |
346 iload 0 |
375 ldc 1 |
347 ldc 1 |
376 isub |
348 isub |
377 iload 1 |
349 iload 1 |
378 invokestatic defs/defs/add(II)I |
350 invokestatic XXX/XXX/add(II)I |
379 invokestatic defs/defs/suc(I)I |
351 invokestatic XXX/XXX/suc(I)I |
380 If_end_3: |
352 If_end: |
381 ireturn |
353 ireturn |
382 .end method |
354 .end method |
383 \end{lstlisting} |
355 \end{lstlisting} |
384 \end{minipage} |
356 \end{minipage} |
385 \end{textblock} |
357 \end{textblock} |
386 |
358 |
387 \begin{textblock}{7}(6,6.2) |
359 \begin{textblock}{7}(6,6.6) |
388 \begin{bubble}[7cm]\small |
360 \begin{bubble}[7cm]\small |
389 \begin{lstlisting}[language=Lisp, |
361 \begin{lstlisting}[language=Lisp, |
390 basicstyle=\ttfamily, |
362 basicstyle=\ttfamily, |
391 numbers=none, |
363 numbers=none, |
392 xleftmargin=1mm] |
364 xleftmargin=1mm] |