import scala.language.implicitConversions    
import scala.language.reflectiveCalls
import scala.annotation.tailrec   
import scala.io.Source
import scala.util.parsing.combinator._

abstract class Rexp 
case object ZERO extends Rexp 
case object ONE extends Rexp
case class CHAR(c: Char) extends Rexp {
  override def toString = c.toString 
}
case class ALT(r1: Rexp, r2: Rexp) extends Rexp {
  override def toString = "(" + r1.toString + "|" + r2.toString + ")" 
}
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp {
  override def toString = "(" + r1.toString + r2.toString +")"
} 
case class STAR(r: Rexp) extends Rexp 
case class RECD(x: String, r: Rexp) extends Rexp

case class Parser(s: String) {
  var i = 0
  
  def peek() = s(i)
  def eat(c: Char) = 
    if (c == s(i)) i = i + 1 else throw new Exception("Expected " + c + " got " + s(i))
  def next() = { i = i + 1; s(i - 1) }
  def more() = s.length - i > 0

  def Regex() : Rexp = {
    val t = Term();
    if (more() && peek() == '|') {
      eat ('|') ;
      val r = Regex();
      ALT(t, r) 
    } 
    else t
  }

  def Term() : Rexp = {
    var f : Rexp = if (more() && peek() != ')' && peek() != '|') Factor() else ZERO;
    while (more() && peek() != ')' && peek() != '|') {
      var nextf = Factor();
      f = SEQ(f, nextf) ;
    }

    f
  }

  def Factor() : Rexp = {
    var b = Base();
    while (more() && peek() == '*') {
      eat('*') ;
      b = STAR(b) ;
    }

    b
  }

  def Base() : Rexp = {
    peek() match {
      case '(' => { eat('(') ; val r = Regex(); eat(')') ; r }
      case _ => CHAR(next())
    }
  }
}

println(Parser("a|(bc)*").Regex())


def process(line: String) : String = {
  val s = line.split("\\t+")(1)
  s + ":   " + Parser(s).Regex().toString
}


val filename = "../tests/forced-assoc.txt"
val filelines : List[String] = Source.fromFile(filename).getLines.toList


filelines.foreach((s: String) => println(process(s)))