Scala Parser Combinator布尔表达式解析递归栈溢出问题如何解决

问题根源 #

你遇到的是递归下降解析器的左递归问题：Scala 标准库默认的 Parser Combinator 是递归下降实现，无法处理规则定义中首个匹配项指向规则自身的场景。你修改后的逻辑中，boolExpression 优先调用andExpression，而andExpression的首个匹配项又是boolExpression，两个函数无限循环调用直接触发栈溢出。

解决方案 #

有两种常用的解决方式：

方式1：手动重构规则消除左递归 #

把表达式规则拆分为「原子项」和「带运算符的表达式」，确保每次匹配首个元素一定是不会递归的原子单元，从根源上避免左递归：

// 原子布尔字面量，无递归逻辑
def boolLiteral: Parser[BoolLiteral] = ("true" | "false") ^^ { s =>
  BoolLiteral(java.lang.Boolean.valueOf(s))
}

// And表达式改为：原子项 + 任意个 "and" + 原子项 的结构
def andExpression: Parser[BoolExpression] = (boolLiteral ~ rep("and" ~ boolLiteral)) ^^ {
  case head ~ rest => 
    // 用foldLeft拼接成嵌套的AndExpression结构，符合左结合逻辑
    rest.foldLeft(head: BoolExpression) {
      case (acc, _ ~ nextBool) => AndExpression(acc, nextBool)
    }
}

// 顶层表达式规则
def boolExpression: Parser[BoolExpression] = andExpression | boolLiteral

这种方式不依赖额外特性，同时可以天然支持true and false and true这类多and连接的表达式，结构符合布尔运算的左结合要求。

方式2：使用支持左递归的Packrat解析器 #

Scala Parser Combinator 提供了PackratParsers扩展，通过缓存解析结果避免重复递归，可以直接支持左递归规则，不需要修改原有规则结构：

1. 让你的解析器类继承PackratParsers特质
2. 把规则声明为lazy val，类型指定为PackratParser

import scala.util.parsing.combinator.PackratParsers
import scala.util.parsing.combinator.syntactical.StandardTokenParsers

class BoolParser extends StandardTokenParsers with PackratParsers {
  lazy val boolExpression: PackratParser[BoolExpression] = andExpression | boolLiteral
  lazy val andExpression: PackratParser[AndExpression] = (boolExpression ~ "and" ~ boolExpression) ^^ {
    case b1 ~ "and" ~ b2 => AndExpression(b1, b2)
  }
  lazy val boolLiteral: PackratParser[BoolLiteral] = ("true" | "false") ^^ { s =>
    BoolLiteral(java.lang.Boolean.valueOf(s))
  }
}

内容的提问来源于stack exchange，提问作者gefei