Created
February 8, 2011 02:40
-
-
Save pchiusano/815747 to your computer and use it in GitHub Desktop.
The parser live-coded at the Feb 7 BASE meeting
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package combinatorsdemo | |
import scala.util.parsing.combinator.RegexParsers | |
import scala.util.parsing.input._ | |
import scala.util.matching.Regex | |
// type Parser[A] = List[T] => M[(A,List[T])] | |
// parser to recognize a single token | |
// parser that always succeeds without consuming input - constant parser | |
// parser that always fails without consuming input | |
// map, flatMap, choice | |
sealed trait Expr { | |
def simplify: Expr = this match { | |
case i@IntLiteral(_) => i | |
case s@Symbol(_) => s | |
case Add(e1, e2) => (e1.simplify, e2.simplify) match { | |
case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a + b) | |
case (a,b) => Add(a,b) | |
} | |
case Subtract(e1, e2) => (e1.simplify, e2.simplify) match { | |
case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a - b) | |
case (a,b) => Subtract(a,b) | |
} | |
case Mult(e1, e2) => (e1.simplify, e2.simplify) match { | |
case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a * b) | |
case (a,b) => Mult(a,b) | |
} | |
} | |
} | |
case class IntLiteral(get: Int) extends Expr | |
case class Symbol(get: String) extends Expr | |
case class Add(e1: Expr, e2: Expr) extends Expr | |
case class Subtract(e1: Expr, e2: Expr) extends Expr | |
case class Mult(e1: Expr, e2: Expr) extends Expr | |
object DemoParser extends RegexParsers { | |
val number: Parser[Expr] = | |
token(regex(new Regex("[0-9]+")) map (str => IntLiteral(str.toInt))) | |
val identifier: Parser[Expr] = | |
token(regex(new Regex("[a-z][a-zA-Z0-9_]*")) map (str => Symbol(str))) | |
def token[A](p: Parser[A]): Parser[A] = for { | |
a <- p | |
_ <- regex(new Regex("[ \\t\\n\\r]*")) | |
} yield a | |
val leaf = number | identifier | |
val fnCall: Parser[(Expr,Expr)] = for { | |
i <- identifier | |
n <- number | |
} yield (i, n) | |
val mult: Parser[Expr] = rep1sep(leaf, token('*')) map ( | |
_.reduceLeft(Mult(_,_))) | |
val addOrSubtract: Parser[Expr] = | |
chainl1(mult, token('+').map(_ => (a,b) => Add(a,b)) | | |
token('-').map(_ => (a,b) => Subtract(a,b))) | |
val expr = phrase(addOrSubtract) | |
def repeat[A](p: Parser[A]): Parser[List[A]] = (for { | |
h <- p | |
t <- repeat(p) | |
} yield h :: t) | success(List()) | |
// add ::= expr '+' expr | |
// a + b | |
def main(args: Array[String]): Unit = { | |
val inputText = "2 + 2 * 3" | |
val input = new CharSequenceReader(inputText) | |
println(expr.map(_.simplify)(input)) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment