import scala.language.implicitConversions    

import scala.language.reflectiveCalls 

import scala.util._

import scala.annotation.tailrec

import scala.sys.process._

abstract class Rexp 

case object NULL extends Rexp

case object EMPTY extends Rexp

case class CHAR(c: Char) extends Rexp

case class ALT(r1: Rexp, r2: Rexp) extends Rexp 

case class RANGE(cs: List[Char]) extends Rexp 

case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 

case class PLUS(r: Rexp) extends Rexp 

case class STAR(r: Rexp) extends Rexp 

case class NTIMES(r: Rexp, n: Int) extends Rexp 

case class NUPTOM(r: Rexp, n: Int, m: Int) extends Rexp

object RANGE {

  def apply(s: String) : RANGE = RANGE(s.toList)

}

def NMTIMES(r: Rexp, n: Int, m: Int) = {

  if(m < n) throw new IllegalArgumentException("the number m cannot be smaller than n.")

  else NUPTOM(r, n, m - n)

}

case class NOT(r: Rexp) extends Rexp 

case class OPT(r: Rexp) extends Rexp 

// some convenience for typing in regular expressions

def charlist2rexp(s : List[Char]) : Rexp = s match {

  case Nil => EMPTY

  case c::Nil => CHAR(c)

  case c::s => SEQ(CHAR(c), charlist2rexp(s))

}

implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)

implicit def RexpOps (r: Rexp) = new {

  def | (s: Rexp) = ALT(r, s)

  def % = STAR(r)

  def ~ (s: Rexp) = SEQ(r, s)

}

implicit def stringOps (s: String) = new {

  def | (r: Rexp) = ALT(s, r)

  def | (r: String) = ALT(s, r)

  def % = STAR(s)

  def ~ (r: Rexp) = SEQ(s, r)

  def ~ (r: String) = SEQ(s, r)

}

// nullable function: tests whether the regular 

// expression can recognise the empty string

def nullable (r: Rexp) : Boolean = r match {

  case NULL => false

  case EMPTY => true

  case CHAR(_) => false

  case ALT(r1, r2) => nullable(r1) || nullable(r2)

  case SEQ(r1, r2) => nullable(r1) && nullable(r2)

  case STAR(_) => true

  case PLUS(r) => nullable(r)

  case NTIMES(r, i) => if (i == 0) true else nullable(r)

  case NUPTOM(r, i, j) => if (i == 0) true else nullable(r)

  case RANGE(_) => false

  case NOT(r) => !(nullable(r))

  case OPT(_) => true

}

// derivative of a regular expression w.r.t. a character

def der (c: Char, r: Rexp) : Rexp = r match {

  case NULL => NULL

  case EMPTY => NULL

  case CHAR(d) => if (c == d) EMPTY else NULL

  case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))

  case SEQ(r1, r2) => 

    if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))

    else SEQ(der(c, r1), r2)

  case STAR(r) => SEQ(der(c, r), STAR(r))

  case PLUS(r) => SEQ(der(c, r), STAR(r))

  case NTIMES(r, i) => 

    if (i == 0) NULL else der(c, SEQ(r, NTIMES(r, i - 1)))

  case NUPTOM(r, i, j) =>

    if (i == 0 && j == 0) NULL else 

    if (i == 0) ALT(der(c, NTIMES(r, j)), der(c, NUPTOM(r, 0, j - 1)))

    else der(c, SEQ(r, NUPTOM(r, i - 1, j)))

  case RANGE(cs) => if (cs contains c) EMPTY else NULL

  case NOT(r) => NOT(der (c, r))

  case OPT(r) => der(c, r)

}

def zeroable (r: Rexp) : Boolean = r match {

  case NULL => true

  case EMPTY => false

  case CHAR(_) => false

  case ALT(r1, r2) => zeroable(r1) && zeroable(r2)

  case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)

  case STAR(_) => false

  case PLUS(r) => zeroable(r)

  case NTIMES(r, i) => if (i == 0) false else zeroable(r)

  case NUPTOM(r, i, j) => if (i == 0) false else zeroable(r)

  case RANGE(_) => false

  case NOT(r) => !(zeroable(r))     // bug: incorrect definition for NOT

  case OPT(_) => false

}

