Scala自定义Packrat Parser匹配完输入后无限挂起问题排查

问题现象 #

自定义Packrat解析器处理自定义Token时，所有Token已被成功匹配，但程序无限挂起。将block的返回类型从PackratParser[Statement]改为Parser[Statement]后，程序正常运行并退出。

原代码 #

import scala.util.parsing.combinator.{PackratParsers, Parsers}
import scala.util.parsing.input.{NoPosition, Position, Positional, Reader}

sealed trait MyToken extends Positional
case class STMT_START(str: String) extends MyToken
case class STMT_END(str: String) extends MyToken

case class Start(str: String) extends MyToken
case class End(str: String) extends MyToken
case class Statement(tokens: Seq[Start], endTokens: Seq[End]) extends MyToken
case class AllStatements(stmts: Seq[Statement]) extends MyToken

class MyParser extends Parsers with PackratParsers {
  override type Elem = MyToken

  class TokenReader(tokens: Seq[MyToken]) extends Reader[MyToken] {
    override def first: MyToken = tokens.head
    override def atEnd: Boolean = tokens.isEmpty
    override def pos: Position =
      tokens.headOption.map(_.pos).getOrElse(NoPosition)
    override def rest: Reader[MyToken] = new TokenReader(tokens.tail)
  }

  // 原定义：返回PackratParser导致挂起
  def block: PackratParser[Statement] = {
    positioned {
      statementStart ~ statementEnd ^^ {
        case STMT_START(str) ~ STMT_END(endStr) ⇒
          Statement(
            Start(str) :: Nil,
            End(endStr) :: Nil
          )
      }
    }
  }

  def myexpressions: PackratParser[AllStatements] = {
    rep(block) ^^ { exprs ⇒
      println(s"matched expressions - expr $exprs ")
      AllStatements(exprs)
    }
  }

  def statementStart: PackratParser[STMT_START] =
    positioned {
      accept(
        "statementStart",
        {
          case jj @ STMT_START(_) =>
            println(s"PARSE: statementStart $jj")
            jj
        }
      )
    }

  def statementEnd: PackratParser[STMT_END] =
    positioned {
      accept(
        "statementEnd",
        {
          case jj @ STMT_END(_) =>
            println(s"PARSE: statementEnd $jj")
            jj
        }
      )
    }

  def parse[T](tokens: List[MyToken], func: Input ⇒ ParseResult[T]): Unit = {
    val reader = new PackratReader(new TokenReader(tokens))
    func(reader) match {
      case NoSuccess(msg, _) ⇒
        println(s"Failed $msg")
      case Success(result, next) ⇒
        if (next.atEnd) println(s"result of parsing - $result")
        else println("end of input expected")
    }
  }
}

object ParserTest {
  def main(args: Array[String]): Unit = {
    val test = new MyParser
    val tokens = List(
      STMT_START("   started"),
      STMT_END("bla"),
      STMT_START("   completed"),
      STMT_END("bla")
    )
    test.parse(tokens, test.myexpressions)
  }
}

原输出 #

PARSE: statementStart STMT_START(   started)
PARSE: statementEnd STMT_END(bla)
PARSE: statementStart STMT_START(   completed)
PARSE: statementEnd STMT_END(bla)

（程序在此处无限挂起）

修改后的关键代码 #

将block的返回类型改为普通Parser：

def block: Parser[Statement] = {
  positioned {
    statementStart ~ statementEnd ^^ {
      case STMT_START(str) ~ STMT_END(endStr) ⇒
        Statement(
          Start(str) :: Nil,
          End(endStr) :: Nil
        )
    }
  }
}

修改后的输出 #

PARSE: statementStart STMT_START(   started)
PARSE: statementEnd STMT_END(bla)
PARSE: statementStart STMT_START(   completed)
PARSE: statementEnd STMT_END(bla)
matched expressions - expr List(Statement(List(Start(   started)),List(End(bla))), Statement(List(Start(   completed)),List(End(bla)))) 
result of parsing - AllStatements(List(Statement(List(Start(   started)),List(End(bla))), Statement(List(Start(   completed)),List(End(bla)))))

原因分析 #

Scala的PackratParsers核心依赖**记忆化（Memoization）**机制：它会缓存每个输入位置上解析器的解析结果，避免重复解析，从而解决普通递归下降解析的左递归问题。

问题出在positioned组合子与PackratParser的结合上：

1. positioned的作用是为解析结果设置位置信息，但它的实现会返回一个普通的Parser，而非PackratParser。当你把block定义为PackratParser时，实际上是把positioned返回的普通Parser隐式转换为PackratParser，但这个转换后的解析器并没有正确集成到Packrat的记忆化机制中。
2. 当rep(block)尝试匹配时，因为block的记忆化缓存失效，解析器无法确认当前输入位置已经无法匹配新的block，会不断重复尝试解析，最终陷入无限循环——即使所有Token已经匹配完成，它仍在尝试匹配更多的block实例。
3. 当把block改为普通Parser时，rep使用的是普通递归下降解析的逻辑：一旦无法匹配新的block，就会停止尝试，不会陷入循环。

另外需要注意：PackratParser的记忆化是基于输入位置的，而positioned会修改元素的位置属性，这会导致解析器误判位置状态，进一步加剧缓存失效的问题，使得循环无法终止。

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