afl-material: comparison solutions/cw5/fun

equal deleted inserted replaced

-:b40aaffe0793
+:2f86ebda3629
-// A parser for the Fun language
+// Author: Zhuo Ying Jiang Li
-//================================
+// Starting code by Dr Christian Urban
+// parser: convert sequence of tokens to AST
 //
-// call with
+// Use this command to print parsed AST:
+// amm fun_parser.sc <name>.fun
 //
-//     amm fun_parser.sc fact.fun
-//
+import $file.fun_tokens, fun_tokens._
-//     amm fun_parser.sc defs.fun
-//
+// more convenience for the map parsers later on;
-// this will generate a parse-tree from a list
+// it allows writing nested patterns as
-// of tokens
+// case x ~ y ~ z => ...
+case class ~[+A, +B](x: A, y: B)
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
+// constraint for the input
+type IsSeq[A] = A => Seq[_]
-import $file.fun_tokens, fun_tokens._
+abstract class Parser[I : IsSeq, T]{
+def parse(in: I): Set[(T, I)]
-// Parser combinators
-//    type parameter I needs to be of Seq-type
+def parse_all(in: I) : Set[T] =
-//
+for ((hd, tl) <- parse(in);
-abstract class Parser[I, T](implicit ev: I => Seq[_]) {
+if tl.isEmpty) yield hd
-def parse(ts: I): Set[(T, I)]
+}
-def parse_single(ts: I) : T =
+// parser combinators
-parse(ts).partition(_._2.isEmpty) match {
-case (good, _) if !good.isEmpty => good.head._1
+// sequence parser
-case (good, err) if err.isEmpty => {
+class SeqParser[I : IsSeq, T, S](p: => Parser[I, T],
-println (s"Parse Error\n $good \n $err") ; sys.exit(-1) }
+q: => Parser[I, S]) extends Parser[I, ~[T, S]] {
-case (_, err) => {
+def parse(in: I) =
-	println (s"Parse Error\n${err.minBy(_._2.length)}") ; sys.exit(-1) }
+for ((hd1, tl1) <- p.parse(in);
+(hd2, tl2) <- q.parse(tl1)) yield (new ~(hd1, hd2), tl2)
+}
+// 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)
+}
+// 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)
+}
+// more convenient syntax for parser combinators
+implicit def ParserOps[I : IsSeq, T](p: Parser[I, T]) = new {
+def ||(q : => Parser[I, T]) = new AltParser[I, T](p, q)
+def ~[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)
+}
+// -------------------------------------------------
+// atomic parsers
+// atomic parser for types
+case class TypeParser(ty: Set[String]) extends Parser[Tokens, String] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "type" && ty.contains(tk._2) => Set((tk._2, tkns))
+case _ => Set()
+}
+}
+// atomic parser for global ids
+case object GlobalIdParser extends Parser[Tokens, String] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "global" => Set((tk._2, tkns))
+case _ => Set()
+}
+}
+// atomic parser for ids
+case object IdParser extends Parser[Tokens, String] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "id" => Set((tk._2, tkns))
+case _ => Set()
+}
+}
+// atomic parser for doubles (I use Float because that's what is used in the AST structures given in CW5)
+case object DoubleParser extends Parser[Tokens, Float] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "double" => Set((tk._2.toFloat, tkns))
+case _ => Set()
+}
+}
+// atomic parser for integers
+case object IntParser extends Parser[Tokens, Int] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "int" => Set((tk._2.toInt, tkns))
+case _ => Set()
+}
+}
+// atomic parser for operators
+case class OpParser(ops: Set[String]) extends Parser[Tokens, String] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "op" && ops.contains(tk._2) => Set((tk._2, tkns))
+case _ => Set()
+}
+}
+// atomic parser for character
+case object CharParser extends Parser[Tokens, Char] {
+def parse(tokens: Tokens) = tokens match {
+case Nil => Set()
+case tk::tkns if tk._1 == "ch" => {
+val stripped = tk._2.slice(1, tk._2.length-1)  // strip off single quotes
+stripped match {
+case "\\n" => Set(('\n', tkns))
+case "\\t" => Set(('\t', tkns))
+case "\\r" => Set(('\r', tkns))
+case c => Set((c(0), tkns))
+}
 }
-}
+case _ => Set()
+}
-// convenience for writing grammar rules
+}
-case class ~[+A, +B](_1: A, _2: B)
+// parser for list of arguments
-class SeqParser[I, T, S](p: => Parser[I, T],
-q: => Parser[I, S])(implicit ev: I => Seq[_]) extends Parser[I, ~[T, S]] {
-def parse(sb: I) =
-for ((head1, tail1) <- p.parse(sb);
-(head2, tail2) <- q.parse(tail1)) yield (new ~(head1, head2), tail2)
-}
-class AltParser[I, T](p: => Parser[I, T],
-q: => Parser[I, T])(implicit ev: I => Seq[_]) extends Parser[I, T] {
-def parse(sb: I) = p.parse(sb) ++ q.parse(sb)
-}
-class FunParser[I, T, S](p: => Parser[I, T],
-f: T => S)(implicit ev: I => Seq[_]) extends Parser[I, S] {
-def parse(sb: I) =
-for ((head, tail) <- p.parse(sb)) yield (f(head), tail)
-}
-// convenient combinators
-implicit def ParserOps[I, T](p: Parser[I, T])(implicit ev: I => Seq[_]) = new {
-def || (q : => Parser[I, T]) = new AltParser[I, T](p, q)
-def ==>[S] (f: => T => S) = new FunParser[I, T, S](p, f)
-def ~[S] (q : => Parser[I, S]) = new SeqParser[I, T, S](p, q)
-}
 def ListParser[I, T, S](p: => Parser[I, T],
 q: => Parser[I, S])(implicit ev: I => Seq[_]): Parser[I, List[T]] = {
-(p ==> ((s) => List(s))) ||
+(p ~ q ~ ListParser(p, q)).map{ case x ~ _ ~ z => x :: z : List[T] } ||
-(p ~ q ~ ListParser(p, q)) ==> { case x ~ _ ~ z => x :: z : List[T] }
+(p.map((s) => List(s)))
 }
