Scala中用PackratParser构建布尔逻辑解析器的问题咨询

一、初始解析器无法处理无括号表达式的原因 #

你的初始语法存在歧义与左递归匹配冲突：

• and规则定义为operator ~ ANDT() ~ operator，而operator又包含node（即and/or）。当解析A == B AND C == D时，左边的operator会尝试匹配尽可能长的输入——它会优先把A == B AND C == D整个当作一个and节点，导致右边的operator没有剩余输入可匹配，最终解析失败。
• 添加operatorWithParens后，and的左右操作数被限制为带括号的表达式，括号明确分割了操作数边界，避免了operator的贪婪匹配，因此(A == B) AND (C == D)能正常解析。

二、左递归语法导致无限循环的原因 #

你添加的positioned包装破坏了PackratParser的记忆化（memoization）机制：
PackratParser支持左递归的核心是缓存每个位置的解析结果，避免重复递归。但positioned会为每个解析位置创建新的解析器实例，导致缓存失效——每次递归调用expr时，都会生成新的positioned(expr)解析器，无法复用之前的缓存结果，最终陷入无限递归循环。

三、解决方案 #

1. 修复无括号表达式解析：明确运算符优先级分层 #

正确的语法需要按优先级从低到高分层，让高优先级表达式作为低优先级运算符的操作数：

sealed trait Operator
case class And(left: Operator, right: Operator) extends Operator
case class Or(left: Operator, right: Operator) extends Operator
case class Not(opr: Operator) extends Operator
case class Equals(a: String, b: String) extends Operator
case class Greater(a: String, b: String) extends Operator
case class Less(a: String, b: String) extends Operator

// 假设已定义ANDT、ORT、NOTT、lparen、rparen等词法解析器
def program: Parser[Operator] = positioned(phrase(expr))

// 最低优先级：OR
def expr: PackratParser[Operator] = 
  (expr1 ~ ORT() ~ expr) ^^ { case l ~ _ ~ r => Or(l, r) } | expr1

// 中优先级：AND
def expr1: PackratParser[Operator] = 
  (expr2 ~ ANDT() ~ expr1) ^^ { case l ~ _ ~ r => And(l, r) } | expr2

// 高优先级：NOT
def expr2: PackratParser[Operator] = 
  (NOTT() ~ expr2) ^^ { case _ ~ o => Not(o) } | expr3

// 最高优先级：括号表达式、叶子节点（比较运算）
def expr3: PackratParser[Operator] = 
  lparen ~> expr <~ rparen | leaf

def leaf: PackratParser[Operator] = 
  (ident ~ "==" ~ ident) ^^ { case a ~ _ ~ b => Equals(a, b) } |
  (ident ~ ">" ~ ident) ^^ { case a ~ _ ~ b => Greater(a, b) } |
  (ident ~ "<" ~ ident) ^^ { case a ~ _ ~ b => Less(a, b) }

分层逻辑：

• expr处理OR，操作数为优先级更高的expr1
• expr1处理AND，操作数为优先级更高的expr2
• expr2处理NOT，操作数为优先级更高的expr3
• expr3处理括号和叶子节点，确保括号可包裹任意优先级表达式

2. 修复左递归无限循环：正确使用positioned #

不要把positioned直接包裹在左递归解析器（expr/expr1/expr2）上，仅在最外层program或叶子节点上使用：

• 示例中program用positioned包装，既保留错误定位功能，又不破坏内部递归解析器的记忆化。
• 若需要叶子节点的错误定位，可将positioned加到leaf规则：

def leaf: PackratParser[Operator] = positioned(
  (ident ~ "==" ~ ident) ^^ { case a ~ _ ~ b => Equals(a, b) } |
  (ident ~ ">" ~ ident) ^^ { case a ~ _ ~ b => Greater(a, b) } |
  (ident ~ "<" ~ ident) ^^ { case a ~ _ ~ b => Less(a, b) }
)

修改后，PackratParser的记忆化机制可正常工作，左递归不会引发无限循环，同时能正确解析无括号表达式，比如A == B AND C == D会被解析为And(Equals(A,B), Equals(C,D))。

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