Binary file cws/cw03.pdf has changed
--- a/cws/cw03.tex Thu Dec 01 13:07:32 2022 +0000
+++ b/cws/cw03.tex Fri Dec 02 16:26:20 2022 +0000
@@ -58,15 +58,16 @@
coursework. For this you might want to filter out whitespaces and
comments. Your parser should be able to handle the WHILE programs in
Figures~\ref{fib} -- \ref{collatz}. In addition give the
-parse tree for the statement:
+parse tree according to your grammar for the statement:
\begin{lstlisting}[language=While,numbers=none]
if (a < b) then skip else a := a * b + 1
\end{lstlisting}
\noindent
-A (possibly incomplete) datatype for parse trees in Scala is shown
-in Figure~\ref{trees}.
+The output of the parser is an abstract syntax tree (AST).
+A (possibly incomplete) datatype for ASTs of the WHILE language
+is shown in Figure~\ref{trees}.
\begin{figure}[p]
\begin{lstlisting}[language=Scala]
@@ -95,14 +96,14 @@
case class Lop(o: String, b1: BExp, b2: BExp) extends BExp
// logical operations: and, or
\end{lstlisting}
-\caption{The datatype for parse trees in Scala.\label{trees}}
+\caption{The datatype for abstract syntax trees in Scala.\label{trees}}
\end{figure}
\subsection*{Question 3}
Implement an interpreter for the WHILE language you designed
and parsed in Question 1 and 2. This interpreter should take
-as input a parse tree. However be careful because, programs
+as input an AST. However be careful because, programs
contain variables and variable assignments. This means
you need to maintain a kind of memory, or environment,
where you can look up a value of a variable and also
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/upload Fri Dec 02 16:26:20 2022 +0000
@@ -0,0 +1,12 @@
+#!/bin/bash
+set -euo pipefail
+
+fls=${1:-"cw01.pdf cw02.pdf cw03.pdf cw04.pdf cw05.pdf"}
+
+for f in $fls; do
+ echo -e "uploading $f"
+done
+
+
+scp $fls k1192855@bastion:public_html/cfl/cws/
+
Binary file hws/hw08.pdf has changed
--- a/hws/hw08.tex Thu Dec 01 13:07:32 2022 +0000
+++ b/hws/hw08.tex Fri Dec 02 16:26:20 2022 +0000
@@ -23,13 +23,13 @@
\texttt{is\_even} and \texttt{is\_odd} tail-recursive?
\begin{lstlisting}[numbers=none]
-def iseven(n: Int) : Boolean = {
- if (n == 0) true else isodd(n - 1)
+def is_even(n: Int) : Boolean = {
+ if (n == 0) true else is_odd(n - 1)
}
-def isodd(n: Int) : Boolean = {
+def is_odd(n: Int) : Boolean = {
if (n == 0) false
- else if (n == 1) true else iseven(n - 1)
+ else if (n == 1) true else is_even(n - 1)
}
\end{lstlisting}
Binary file hws/hw09.pdf has changed
--- a/hws/hw09.tex Thu Dec 01 13:07:32 2022 +0000
+++ b/hws/hw09.tex Fri Dec 02 16:26:20 2022 +0000
@@ -44,6 +44,38 @@
if_icmpge label
\end{lstlisting}
+\item What does the following JVM function calculate?
+
+\begin{lstlisting}[language=JVMIS2,numbers=none]
+.method public static bar(I)I
+.limit locals 1
+.limit stack 9
+ iload 0
+ ldc 0
+ if_icmpne If_else_8
+ ldc 0
+ goto If_end_9
+If_else_8:
+ iload 0
+ ldc 1
+ if_icmpne If_else_10
+ ldc 1
+ goto If_end_11
+If_else_10:
+ iload 0
+ ldc 1
+ isub
+ invokestatic bar(I)I
+ iload 0
+ ldc 2
+ isub
+ invokestatic bar(I)I
+ iadd
+If_end_11:
+If_end_9:
+ ireturn
+.end method
+\end{lstlisting}
\item What does the following LLVM function calculate? Give the
corresponding arithmetic expression .
--- a/progs/fun/funt.sc Thu Dec 01 13:07:32 2022 +0000
+++ b/progs/fun/funt.sc Fri Dec 02 16:26:20 2022 +0000
@@ -1,3 +1,4 @@
+
// A Small Compiler for a Simple Functional Language
// - includes a lexer and a parser
// - performs tail-call optimisations
@@ -165,7 +166,7 @@
// import ammonite.ops._
// post 2.5.0 ammonite
-// import os._
+import os._
def compile_to_file(prog: List[Decl], class_name: String) : Unit =
write.over(pwd / s"$class_name.j", compile(prog, class_name))
Binary file slides/slides09.pdf has changed
--- a/slides/slides09.tex Thu Dec 01 13:07:32 2022 +0000
+++ b/slides/slides09.tex Fri Dec 02 16:26:20 2022 +0000
@@ -22,16 +22,17 @@
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-2mm]
- \LARGE Formal Languages\\[3mm]
+ \LARGE Formal Languages\\[-3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
- Email: & christian.urban at kcl.ac.uk\\
- %Office Hours: & Thursdays 12 -- 14\\
- %Location: & N7.07 (North Wing, Bush House)\\
- Slides \& Progs: & KEATS (also homework is there)\\
+ Email: & christian.urban at kcl.ac.uk\\
+ Office Hour: & Fridays 11 -- 12\\
+ Location: & N7.07 (North Wing, Bush House)\\
+ Slides \& Progs: & KEATS\\
+ Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\end{tabular}
\end{center}
@@ -75,7 +76,41 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c, fragile]
+\frametitle{Stack Estimation}
+\small
+\mbox{}\\[-15mm]
+
+\bl{\begin{center}
+\begin{tabular}{@{\hspace{-4mm}}l@{\hspace{2mm}}c@{\hspace{2mm}}l@{}}
+$\textit{estimate}(n)$ & $\dn$ & $1$\\
+$\textit{estimate}(x)$ & $\dn$ & $1$\\
+$\textit{estimate}(a_1\;aop\;a_2)$ & $\dn$ &
+$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+$\textit{estimate}(\pcode{if}\;b\;\pcode{then}\;e_1\;\pcode{else}\;e_2)$ & $\dn$ &
+$\textit{estimate}(b) +$\\
+& & $\quad max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+$\textit{estimate}(\pcode{write}(e))$ & $\dn$ &
+$\textit{estimate}(e) + 1$\\
+$\textit{estimate}(e_1 ; e_2)$ & $\dn$ &
+$max(\textit{estimate}(e_1), \textit{estimate}(e_2))$\\
+$\textit{estimate}(f(e_1, ..., e_n))$ & $\dn$ &
+$\sum_{i = 1..n}\;estimate(e_i)$\medskip\\
+$\textit{estimate}(a_1\;bop\;a_2)$ & $\dn$ &
+$\textit{estimate}(a_1) + \textit{estimate}(a_2)$\\
+\end{tabular}
+\end{center}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
\begin{frame}[c,fragile]
\frametitle{\mbox{}\hspace{5cm}Factorial}
@@ -229,52 +264,69 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c,fragile]
-\frametitle{Factorial Funct.~on the JVM}
+\frametitle{Peephole Optimisations}
-\begin{textblock}{7}(1,1.8)\footnotesize
-\begin{minipage}{6cm}
-\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
-.method public static facT(II)I
-.limit locals 2
-.limit stack 6
- iload 0
- ldc 0
- if_icmpne If_else_2
- iload 1
- goto If_end_3
-If_else_2:
- iload 0
- ldc 1
- isub
- iload 0
- iload 1
- imul
- invokestatic fact/fact/facT(II)I
-If_end_3:
- ireturn
-.end method
-\end{lstlisting}
-\end{minipage}
-\end{textblock}
-
-\begin{textblock}{7}(6,7)
-\begin{bubble}[7cm]\small
-\begin{lstlisting}[language=Lisp,
- basicstyle=\ttfamily,
- numbers=none,
- xleftmargin=1mm,linebackgroundcolor=\color{cream}]
-def facT(n, acc) =
- if n == 0 then acc
- else facT(n - 1, n * acc);
-\end{lstlisting}
-\end{bubble}
-\end{textblock}
+\begin{center}
+\begin{tabular}{ll}
+ \texttt{ldc}: & \texttt{iconst\_0} \ldots \texttt{iconst\_5}\\
+ & \texttt{bipush} $n$ where $-128 < n <= 128$\bigskip\\
+ \texttt{iload}: & \texttt{iload\_0} \ldots \texttt{iload\_3}\bigskip\\
+ \texttt{istore}: & \texttt{istore\_0} \ldots \texttt{istore\_3}\\
+\end{tabular}
+\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c,fragile]
+%\frametitle{Factorial Funct.~on the JVM}
+%
+%\begin{textblock}{7}(1,1.8)\footnotesize
+%\begin{minipage}{6cm}
+%\begin{lstlisting}[language=JVMIS,basicstyle=\ttfamily, numbers=none]
+%.method public static facT(II)I
+%.limit locals 2
+%.limit stack 6
+% iload 0
+% ldc 0
+% if_icmpne If_else_2
+% iload 1
+% goto If_end_3
+%If_else_2:
+% iload 0
+% ldc 1
+% isub
+% iload 0
+% iload 1
+% imul
+% invokestatic fact/fact/facT(II)I
+%If_end_3:
+% ireturn
+%.end method
+%\end{lstlisting}
+%\end{minipage}
+%\end{textblock}
+%
+%\begin{textblock}{7}(6,7)
+%\begin{bubble}[7cm]\small
+%\begin{lstlisting}[language=Lisp,
+% basicstyle=\ttfamily,
+% numbers=none,
+% xleftmargin=1mm,linebackgroundcolor=\color{cream}]
+%def facT(n, acc) =
+% if n == 0 then acc
+% else facT(n - 1, n * acc);
+%\end{lstlisting}
+%\end{bubble}
+%\end{textblock}
+%
+%\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile,c]
\frametitle{LLVM}