从手写递归下降到Parser combinator

这次继续讨论递归下降算法吧。

上次提到的框架基本上就是递归下降的纯函数式编程的实现了，不过，缺点也很显然，首先就是太长，样板代码太多，可读性和可维护性差。上次倒是也提到了。

不过也不难发现，这里重复的模式和样板代码，做的东西基本就是一件事：在纯函数环境下（没有副作用和状态的场合），模拟出「可变状态和副作用」的效果。

比如那个二元组的第二项tokens列表的操作。

又比如逐层嵌套下去的if语句块。

会想到什么呢，嗯，那就是monad了。毕竟写了这么多年的函数式代码，哪怕写不出一篇介绍monad的教程，但是还是大概对一些基本概念有点印象的。

这里就不展开了，不过，显然，二元组的第二项可以转化为这样的一个monad：

class ParserMonad[R](val run: List[Token] => Either[List[String], (R, List[Token])])

这里就直接给最后产物了，用Either而不是Option，也算彻底干掉了基于异常的错误处理。

有了基本结构，就可以进一步完善定义让他符合monad的定义：

def map[S](f: R => S): ParserMonad[S] = ParserMonad { input =>
  run(input) match
    case Left(stack) => Left(stack)
    case Right((value, rest)) => Right(f(value), rest)
}

def flatMap[S](f: R => ParserMonad[S]): ParserMonad[S] = ParserMonad { input =>
  run(input) match
    case Left(stack) => Left(stack)
    case Right(value, rest) => f(value).run(rest)
}

