edadma / pattern-matcher   0.2.2

ISC License GitHub

simple combinator parsing library

Scala versions: 2.12 2.11

Pattern Matcher

Build Status Build status Coverage Status License Version

pattern-matcher is a small combinator parsing library written in Scala mainly as a learning experience. For serious parsing needs, it is recommended to use Scala's scala-parser-combinators library.

Example 1

Here is an example expression parser.

package io.github.edadma.pattern_matcher

import io.github.edadma.char_reader.CharReader

@main def Example1(): Unit =
  Example1Parser.run("-3 + 4 * (-5)")
  Example1Parser.run("5")
  Example1Parser.run("2 +")

  object Example1Parser extends Matchers[CharReader] {

    delimiters ++= List("+", "-", "*", "/", "(", ")")

    def input: Example1Parser.Matcher[Int] = matchall(expression)

    def additive: Matcher[(Int, Int) => Int] = ("+" | "-") ^^ {
      case "+" => _ + _
      case "-" => _ - _
    }

    def sign: Matcher[Int => Int] = opt("+" | "-") ^^ {
      case Some("-") => -_
      case _ => identity
    }

    def multiplicative: Matcher[(Int, Int) => Int] = ("*" | "/") ^^ {
      case "*" => _ * _
      case "/" => _ / _
    }

    def expression: Matcher[Int] = sign ~ term ~ rep(additive ~ term) ^^ {
      case s ~ n ~ l => (l foldLeft s(n)) { case (x, f ~ y) => f(x, y) }
    }

    def term: Example1Parser.Matcher[Int] = factor ~ rep(multiplicative ~ factor) ^^ {
      case n ~ l => (l foldLeft n) { case (x, f ~ y) => f(x, y) }
    }

    def factor: Example1Parser.Matcher[Int] = integerLit | "(" ~> expression <~ ")"

    def run(s: String): Unit =
      input(CharReader.fromString(s)) match {
        case Match(result, _) => println(result)
        case m: Mismatch => Console.err.println(m.errorString)
      }

  }

output

-23
5
expected end of input (line 1, column 3):
2 +
  ^

Example 2

As a longer example, here is an implementation of Niklaus Wirth's PL/0 programming language from his 1976 book, "Algorithms + Data Structures = Programs".

package io.github.edadma.pattern_matcher

import io.github.edadma.char_reader.CharReader

import scala.annotation.tailrec

