LARA

// A minimalistic implementation of parser combinators in Scala
object Parsing {
  def main(args : Array[String]) : Unit = {
    // Concatenates all command line arguments into a string
    val argsAsString = args.foldLeft[String]("")(_ + " " + _).trim
    val argsAsStream = argsAsString.toStream
 
    println("Input string: " + argsAsString)
 
    // Avoids having to build Keyword("...") parsers for each constant
    // string
    implicit def str2parser(str: String) : Parser = new Keyword(str)
 
    // The Empty parser
    val epsilon = Empty
 
    def ID : Parser = "x" | "y" | "z"
 
    def expr : Parser = factor ~ ((
      "+" ~ factor
    | "-" ~ factor
    ) | epsilon)
 
    def factor : Parser = term ~ ((
      "*" ~ term
    | "/" ~ term
    ) | epsilon)
 
    def term : Parser = (
      "(" ~ expr ~ ")"
    | ID
    | NUM
    )
 
    val parser = expr
    // Attempts to parse the input with our parser
    println(parser(argsAsStream))
  }
}
 
abstract class Parser {
  // A parser by definition reads from a stream, and either succeeds and
  // consumes part of the stream, or fails
  def apply(input: Stream[Char]) : Result
 
  def ~(other: =>Parser) : Parser = new Sequence(this, other)
  def |(other: =>Parser) : Parser = new Alternative(this, other)
}
 
sealed abstract class Result
case class Success(rest: Stream[Char]) extends Result
case object Failure extends Result
 
class Keyword(value: String) extends Parser {
  def apply(input: Stream[Char]) : Result = {
    val beginning = input.take(value.length)
    if(beginning.length != value.length) {
      Failure
    } else {
      val asString = beginning.foldLeft[String]("")(_ + _)
      if(asString == value) {
        Success(input.drop(value.length))
      } else {
        Failure
      }
    }
  }
}
 
object Empty extends Parser {
  def apply(input: Stream[Char]) = Success(input)
}
 
class Sequence(left: =>Parser, right: =>Parser) extends Parser {
  def apply(input: Stream[Char]) : Result = left(input) match {
    case Success(rest) => right(rest)
    case f @ Failure => f
  }
}
 
class Alternative(first: =>Parser, second: =>Parser) extends Parser {
  def apply(input: Stream[Char]) : Result = first(input) match {
    case s @ Success(_) => s
    case Failure => second(input)
  }
}
 
// A hand-written "parser" for integer literals
object NUM extends Parser {
  def apply(input: Stream[Char]) : Result = if(input.isEmpty) {
    Failure
  } else {
    val c = input.head
    if(c == '0') {
      Success(input.tail)
    } else {
      var copy = input.tail
      while(!copy.isEmpty && copy.head >= '0' && copy.head <= '9') {
        copy = copy.tail
      }
      Success(copy)
    }
  }
}