Simple parser combinators example

## parser_combinators.scala
// Parser definitions

type Parser[+A] = String => Option[(A, String)]

object Parser{

  def apply[A](re: String)(f: String => A): Parser[A] =
    input => s"""\\s*($re)(\\s*)""".r
      .findPrefixMatchOf(input)
      .map { n =>
        val terminal = f(n.group(1))
        val unmatched = input.substring(n.group(0).length)
        terminal -> unmatched
      }
}

implicit class ParserOps[A](parser: Parser[A]) {

  def |[B >: A](another: => Parser[B]): Parser[B] =
    input => if (input.isEmpty) None
             else parser(input) orElse another(input)

  def &[B](another: => Parser[B]): Parser[(A, B)] =
    input => if (input.isEmpty) None
             else for {
               (a, in2) <- parser(input)
               (b, in3) <- another(in2)
             } yield (a, b) -> in3

  def map[B](f: A => B): Parser[B] =
    input => parser(input).map { case (a, in2) => f(a) -> in2 }
}

// AST

{
sealed trait Terminal

final case class Number(value: java.lang.Number)
    extends Terminal

sealed trait BinaryOperator
case object Plus extends BinaryOperator with Terminal
case object Minus extends BinaryOperator with Terminal
case object Times extends BinaryOperator with Terminal
case object Div extends BinaryOperator with Terminal

sealed trait Expression
final case class FromNumber(number: Number) extends Expression
final case class FromBinary(operand1: Expression,
                            operand2: Expression,
                            bin: BinaryOperator)
    extends Expression
}

// our parser

{
val number = Parser[Number]("""[0-9]+""")(n => Number(n.toInt))
val plus = Parser[Plus.type]("""\+""")(_ => Plus)
val minus = Parser[Minus.type]("""-""")(_ => Minus)
val times = Parser[Times.type]("""\*""")(_ => Times)
val div = Parser[Div.type]("""\/""")(_ => Div)

val binaryOperator: Parser[BinaryOperator] =
  plus | minus | times | div

def expression: Parser[Expression] = {
  def fromNumber =
    number.map(FromNumber(_))

  def fromBinary =
    ((fromNumber | inParenthesis) &
      binaryOperator &
     (fromNumber | inParenthesis)).map {
      case ((ex1, bin), ex2) => FromBinary(ex1, ex2, bin)
    }

  fromBinary | fromNumber
}

def inParenthesis: Parser[Expression] =
  (Parser[Unit]("""\(""")(_ => ()) &
   expression &
   Parser[Unit]("""\)""")(_ => ())).map {
    case ((_, ex), _) => ex
  }
}

// test

expression(""" 12 + 23 """).map(_._1).foreach(println)