def orElse(other: ParserMonad[R]): ParserMonad[R] = ParserMonad { input =>
  run(input) match
    case Left(err1) =>
      other.run(input) match
        case Left(err2) => Left(err1 ++ err2)
        case success @ Right(_, _) => success
    case success @ Right(_, _) => success

或者，用更熟悉的语法：

@targetName("bind")
infix def >>=[S](f: R => ParserMonad[S]): ParserMonad[S] = this.flatMap(f)

@targetName("elvis")
infix def ??(v: ParserMonad[R]): ParserMonad[R] = this.orElse(v)

@targetName("alt")
infix def <|>(other: ParserMonad[R]): ParserMonad[R] = this.orElse(other)

这里用原地扩展一个class的方式而不是用trait的写法，因为Scala里面的trait用来描述typeclass还是没那么方便，而单独为「每一个monad的实例」写一个专门的trait又多少有点anti-pattern了。不过，大体上，也可以看得到，通过这一系列函数，定义了ParserMonad的互相转换，之前困扰我们的二元组，其实只有真正执行run之后才会拿到，无形中就把可变状态封装在ParserMonad的互相转换中了。

然后就该把原先的递归下降Parser移植过来了。首先把基础函数写了：

object MonadicParser:

  def eat(expected: Token): ParserMonad[Token] = ParserMonad {
    case head :: tail if head == expected => Right((head, tail))
    case head :: _ => Left(List(s"eat: Expected $expected but found $head"))
    case Nil => Left(List(s"eat: Expected $expected but found end of input"))
  }

  def peek(expected: Token): ParserMonad[Token] = ParserMonad {
    case tokens@(head :: _) if head == expected => Right((head, tokens))
    case head :: _ => Left(List(s"peek: Expected $expected but found $head"))
    case Nil => Left(List(s"peek: Expected $expected but found end of input"))
  }

  def peek[R](select: Token => ParserMonad[R]) = ParserMonad {
    case tokens@(head :: _) => select(head).run(tokens)
    case Nil => Left(List(s"peek: Expected a token but found end of input"))
  }

  def cond[R](call: List[Token] => ParserMonad[R]) = ParserMonad { tokens =>
    call(tokens).run(tokens)
  }

  private def consume[R](matcher: Token => Either[List[String], R]) (message: String): ParserMonad[R] = ParserMonad {
    case head :: tail =>
      matcher(head)
        .map(result => Right(result, tail))
        .getOrElse(Left(List(s"consume[$message] : Token did not match: $head")))
    case Nil => Left(List(s"consume[$message]: Unexpected end of input"))
  }

这里的peek其实就相当于lookahead了。大致也展现了一下结合lambda和高阶函数后可以灵活的实现各种需要的原子语义。

也可以定义一些类似parser combinator的组合语句，看起来就更像Haskell的语法了：

extension [T](t: ParserMonad[T])

  def nullable: ParserMonad[Option[T]] =
    t.map(Some(_)).orElse(ParserMonad(None))

  def ~[U](other: ParserMonad[U]): ParserMonad[(T, U)] =
    for {
      first <- t
      second <- other
    } yield (first, second)

  def ^^[U](f: T => U): ParserMonad[U] = t.map(f)

  def ^^^[U](value: U): ParserMonad[U] = t.map(_ => value)

  def ~>[U](other: ParserMonad[U]): ParserMonad[U] =
    for {
      _ <- t
      result <- other
    } yield result

  def <~[U](other: ParserMonad[U]): ParserMonad[T] =
    for {
      result <- t
      _ <- other
    } yield result
    
def chainl1[T](p: ParserMonad[T], op: ParserMonad[(T, T) => T]): ParserMonad[T] =

def rest(acc: T): ParserMonad[T] =
  (for {
    f <- op
    b <- p
    next <- rest(f(acc, b))
  } yield next) <|> ParserMonad(acc)

  p.flatMap(first => rest(first))

def binaryAssocLeft(p: ParserMonad[Expr])(op: ParserMonad[Op]): ParserMonad[Expr] =
  chainl1(p, op ^^ { op => (x, y) =>
    op match
      case op: ArithOp => BinArith(op, x, y)
      case op: LogicalOp => BinLogic(op, x, y)
  })

类似some、many、sepBy、sepEndBy之类的语句定义起来也不复杂，这里就不展开了。

也许值得提的是表达式部分的实现吧，因为希望能够处理例如

1 + 2 * (3 - 4) - 5 / 6
1 :: 2 :: f x :: list
f a b c

这样的语句，所以在之前的手写递归下降算法的逻辑上，增加了右递归的处理：

def parseTerm: ParserMonad[Expr] =
  parseTupleOrFunc <|> parseRecord <|> parseList <|> parseNil <|> parseLiteral

def parseExprOfLevel(level: Int): ParserMonad[Expr] = {
  val OpParser = binOpParsers.getOrElse(level, fail("level out of bound"))

  // additional level for function calls
  if (level < 4) {
    // Left-associate binary operations
    binaryAssocLeft(parseExprOfLevel(level + 1))(OpParser)
  } else {
    // Function application, if applies, or basic terms if singleton
    listAssocRight(funcCallAssocRight(parseTerm))
  }
}

def listAssocRight(baseParser: ParserMonad[Expr]): ParserMonad[Expr] = {
  def loop(head: Expr): ParserMonad[Expr] = {
    (for {
      _ <- eat(DoubleColonToken)
      curr <- baseParser
      next <- loop(Append(head, curr))
    } yield next) <|> ParserMonad(head)
  }

  for {
    head <- baseParser
    result <- loop(head) <|> ParserMonad(head)
  } yield result
}

def funcCallAssocRight(baseParser: ParserMonad[Expr]): ParserMonad[Expr] = {
  def loop(head: Expr): ParserMonad[Expr] = {
    for {
      curr <- baseParser
      next <- peek {
        case _ => // Continue on function applications
          loop(Call(head, curr))
      } <|> ParserMonad(Call(head, curr)) // pure it if nothing more to eat
    } yield next
  }

  for {
    head <- baseParser
    result <- loop(head) <|> ParserMonad(head)
  } yield result
}

其实这个代码蛮像我两年前写的blog文章里面的代码来着。也许算是那时候的思路的完善吧。

不过从上一篇的手写递归下降过来，不难发现，从递归下降的角度，也许可以为理解parser和parser combinator提供一个不同的视角，也许也对工程化有帮助吧。

提到这里的话，这个代码其实也不是完美的。虽然在写现在的parser combinator的时候，还是尽力去遵照CFG和LL(1)的思路，让语法规则尽量满足LL(1)的要求，但是<|>操作符的引入，仍然意味着我们需要跟回溯斗智斗勇。

比如说，在解析失败的时候，报错的内容很可能是「在LetRec语句中要求一个in符号」这种理由，而很可能我实际犯的错是把双箭头⇒写成了单箭头→，或者用了例如#这种预留符号。

之所以会出现这种问题，因为<|>会在解析失败后，往回走然后尝试其他可能的组合，一方面，这会让报错变得不明所以，另一方面，回溯引入的复杂度也会让parser的性能变得很糟糕。

所以，解决办法的话，也许可能是限制回溯的层级，或者压根用peek（lookahead）来替代而直接禁止回溯，不过这个倒是工程细节了。

提到这里也想起之前有看到有人说，「parser combinator本身是乏善可陈的，它没有引入任何新东西」。

现在的话，我想，对于这个问题，我的看法是「幸亏他没有引入新的东西，这样我只是在用一种不同的写法来写我熟悉的LL(1)递归下降和CFG的解析算法，不过，声明式DSL总归是个好东西」。

那么这次的讨论也就告一段落了呢。