Skip to content

Instantly share code, notes, and snippets.

@MateuszKubuszok
Created March 18, 2019 14:54
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Embed
What would you like to do?
Simple parser combinators example
// 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)
@MateuszKubuszok
Copy link
Author

Usage: copy-paste into ammonite

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment