Skip to content

Instantly share code, notes, and snippets.

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

This comment has been minimized.

Copy link
Owner Author

commented Mar 18, 2019

Usage: copy-paste into ammonite

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.