// derivative w.r.t. a string (iterates der)

def ders (s: List[Char], r: Rexp) : Rexp = s match {

  case Nil => r

  case c::s => ders(s, der(c, r))

}

// regular expressions for the While language

val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_")

val DIGIT = RANGE("0123456789")

val ID = SYM ~ (SYM | DIGIT).% 

val NUM = PLUS(DIGIT)

val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false"

val SEMI: Rexp = ";"

val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "%" | "/"

val WHITESPACE = PLUS(" " | "\n" | "\t")

val RPAREN: Rexp = ")"

val LPAREN: Rexp = "("

val BEGIN: Rexp = "{"

val END: Rexp = "}"

val ALL = SYM | DIGIT | OP | " " | ":" | ";" | "\"" | "(" | ")" | "{" | "}" 

val ALL2 = ALL | "\n"

val COMMENT2 = ("/*" ~ NOT(ALL.% ~ "*/" ~ ALL.%) ~ "*/")

val COMMENT = ("/*" ~ ALL2.% ~ "*/") | ("//" ~ ALL.% ~ "\n")

val STRING = "\"" ~ ALL.% ~ "\""

// token for While languag

abstract class Token

case object T_WHITESPACE extends Token

case object T_SEMI extends Token

case object T_LPAREN extends Token

case object T_RPAREN extends Token

case object T_BEGIN extends Token

case object T_END extends Token

case object T_COMMENT extends Token

case class T_ID(s: String) extends Token

case class T_OP(s: String) extends Token

case class T_NUM(s: String) extends Token

case class T_KWD(s: String) extends Token

case class T_STRING(s: String) extends Token

case class T_ERR(s: String) extends Token // special error token

type TokenFun = String => Token

type LexRules = List[(Rexp, TokenFun)]

val While_lexing_rules: LexRules = 

  List((KEYWORD, (s) => T_KWD(s)),

       (ID, (s) => T_ID(s)),

       (COMMENT, (s) => T_COMMENT),

       (OP, (s) => T_OP(s)),

       (NUM, (s) => T_NUM(s)),

       (SEMI, (s) => T_SEMI),

       (LPAREN, (s) => T_LPAREN),

       (RPAREN, (s) => T_RPAREN),

       (BEGIN, (s) => T_BEGIN),

       (END, (s) => T_END),

       (STRING, (s) => T_STRING(s.drop(1).dropRight(1))),

       (WHITESPACE, (s) => T_WHITESPACE))

// calculates derivatives until all of them are zeroable

@tailrec

def munch(s: List[Char], 

          pos: Int, 

          rs: LexRules, 

          last: Option[(Int, TokenFun)]): Option[(Int, TokenFun)] = {

  rs match {

  case Nil => last

  case rs if (s.length <= pos) => last

  case rs => {

    val ders = rs.map({case (r, tf) => (der(s(pos), r), tf)})

    val rs_nzero = ders.filterNot({case (r, _) => zeroable(r)})

    val rs_nulls = ders.filter({case (r, _) => nullable(r)})

    val new_last = if (rs_nulls != Nil) Some((pos, rs_nulls.head._2)) else last

    munch(s, 1 + pos, rs_nzero, new_last)

  }

}}

// iterates the munching function and returns a Token list

def tokenize(s: String, rs: LexRules) : List[Token] = munch(s.toList, 0, rs, None) match {

  case None if (s == "") => Nil

  case None => List(T_ERR(s"Lexing error: $s"))

  case Some((n, tf)) => {

    val (head, tail) = s.splitAt(n + 1)

    tf(head)::tokenize(tail, rs)

  }

}

def tokenizer(s:String) : List[Token] = 

  tokenize(s, While_lexing_rules).filter {

    case T_ERR(s) => { println(s); sys.exit(-1) }

    case T_WHITESPACE => false

    case T_COMMENT => false

    case _ => true

  } 

def fromFile(name: String) : String = 

  io.Source.fromFile(name).mkString

// tokenizer tests

//println(tokenizer(fromFile("loops.while")).mkString("\n"))

//println(tokenizer(fromFile("fib.while")).mkString("\n"))

//println(tokenizer(fromFile("collatz.while")).mkString("\n"))

// Parser - Abstract syntax trees

abstract class Stmt

abstract class AExp

abstract class BExp 

type Block = List[Stmt]

case object Skip extends Stmt

case class If(a: BExp, bl1: Block, bl2: Block) extends Stmt

case class While(b: BExp, bl: Block) extends Stmt

case class Assign(s: String, a: AExp) extends Stmt

case class Read(s: String) extends Stmt

case class Write(s: String) extends Stmt

case class WriteS(s: String) extends Stmt

case class Var(s: String) extends AExp

case class Num(i: Int) extends AExp

case class Aop(o: String, a1: AExp, a2: AExp) extends AExp

case object True extends BExp

case object False extends BExp

case class Bop(o: String, a1: AExp, a2: AExp) extends BExp

// Parser combinators

abstract class Parser[I <% Seq[_], T] {

  def parse(ts: I): Set[(T, I)]

  def parse_all(ts: I) : Set[T] =

    for ((head, tail) <- parse(ts); if (tail.isEmpty)) yield head

  def parse_single(ts: I) : T = parse_all(ts).toList match {

    case List(t) => t

    case _ => { println ("Parse Error") ; sys.exit(-1) }

  }

}

class SeqParser[I <% Seq[_], T, S](p: => Parser[I, T], q: => Parser[I, S]) extends Parser[I, (T, S)] {

  def parse(sb: I) = 

    for ((head1, tail1) <- p.parse(sb); 

         (head2, tail2) <- q.parse(tail1)) yield ((head1, head2), tail2)

}

class AltParser[I <% Seq[_], T](p: => Parser[I, T], q: => Parser[I, T]) extends Parser[I, T] {

  def parse(sb: I) = p.parse(sb) ++ q.parse(sb)   

}

class FunParser[I <% Seq[_], T, S](p: => Parser[I, T], f: T => S) extends Parser[I, S] {

  def parse(sb: I) = 

    for ((head, tail) <- p.parse(sb)) yield (f(head), tail)

}

case class TokParser(tok: Token) extends Parser[List[Token], Token] {

  def parse(ts: List[Token]) = ts match {

    case t::ts if (t == tok) => Set((t, ts)) 

    case _ => Set ()

  }

}

implicit def token2tparser(t: Token) = TokParser(t)

