Scala中的递归正则表达式

Question

我有一个Scala方法，目前接受输入并将其与正则表达式匹配：

def valiateMap(mapDef : String) : String = {
    val mapRegex = "map<([int,string,date]),([int,string,date])>".r
    mapDef match {
        case mapRegex(keyGroup, valueGroup)   =>    "Yes, we have a match!"
        case _                                =>    "'Fraid not."
    }
}

如您所见，传入各种值将产生以下结果：

• validateMap("map<int,date>") -> "是的，我们有一个匹配！"
• validateMap("fizzbuzz") -> "'很遗憾，没有匹配。"
• validateMap("map<int,fizz>") -> "'很遗憾，没有匹配。"（fizz不符合正则表达式的规定）

现在我需要将这个正则表达式递归，以便“valueGroup”（第2组）的值本身可以是一个地图，其遵循与上述相同的正则表达式。那张地图也可能会有一个地图作为其值，该地图需要遵守相同的正则表达式。以此类推。

因此，我需要修改正则表达式（和/或代码）以处理以下输入：

• validateMap("map<int,map<date,string>>") -> "是的，我们有一个匹配！"
• validateMap("map<int,map<int,map<int,string>>>") -> "是的，我们有一个匹配！"
• validateMap("map<int,map<fizz,date>>") -> "'很遗憾，没有匹配。"

关键是这需要是（可能）无限递归的，并处理任何数量的内部嵌套映射。

有任何想法如何实现这一点吗？

- smeeb

---

阅读 RegEx 匹配开放标签，除了 XHTML 自包含标签，然后决定这是一个不好的想法，并选择 https://github.com/tpolecat/atto 或 https://github.com/lihaoyi/fastparse 中的一个。 - Reactormonk

啊？什么？！？！ - smeeb

好的，不知怎么忘了链接：https://dev59.com/X3I-5IYBdhLWcg3wq6do - Reactormonk

Answer 1

正则表达式是一种形式化的语言，用于匹配输入符号串中某些类型的模式。作为基本定义，正则表达式不支持递归嵌套模式的一种类型。

@Reactormonk在他们的评论中提供的链接涉及到尝试使用正则表达式正确解析HTML的类似问题，由于存在递归嵌套模式匹配，这种方法会失败。

既然正则表达式是错误的工具，您可以考虑使用解析器组合器。虽然这将更复杂，但它可以处理更一般的情况。Scala内置了一个API，或者您可以使用第三方库fastparse。

- hayden.sikh

Answer 2

试试这个：

def validateMap(mapDef : String) : String = {
  val terminal = "map<(int|string|date),(int|string|date)>".r
  val arbitrary = "map<(int|string|date),(.*)>".r
  mapDef match {
    case terminal(keyGroup, valueGroup)   =>    "Yes, we have a match!"
    case arbitrary(keyGroup, valueGroup)  =>    validateMap(valueGroup)
    case _                                =>    "'Fraid not."
  }
}

- Nyavro