--- a/progs/parser-combinators/comb2.sc Fri Oct 18 05:59:04 2024 +0100
+++ b/progs/parser-combinators/comb2.sc Fri Oct 25 18:54:08 2024 +0100
@@ -9,48 +9,40 @@
//
// amm comb2.sc
+
// more convenience for the map parsers later on;
// it allows writing nested patterns as
// case x ~ y ~ z => ...
-
-case class o[+A, +B](x: A, y: B)
-
-
-type IsSeq[I] = I => Seq[?]
+case class ~[+A, +B](x: A, y: B)
-abstract class Parser[I, T](using is: I => Seq[?]) {
- def parse(in: I): Set[(T, I)]
-
- def parse_all(in: I) : Set[T] =
- for ((hd, tl) <- parse(in);
- if is(tl).isEmpty) yield hd
-}
// parser combinators
+abstract class Parser[I, T] { p =>
+ def parse(in: I): Set[(T, I)]
-// alternative parser
-class AltParser[I : IsSeq, T](p: => Parser[I, T],
- q: => Parser[I, T]) extends Parser[I, T] {
- def parse(in: I) = p.parse(in) ++ q.parse(in)
-}
+ def parse_all(in: I)(using toSeq: I => Seq[?]) : Set[T] =
+ for ((hd, tl) <- parse(in);
+ if toSeq(tl).isEmpty) yield hd
+
+ // alternative parser
+ def ||(q: => Parser[I, T]) = new Parser[I, T] {
+ def parse(in: I) = p.parse(in) ++ q.parse(in)
+ }
-// sequence parser
-class SeqParser[I : IsSeq, T, S](p: => Parser[I, T],
- q: => Parser[I, S]) extends Parser[I, o[T, S]] {
- def parse(in: I) =
- for ((hd1, tl1) <- p.parse(in);
- (hd2, tl2) <- q.parse(tl1)) yield (new o(hd1, hd2), tl2)
-}
+ // sequence parser
+ def ~[S](q: => Parser[I, S]) = new Parser[I, T ~ S] {
+ def parse(in: I) =
+ for ((hd1, tl1) <- p.parse(in);
+ (hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2)
+ }
-// map parser
-class MapParser[I : IsSeq, T, S](p: => Parser[I, T],
- f: T => S) extends Parser[I, S] {
- def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)
+ // map parser
+ def map[S](f: => T => S) = new Parser[I, S] {
+ def parse(in: I) = for ((hd, tl) <- p.parse(in)) yield (f(hd), tl)
+ }
}
-
-
// atomic parser for (particular) strings
case class StrParser(s: String) extends Parser[String, String] {
def parse(sb: String) = {
@@ -68,7 +60,6 @@
}
}
-
// atomic parser for numbers (transformed into Ints)
case object NumParser extends Parser[String, Int] {
val reg = "[0-9]+".r
@@ -89,15 +80,6 @@
extension (sc: StringContext)
def p(args: Any*) = StrParser(sc.s(args*))
-
-// more convenient syntax for parser combinators
-extension [I : IsSeq, T](p: Parser[I, T]) {
- def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)
- def o[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
- def map[S](f: => T => S) = new MapParser[I, T, S](p, f)
-}
-
-
// the abstract syntax trees for the WHILE language
abstract class Stmt
abstract class AExp
@@ -124,47 +106,44 @@
// arithmetic expressions
lazy val AExp: Parser[String, AExp] =
- (Te o p"+" o AExp).map[AExp]{ case x o _ o z => Aop("+", x, z): AExp } ||
- (Te o p"-" o AExp).map[AExp]{ case x o _ o z => Aop("-", x, z) } || Te
+ (Te ~ p"+" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("+", x, z) } ||
+ (Te ~ p"-" ~ AExp).map[AExp]{ case x ~ _ ~ z => Aop("-", x, z) } || Te
lazy val Te: Parser[String, AExp] =
- (Fa o p"*" o Te).map[AExp]{ case x o _ o z => Aop("*", x, z) } ||
- (Fa o p"/" o Te).map[AExp]{ case x o _ o z => Aop("/", x, z) } || Fa
+ (Fa ~ p"*" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("*", x, z) } ||
+ (Fa ~ p"/" ~ Te).map[AExp]{ case x ~ _ ~ z => Aop("/", x, z) } || Fa
lazy val Fa: Parser[String, AExp] =
- (p"(" o AExp o p")").map{ case _ o y o _ => y } ||
+ (p"(" ~ AExp ~ p")").map{ case _ ~ y ~ _ => y } ||
IdParser.map(Var(_)) ||
NumParser.map(Num(_))
// boolean expressions with some simple nesting
lazy val BExp: Parser[String, BExp] =
- (AExp ~ p"==" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } ||
- (AExp ~ p"!=" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } ||
- (AExp ~ p"<" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } ||
- (AExp ~ p">" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } ||
- (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } ||
- (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } ||
- (p"true".map[BExp]{ _ => True }) ||
- (p"false".map[BExp]{ _ => False }) ||
- (p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ x ~ _ => x }
+ (AExp ~ p"==" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("==", x, z) } ||
+ (AExp ~ p"!=" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("!=", x, z) } ||
+ (AExp ~ p"<" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop("<", x, z) } ||
+ (AExp ~ p">" ~ AExp).map[BExp]{ case x ~ _ ~ z => Bop(">", x, z) } ||
+ (p"(" ~ BExp ~ p")" ~ p"&&" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => And(y, v) } ||
+ (p"(" ~ BExp ~ p")" ~ p"||" ~ BExp).map[BExp]{ case _ ~ y ~ _ ~ _ ~ v => Or(y, v) } ||
+ (p"true".map[BExp]{ _ => True }) ||
+ (p"false".map[BExp]{ _ => False }) ||
+ (p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ x ~ _ => x }
-// a single statement
+// Stmt: a single statement
+// Stmts: multiple statements
+// Block: blocks (enclosed in curly braces)
lazy val Stmt: Parser[String, Stmt] =
((p"skip".map[Stmt]{_ => Skip }) ||
- (IdParser ~ p":=" ~ AExp).map[Stmt]{ case x ~ _ ~ z => Assign(x, z) } ||
- (p"write(" ~ IdParser ~ p")").map[Stmt]{ case _ ~ y ~ _ => Write(y) } ||
- (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block)
- .map[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } ||
- (p"while" ~ BExp ~ p"do" ~ Block).map[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) })
-
-
-// statements
+ (IdParser ~ p":=" ~ AExp).map[Stmt]{ case x ~ _ ~ z => Assign(x, z) } ||
+ (p"write(" ~ IdParser ~ p")").map[Stmt]{ case _ ~ y ~ _ => Write(y) } ||
+ (p"if" ~ BExp ~ p"then" ~ Block ~ p"else" ~ Block)
+ .map[Stmt]{ case _ ~ y ~ _ ~ u ~ _ ~ w => If(y, u, w) } ||
+ (p"while" ~ BExp ~ p"do" ~ Block).map[Stmt]{ case _ ~ y ~ _ ~ w => While(y, w) })
lazy val Stmts: Parser[String, Block] =
(Stmt ~ p";" ~ Stmts).map[Block]{ case x ~ _ ~ z => x :: z } ||
(Stmt.map[Block]{ s => List(s) })
-
-// blocks (enclosed in curly braces)
lazy val Block: Parser[String, Block] =
((p"{" ~ Stmts ~ p"}").map{ case _ ~ y ~ _ => y } ||
- (Stmt.map(s => List(s))))
+ (Stmt.map(s => List(s))))
// Examples
@@ -194,40 +173,43 @@
// an interpreter for the WHILE language
type Env = Map[String, Int]
-def eval_aexp(a: AExp, env: Env) : Int = a match {
- case Num(i) => i
- case Var(s) => env(s)
- case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
- case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
- case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
- case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)
-}
+def eval_aexp(a: AExp, env: Env) : Int =
+ a match {
+ case Num(i) => i
+ case Var(s) => env(s)
+ case Aop("+", a1, a2) => eval_aexp(a1, env) + eval_aexp(a2, env)
+ case Aop("-", a1, a2) => eval_aexp(a1, env) - eval_aexp(a2, env)
+ case Aop("*", a1, a2) => eval_aexp(a1, env) * eval_aexp(a2, env)
+ case Aop("/", a1, a2) => eval_aexp(a1, env) / eval_aexp(a2, env)
+ }
-def eval_bexp(b: BExp, env: Env) : Boolean = b match {
- case True => true
- case False => false
- case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
- case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
- case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
- case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
- case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)
- case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)
-}
+def eval_bexp(b: BExp, env: Env) : Boolean =
+ b match {
+ case True => true
+ case False => false
+ case Bop("==", a1, a2) => eval_aexp(a1, env) == eval_aexp(a2, env)
+ case Bop("!=", a1, a2) => !(eval_aexp(a1, env) == eval_aexp(a2, env))
+ case Bop(">", a1, a2) => eval_aexp(a1, env) > eval_aexp(a2, env)
+ case Bop("<", a1, a2) => eval_aexp(a1, env) < eval_aexp(a2, env)
+ case And(b1, b2) => eval_bexp(b1, env) && eval_bexp(b2, env)
+ case Or(b1, b2) => eval_bexp(b1, env) || eval_bexp(b2, env)
+ }
-def eval_stmt(s: Stmt, env: Env) : Env = s match {
- case Skip => env
- case Assign(x, a) => env + (x -> eval_aexp(a, env))
- case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env)
- case While(b, bl) =>
- if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
- else env
- case Write(x) => { println(env(x)) ; env }
-}
-
-def eval_bl(bl: Block, env: Env) : Env = bl match {
- case Nil => env
- case s::bl => eval_bl(bl, eval_stmt(s, env))
-}
+def eval_stmt(s: Stmt, env: Env) : Env =
+ s match {
+ case Skip => env
+ case Assign(x, a) => env + (x -> eval_aexp(a, env))
+ case If(b, bl1, bl2) => if (eval_bexp(b, env)) eval_bl(bl1, env) else eval_bl(bl2, env)
+ case While(b, bl) =>
+ if (eval_bexp(b, env)) eval_stmt(While(b, bl), eval_bl(bl, env))
+ else env
+ case Write(x) => { println(env(x)) ; env }
+ }
+def eval_bl(bl: Block, env: Env) : Env =
+ bl match {
+ case Nil => env
+ case s::bl => eval_bl(bl, eval_stmt(s, env))
+ }
def eval(bl: Block) : Env = eval_bl(bl, Map())
@@ -236,7 +218,7 @@
println(eval(Stmts.parse_all(fib).head)("result"))
-// more examles
+// more examples
// calculate and print all factors bigger
// than 1 and smaller than n
--- a/slides/slides04.tex Fri Oct 18 05:59:04 2024 +0100
+++ b/slides/slides04.tex Fri Oct 25 18:54:08 2024 +0100
@@ -358,7 +358,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Sulzmann \& Lu Matcher}
+\frametitle{Sulzmann \& Lu Lexer}
We want to match the string \bl{$abc$} using \bl{$r_1$}:
@@ -1687,10 +1687,10 @@
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
- \includegraphics[scale=0.20]{s1.png} &
- \includegraphics[scale=0.20]{s2.png} \\
- \includegraphics[scale=0.20]{s3.png} &
- \includegraphics[scale=0.20]{s4.png} \\
+ \includegraphics[scale=0.18]{s1.png} &
+ \includegraphics[scale=0.18]{s2.png} \\
+ \includegraphics[scale=0.18]{s3.png} &
+ \includegraphics[scale=0.18]{s4.png} \\
\end{tabular}
\end{center}
\end{frame}
@@ -1698,10 +1698,10 @@
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
- \includegraphics[scale=0.20]{s5.png} &
- \includegraphics[scale=0.20]{s6.png} \\
- \includegraphics[scale=0.20]{s7.png} &
- \includegraphics[scale=0.20]{s8.png} \\
+ \includegraphics[scale=0.18]{s5.png} &
+ \includegraphics[scale=0.18]{s6.png} \\
+ \includegraphics[scale=0.18]{s7.png} &
+ \includegraphics[scale=0.18]{s8.png} \\
\end{tabular}
\end{center}
\end{frame}
@@ -1709,8 +1709,8 @@
\begin{frame}[c]
\begin{center}
\begin{tabular}{cc}
- \includegraphics[scale=0.20]{s9.png} &
- \includegraphics[scale=0.20]{s10.png}
+ \includegraphics[scale=0.18]{s9.png} &
+ \includegraphics[scale=0.18]{s10.png}
\end{tabular}
\end{center}
\end{frame}
@@ -1720,37 +1720,37 @@
\begin{frame}[c]
\small
\begin{itemize}
- \item[$\bullet$] Great lecturer. Looking forward to the next lecture!
-
- \item[$\bullet$] Would it be possible for you to post the answer of
- the homework to KEATS after sgts each week? It will be very
- helpful for us to prepare for the exam. Thank you.
-
- \item[$\bullet$] A lot of the parts of the LGT are going through
- what was covered in the videos. While this is helpful to refresh
- students' minds, I think it would be better if the Pollev
- questions were checked more regularly to focus on what students
- want support with
+ \item[$\bullet$] Thank you for your hand out. I took your advice and
+ finally read the ho4 before the lecture videos. It was very smooth
+ to read, but at times it was hard to understand. But knowing my
+ friendly lecturer would explain the concepts in the videos I
+ carried on. Although it was a bit painful, new information always
+ is, and a bit boring at times, it’s probably my bad attention
+ span. I finished it and found it quite fun, probably the most
+ approachable and fun technical handout I’ve read so far. Reading
+ it before the videos encouraged me to stay on it because I didn’t
+ assume I understood the content and the anticipation of the
+ unknown was fun.
\end{itemize}\bigskip
- $\Rightarrow$ Reluctant, but I am prepared for selected questions to
- make the answers public.
+\end{frame}
- $\Rightarrow$ The content viewing numbers are a bit worrying. Therefore
- the reflex on my side is to lecture the content again. I also receive
- quite a large number of basic questions about CW2.
-\end{frame}
\begin{frame}[c]
\small
\begin{minipage}{1.3\textwidth}
\begin{itemize}
\item[$\bullet$]
- Regarding module content, the content is not only interesting but relevant, up-to-date, and applicable to the real world. The practical, real-world application of the module is made abundantly clear through the coursework-focused delivery of the module. The content of the module progresses fast, but that is due to the nature of the content and the aims of the module. The learning aims and assessment are clearly explained.
+ things are going well initially, but in week3 i am really lost, each 30 mins video took me hours to understand, things are too abstract, wish there are more explanations
+
+ \item[$\bullet$]
+ The LGTs kind of just repeat the information from the lectures. I think they would be more beneficial if you could explain certain topics in more detail and go through more examples.
-Regarding teaching, Dr. Urban is incredibly helpful both inside (and even outside) contact hours. I can tell the lecturer is very passionate about teaching the module. TAs are on hand to help with all aspects of the module, with the lecturer having taken care to have dedicated TAs for resolving technical issues. Discussions both on the forum and in lessons are encouraged, and the module is structured so that high engagement with the content and live lessons will make it easier for students to do the module (which is, of course, a good thing).
+ \item[$\bullet$]
+ The room is somehow always either too warm or too cold.
-Only 3 weeks in I would very highly recommend the module. It is a difficult subject, but a pleasure to study at the same time.
+ \item[$\bullet$]
+ Module content is enjoyable and interesting. Even with difficult part of contents, Dr Urban provides clear explanations.
\end{itemize}
\end{minipage}
\end{frame}
@@ -1759,17 +1759,30 @@
\small
\begin{minipage}{1.2\textwidth}
\begin{itemize}
- \item[$\bullet$] Professor Christian is incredibly patient. He always stays longer after live session lectures to answer additional questions, even though he doesn't need to. He made me feel that no questions are stupid. Thanks so much!
-
- \item[$\bullet$] I am enjoying your module at the moment, I think you clearly explain every point and answer all questions during the live tutorial.
-
- \item[$\bullet$] It would be helpful to be given the full set of coursework templates on GitHub so that there is less ambiguity regarding future courseworks.
-
-\item[$\bullet$] Maybe some additional exercises in the LGT would be useful
-\item[$\bullet$] This module handout are the most useful thing I have ever seen in this uni.
-\item[$\bullet$] This module is structured very well and is very interesting. Thank you
+ \item[$\bullet$] The in person lectures could be a bit faster, I think more focus on questions would be useful rather than repeating the videos.
+
+ \item[$\bullet$]
+ The teacher explains the material very well and is able to answer most questions during the large group tutorials. I really like the teacher's enthusiasm; throwing in little jokes from time to time and referring to the history of compilers makes me more interested in the subject and inspires me to delve deeper into it. Since I am an MSc student, I did not take any previous Level 6 modules, which the teacher refers to quite often. However, the teacher provides enough basic knowledge, even if you haven't learned about these topics before. The module is conducted using a flipped-classroom system, so the 2-hour lecture every Friday is spent 'revising' the material that was provided in the videos. Personally, I like this approach as it helps reinforce important aspects of both current and previous lessons.
\end{itemize}
-$\Rightarrow$ In case of CW3 the starting files are comb1.sc and comb2.sc uploaded to KEATS. The CW3 \& 4 files are now on Github.
+\end{minipage}
+\end{frame}
+
+\begin{frame}[c]
+ \small
+ \begin{minipage}{1.2\textwidth}
+ \begin{itemize}
+ \item[$\bullet$]
+ Would appreciate some time in the LGTs to go over specific examples of questions from the slides.
+
+ \item[$\bullet$]
+ The recorded content is too long. Also, the Sgt room (Monday 2-3 with Harry) is really small compared to the students who show up.
+
+ \item[$\bullet$]
+ hopefully there will be solution or any tutorials / lectures for cw1
+
+ \item[$\bullet$]
+ Normally, I wouldn't have such an audacious request as this. However, the lecture hall we were assigned is absoluely terrible; this is mainly because indivduals at the back are so far away from the front that they think they can get away with talking loudly and being distracting. If that isn't possible, then can the wall sockets on the right side at least work.
+\end{itemize}
\end{minipage}
\end{frame}