--- 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
Binary file hws/hw01.pdf has changed
Binary file hws/hw02.pdf has changed
Binary file hws/hw03.pdf has changed
Binary file hws/hw04.pdf has changed
Binary file hws/hw05.pdf has changed
Binary file hws/hw06.pdf has changed
Binary file hws/hw07.pdf has changed
--- 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
Binary file hws/hw08.pdf has changed
--- 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}
Binary file hws/hw09.pdf has changed
--- 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
}
--- 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"))
--- 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"))
--- 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`
Binary file slides/slides03.pdf has changed
Binary file slides/slides08.pdf has changed
--- 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)