--- 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