# HG changeset patch # User Christian Urban # Date 1701171751 0 # Node ID ae9782e62bdd4e73284368a47cc025bd7af6342a # Parent 47acfd7f90964120a5503ca3a94137b3a46ec0f9 updated diff -r 47acfd7f9096 -r ae9782e62bdd cws/cw03.tex --- a/cws/cw03.tex Fri Nov 17 20:06:43 2023 +0000 +++ b/cws/cw03.tex Tue Nov 28 11:42:31 2023 +0000 @@ -12,7 +12,8 @@ \noindent This coursework is worth 10\% and is due on \cwTHREE{} at 16:00. You are asked to implement a parser for the WHILE language and -also an interpreter. You can do the implementation in any programming +also an interpreter. The parser needs to use parser combinators. +You can do the implementation in any programming language you like, but you need to submit the source code with which you answered the questions, otherwise a mark of 0\% will be awarded. You should use the lexer from the previous coursework for the diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw06.pdf Binary file hws/hw06.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw07.pdf Binary file hws/hw07.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw07.tex --- a/hws/hw07.tex Fri Nov 17 20:06:43 2023 +0000 +++ b/hws/hw07.tex Tue Nov 28 11:42:31 2023 +0000 @@ -1,6 +1,7 @@ \documentclass{article} \usepackage{../style} \usepackage{../grammar} +\usepackage{../graphics} \begin{document} @@ -24,6 +25,14 @@ What can you say about the number of as and bs in the strings recognised by this grammar. +\solution{ + S -> bSAA -> bbSAAAA -> + bbbSAAAAAA -> + bbbAAAAAA -> + bbAbAAAAA -> .. -> + bbAAAAAAb -> .. -> AAAbAAAbb -> .. -> aaabaaabb + } + \item Consider the following grammar @@ -46,6 +55,69 @@ \texttt{The trainer trains the student team} \end{center} +\solution{ +\begin{center} + \begin{tikzpicture}[scale=0.7,line width=0.8mm] + \draw (-2,0) -- (4,0); + \draw (-2,1) -- (4,1); + \draw (-2,2) -- (3,2); + \draw (-2,3) -- (2,3); + \draw (-2,4) -- (1,4); + \draw (-2,5) -- (0,5); + \draw (-2,6) -- (-1,6); + + \draw (0,0) -- (0, 5); + \draw (1,0) -- (1, 4); + \draw (2,0) -- (2, 3); + \draw (3,0) -- (3, 2); + \draw (4,0) -- (4, 1); + \draw (-1,0) -- (-1, 6); + \draw (-2,0) -- (-2, 6); + + \draw (-1.5,-0.5) node {\footnotesize{}\texttt{The}}; + \draw (-0.5,-1.0) node {\footnotesize{}\texttt{trainer}}; + \draw ( 0.5,-0.5) node {\footnotesize{}\texttt{trains}}; + \draw ( 1.5,-1.0) node {\footnotesize{}\texttt{the}}; + \draw ( 2.5,-0.5) node {\footnotesize{}\texttt{student}}; + \draw ( 3.5,-1.0) node {\footnotesize{}\texttt{team}}; + + \draw (-1.5,0.5) node {$A$}; + \draw (-0.5,0.5) node {$N$}; + \draw ( 0.5,0.5) node {$N,\!V$}; + \draw ( 1.5,0.5) node {$A$}; + \draw ( 2.5,0.5) node {$N$}; + \draw ( 3.5,0.5) node {$N,\!V$}; + + \draw (-1.5,1.5) node {$N$}; + \draw (-0.5,1.5) node {$N$}; + \draw ( 0.5,1.5) node {$$}; + \draw ( 1.5,1.5) node {$N$}; + \draw ( 2.5,1.5) node {$N$}; + + \draw (-1.5,2.5) node {$N$}; + \draw (-0.5,2.5) node {$ $}; + \draw ( 0.5,2.5) node {$N,\!P$}; + \draw ( 1.5,2.5) node {$N$}; + + \draw (-1.5,3.5) node {$$}; + \draw (-0.5,3.5) node {$N,\!S$}; + \draw ( 0.5,3.5) node {$N,\!P$}; + + \draw (-1.5,4.5) node {$N,\!S$}; + \draw (-0.5,4.5) node {$N,\!S$}; + + \draw (-1.5,5.5) node {$N,\!S$}; + + \draw (-2.4, 5.5) node {$1$}; + \draw (-2.4, 4.5) node {$2$}; + \draw (-2.4, 3.5) node {$3$}; + \draw (-2.4, 2.5) node {$4$}; + \draw (-2.4, 1.5) node {$5$}; + \draw (-2.4, 0.5) node {$6$}; + \end{tikzpicture} + \end{center} + } + \item Transform the grammar \begin{center} @@ -58,6 +130,31 @@ \noindent into Chomsky normal form. +\solution{ + First one has to eliminate $\epsilon$. This means we obtain the rules: + + \begin{center} + \begin{tabular}{lcl} + $A$ & $::=$ & $0A1 \;|\; 01 \;|\; BB \;|\; B$\\ + $B$ & $::=$ & $2 \;|\; 2B$ + \end{tabular} + \end{center} + + Now we have to bring the rules into CNF form by adding additional + non-terminals, like $Z$, $O$, $T$, and splitting up the rules into ``twos'': + + \begin{center} + \begin{tabular}{lcl} + $A$ & $::=$ & $ZC \;|\; ZO \;|\; BB \;|\; 2$\\ + $B$ & $::=$ & $2 \;|\; TB$\\ + $C$ & $::=$ & $AO$\\ + $Z$ & $::=$ & $0$\\ + $O$ & $::=$ & $1$\\ + $T$ & $::=$ & $2$\\ + \end{tabular} + \end{center} +} + \item Consider the following grammar $G$ \begin{center} @@ -89,6 +186,12 @@ \end{tabular} \end{center} +\solution{ + (i) this is ambiguous -> it's an instance of the dangling else; + (ii) rules of the form $B ::= B \cdot B$ are always ambiguous $B \cdot B\cdot B$ + (iii) this is fine + (iv) same as (ii) $E\cdot + \cdot E \cdot + \cdot E$ + } \item Suppose the string $``9-5+2''$. Give all ASTs that the following two grammars generate for this string. @@ -111,6 +214,12 @@ \end{tabular} \end{center} +\solution{ + The point is that Grammar 1 is un-ambiguous, while the second is ambiguous. + Grammar 1 parses the strings as (9 - 5) + 2. Grammar 2 is ambiguous and + there are two possibilities (9 - 5) + 2 and 9 - (5 + 2). + +} %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, @@ -129,3 +238,21 @@ %%% mode: latex %%% TeX-master: t %%% End: + + +The| trainer trains the student A {N,S} => N +The trainer |trains the student N {N, P} => N S +The trainer trains |the student N N => N +The trainer trains the |student + +trainer |trains the student team N o {N, P} => N, S +trainer trains| the student team N o N => N +trainer trains the |student team +trainer trains the student |team {N, P} o {N, V} => N + + +The| trainer trains the student team A o (N,S) => N +The trainer| trains the student team N o (N,P) => N, S +The trainer trains| the student team N o N => N +The trainer trains the| student team +The trainer trains the student| team (N,S) o (N,V) => N diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw08.pdf Binary file hws/hw08.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw08.tex --- a/hws/hw08.tex Fri Nov 17 20:06:43 2023 +0000 +++ b/hws/hw08.tex Tue Nov 28 11:42:31 2023 +0000 @@ -11,20 +11,63 @@ \begin{enumerate} \item Write a program in the WHILE-language that calculates - the factorial function. + the factorial function. + +\begin{lstlisting} +write "factorial: "; +read n; +minus1 := 1; +while n > 0 do { +minus1 := minus1 * n; +n := n - 1 +}; +write "Result: "; +write minus1 ; +write "\n" +\end{lstlisting} \item What optimisations could a compiler perform when - compiling a WHILE-program? + compiling a WHILE-program? + + \solution{ + \begin{itemize} + \item peephole optimisations (more specific instructions) + \item common sub-expression elimination %, for example + +%\begin{lstlisting} +%x := 3 + a +%y := 3 + a +%\end{lstlisting} + + %can be optimised to + + %\begin{lstlisting}[numbers=none,language={}] + % z := 3 + a + % x := z + % y := z + %\end{lstlisting} + + \item constant folding / constant propagation (that is calculate the result of 3 + 4 already during + compilation) + \item tail-recursion optimisation cannot be applied to the WHILE language + because there are no recursive functions + \end{itemize} + } \item What is the main difference between the Java assembler (as processed by Jasmin) and Java Byte Code? + \solution{ The main difference is that the j-files have symbols + for places where to jump, while class files have this resolved + to concrete addresses (or relative jumps). That is what the + assembler has to generate. } + \item Remember symbolic labels in the Jasmin-assembler are meant to be used for jumps (like in loops or if-conditions). Assume you generated a Jasmin-file with some redundant labels, that is some labels are not used in your code for any jumps. For example \texttt{L\_begin} and \texttt{L\_end} are not used - in the fol,lowing code-snippet: + in the following code-snippet: \begin{lstlisting}[language=JVMIS,numbers=none] L_begin: @@ -42,7 +85,7 @@ Do these redundant labels affect the size of the generated JVM-code? (Hint: What are the labels translated to by - the Jasmin-assembler?). + the Jasmin-assembler?). \solution{The answer is no. The reason is that assemblers calculate for labels either relative or explicit adresses, @@ -67,10 +110,21 @@ Do they cause stack-overflows when compiled to the JVM (for example by Scala)? +\solution{ +Scala cannot generate jumps in between different methods (to which functions are compiled to). So cannot eliminate the tail-calls. Haskell for example can do this because it compiles the code in a big ``blob'' inside a main-method (similar to the WHILE language). +} + \item Explain what is meant by the terms lazy evaluation and eager evaluation. + \solution{ Lazy evaluation only evaluates expressions when they are + needed and if they are needed twice, the results will be + re-used. Eager evaluation immediately evaluates expressions, for + example if they are arguments to function calls or allocated to + variables.} + + \item \POSTSCRIPT \end{enumerate} diff -r 47acfd7f9096 -r ae9782e62bdd hws/hw09.pdf Binary file hws/hw09.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd progs/fun/funt.sc --- a/progs/fun/funt.sc Fri Nov 17 20:06:43 2023 +0000 +++ b/progs/fun/funt.sc Tue Nov 28 11:42:31 2023 +0000 @@ -5,13 +5,13 @@ // // call with // -// amm fun.sc main defs.fun -// amm fun.sc main fact.fun +// amm funt.sc main defs.fun +// amm funt.sc main fact.fun // // or // -// amm fun.sc run defs.fun -// amm fun.sc run fact.fun +// amm funt.sc run defs.fun +// amm funt.sc run fact.fun // // the first prints out the JVM instructions // the second runs the generated class files @@ -66,13 +66,10 @@ // convenient string interpolations // for instructions, labels and methods -import scala.language.implicitConversions -import scala.language.reflectiveCalls - -implicit def sring_inters(sc: StringContext) = new { - def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" - def l(args: Any*): String = sc.s(args:_*) ++ ":\n" - def m(args: Any*): String = sc.s(args:_*) ++ "\n" +extension (sc: StringContext) { + def i(args: Any*): String = " " ++ sc.s(args:_*) ++ "\n" // instructions + def l(args: Any*): String = sc.s(args:_*) ++ ":\n" // labels + def m(args: Any*): String = sc.s(args:_*) ++ "\n" // methods } diff -r 47acfd7f9096 -r ae9782e62bdd progs/parser-combinators/comb1.sc --- a/progs/parser-combinators/comb1.sc Fri Nov 17 20:06:43 2023 +0000 +++ b/progs/parser-combinators/comb1.sc Tue Nov 28 11:42:31 2023 +0000 @@ -149,9 +149,6 @@ // A parser for arithmetic expressions (Terms and Factors) -"1 + 2 * 3" -"(1 + 2) * 3" -{ lazy val E: Parser[String, Int] = { (T ~ p"+" ~ E).map{ case ((x, _), z) => x + z } || (T ~ p"-" ~ E).map{ case ((x, _), z) => x - z } || T } @@ -159,7 +156,8 @@ (F ~ p"*" ~ T).map{ case ((x, _), z) => x * z } || F } lazy val F: Parser[String, Int] = { (p"(" ~ E ~ p")").map{ case ((_, y), _) => y } || NumParserInt } -} + +println(E.parse_all("2*2*2")) println(E.parse_all("1+3+4")) println(E.parse("1+3+4")) println(E.parse_all("4*2+3")) diff -r 47acfd7f9096 -r ae9782e62bdd progs/parser-combinators/comb2.sc --- a/progs/parser-combinators/comb2.sc Fri Nov 17 20:06:43 2023 +0000 +++ b/progs/parser-combinators/comb2.sc Tue Nov 28 11:42:31 2023 +0000 @@ -168,6 +168,7 @@ // Examples +println(AExp.parse_all("2*2*2")) println(BExp.parse_all("5+3")) println(Stmt.parse_all("5==3")) println(Stmt.parse_all("x2:=5+3")) diff -r 47acfd7f9096 -r ae9782e62bdd progs/while-arrays/compile_bfc.sc --- a/progs/while-arrays/compile_bfc.sc Fri Nov 17 20:06:43 2023 +0000 +++ b/progs/while-arrays/compile_bfc.sc Tue Nov 28 11:42:31 2023 +0000 @@ -22,8 +22,6 @@ // fastparse used in this file is not yet supported // under ammonite. - -//> using toolkit latest //> using file compile_arrays2.sc import compile_arrays2._ @@ -120,8 +118,8 @@ def Fa[$ : P]: P[AExp] = P( "(" ~ AExp ~ ")" | P (Ident ~ "[" ~ AExp ~ "]").map{Ref(_, _)} - | P(Number).map{Num} - | P(Ident).map{Var} ) + | P(Number).map{Num(_)} + | P(Ident).map{Var(_)} ) // boolean expressions def BExp[$ : P]: P[BExp] = @@ -141,7 +139,7 @@ | P("if" ~ BExp ~ "then" ~ Block ~ "else" ~ Block).map{If(_, _, _)} | P("while" ~ BExp ~ "do" ~ Block).map{While(_, _)} | P("new(" ~ Ident ~ "[" ~ Number ~ "])").map{ArrayDef(_, _)} - | P("write(" ~ Ident ~ ")").map{Write} ) + | P("write(" ~ Ident ~ ")").map{Write(_)} ) def Stmts[$ : P]: P[Block] = P( P(Stmt ~ ";" ~ Stmts).map{ case (x, z) => x :: z } @@ -192,7 +190,6 @@ case '+' => "mem[ptr] := mem[ptr] + 1;" case '-' => "mem[ptr] := mem[ptr] - 1;" case '.' => "x := mem[ptr]; write x;" - //case ',' => "XXX" // "ptr = getchar();\n" case '[' => "while (mem[ptr] != 0) do {" case ']' => "skip};" case _ => "" @@ -322,8 +319,8 @@ //@main def all() = { bfc0(); bfc1(); bfc2(); bfc3(); bfc4() } -all() - +//all() +bfc4() @@ -341,4 +338,4 @@ //import compile_arrays2._ // // load fastparse -//import $ivy.`com.lihaoyi::fastparse:3.0.2` \ No newline at end of file +//import $ivy.`com.lihaoyi::fastparse:3.0.2` diff -r 47acfd7f9096 -r ae9782e62bdd slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd slides/slides08.pdf Binary file slides/slides08.pdf has changed diff -r 47acfd7f9096 -r ae9782e62bdd slides/slides08.tex --- a/slides/slides08.tex Fri Nov 17 20:06:43 2023 +0000 +++ b/slides/slides08.tex Tue Nov 28 11:42:31 2023 +0000 @@ -67,7 +67,93 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t,fragile] -%%\frametitle{CW2} +\mbox{}\\[-20mm]\mbox{} + +\footnotesize +\begin{textblock}{13}(-0.5,0.2) +\begin{lstlisting}[language=JVMIS2,numbers=none] +.method public static main([Ljava/lang/String;)V + .limit locals 200 + .limit stack 200 + invokestatic foo/foo/read()I + istore 0 + ldc 1 + istore 1 +Loop_begin_4: + iload 0 + ldc 0 + if_icmple Loop_end_5 + iload 0 + iload 1 + imul + istore 1 + iload 0 + ldc 1 + isub + istore 0 + goto Loop_begin_4 +\end{lstlisting} +\end{textblock} + +\begin{textblock}{13}(7,8) +\begin{lstlisting}[language=JVMIS2,numbers=none] +Loop_end_5: + iload 1 + invokestatic foo/foo/write(I)V + return +.end method +\end{lstlisting} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t,fragile] +\mbox{}\\[-20mm]\mbox{} + +\footnotesize +\begin{textblock}{13}(-0.5,0.2) +\begin{lstlisting}[language=JVMIS2,numbers=none] +.method public static main([Ljava/lang/String;)V + .limit locals 200 + .limit stack 200 + invokestatic foo/foo/read()I + istore 0 ; n + ldc 1 + istore 1 ; res +Loop_begin_4: + iload 0 ; n + ldc 0 + if_icmple Loop_end_5 + iload 0 ; n + iload 1 ; res + imul + istore 1 ; res + iload 0 ; n + ldc 1 + isub + istore 0 ; n + goto Loop_begin_4 +\end{lstlisting} +\end{textblock} + +\begin{textblock}{13}(7,8) +\begin{lstlisting}[language=JVMIS2,numbers=none] +Loop_end_5: + iload 1 ; res + invokestatic foo/foo/write(I)V + return +.end method +\end{lstlisting} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t,fragile] \small \begin{textblock}{13}(-0.5,1)