Skip to content

Instantly share code, notes, and snippets.

@MateuszKubuszok
Created March 18, 2019 14:54
Show Gist options
  • Save MateuszKubuszok/dda5253281e59c75b7b669a1164a3db8 to your computer and use it in GitHub Desktop.
Save MateuszKubuszok/dda5253281e59c75b7b669a1164a3db8 to your computer and use it in GitHub Desktop.
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