# HG changeset patch # User Christian Urban # Date 1669998380 0 # Node ID 33cff35bdc1a6b7b3e0ba8c14d556caf53b5fcb1 # Parent 3be23d0df3db39ef1a37a83c669dee7a9dbac4f1 updated diff -r 3be23d0df3db -r 33cff35bdc1a cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r 3be23d0df3db -r 33cff35bdc1a cws/cw03.tex --- 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 diff -r 3be23d0df3db -r 33cff35bdc1a cws/upload --- /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/ + diff -r 3be23d0df3db -r 33cff35bdc1a hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 3be23d0df3db -r 33cff35bdc1a hws/hw08.tex --- 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} diff -r 3be23d0df3db -r 33cff35bdc1a hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r 3be23d0df3db -r 33cff35bdc1a hws/hw09.tex --- 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 . diff -r 3be23d0df3db -r 33cff35bdc1a progs/fun/funt.sc --- 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)) diff -r 3be23d0df3db -r 33cff35bdc1a slides/slides09.pdf Binary file slides/slides09.pdf has changed diff -r 3be23d0df3db -r 33cff35bdc1a slides/slides09.tex --- 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}