-case class TokParser(tok: Token) extends Parser[List[Token], Token] {
+// I may want to write string interpolations for:
-def parse(ts: List[Token]) = ts match {
+// keywords, semicolon, colon, comma, parentheses
-case t::ts if (t == tok) => Set((t, ts))
+case class StrParser(s: String) extends Parser[Tokens, String] {
-case _ => Set()
+def parse(tokens: Tokens) = tokens match {
-}
+case Nil => Set()
-}
+case tk::tkns if tk._2 == s => Set((s, tkns))
+case _ => Set()
-implicit def token2tparser(t: Token) = TokParser(t)
+}
+}
-implicit def TokOps(t: Token) = new {
-def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q)
+implicit def parser_interpolation(sc: StringContext) = new {
-def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f)
+def p(args: Any*) = StrParser(sc.s(args:_*))
-def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q)
+}
-}
-case object EmptyParser extends Parser[List[Token], String] {
+// the AST datastructures for the FUN language
-def parse(ts: List[Token]) = Set(("", ts))
-}
+abstract class Exp
+abstract class BExp
-case object NumParser extends Parser[List[Token], Int] {
+abstract class Decl
-def parse(ts: List[Token]) = ts match {
-case T_NUM(n)::ts => Set((n, ts))
-case _ => Set ()
-}
-}
-case object FNumParser extends Parser[List[Token], Double] {
-def parse(ts: List[Token]) = ts match {
-case T_FNUM(x)::ts => Set((x, ts))
-case _ => Set()
-}
-}
-case object IdParser extends Parser[List[Token], String] {
-def parse(ts: List[Token]) = ts match {
-case T_ID(s)::ts => Set((s, ts))
-case _ => Set ()
-}
-}
-case object CharConstParser extends Parser[List[Token], Int] {
-def parse(ts: List[Token]) = ts match {
-case T_CHR(c)::ts => Set((c, ts))
-case _ => Set ()
-}
-}
-case object TyParser extends Parser[List[Token], String] {
-def parse(ts: List[Token]) = ts match {
-case T_TY(s)::ts => Set((s, ts))
-case _ => Set ()
-}
-}
-// Abstract syntax trees for the Fun language
-abstract class Exp
-abstract class BExp
-abstract class Decl
 case class Def(name: String, args: List[(String, String)], ty: String, body: Exp) extends Decl
 case class Main(e: Exp) extends Decl
 case class Const(name: String, v: Int) extends Decl
