import scala.language.implicitConversions

import scala.language.reflectiveCalls

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

 * I <% Seq[_] , which means that the input type I can be

 * treated, or seen, as a sequence. */

trait Input { 

  def isEmpty: Boolean

}

abstract class Parser[T] {

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

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

    for ((head, tail) <- parse(ts); 

        if (tail.isEmpty)) yield head

}

class SeqParser[T, S](p: => Parser[T], 

                      q: => Parser[S]) extends Parser[(T, S)] {

  def parse(sb: Input) = 

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

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

}

class AltParser[T](p: => Parser[T], 

                   q: => Parser[T]) extends Parser[T] {

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

}

class FunParser[T, S](p: => Parser[T], 

                      f: T => S) extends Parser[S] {

  def parse(sb: Input) = 

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

}

// atomic parsers  

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

  type Input = String

  def parse(sb: String) = 

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

}

case class StringParser(s: String) extends Parser[String, String] {

  def parse(sb: String) = {

    val (prefix, suffix) = sb.splitAt(s.length)

    if (prefix == s) Set((prefix, suffix)) else Set()

  }

}

case object NumParser extends Parser[String, Int] {

  val reg = "[0-9]+".r

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

    case None => Set()

    case Some(s) => Set(sb.splitAt(s.length) match {

      case (x, y) => (x.toInt, y)

    }) 

  }

}

// convenience

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

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

}

// a parse palindromes

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

println("Palindrom: " + Pal.parse_all("ababbaba"))

// well-nested parenthesis parser

lazy val P : Parser[String, String] = 

  "(" ~ P ~ ")" ~ P ==> { case (((u, x), y), z) => "{" + x + "}" + z } || ""

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

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

P.parse_all(")(")

P.parse_all("()")

// arithmetic expressions

lazy val E: Parser[String, Int] = 

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

lazy val F: Parser[String, Int] = 

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

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

lazy val T: Parser[String, Int] = 

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

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

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

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

println(E.parse_all("1+2+3"))  // this is not parsed, because of 

                               // how the grammar is set up

// non-ambiguous vs ambiguous grammars

lazy val S : Parser[String, String] =

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

S.parse_all("1" * 15)

lazy val U : Parser[String, String] =

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

U.parse("11")

U.parse("11111")

U.parse("11011")

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