Parser Combinator开发者社区

Parser Combinator

bool_literal ::= "true" | "false"

boolLiteral = string "true" <|> string "false"

boolLiteral = (<|>) (string "true") (string "false")

data JBool = JBool Bool 
boolLiteral = (string "true" >> return (JBool True))
          <|> (string "false" >> return (JBool False))

data SBool = SBool Bool 
boolLiteral = (string "#t" >> return (SBool True))
          <|> (string "#f" >> return (SBool False))

boolLiteral = try (string "#t" >> return (SBool True))
          <|> (string "#f" >> return (SBool False))

x = myFunc(a, b)(c)

expression ::= ... | var_name | function_call | ...
function_call ::= expression "(" argument_list ")"

data JSExpression = 
  | JSVar String
  | JSFuncCall JSExpression [JSExpression] 
  | ...
expression = ... <|> try variable <|> try functionCall <|> ...
functionCall = do func <- expression
                  args <- between (symbol "(") (symbol ")") argumentList
                  return (JSFuncCall func args)

JSFuncCall 
  (JSFuncCall (JSVar "myFunc") [JSVar "a", JSVar "b"]) 
  [JSVar "c"]

arr[1][2][3]
obj.field1.method1()

expression = do 
  varExpr <- variable
  tailExpression varExpr
expressionTail expr = checkAhead expr <|> return expr
checkAhead expr = do 
  c <- lookAhead (oneOf "[(.")
  case c of
    '[' -> brcketField
    '(' -> funcCall
    '.' -> dotField
  where
    brcket = between (symbol "[") (symbol "]") 
    parens = between (symbol "(") (symbol ")")
    argumentList = sepBy expression (symbol ",")
    brcketField = do inside <- braket expression
                     expressionTail (JSBracketField expr inside)
    funcCall    = do inside <- parens argumentList
                     expressionTail (JSFuncCall expr inside)
    dotField    = do after <- expression
                     expressionTail (JSDotField expr after)

trait Parser[+A] {
  def parse(input: String): Option[A]
  def run(state: State): Result[A]
}

case class State(input: String, cursor: Int) {
  def moveForward(n: Int): State = copy(cursor = cursor + n)
  def currentInput: String = input.substring(cursor)
}

