import scala.language.implicitConversions
import scala.language.reflectiveCalls
import scala.util._
import scala.annotation.tailrec

sealed 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 SEQ(r1: Rexp, r2: Rexp) extends Rexp
case class STAR(r: Rexp) extends Rexp

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

def Range(s : List[Char]) : Rexp = s match {
  case Nil => NULL
  case c::Nil => CHAR(c)
  case c::s => ALT(CHAR(c), Range(s))
}
def RANGE(s: String) = Range(s.toList)

def PLUS(r: Rexp) = SEQ(r, STAR(r))

val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvwxyz_")
val DIGIT = RANGE("0123456789")
val ID = SYM ~ (SYM | DIGIT).% 
val NUM = PLUS(DIGIT)
val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" 
val SEMI: Rexp = ";"
val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"
val WHITESPACE = PLUS(RANGE(" \n"))
val RPAREN: Rexp = ")"
val LPAREN: Rexp = "("
val BEGIN: Rexp = "{"
val END: Rexp = "}"

//regular expressions ranked by position in the list
val regs: List[Rexp] = 
  List(KEYWORD, ID, OP, NUM, SEMI, LPAREN, RPAREN, BEGIN, END, WHITESPACE)

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
}

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
}

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

// returns the position of the last Some-element in the list
def last(stack: List[Option[Rexp]]) : Int = stack match {
  case Nil => 0
  case None::stack => last(stack)
  case Some(r)::stack => 1 + stack.length
}

// calculates derivatives until all of them are zeroable
@tailrec
def munch(cs: List[Char], rs: List[Rexp], stack: List[Option[Rexp]]) : Int = (cs, rs) match {
  case (_, Nil) => last(stack)
  case (Nil, _) => last(stack)
  case (c::cs, rs) => {
    val ds = rs.map(der(c, _))
    val rs_nzero = ds.filterNot(zeroable(_))
    val rs_nulls = ds.filter(nullable(_))
    val opt = Try(Some(rs_nulls.head)) getOrElse None
    munch(cs, rs_nzero, opt::stack)
  }
}

// iterates the munching function and prints 
// out the component strings
@tailrec
def tokenize(s: String, rs: List[Rexp]) : Unit = munch(s.toList, rs, Nil) match {
  case 0 if (s == "") => println("EOF")
  case 0 => println(s"Lexing error: $s")
  case n => {
    val (head, tail) = s.splitAt(n)
    print(s"|${head.replaceAll("\n","Ret")}|")
    tokenize(tail, rs)
  }
}

val test_prog = """
start := XXX;
x := start;
y := start;
z := start;
while 0 < x do {
 while 0 < y do {
  while 0 < z do {
    z := z - 1
  };
  z := start;
  y := y - 1
 };     
 y := start;
 x := x - 1
};
write x;
write y;
write z
"""

tokenize(test_prog, regs)