# HG changeset patch # User Christian Urban # Date 1708506852 0 # Node ID 64ec1884d860d3eb1257fdbea730f6b4b1e9f27e # Parent fddf099a82f8265df5e833915ea784562e47a116 updated and added pascal.while file diff -r fddf099a82f8 -r 64ec1884d860 cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 cws/cw02.pdf Binary file cws/cw02.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 cws/cw03.pdf Binary file cws/cw03.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 cws/cw04.pdf Binary file cws/cw04.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 cws/cw04.tex --- a/cws/cw04.tex Sat Dec 02 21:37:04 2023 +0000 +++ b/cws/cw04.tex Wed Feb 21 09:14:12 2024 +0000 @@ -103,7 +103,7 @@ below as a slightly different syntax. -\subsection*{Krakatau Assembler} +\subsection*{Krakatau Assembler (Version 1 \& 2)} The Krakatau assembler is available from @@ -119,11 +119,11 @@ \end{center} \noindent This assembler is largely compatible with the Jasmin -syntax---that means for the files we are concerned with here, -it understands the same input syntax (no changes to your -compiler need to be made; ok maybe some small syntactic -adjustments are needed). You can generate Java Byte Code by -using +syntax---that means for the files we are concerned with here, it +understands the same input syntax (no changes to your compiler need to +be made; ok maybe some small syntactic adjustments are needed, for +example labels need to start with a capital '\texttt{L}'). You can generate Java +Byte Code by using \begin{center} \texttt{python Krakatau-master/assemble.py loops.j} @@ -161,16 +161,16 @@ \subsection*{Question 1} -You need to lex and parse WHILE programs, and then generate -Java Byte Code instructions for the Jasmin assembler (or -Krakatau assembler). As solution you need to submit the -assembler instructions for the Fibonacci and Factorial -programs. Both should be so modified that a user can input on -the console which Fibonacci number and which Factorial should -be calculated. The Fibonacci program is given in -Figure~\ref{fibs}. You can write your own program for -calculating factorials. Submit your assembler code as -a file that can be run, not as PDF-text. +You need to lex and parse WHILE programs, and then generate Java Byte +Code instructions for the Jasmin assembler (or Krakatau +assembler). For this you should use the ASTs defined in CW3 (including +logical operators). As part of the solution you need to submit the assembler +instructions for the Fibonacci and Factorial programs. Both should be +so modified that a user can input on the console which Fibonacci +number and which Factorial should be calculated. The Fibonacci program +is given in Figure~\ref{fibs}. You can write your own program for +calculating factorials. Submit your assembler code as a file that can +be run, not as PDF-text. \begin{figure}[t] \lstinputlisting[language=while]{../cwtests/cw04/fib.while} @@ -255,8 +255,8 @@ Extend the lexer and parser to add a \textcolor{codepurple}{\pcode{break}} keyword. Modify the compiler (including lexer and parser) such that when a \textcolor{codepurple}{\texttt{break}}-statement is encountered -the code should jump out of the ``enclosing'' for-loop, or in case it -is not inside a for-loop to the end of the program. For example the +the code should jump out of the ``enclosing'' for/while-loop, or in case it +is not inside such a loop to the end of the program. For example the program \begin{center} @@ -286,7 +286,7 @@ should print out 0 to 10 with the first for-loop, but only 0 to 4 in the second. Similarly it should print out \code{"Should print"}, but not \code{"Should not print"}. For this you need to add -a label to the end of every for-loop and also to the end of the +a label to the end of every for- and while-loop and also to the end of the whole program just in case you need to jump to that label via a \code{break}. The file you need to be able to process for this question is called \texttt{break.while}. diff -r fddf099a82f8 -r 64ec1884d860 cws/cw05.pdf Binary file cws/cw05.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 cws/cw05.tex --- a/cws/cw05.tex Sat Dec 02 21:37:04 2023 +0000 +++ b/cws/cw05.tex Wed Feb 21 09:14:12 2024 +0000 @@ -9,27 +9,27 @@ \begin{document} -\color{pansypurple} -\section*{RESIT / REPLACEMENT} +%\color{pansypurple} +%\section*{RESIT / REPLACEMENT} -{\bf -The resit / replacement task is essentially CW5 (listed below) with -the exception that the lexer and parser is already provided. The -parser will generate an AST (see file \texttt{fun\_llvm.sc}). Your task -is to generate an AST for the K-intermediate language and supply -sufficient type annotations such that you can generate valid code for -the LLVM-IR. The submission deadline is 4th August at 16:00. At the -deadline, please send me an email containing a zip-file with your -files. -Feel free to reuse the files I have uploaded on KEATS (especially -the files generating simple LLVM-IR code). Of help might also be the -videos of Week~10.\bigskip - -\noindent -Good Luck!}\smallskip\\ -\noindent -Christian -\color{black} +%{\bf +%The resit / replacement task is essentially CW5 (listed below) with +%the exception that the lexer and parser is already provided. The +%parser will generate an AST (see file \texttt{fun\_llvm.sc}). Your task +%is to generate an AST for the K-intermediate language and supply +%sufficient type annotations such that you can generate valid code for +%the LLVM-IR. The submission deadline is 4th August at 16:00. At the +%deadline, please send me an email containing a zip-file with your +%files. +%Feel free to reuse the files I have uploaded on KEATS (especially +%the files generating simple LLVM-IR code). Of help might also be the +%videos of Week~10.\bigskip +% +%\noindent +%Good Luck!}\smallskip\\ +%\noindent +%Christian +%\color{black} \section*{Coursework 5} @@ -40,7 +40,7 @@ 16:00. You are asked to implement a compiler targeting the LLVM-IR. Be careful that this CW needs some material about the LLVM-IR that has not been shown in the lectures and your own experiments -might be required. You can find information about the LLVM-IR at +and research might be required. You can find information about the LLVM-IR at \begin{itemize} \item \url{https://bit.ly/3rheZYr} @@ -56,15 +56,18 @@ coursework. You should use the lexer and parser from the previous courseworks, but you need to make some modifications to them for the `typed' version of the Fun-language. I will award up to 5\% if a lexer -and a parser are correctly implemented. At the end, please package -everything(!) in a zip-file that creates a directory with the name +and a parser are correctly implemented. -\begin{center} -\texttt{YournameYourFamilyname} -\end{center} - -\noindent -on my end. You will be marked according to the input files +%At the end, please package +%everything(!) in a zip-file that creates a directory with the name +% +%\begin{center} +%\texttt{YournameYourFamilyname} +%\end{center} +% +%\noindent +%on my end. +You will be marked according to the input files \begin{itemize} \item\href{https://nms.kcl.ac.uk/christian.urban/cfl/progs/sqr.fun}{sqr.fun} @@ -75,7 +78,7 @@ \end{itemize} \noindent -which are uploaded to KEATS. +which are uploaded to KEATS and Github. \subsection*{Disclaimer\alert} diff -r fddf099a82f8 -r 64ec1884d860 cwtests/cw05/fact.fun --- a/cwtests/cw05/fact.fun Sat Dec 02 21:37:04 2023 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,21 +0,0 @@ -// a simple factorial program -// (including a tail recursive version) - - -def fact(n: Int) : Int = - if n == 0 then 1 else n * fact(n - 1); - -def facT(n: Int, acc: Int) : Int = - if n == 0 then acc else facT(n - 1, n * acc); - -def facTi(n: Int) : Int = facT(n, 1); - -def top() : Void = { - print_int(fact(6)); - print_char(','); - print_int(facTi(6)); - print_char('\n') -}; - -top() - diff -r fddf099a82f8 -r 64ec1884d860 cwtests/cw05/fact2.fun --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/cwtests/cw05/fact2.fun Wed Feb 21 09:14:12 2024 +0000 @@ -0,0 +1,21 @@ +// a simple factorial program +// (including a tail recursive version) + + +def fact(n: Int) : Int = + if n == 0 then 1 else n * fact(n - 1); + +def facT(n: Int, acc: Int) : Int = + if n == 0 then acc else facT(n - 1, n * acc); + +def facTi(n: Int) : Int = facT(n, 1); + +def top() : Void = { + print_int(fact(6)); + print_char(','); + print_int(facTi(6)); + print_char('\n') +}; + +top() + diff -r fddf099a82f8 -r 64ec1884d860 hws/hw07.tex --- a/hws/hw07.tex Sat Dec 02 21:37:04 2023 +0000 +++ b/hws/hw07.tex Wed Feb 21 09:14:12 2024 +0000 @@ -193,7 +193,7 @@ (iv) same as (ii) $E\cdot + \cdot E \cdot + \cdot E$ } -\item Suppose the string $``9-5+2''$. Give all ASTs that +\item Suppose the string $``9-5+2''$. Give all parse trees that the following two grammars generate for this string. Grammar 1, where List is the starting symbol: diff -r fddf099a82f8 -r 64ec1884d860 progs/catastrophic/catastrophic9.java --- a/progs/catastrophic/catastrophic9.java Sat Dec 02 21:37:04 2023 +0000 +++ b/progs/catastrophic/catastrophic9.java Wed Feb 21 09:14:12 2024 +0000 @@ -27,7 +27,7 @@ Pattern pattern = Pattern.compile("(a*)*b"); // Run from 0 to 50000 characters - for (int length = 0; length < 50000; length += 5000) { + for (int length = 0; length < 65000; length += 5000) { // Build input of specified length String input = ""; diff -r fddf099a82f8 -r 64ec1884d860 progs/fun/fun_llvm.sc --- a/progs/fun/fun_llvm.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/progs/fun/fun_llvm.sc Wed Feb 21 09:14:12 2024 +0000 @@ -267,7 +267,7 @@ } } - +print("%d\n", i) val prelude = """ @.str = private constant [4 x i8] c"%d\0A\00" @@ -352,16 +352,25 @@ else factC(n - 1, x => ret(x * n)) } -factC(6, x => x) -factC(6, x => {println(s"The final Result is $x") ; 0}) -factC(6, _ + 1) + -def fibC(n: Int, ret: Int => Int) : Int = { - if (n == 0 || n == 1) ret(1) - else fibC(n - 1, x => fibC(n - 2, y => ret(x + y))) -} + fibC(10, x => {println(s"Result: $x") ; 1}) */ +factC(6, x => x) +factC(6, x => {println(s"The final Result is $x") ; 0}) +factC(6, _ + 1) + +def fib(n: Int) : Int = { + if (n == 0 || n == 1) 1 + else fib(n - 1) + fib(n - 2) +} + + +def fibC(n: Int, ret: Int => Int) : Int = { + if (n == 0 || n == 1) ret(1) + else fibC(n - 1, x => fibC(n - 2, y => ret(x + y))) +} \ No newline at end of file diff -r fddf099a82f8 -r 64ec1884d860 progs/lexer/lex.sc --- a/progs/lexer/lex.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/progs/lexer/lex.sc Wed Feb 21 09:14:12 2024 +0000 @@ -35,8 +35,8 @@ case c::Nil => CHAR(c) case c::s => SEQ(CHAR(c), charlist2rexp(s)) } -implicit def string2rexp(s : String) : Rexp = - charlist2rexp(s.toList) + +given Conversion[String, Rexp] = (s => charlist2rexp(s.toList)) val HELLO : Rexp = "hello" @@ -181,7 +181,7 @@ // Two Simple While Tests //======================== -@arg(doc = "small tests") +//@arg(doc = "small tests") @main def small() = { diff -r fddf099a82f8 -r 64ec1884d860 progs/parser-combinators/comb1.sc --- a/progs/parser-combinators/comb1.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/progs/parser-combinators/comb1.sc Wed Feb 21 09:14:12 2024 +0000 @@ -266,3 +266,14 @@ println(E2.parse("((((((1))))))")) println(E2.parse("(((((((1)))))))")) println(E2.parse("((((((((1))))))))")) + + + + + +/* +Try + +6 / 2 * (2+1) + +*/ diff -r fddf099a82f8 -r 64ec1884d860 slides/slides10.pdf Binary file slides/slides10.pdf has changed diff -r fddf099a82f8 -r 64ec1884d860 slides/slides10.tex --- a/slides/slides10.tex Sat Dec 02 21:37:04 2023 +0000 +++ b/slides/slides10.tex Wed Feb 21 09:14:12 2024 +0000 @@ -912,6 +912,35 @@ \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Big Thank You!} +\large + +\only<1>{% +\begin{itemize} +\item<-1> It is always fun to learn new things in CFL +\item<-1> I want to add Higher-Order Functions and Algebraic Datatypes + to Fun +\end{itemize}} + +\only<2->{% +\begin{itemize} +\item<2-> Thanks for ALL the EoY feedback:\medskip\bigskip + +\begin{minipage}{13cm} +\begin{quote}\it +``If all modules were as good as this one I would start recommending KCL over basically every single university instead of suggesting people look somewhere else.'' +\end{quote} +\end{minipage} +\end{itemize}} + +\hfill\includegraphics[scale=0.12]{thanks.png} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + \end{document} %%% Local Variables: diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw3/lexer.sc --- a/solutions/cw3/lexer.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/solutions/cw3/lexer.sc Wed Feb 21 09:14:12 2024 +0000 @@ -233,7 +233,7 @@ } def escape(tks: List[(String, String)]) = - tks.map{ case (s1, s2) => (s1, esc(s2))} + tks.map{ case (s1, s2) => (esc(s1), esc(s2))} // Tokens @@ -257,5 +257,11 @@ } // Tokenise -def tokenise(s: String) : List[Token] = - lexing_simp(WHILE_REGS, s).collect(token) +def tokenise(s: String) = //: List[Token] = + escape(lexing_simp(WHILE_REGS, s)).filter{p => p._1 != "\"w\""}//.collect(token) + + + + +println(tokenise(os.read(os.pwd / "primes.while"))) + diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw3/parser.sc --- a/solutions/cw3/parser.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/solutions/cw3/parser.sc Wed Feb 21 09:14:12 2024 +0000 @@ -244,6 +244,13 @@ def eval(bl: Block) : Env = eval_bl(bl, Map()) + +//println(tokenise(os.read(os.pwd / "primes.while"))) + +//println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "primes.while"))).head)) + + + @main def run(file: String) = { val contents = os.read(os.pwd / file) @@ -267,7 +274,7 @@ /* println("Loops eval") val start = System.nanoTime() -println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "loops.while"))).head)) +println(eval(Stmts.parse_all(tokenise(os.read(os.pwd / "primes.while"))).head)) val end = System.nanoTime() println("Time taken in seconds: ") println((end - start)/(1.0e9)) diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw4/compiler.sc --- a/solutions/cw4/compiler.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/solutions/cw4/compiler.sc Wed Feb 21 09:14:12 2024 +0000 @@ -119,6 +119,8 @@ case "!=" => "if_icmpeq" case "<" => "if_icmpge" case ">" => "if_icmple" + case "<=" => "if_icmpgt" + case "=>" => "if_icmplt" } def compile_bexp(b: BExp, env : Env, jmp: String) : String = b match { @@ -233,6 +235,8 @@ println(s"done.") } +//compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "pr.while"))).head, "pr") + // ---- Q1 // Fibonacci @@ -250,7 +254,7 @@ write "Result"; write minus2""" -compile_all(Stmts.parse_all(tokenise(fibonacciProgram)).head, "fib") +//compile_all(Stmts.parse_all(tokenise(fibonacciProgram)).head, "fib") val factorialProgram = """write "Factorial"; read n; @@ -265,7 +269,7 @@ write fact """ -compile_all(Stmts.parse_all(tokenise(factorialProgram)).head, "factorial") +//compile_all(Stmts.parse_all(tokenise(factorialProgram)).head, "factorial") // ---- Q3 @@ -279,9 +283,13 @@ //compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "collatz2.while"))).head, "collatz2") -println(tokenise(os.read(os.pwd / "forloop.while"))) -compile_all(Stmts.parse_all(tokenise(os.read(os.pwd / "forloop.while"))).head, "forloop") +//println(tokenise(os.read(os.pwd / "forloop.while"))) +//compile_all(Stmts.parse_all(tokenise(os.read(os.pwd / "forloop.while"))).head, "forloop") + +//compile_all(Stmts.parse_all(tokenise(os.read(os.pwd / "primes.while"))).head, "primes") + +//compile_run(Stmts.parse_all(tokenise(os.read(os.pwd / "pr.while"))).head, "pr") // for automated testing @@ -292,11 +300,40 @@ } @main -def test(file: String) = { +def run(file: String) = { val contents = os.read(os.pwd / file) - val class_name = file.stripSuffix(".") - compile_all(Stmts.parse_all(tokenise(os.read(os.pwd / file))).head, class_name) - tokenise(contents) + val class_name = file.stripSuffix(".while") + val tks = tokenise(os.read(os.pwd / file)) + //println(tks) + //println(Stmts.parse(tks)) + compile_run(Stmts.parse_all(tks).head, class_name) + //tokenise(contents) + //println(Stmts.parse_all(tokenise(os.read(os.pwd / file))).head) } +//println("TEST") +//println(tokenise(os.read(os.pwd / "pr.while"))) +//println(Stmts.parse_all(tokenise(os.read(os.pwd / "pr.while"))).head) + + + + +/* For with scopes + +case For(x,a,b,bl) => { + val loop_begin = Fresh("Loop_begin") + val loop_end = Fresh("Loop_end") + + val ind = env.getOrElse(x, -1) + val new_ind = Fresh_index() + val (assign,env1) = (compile_aexp(a, env) ++ i"istore $new_ind \t\t; ${x}-new", env + (x -> new_ind)) + + val bool = l"$loop_begin" ++ compile_aexp(Var(x), env1) ++ compile_aexp(b, env1) ++ i"if_icmpgt $loop_end" + val (block, env2) = compile_block(bl,env1,loop_end) + val inc = compile_stmt(Assign(x,Aop("+", Var(x), Num(1))),env2, "")._1 ++ i"goto $loop_begin" ++ l"$loop_end" + (assign ++ bool ++ block ++ inc, if (ind != -1){env2 + (x -> ind)} else {env2 - x}) + } + + +*/ diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw4/lexer.sc --- a/solutions/cw4/lexer.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/solutions/cw4/lexer.sc Wed Feb 21 09:14:12 2024 +0000 @@ -251,4 +251,4 @@ def tokenise(s: String) : List[Token] = lexing_simp(WHILE_REGS, s).collect(token) - +//println(tokenise(os.read(os.pwd / "pr.while"))) diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw4/parser.sc --- a/solutions/cw4/parser.sc Sat Dec 02 21:37:04 2023 +0000 +++ b/solutions/cw4/parser.sc Wed Feb 21 09:14:12 2024 +0000 @@ -152,6 +152,8 @@ (AExp ~ T_OP("!=") ~ AExp).map{ case x ~ _ ~ z => Bop("!=", x, z): BExp } || (AExp ~ T_OP("<") ~ AExp).map{ case x ~ _ ~ z => Bop("<", x, z): BExp } || (AExp ~ T_OP(">") ~ AExp).map{ case x ~ _ ~ z => Bop(">", x, z): BExp } || + (AExp ~ T_OP("<=") ~ AExp).map{ case x ~ _ ~ z => Bop("<=", x, z): BExp } || + (AExp ~ T_OP("=>") ~ AExp).map{ case x ~ _ ~ z => Bop("=>", x, z): BExp } || (T_PAREN("(") ~ BExp ~ T_PAREN(")") ~ T_OP("&&") ~ BExp).map{ case _ ~ y ~ _ ~ _ ~ v => And(y, v): BExp } || (T_PAREN("(") ~ BExp ~ T_PAREN(")") ~ T_OP("||") ~ BExp).map{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v): BExp } || (T_KEYWORD("true").map(_ => True: BExp )) || diff -r fddf099a82f8 -r 64ec1884d860 solutions/cw4/pascal.while --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/solutions/cw4/pascal.while Wed Feb 21 09:14:12 2024 +0000 @@ -0,0 +1,35 @@ +rows := 13; +coef := 1; + +i := 0; +while (i < rows) do { + + space := 1; + + while (space <= rows - i) do { + write(" "); + space := space + 1 + }; + + j := 0; + while (j <= i) do { + + if ((j == 0) || i == 0) then { + coef := 1 + } else { + coef := (coef * ((i - j) + 1)) / j + }; + + if (coef < 10) then write(" ") else + if (coef < 100) then write(" ") else + if (coef < 1000) then write(" ") + else skip; + + write(coef); + j := j + 1 + }; + + + write("\n"); + i := i + 1 +}