-case class FConst(name: String, x: Double) extends Decl
+case class FConst(name: String, x: Float) extends Decl
 case class Call(name: String, args: List[Exp]) extends Exp
 case class If(a: BExp, e1: Exp, e2: Exp) extends Exp
 case class Var(s: String) extends Exp
-case class Num(i: Int) extends Exp     // integer numbers
+case class Num(i: Int) extends Exp  // integer numbers
-case class FNum(i: Double) extends Exp  // floating numbers
+case class FNum(i: Float) extends Exp  // float numbers
-case class ChConst(c: Int) extends Exp // char constant
+case class ChConst(c: Int) extends Exp  // character constants
 case class Aop(o: String, a1: Exp, a2: Exp) extends Exp
-case class Sequence(e1: Exp, e2: Exp) extends Exp
+case class Sequence(e1: Exp, e2: Exp) extends Exp  // expressions separated by semicolons
 case class Bop(o: String, a1: Exp, a2: Exp) extends BExp
-// arithmetic expressions (there needs to be an F in the SEMICOLON case)
+lazy val Exps: Parser[Tokens, Exp] =
-lazy val Exp: Parser[List[Token], Exp] =
+(Exp ~ p";" ~ Exps).map[Exp]{ case x ~ _ ~ z => Sequence(x, z) } ||
-(T_KWD("if") ~ BExp ~ T_KWD("then") ~ Exp ~ T_KWD("else") ~ Exp) ==>
+Exp
-{ case _ ~ x ~ _ ~ y ~ _ ~ z => If(x, y, z): Exp } ||
-(F ~ T_SEMI ~ Exp) ==> { case x ~ _ ~ y => Sequence(x, y): Exp } || L
+lazy val Exp: Parser[Tokens, Exp] =
-lazy val L: Parser[List[Token], Exp] =
+(p"if" ~ BExp ~ p"then" ~ Exp ~ p"else" ~ Exp).map[Exp]{ case _ ~ x ~ _ ~ y ~ _ ~ z => If(x, y, z) } ||
-(T ~ T_OP("+") ~ Exp) ==> { case x ~ _ ~ z => Aop("+", x, z): Exp } ||
+M
-(T ~ T_OP("-") ~ Exp) ==> { case x ~ _ ~ z => Aop("-", x, z): Exp } || T
-lazy val T: Parser[List[Token], Exp] =
+lazy val M: Parser[Tokens, Exp] =
-(F ~ T_OP("*") ~ T) ==> { case x ~ _ ~ z => Aop("*", x, z): Exp } ||
+(T ~ OpParser(Set("+", "-")) ~ M).map[Exp]{ case x ~ y ~ z => Aop(y, x, z) } ||
-(F ~ T_OP("/") ~ T) ==> { case x ~ _ ~ z => Aop("/", x, z): Exp } ||
+T
-(F ~ T_OP("%") ~ T) ==> { case x ~ _ ~ z => Aop("%", x, z): Exp } || F
-lazy val F: Parser[List[Token], Exp] =
+lazy val T: Parser[Tokens, Exp] =
-(IdParser ~ T_LPAREN ~ T_RPAREN) ==> { case x ~ _ ~ _ => Call(x, Nil): Exp } ||
+(U ~ OpParser(Set("*", "/", "%")) ~ T).map[Exp]{ case x ~ y ~ z => Aop(y, x, z) } ||
-(IdParser ~ T_LPAREN ~ ListParser(Exp, T_COMMA) ~ T_RPAREN) ==> { case x ~ _ ~ z ~ _ => Call(x, z): Exp } ||
+U
-(T_LPAREN ~ Exp ~ T_RPAREN) ==> { case _ ~ y ~ _ => y: Exp } ||
-IdParser ==> { case x => Var(x): Exp } ||
+// includes negative factor
-NumParser ==> { case x => Num(x): Exp } ||
+// a + - b CAN be recognised
-CharConstParser ==> { case x => ChConst(x): Exp } ||
+// - - - b CAN be recognised
-FNumParser ==> { case x => FNum(x): Exp }
+lazy val U: Parser[Tokens, Exp] =
+(OpParser(Set("-")) ~ U).map[Exp]{ case _ ~ y => Aop("*", Num(-1), y) } ||
-// boolean expressions
+(OpParser(Set("+")) ~ U).map[Exp]{ case _ ~ y => y } ||
-lazy val BExp: Parser[List[Token], BExp] =
+F
-(Exp ~ T_OP("==") ~ Exp) ==> { case x ~ _ ~ z => Bop("==", x, z): BExp } ||
-(Exp ~ T_OP("!=") ~ Exp) ==> { case x ~ _ ~ z => Bop("!=", x, z): BExp } ||
+lazy val F: Parser[Tokens, Exp] =
-(Exp ~ T_OP("<") ~ Exp)  ==> { case x ~ _ ~ z => Bop("<",  x, z): BExp } ||
+(p"(" ~ Exp ~ p")").map[Exp]{ case _ ~ y ~ _ => y } ||
-(Exp ~ T_OP(">") ~ Exp)  ==> { case x ~ _ ~ z => Bop("<",  z, x): BExp } ||
+(p"skip").map(_ => Call("skip", Nil)) ||  // hardcoded
-(Exp ~ T_OP("<=") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", x, z): BExp } ||
+(p"skip" ~ p"(" ~ p")").map(_ => Call("skip", Nil)) ||  // hardcoded
-(Exp ~ T_OP("=>") ~ Exp) ==> { case x ~ _ ~ z => Bop("<=", z, x): BExp } ||
+(IdParser ~ p"(" ~ ListParser(Exp, p",") ~ p")").map[Exp]{ case id ~ _ ~ args ~ _ => Call(id, args) } ||
-(T_LPAREN ~ BExp ~ T_RPAREN) ==> { case _ ~ b ~ _ => b : BExp }
+(IdParser ~ p"(" ~ p")").map[Exp]{ case id ~ _ ~ _ => Call(id, Nil) } ||  // NOTE: empty args are also accepted!
+(IdParser || GlobalIdParser).map(x => Var(x)) ||
-lazy val Arg : Parser[List[Token], (String, String)] =
+IntParser.map(x => Num(x)) ||
-(IdParser ~ T_COLON ~ TyParser) ==> { case x ~ _ ~ ty => (x, ty) }
+DoubleParser.map(x => FNum(x)) ||
+CharParser.map(x => ChConst(x.toInt)) ||
-lazy val Defn: Parser[List[Token], Decl] = {
+(p"{" ~ Exps ~ p"}").map[Exp]{ case _ ~ x ~ _ => x }
-(T_KWD("def") ~ IdParser ~ T_LPAREN ~ T_RPAREN ~ T_COLON ~ TyParser ~ T_OP("=") ~ Exp) ==>
-{ case _ ~ y ~ _ ~ _ ~ _~ ty ~ _ ~ r => Def(y, Nil, ty, r): Decl } ||
+lazy val BExp: Parser[Tokens, BExp] =
-(T_KWD("def") ~ IdParser ~ T_LPAREN ~ ListParser(Arg, T_COMMA) ~ T_RPAREN ~ T_COLON ~ TyParser ~ T_OP("=") ~ Exp) ==>
+(Exp ~ OpParser(Set("==", "!=", "<", ">", "<=", ">=")) ~ Exp).map[BExp]{ case x ~ y ~ z => Bop(y, x, z) } ||
-{ case _ ~ y ~ _ ~ w ~ _ ~ _~ ty ~ _ ~ r => Def(y, w, ty, r): Decl }
+(p"(" ~ BExp ~ p")").map[BExp]{ case _ ~ y ~ _ => y }
-}
+lazy val TypedIdParser: Parser[Tokens, (String, String)] =
-lazy val Const_decl: Parser[List[Token], Decl] =
+(IdParser ~ p":" ~ TypeParser(Set("Int", "Double"))).map{ case n ~ _ ~ t => (n, t) }
-(T_KWD("val") ~ Arg ~ T_OP("=") ~ NumParser) ==>
-{ case _ ~ x ~ _ ~ v => Const(x._1, v): Decl } ||
+lazy val Defn: Parser[Tokens, Decl] =
-(T_KWD("val") ~ Arg ~ T_OP("=") ~ FNumParser) ==>
+(p"def" ~ IdParser ~ p"(" ~ ListParser(TypedIdParser, p",") ~ p")" ~ p":" ~ TypeParser(Set("Int", "Double", "Void")) ~ OpParser(Set("=")) ~ Exp).map[Decl]{
-{ case _ ~ x ~ _ ~ v => FConst(x._1, v): Decl }
+case _ ~ y ~ _ ~ w ~ _ ~ _ ~ t ~ _ ~ b => Def(y, w, t, b)
+} ||
-lazy val Prog: Parser[List[Token], List[Decl]] =
+(p"def" ~ IdParser ~ p"(" ~ p")" ~ p":" ~ TypeParser(Set("Int", "Double", "Void")) ~ OpParser(Set("=")) ~ Exp).map[Decl]{
-(Defn ~ T_SEMI ~ Prog) ==> { case x ~ _ ~ z => x :: z : List[Decl] } ||
+case _ ~ y ~ _ ~ _ ~ _ ~ t ~ _ ~ b => Def(y, Nil, t, b)
-(Const_decl ~ T_SEMI ~ Prog) ==> { case x ~ _ ~ z => x :: z : List[Decl] } ||
+}
-(Exp ==> ((s) => List(Main(s)) : List[Decl]))
+lazy val Constp: Parser[Tokens, Decl] =
+(p"val" ~ GlobalIdParser ~ p":" ~ TypeParser(Set("Int")) ~ OpParser(Set("=")) ~ IntParser).map[Decl]{  // IntParser? Not Exp? For this AST, impossible to define Exp
+case _ ~ id ~ _ ~ _ ~ _ ~ n => Const(id, n)
-// Reading tokens and Writing parse trees
+} ||
+(p"val" ~ GlobalIdParser ~ p":" ~ TypeParser(Set("Int")) ~ OpParser(Set("=")) ~ OpParser(Set("-")) ~ IntParser).map[Decl]{  // IntParser? Not Exp? For this AST, impossible to define Exp
-//import ammonite.ops._
+case _ ~ id ~ _ ~ _ ~ _ ~ _ ~ n => Const(id, -n)
+}
-def parse_tks(tks: List[Token]) : List[Decl] = {
-//println(Prog.parse(tks))
+// Int can be converted to Double but not viceversa
-Prog.parse_single(tks)
+lazy val FConstp: Parser[Tokens, Decl] =
-}
+(p"val" ~ GlobalIdParser ~ p":" ~ TypeParser(Set("Double")) ~ OpParser(Set("=")) ~ (DoubleParser || IntParser.map[Float](i => i.toFloat))).map[Decl]{
+case _ ~ id ~ _ ~ _ ~ _ ~ n => FConst(id, n)
-//@doc("Parses a file.")
+} ||
+(p"val" ~ GlobalIdParser ~ p":" ~ TypeParser(Set("Double")) ~ OpParser(Set("=")) ~ OpParser(Set("-")) ~ (DoubleParser || IntParser.map[Float](i => i.toFloat))).map[Decl]{
+case _ ~ id ~ _ ~ _ ~ _ ~ _ ~ n => FConst(id, -n)
+}
+// Prog consists of global const declarations, f(x) defs, and exp in ANY order
+// restricted to main body at the bottom
+lazy val Prog: Parser[Tokens, List[Decl]] =
+(Defn ~ p";" ~ Prog).map[List[Decl]]{ case x ~ _ ~ z => x :: z } ||
+(Constp ~ p";" ~ Prog).map[List[Decl]]{ case x ~ _ ~ z => x :: z } ||
+(FConstp ~ p";" ~ Prog).map[List[Decl]]{ case x ~ _ ~ z => x :: z } ||
+Exp.map[List[Decl]](s => List(Main(s)))
+def parse_tks(tokens: Tokens) = Prog.parse_all(tokens)
+import scala.io.Source._
 @main
-def main(fname: String) : Unit = {
+def parse(filename: String) = {
-val tks = tokenise(os.read(os.pwd / fname))
+val fun_code = fromFile(filename).getLines.mkString("\n")
-println(parse_tks(tks))
+// print the AST list to screen
-}
+println(parse_tks(tokenise(fun_code)))
+}

changeset 903	2f86ebda3629
parent 894	02ef5c3abc51
child 920	7af2eea19646