import scala.language.implicitConversions

import scala.language.reflectiveCalls

// more convenience for the semantic actions later on

case class ~[+A, +B](_1: A, _2: B)

/* Note, in the lectures I did not show the implicit type consraint

 * I => Seq[_], which means that the input type 'I' needs to be

 * a sequence. */

type IsSeq[A] = A => Seq[_]

abstract class Parser[I : IsSeq, 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

}

class SeqParser[I : IsSeq, 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 (new ~(head1, head2), tail2)

}

class AltParser[I : IsSeq, 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 : IsSeq, 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)

}

// atomic parsers for characters, numbers and strings

case class CharParser(c: Char) extends Parser[String, Char] {

  def parse(sb: String) = 

    if (sb != "" && sb.head == c) Set((c, sb.tail)) else Set()

}

import scala.util.matching.Regex

case class RegexParser(reg: Regex) extends Parser[String, String] {

  def parse(sb: String) = reg.findPrefixMatchOf(sb) match {

    case None => Set()

    case Some(m) => Set((m.matched, m.after.toString))  

  }

}

val NumParser = RegexParser("[0-9]+".r)

def StringParser(s: String) = RegexParser(Regex.quote(s).r)

// NumParserInt2 transforms a "string integer" into an Int;

// needs new, because FunParser is not a case class

val NumParserInt2 = new FunParser(NumParser, (s: String) => s.toInt)

// convenience

implicit def string2parser(s: String) = StringParser(s)

implicit def char2parser(c: Char) = CharParser(c)

implicit def ParserOps[I : IsSeq, 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 StringOps(s: String) = new {

  def ||(q : => Parser[String, String]) = new AltParser[String, String](s, q)

  def ||(r: String) = new AltParser[String, String](s, r)

  def ==>[S] (f: => String => S) = new FunParser[String, String, S](s, f)

  def ~[S](q : => Parser[String, S]) = 

    new SeqParser[String, String, S](s, q)

  def ~(r: String) = 

    new SeqParser[String, String, String](s, r)

}

// NumParserInt can now be written as

val NumParserInt = NumParser ==> (s => s.toInt)

lazy val Pal : Parser[String, String] = 

  (("a" ~ Pal ~ "a") ==> { case x ~ y ~ z => x + y + z } ||

   ("b" ~ Pal ~ "b") ==> { case x ~ y ~ z => x + y + z } || "a" || "b" || "")

Pal.parse_all("abaaaba")

Pal.parse("abaaaba")

println("Palindrome: " + Pal.parse_all("abaaaba"))

// well-nested parentheses parser (transforms '(' -> '{' , ')' -> '}' )

lazy val P : Parser[String, String] = 

  "(" ~ P ~ ")" ~ P ==> { case _ ~ x ~ _ ~ y => "{" + x + "}" + y } || ""

P.parse_all("(((()()))())")

P.parse_all("(((()()))()))")

P.parse_all(")(")

P.parse_all("()")

// Arithmetic Expressions (Terms and Factors)

lazy val E: Parser[String, Int] = 

  (T ~ "+" ~ E) ==> { case x ~ _ ~ z => x + z } ||

  (T ~ "-" ~ E) ==> { case x ~ _ ~ z => x - z } || T 

lazy val T: Parser[String, Int] = 

  (F ~ "*" ~ T) ==> { case x ~ _ ~ z => x * z } || F

lazy val F: Parser[String, Int] = 

  ("(" ~ E ~ ")") ==> { case _ ~ y ~ _ => y } || NumParserInt

/* same parser but producing a string

lazy val E: Parser[String, String] = 

  (T ~ "+" ~ E) ==> { case x ~ y ~ z => "(" + x + ")+(" + z + ")"} || T 

lazy val T: Parser[String, String] = 

  (F ~ "*" ~ T) ==> { case x ~ y ~ z => "(" + x + ")*("+ z + ")"} || F

lazy val F: Parser[String, String] = 

  ("(" ~ E ~ ")") ==> { case x ~ y ~ z => y } || NumParser

*/

println(E.parse_all("1+3+4"))

println(E.parse("1+3+4"))

println(E.parse_all("4*2+3"))

println(E.parse_all("4*(2+3)"))

println(E.parse_all("(4)*((2+3))"))

println(E.parse_all("4/2+3"))

println(E.parse("1 + 2 * 3"))

println(E.parse_all("(1+2)+3"))

println(E.parse_all("1+2+3"))  

// no left-recursion allowed, otherwise will loop

lazy val EL: Parser[String, Int] = 

  (EL ~ "+" ~ EL ==> { case x ~ y ~ z => x + z} || 

   EL ~ "*" ~ EL ==> { case x ~ y ~ z => x * z} ||

   "(" ~ EL ~ ")" ==> { case x ~ y ~ z => y} ||

   NumParserInt)

//println(EL.parse_all("1+2+3"))

// non-ambiguous vs ambiguous grammars

// ambiguous

lazy val S : Parser[String, String] =

  ("1" ~ S ~ S) ==> { case x ~ y ~ z => x + y + z } || ""

S.parse("1" * 10)

// non-ambiguous

lazy val U : Parser[String, String] =

  ("1" ~ U) ==> { case x ~ y => x + y  } || ""

U.parse("1" * 25)

U.parse("11")

U.parse("11111")

U.parse("11011")

U.parse_all("1" * 100)

U.parse_all("1" * 100 + "0")

lazy val UCount : Parser[String, Int] =

  ("1" ~ UCount) ==> { case x ~ y => y + 1 } || "" ==> { x => 0 }

UCount.parse("11111")

UCount.parse_all("11111")

// Single Character parser

lazy val One : Parser[String, String] = "1"

lazy val Two : Parser[String, String] = "2"

One.parse("1")

One.parse("111")

(One ~ One).parse("111")

(One ~ One ~ One).parse("111")

(One ~ One ~ One ~ One).parse("1111")

(One || Two).parse("111")

// a problem with the arithmetic expression parser -> gets 

// slow with deeply nested parentheses

println("Runtime problem")

E.parse("1")

E.parse("(1)")

E.parse("((1))")

E.parse("(((1)))")

E.parse("((((1))))")

E.parse("((((((1))))))")

E.parse("(((((((1)))))))")

E.parse("((((((((1)))))))")