case object NumParser extends Parser[List[Token], Int] {

  def parse(ts: List[Token]) = ts match {

    case T_NUM(s)::ts => Set((s.toInt, 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 StringParser extends Parser[List[Token], String] {

  def parse(ts: List[Token]) = ts match {

    case T_STRING(s)::ts => Set((s, ts)) 

    case _ => Set ()

  }

}

implicit def ParserOps[I<% Seq[_], T](p: Parser[I, T]) = 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)

}

implicit def TokOps(t: Token) = new {

  def || (q : => Parser[List[Token], Token]) = new AltParser[List[Token], Token](t, q)

  def ==>[S] (f: => Token => S) = new FunParser[List[Token], Token, S](t, f)

  def ~[S](q : => Parser[List[Token], S]) = new SeqParser[List[Token], Token, S](t, q)

}

// arithmetic expressions

lazy val AExp: Parser[List[Token], AExp] = 

  (T ~ T_OP("+") ~ AExp) ==> { case ((x, y), z) => Aop("+", x, z): AExp } ||

  (T ~ T_OP("-") ~ AExp) ==> { case ((x, y), z) => Aop("-", x, z): AExp } || T  

lazy val T: Parser[List[Token], AExp] = 

  (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => Aop("*", x, z): AExp } || 

  (F ~ T_OP("/") ~ T) ==> { case ((x, y), z) => Aop("/", x, z): AExp } || 

  (F ~ T_OP("%") ~ T) ==> { case ((x, y), z) => Aop("%", x, z): AExp } || F

lazy val F: Parser[List[Token], AExp] = 

  (T_LPAREN ~ AExp ~ T_RPAREN) ==> { case ((x, y), z) => y: AExp }|| 

  IdParser ==> { case x => Var(x): AExp } || 

  NumParser ==> { case x => Num(x): AExp }

// boolean expressions

lazy val BExp: Parser[List[Token], BExp] = 

  (AExp ~ T_OP("==") ~ AExp) ==> { case ((x, y), z) => Bop("==", x, z): BExp } || 

  (AExp ~ T_OP("!=") ~ AExp) ==> { case ((x, y), z) => Bop("!=", x, z): BExp } || 

  (AExp ~ T_OP("<") ~ AExp) ==> { case ((x, y), z) => Bop("<", x, z): BExp } || 

  (AExp ~ T_OP(">") ~ AExp) ==> { case ((x, y), z) => Bop("<", z, x): BExp } || 

  (T_KWD("true") ==> ((_) => True)) || 

  (T_KWD("false") ==> ((_) => False: BExp))

lazy val Stmt: Parser[List[Token], Stmt] =

  (T_KWD("skip") ==> ((_) => Skip: Stmt)) ||

  (IdParser ~ T_OP(":=") ~ AExp) ==> { case ((x, y), z) => Assign(x, z): Stmt } ||

  (T_KWD("if") ~ BExp ~ T_KWD("then") ~ Block ~ T_KWD("else") ~ Block) ==>

    { case (((((x,y),z),u),v),w) => If(y, u, w): Stmt } ||

  (T_KWD("while") ~ BExp ~ T_KWD("do") ~ Block) ==> { case (((x, y), z), w) => While(y, w) } ||

  (T_KWD("read") ~ IdParser) ==> { case (x, y) => Read(y) } ||

  (T_KWD("write") ~ IdParser) ==> { case (x, y) => Write(y) } ||

  (T_KWD("write") ~ StringParser) ==> { case (x, y) => WriteS(y) }

lazy val Stmts: Parser[List[Token], Block] =

  (Stmt ~ T_SEMI ~ Stmts) ==> { case ((x, y), z) => x :: z : Block } ||

  (Stmt ==> ((s) => List(s) : Block))

lazy val Block: Parser[List[Token], Block] =

  (T_BEGIN ~ Stmts ~ T_END) ==> { case ((x, y), z) => y : Block } || 

  (Stmt ==> ((s) => List(s)))

// parser examples

val p1 = "x := 5"

val p1_toks = tokenizer(p1) 

val p1_ast = Block.parse_all(p1_toks)

//println(p1_toks)

//println(p1_ast)

val p2 = "{ x := 5; y := 8}"

val p2_toks = tokenizer(p2) 

val p2_ast = Block.parse_all(p2_toks)

//println(p2_ast)

val p3 = "5 == 6"

val p3_toks = tokenizer(p3) 

val p3_ast = BExp.parse_all(p3_toks)

//println(p3_ast)

val p4 = "true"

val p4_toks = tokenizer(p4) 

val p4_ast = BExp.parse_all(p4_toks)

//println(p4_ast)

val p5 = "if true then skip else skip"

val p5_toks = tokenizer(p5) 

val p5_ast = Stmt.parse_all(p5_toks)

//println(p5_ast)

val p6 = "if true then x := 5 else x := 10"

val p6_toks = tokenizer(p6) 

val p6_ast = Stmt.parse_all(p6_toks)

//println(p6_ast)

val p7 = "if false then x := 5 else x := 10"

val p7_toks = tokenizer(p7) 

val p7_ast = Stmt.parse_all(p7_toks)

//println(p7_ast)

val p8 = "write x; write \"foo\"; read x "

val p8_toks = tokenizer(p8) 

val p8_ast = Stmts.parse_all(p8_toks)

//println(p8_ast)

// multiplication

val p9 = """  x := 5;

              y := 4;

              r := 0;

              while y > 0 do {

                 r := r + x;

                 y := y - 1

              } 

         """

val p9_toks = tokenizer(p9) 

val p9_ast = Stmts.parse_all(p9_toks)

//println(p9_ast)

// fibonacci numbers

val p10 = """

 write "Fib: ";

 read n;

 minus1 := 0;

 minus2 := 1;

 temp := 0;

 while n > 0 do  {

   temp := minus2;

   minus2 := minus1 + minus2;

   minus1 := temp;

   n := n - 1

 };

 write "Result:";

 write minus2