用Scala实现手写的递归下降算法

最近重拾编程语言设计的事情，不可避免的又要遇到写parser的事情了。

想起来，三年前也做过类似的事情，不过那时候是用Haskell写parser combinator，有点知其然而不知其所以然的感觉吧。

这次重拾parser的话，为了能够让自己明白到底代码在干什么，也为了之后可以更好的维护和扩展语法吧，就选择了直接手写递归下降语法。当然，用的是Scala，也尽量保持了纯函数式的风格。不过，在写着写着的时候，发现许多boilerplate和惯用模式，似乎可以很好的成为parser combinator的直觉呢。于是就也来水一篇文章。

在这里，我们先不考虑monad之类的东西，我们可能也很熟悉递归下降的算法规则，也知道命令式的递归下降函数如何写。首先假设有四则运算语法：

expr ::= factor expr'
expr' ::= + factor expr' | {}
factor ::= term factor'
factor' ::= * term factor' | {}
term ::= num | ( expr )

这里我们需要先把不是LL(1)的四则运算转化为LL(1)的，这里主要是消除四则运算语法里面的左递归，用expr’和factor’把左递归转化为右递归。

用C语言的话，我们可能会得到这样的代码：

int expr() {
  int first = factor();
  return expr_sub(first);
}

int expr_sub(int first) {
  if (token == '+') {
    eat('+');
    int curr = first + factor();
    return expr_sub(curr);
  } else {
    return first;
  }
}

其实这个实现不太规范，因为每次返回的int，算是计算结果，并且把解释运行的步骤揉合在产生式规则里面了。不过这里的重点也不是C代码。但是大体上，递归下降的实现，就是逐个产生式依次按照BNF规则的从上到下从左到右的顺序调用，每层按照第一个元素的字面量来决定选择哪条产生式，这样递归地叠下去吧。

在C语言或者Java实现里，也一般会用副作用来传递一些关键信息，比如读到的token，比如剩下哪些token待读，再比如说生成中间产物。

有了这些情报后，我们就可以写自己的Scala版本了。不过在重新考虑四则运算之前，让我们考虑一个简单一点的例子：

if ::= 'if' expr 'then' expr 'else' expr

在Scala里面，不难写出这样的代码：

def parseIf(tokens: List[Token]): (Expr, List[Token]) =
  val (condExpr, condCont) = parseExpr(tokens.drop(1))
  if condCont.head != ThenToken then
    throw IllegalStateException("Expected `then` in if expression")
  else
    val (thenExpr, thenCont) = parseExpr(condCont.drop(1))
    if thenCont.head != ElseToken then
      throw IllegalStateException("Expected `else` in if expression")
    else
      val (elseExpr, elseCont) = parseExpr(thenCont.drop(1))
      (If(condExpr, thenExpr, elseExpr), elseCont)

简单说的话，这里用一个二元组来同时存放parse的产物和剩余的token列表，相当于把副作用移到返回值里面了。首先假设tokens的第一项是if，这个是上层语法规则检测到再调用现在的parseIf的，虽说在parseIf里面检测然后抛出异常也可以就是了……然后调用parseExpr，得到parseExpr的产物和剩下的tokens后，检测thentoken之后再调用一次parseExpr，再照样子处理else部分，就行了。

这个代码稍显冗长，因为我们并不想依赖任何副作用，以保持纯函数风格——之后会有用。另外，也会注意到，这里出现了走楼梯一样的模式，好几个if逐个嵌套起来了，而且，每个if里面都会产生新的二元组，并且每个二元组都只使用一次。

这大概就是用纯函数式风格重新手写递归下降语法的思路了。有了这个思路的话，按理来说，任何的LL(1)语法也都能解决了吧。

那么回到四则运算的问题。很显然，在设计一个编程语言的时候，会希望支持的，不仅仅是四则运算，而是可以任意组合的多层运算规则吧。每层运算都是类似加减乘除那样，按照优先级和括号来计算的，但是，加减乘除有两级，而一个复杂一点的语言可能会有更多的等级。