sealed trait Result[+A] {
  // convert Result to Option
  def toOption: Option[A] = this match {
    case Success(res, _) => Some(res)
    case Failure(_) => None
case class Success[A](res: A, consumed: Int) extends Result[A]
case class Failure(cursor: Int) extends Result[Nothing]

// defined inside Parser[A] trait
// run from 0, and convert the result to Option type
def parse(input: String): Option[A] = run(State(input, 0)).toOption

object Parser {
  // convert a function to a Parser
  def apply[A](func: State => Result[A]): Parser[A] = 
    new Parser[A] { 
      def run(state: State): Result[A] = func(state)
}

val parser = Parser(someFunc)

// defined inside Parser object
// always succeed without consuming any input
def success[A](a: A): Parser[A] = Parser(state => Success(a, 0))
// always fail without consuming any input
def failure: Parser[Nothing] = Parser(state => Failure(state.cursor))
 * if currentInput is empty string, then the parsing will fail, otherwise,
 * it will succeed and consume one char
def item: Parser[Char] = Parser(state => state.currentInput match {
  case "" => Failure(state.cursor)
  case s => Success(s.head, 1)
 * if the head char of the input string equals to the given char, 
 * the parsing will succeed, otherwise, it will fail
def char(c: Char): Parser[Char] = Parser(state =>
  state.currentInput.headOption match {
    case Some(h) => 
      if (h == c) Success(c, 1) else Failure(state.cursor)
    case None => Failure(state.cursor)
)

// defined inside Parser object
def string(s: String): Parser[String] = {
  def charList(lst: List[Char]): Parser[List[Char]] = lst match {
    case Nil => success(Nil)
    case notNil => for {
      // parse the first char
      h <- char(notNil.head)
      // parse tail chars
      t <- charList(notNil.tail)
    } yield h::t // append the char at the head of tail list
  for {
    // parse chars
    lst <- charList(s.toList)
  } yield lst.mkString // convert the char list and build result string
}

// defined inside Parser[A] trait
// type of ??? should be Parser[B]
def flatMap[B](func: A => Parser[B]): Parser[B] = ???
def map[B](f: A => B): Parser[B] = flatMap(a => success(f(a)))
def filter(predicate: A => Boolean): Parser[A] =
  flatMap(x => if (predicate(x)) success(x) else failure)

// type of ??? should be State => Result[B]
def flatMap[B](func: A => Parser[B]): Parser[B] = Parser(???)

// type of ??? should be Result[B]
def flatMap[B](func: A => Parser[B]): Parser[B] = Parser(state => ???)

// defined inside Parser[A] trait
def flatMap[B](func: A => Parser[B]): Parser[B] = Parser(state => 
  run(state) match {
    case Success(a, c1) =>
      val newState = state.moveForward(c1)
      func(a).run(newState) match {
        case Success(b, c2) => Success(b, c1 + c2)
        case f@Failure(_) => f
    case f@Failure(_) => f
)

>>> string("hello").parse("hello world")
Some(hello)
>>> string("hello").parse("world")
None

// defined inside Parser[A] trait
def or[B >: A](other: => Parser[B]): Parser[B] = Parser(state =>
  // run first parser on current state
  run(state) match {
    // if parsing succeeds, return the result
    case s1@Success(_, _) => s1
    // if parsing fails, fetch the latest position
    case Failure(pos1) => {
      // run the second parser on the latest position
      other.run(state.copy(cursor = pos1)) match {
        case s2@Success(_, _) => s2
        case f@Failure(_) => f
def |[B >: A](other: => Parser[B]): Parser[B] = or(other)

def or(other: => Parser[A]): Parser[A]

>>> (string("true") | string("false")).parse("false")
Some(false)
>>> (string("#t") | string("#f")).parse("#f")
None

// defined inside Parser[A] trait
def attempt: Parser[A] = Parser(state => 
  run(state) match {
    case s@Success(_, _) => s
    // if parsing fails, the position will be set to the position of input state
    case Failure(_) => Failure(state.cursor)
)

// defined inside Parser[A] trait
def or[B >: A](other: => Parser[B]): Parser[B] = Parser(state =>
  run(state) match {
    case s1@Success(_, _) => s1
    // if parsing fails, ignore the latest position
    case Failure(_) => {
      // run the second parser on the original position 
      other.run(state) match {
        case s2@Success(_, _) => s2
        case f@Failure(_) => f
)

>>> (string("true") | string("false")).parse("false")
Some(false)
>>> (string("#t").attempt | string("#f")).parse("#f")
Some(#f)

// defined inside Parser object
def string(s: String): Parser[String] = {
  def charList(lst: List[Char]): Parser[Unit] = lst match {
    case Nil => success(())
    case notNil => for {
      _ <- char(notNil.head)
      _ <- charList(notNil.tail)
    } yield ()
  charList(s.toList).map(_ => s)
}

// defined inside Parser object
def string(s: String): Parser[String] = Parser(state =>
  if (state.currentInput.startsWith(s)) Success(s, s.length)
  else Failure(state.cursor)
)

// defined inside Parser object
def char(c: Char): Parser[Char] = string(c.toString).map(_.head)

// defined inside Parser object
def char(c: Char): Parser[Char] = item.filter(_ == c)

// defined inside Parser[A] trait
def skipLeft[B](pr: Parser[B]): Parser[B] =
  for {
    _ <- this
    r <- pr
  } yield r
def skipRight(pr: Parser[Any]): Parser[A] =
  for {
    l <- this
    _ <- pr
  } yield l
def >>[B](pr: Parser[B]): Parser[B] = skipLeft(pr)
def <<(pr: Parser[Any]): Parser[A] = skipRight(pr)

// defined inside Parser object
val space: Parser[Char] = item.filter(_.isSpaceChar)
// defined inside Parser[A] trait
def between(pl: Parser[Any], pr: Parser[Any]): Parser[A] = pl >> this << pr

// defined inside Parser[A] trait 
def some: Parser[List[A]] = for {
  a <- this
  as <- many
} yield a::as
def many: Parser[List[A]] = some.attempt | success(Nil)
def + : Parser[List[A]] = some
def * : Parser[List[A]] = many

>>> ((space+) >> string("hello")).parse("hello")
>>> ((space+) >> string("hello")).parse("   hello")
Some(hello)

// defined inside Parser[A] trait 
def many: Parser[List[A]] = {
  def rec(s: State, acc: List[A], total: Int): (List[A], Int) =
    run(s) match {
       * if parsing succeeds, 
       * append the current result at the head of accumulation,
       * then continue to parse the remain input string
      case Success(a, c) => rec(s.moveForward(c), a::acc, total + c)
       * if parsing fails, stop and return the accumulation result
       * note that we need to reverse the accumulation list
      case Failure(_) => (acc.reverse, total)
  Parser(state => {
    val (res, len) = rec(state, Nil, 0)
    Success(res, len)
}

Parser Combinator

Parser Combinator

词法分析和语法分析

使用 Parser Combinator 解析文本

构建一套简易的 Parser Combinator

面向组合子编程

参考资料