如何在scala-parser-combinators中实现非贪婪重复匹配？

核心思路 #

问题本质是rep组合子默认贪婪匹配，且普通行的匹配规则覆盖了目标整数行的规则，导致目标行被提前消耗。通用解法是在匹配每一行普通内容前，先做负向预判：只要当前行不是目标整数行，才进行普通行消耗，这个逻辑可以通过not组合子实现。
not组合子不会消耗输入内容，仅做规则校验：如果输入匹配传入的解析器则返回失败，反之返回成功，刚好符合预判需求。

修改代码 #

仅需要调整meaning解析器的定义即可：

def meaning: Parser[Int] = rep(not(intLine) ~> (textLine | blankLine)) ~> intLine

逻辑说明 #

1. 每次进入rep循环时，先执行not(intLine)校验：如果当前输入匹配intLine，校验失败，rep循环自动终止
2. 校验通过后才会消耗普通行/空行，不会提前吃掉目标整数行
3. rep循环终止后，剩下的输入刚好交给后面的intLine解析，就能拿到结果42

用到的组合子说明 #

• 仅需要not组合子即可满足需求
• guard是正向预判组合子，逻辑和not相反，不适用于此场景
• ~!是禁止回溯的定序组合子，这个场景不需要禁止回溯，无需使用

修改后运行代码即可正常输出42。

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