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