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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
Usage: copy-paste into ammonite