于是首先设计优先级表格：

val binOps = Map(
  0 -> List(Logical.EQ, Logical.NEQ),
  1 -> List(Logical.LT, Logical.LE),
  2 -> List(Arith.ADD, Arith.SUB),
  3 -> List(Arith.MULT, Arith.DIV, Arith.MOD),
)

然后就该设计bnf语法了，这一步不难，虽然可能没那么直观：

expr ::= expr1
exprN ::= exprN+1 exprN'
exprN' ::= <op-N> exprN+1 exprN' | {}
exprMAX ::= literal | ( expr )

转化为Scala的递归下降实现会稍微绕一点，不过也不至于太复杂：

def parseExprOfLevel(level: Int, tokens: List[Token]): (Expr, List[Token]) =
  val (factorExp, afterFactor) =
    if level < (binOps.size - 1) then parseExprOfLevel(level + 1, tokens) else parseTerm(tokens)
  if afterFactor.isEmpty then
    (factorExp, afterFactor)
  else
    val (subOpt, afterSub) = parseExprSubOfLevel(level, afterFactor)
    subOpt match
      case Some(o, right) =>
        o match
          case binary: ArithOp => (BinArith(binary, factorExp, right), afterSub)
          case logical: LogicalOp => (BinLogic(logical, factorExp, right), afterSub)
      case None => (factorExp, afterFactor)

  
def parseExprSubOfLevel(level: Int, tokens: List[Token]): (Option[(Op, Expr)], List[Token]) =
  if tokens.isEmpty then
    throw IllegalStateException("expect a complement of expr")
  else tokens.head match
    case OperToken(o: Op) if binOps(level).contains(o) =>
      val (factorExp, after) = if level < (binOps.size - 1) then parseExprOfLevel(level + 1, tokens.drop(1)) else parseTerm(tokens.drop(1))
      if after.isEmpty then
        (Some(o, factorExp), after)
      else
        val (nextSubOpt, nextAfter) = parseExprSubOfLevel(level, after)
        nextSubOpt match
          case Some(innerOp, rightExp) =>
            innerOp match
              case binary: ArithOp => (Some(o, BinArith(binary, factorExp, rightExp)), nextAfter)
              case logical: LogicalOp => (Some(o, BinLogic(logical, factorExp, rightExp)), nextAfter)
          case _ => (Some(o, factorExp), after)
    case _ => (None, tokens)

这里我用了Option来表达helper规则，因为helper规则既可以套起来，也可以不消耗任何token而直接返回，正好用Option的Some和None就很合适了，同时二元组的第二位也能够按照具体情况来选择返回原tokens列表的后面部分或者完整的列表，来模拟「消耗」和「不消耗」这两种操作。

这里引入的level参数，也就通过跟字典的大小做比较和查表，来提供一种动态扩展规则的可能性，而不是把加减乘除等操作硬编码进语法产生式里。剩下的，peek和模式匹配，也算是函数式的基础操作了吧。

那么实现了四则运算后，基于类似的思路，也可以实现其他的语法，例如tuple的语法，乃至于用LL(1)实现整个编程语言的parser，这里就不展开了。

不过总体来说，这个实现倒是简单粗暴，但也有不少缺点，首先就是重复代码和模式奇多，行数特别长，感觉就很难读。另外，这里也有不少「潜规则」需要开发者自己去注意和维护，比如tokens的peek和eat的区别，比如遇到空tokens的处理，再比如说二元组的第二项是需要手动去填充的。虽然手动填充可以让我们有完全的控制权，但是这也让代码难以检查和维护了吧。

这些，也就是下一次我们会回顾的问题。不过总的来说，作为递归下降算法的命令式实现，这一个实现倒是满足Scala的纯函数式编程的要求，因为它既没有任何副作用，也不依赖可变变量，每个函数的输出在给定输入的时候都是确定，可预测的。

也许这也是一个不错的直觉吧。