@main def Example2(): Unit =
  Example2Parser.run(
  """
    |const max = 20;
    |var arg, ret;
    |
    |procedure isprime;
    |var i;
    |begin
    |  ret := 1;
    |  i := 2;
    |  while arg / (i * i) > 0 do begin
    |    if arg / i * i = arg then begin
    |      ret := 0;
    |      i := arg
    |    end;
    |    i := i + 1
    |  end
    |end;
    |
    |procedure primes;
    |begin
    |  arg := 2;
    |  while arg < max do begin
    |    call isprime;
    |    if ret = 1 then !arg;
    |    arg := arg + 1
    |  end
    |end;
    |
    |call primes.
  """.stripMargin
  )

  object Example2Parser extends Matchers[CharReader] {

    reserved ++= List("const", "var", "procedure", "odd", "begin", "end", "if", "then", "while", "do", "call")
    delimiters ++= List("+", "-", "*", "/", "(", ")", ";", ",", ".", ":=", "=", "#", "<", "<=", ">", ">=", "!")

    def program: Example2Parser.Matcher[Block] = matchall(block <~ ".")

    def const: Example2Parser.Matcher[(String, (CharReader, Int))] = pos ~ ident ~ "=" ~ integerLit ^^ {
      case p ~ n ~ _ ~ v => n -> (p, v)
    }

    def consts: Example2Parser.Matcher[List[(String, (CharReader, Int))]] = opt("const" ~> rep1sep(const, ",") <~ ";") ^^ {
      case None => Nil
      case Some(l) => l
    }

    def vari: Example2Parser.Matcher[(String, (CharReader, Var))] = pos ~ ident ~ opt("=" ~> integerLit) ^^ {
      case p ~ n ~ None => n -> (p, new Var(0))
      case p ~ n ~ Some(v) => n -> (p, new Var(v))
    }

    def vars: Example2Parser.Matcher[List[(String, (CharReader, Var))]] = opt("var" ~> rep1sep(vari, ",") <~ ";") ^^ {
      case None => Nil
      case Some(l) => l
    }

    def proc: Matcher[(String, (CharReader, Block))] = "procedure" ~ pos ~ ident ~ ";" ~ block ~ ";" ^^ {
      case _ ~ p ~ n ~ _ ~ b ~ _ => n -> (p, b)
    }

    def block: Example2Parser.Matcher[Block] = consts ~ vars ~ rep(proc) ~ statement ^^ {
      case c ~ v ~ p ~ s => Block(c ++ v ++ p, s)
    }

    def statement: Matcher[Statement] =
      pos ~ ident ~ ":=" ~ expression ^^ { case p ~ n ~ _ ~ e => Assign(p, n, e) } |
        "call" ~ pos ~ ident ^^ { case _ ~ p ~ n => Call(p, n) } |
        "!" ~> expression ^^ Write |
        "begin" ~> rep1sep(statement, ";") <~ "end" ^^ Sequence |
        "if" ~ condition ~ "then" ~ statement ^^ { case _ ~ c ~ _ ~ s => If(c, s) } |
        "while" ~ condition ~ "do" ~ statement ^^ { case _ ~ c ~ _ ~ s => While(c, s) }

    def condition: Example2Parser.Matcher[Condition] =
      "odd" ~> expression ^^ Odd |
        expression ~ ("=" | "#" | "<" | "<=" | ">" | ">=") ~ expression ^^ { case l ~ c ~ r => Comparison(l, c, r) }

    def expression: Matcher[Expression] = opt("+" | "-") ~ term ~ rep(("+" | "-") ~ term) ^^ {
      case (None | Some("+")) ~ t ~ l => (l foldLeft t) { case (x, o ~ y) => Operation(x, o, y) }
      case _ ~ t ~ l => (l foldLeft (Negate(t): Expression)) { case (x, o ~ y) => Operation(x, o, y) }
    }

    def term: Example2Parser.Matcher[Expression] = factor ~ rep(("*" | "/") ~ factor) ^^ {
      case f ~ l => (l foldLeft f) { case (x, o ~ y) => Operation(x, o, y) }
    }

    def factor: Example2Parser.Matcher[Expression] =
      pos ~ ident ^^ { case p ~ v => Ident(p, v) } |
        integerLit ^^ Number |
        "(" ~> expression <~ ")"

    def run(s: String): Unit =
      program(CharReader.fromString(s)) match {
        case Match(result, _) => evalBlock(result, Nil)
        case m: Mismatch => m.error
      }

    def evalBlock(block: Block, outer: List[Map[String, Any]]): Unit =
      block.decls.groupBy(_._1) collectFirst { case (_, _ :: x :: _) => List(x) } match {
        case None => evalStatement(block.stat, block.decls.map { case (k, (_, v)) => k -> v }.toMap :: outer)
        case Some(List((name, (pos, _)))) => sys.error(pos.longErrorText(s"'$name' is a duplicate"))
      }

    @tailrec
    def find(name: String, scope: List[Map[String, Any]]): Option[(Any, List[Map[String, Any]])] =
      scope match {
        case Nil => None
        case inner@h :: t => h get name match {
          case None => find(name, t)
          case Some(v) => Some((v, inner))
        }
      }

    def evalStatement(stat: Statement, scope: List[Map[String, Any]]): Unit =
      stat match {
        case Assign(pos, name, expr) =>
          find(name, scope) match {
            case None => sys.error(pos.longErrorText(s"variable '$name' not declared"))
            case Some((v: Var, _)) => v.v = evalExpression(expr, scope)
            case _ => sys.error(pos.longErrorText(s"'$name' not assignable"))
          }
        case Call(pos, name) =>
          find(name, scope) match {
            case None => sys.error(pos.longErrorText(s"procedure '$name' not declared"))
            case Some((b: Block, inner)) => evalBlock(b, inner)
            case _ => sys.error(pos.longErrorText(s"'$name' not a procedure"))
          }

        case Write(expr) => println(evalExpression(expr, scope))
        case Sequence(stats) => stats foreach (evalStatement(_, scope))
        case If(cond, body) => if (evalCondition(cond, scope)) evalStatement(body, scope)
        case While(cond, body) => while (evalCondition(cond, scope)) evalStatement(body, scope)
      }

    def evalCondition(cond: Condition, scope: List[Map[String, Any]]): Boolean =
      cond match {
        case Odd(expr) => evalExpression(expr, scope) % 2 == 1
        case Comparison(left, "<", right) => evalExpression(left, scope) < evalExpression(right, scope)
        case Comparison(left, ">", right) => evalExpression(left, scope) > evalExpression(right, scope)
        case Comparison(left, "=", right) => evalExpression(left, scope) == evalExpression(right, scope)
        case Comparison(left, "#", right) => evalExpression(left, scope) != evalExpression(right, scope)
        case Comparison(left, "<=", right) => evalExpression(left, scope) <= evalExpression(right, scope)
        case Comparison(left, ">=", right) => evalExpression(left, scope) >= evalExpression(right, scope)
      }

    def evalExpression(expr: Expression, scope: List[Map[String, Any]]): Int =
      expr match {
        case Ident(pos, name) =>
          find(name, scope) match {
            case None => sys.error(pos.longErrorText(s"'$name' not declared"))
            case Some((v: Var, _)) => v.v
            case Some((n: Int, _)) => n
            case _ => sys.error(pos.longErrorText(s"'$name' not an integer"))
          }
        case Number(n) => n
        case Operation(left, "+", right) => evalExpression(left, scope) + evalExpression(right, scope)
        case Operation(left, "-", right) => evalExpression(left, scope) - evalExpression(right, scope)
        case Operation(left, "*", right) => evalExpression(left, scope) * evalExpression(right, scope)
        case Operation(left, "/", right) => evalExpression(left, scope) / evalExpression(right, scope)
      }

    class Var(var v: Int)

    case class Block(decls: List[(String, (CharReader, Any))], stat: Statement)

    abstract class Statement

    case class Assign(pos: CharReader, name: String, expr: Expression) extends Statement

    case class Call(pos: CharReader, name: String) extends Statement

    case class Write(expr: Expression) extends Statement

    case class Sequence(stats: List[Statement]) extends Statement

    case class If(cond: Condition, stat: Statement) extends Statement

    case class While(cond: Condition, stat: Statement) extends Statement

    abstract class Condition

    case class Odd(expr: Expression) extends Condition

    case class Comparison(left: Expression, comp: String, right: Expression) extends Condition

    abstract class Expression

    case class Negate(x: Expression) extends Expression

    case class Operation(left: Expression, op: String, right: Expression) extends Expression

    case class Number(n: Int) extends Expression

    case class Ident(pos: CharReader, name: String) extends Expression

  }

output

2
3
5
7
11
13
17
19

Usage

Library

Use the following definition to use pattern-matcher in your Maven project:

<repository>
  <id>hyperreal</id>
  <url>https://dl.bintray.com/edadma/maven</url>
</repository>

<dependency>
  <groupId>io.github.edadma</groupId>
  <artifactId>pattern-matcher</artifactId>
  <version>0.3.1</version>
</dependency>

Add the following to your build.sbt file to use Backslash in your SBT project:

resolvers += "Hyperreal Repository" at "https://dl.bintray.com/edadma/maven"

libraryDependencies += "io.github.edadma" %% "pattern-matcher" % "0.1.6"

Building

Requirements

  • Java 11+
  • SBT 1.7.1+
  • Scala 3.2.0+

Clone and Assemble Executable

git clone git://github.com/edadma/pattern-matcher.git
cd pattern-matcher
sbt assembly

The command sbt assembly also runs all the unit tests.

License

ISC © 2019 Edward A. Maxedon, Sr.