如何使我的解析器支持逻辑运算和不区分大小写的单词？

Question

最近在学习Scala解析器组合器。我想解析给定字符串中的 key 。例如，

val expr1 = "local_province != $province_name$ or city=$city_name$ or people_number<>$some_digit$"

// ==> List("local_province", "city", "people_number")

val expr2 = "(local_province=$province_name$)"

// ==> List("local_province")

val expr3 = "(local_province=$province_name$ or city=$city_name$) and (lib_name=$akka$ or lib_author=$martin$)"

// ==> List("local_province", "city", "lib_name", "lib_author")

试用

import scala.util.parsing.combinator.JavaTokenParsers

class KeyParser extends JavaTokenParsers {
  lazy val key = """[a-zA-Z_]+""".r
  lazy val value = "$" ~ key ~ "$"
  lazy val logicOps = ">" | "<" | "=" | ">=" | "<=" | "!=" | "<>"
  lazy val elem: Parser[String] = key <~ (logicOps  ~ value)
  lazy val expr: Parser[List[String]] =
    "(" ~> repsep(elem, "and" | "or") <~ ")" | repsep(elem, "and" | "or")

  lazy val multiExpr: Parser[List[String]] =
    repsep(expr, "and" | "or") ^^ { _.foldLeft(List.empty[String])(_ ++ _) }
}

object KeyParser extends KeyParser {
  def parse(input: String) = parseAll(multiExpr, input)
}

这是我在 Scala REPL 中的测试

KeyParser.parse(expr1)

[1.72] failure: $' expected but >' found

KeyParser.parse(expr2)

[1.33] parsed: List(local_province)

KeyParser.parse(expr3)

[1.98] parsed: List(local_province, city, lib_name, lib_author)

我注意到 KeyParser 仅适用于 "="，它不支持像 "(local_province<>$province_name$ AND city!=$city_name$)" 这样包含 "<> | !=" 和“AND”的情况。

所以想知道怎么修改。

Answer 1

I notice that the KeyParser only works for "="

这不完全正确。它也适用于 !=、< 和 >。它不适用于 >=、<= 和 <>.

更一般地说，它不适用于那些有前缀的运算符出现在它们之前的备选列表中。即>=不匹配，因为>出现在它前面，是它的前缀。

那么为什么会这样呢？ | 运算符创建一个解析器，如果成功则生成左解析器的结果，否则生成右解析器的结果。因此，如果您有一个 | 链，您将获得该链中第一个可以匹配当前输入的解析器的结果。因此，如果当前输入是 <>$some_digit$，解析器 logicOps 将匹配 < 并留下 >$some_digit$ 作为剩余输入。所以现在它尝试将 value 与该输入匹配并失败。

为什么回溯在这里没有帮助？因为 logicOps 解析器已经成功，所以无处可回溯。如果解析器的结构如下：

lazy val logicOpAndValue = ">" ~ value | "<" ~ value | "=" ~ value |
                           ">=" ~ value | "<=" ~ value | "!=" ~ value |
                           "<>" ~ value
lazy val elem: Parser[String] = key <~ logicOpAndValue

然后会发生以下情况（当前输入为 <>$some_digit$）：

">" 与当前输入不匹配，因此转到下一个备选方案
"<" 确实与当前输入匹配，因此请尝试将 ~ 的右操作数（即 value）与当前输入 >$some_digit$ 匹配。这失败了，所以继续下一个替代方案。
...一堆不匹配的替代品...
"<>" 确实匹配当前输入，因此请尝试 ~ 的右操作数。这也符合。成功！

但是在您的代码中，~ value 在备选方案列表之外，而不是在每个备选方案内。因此，当解析器失败时，我们不再处于任何替代方案中，因此没有下一个替代方案可以尝试，它就失败了。

当然，将 ~ value 移动到备选方案中并不是一个真正令人满意的解决方案，因为它非常丑陋，而且在一般情况下不太易于维护。

一种解决方案是将较长的运算符简单地移动到备选方案的开头（即 ">=" | "<=" | "<>" | ">" | "<" | ...）。这样 ">" 和 "<" 只有在 ">="、"<=" 和 "<>" 已经失败时才会尝试。

一个更好的解决方案是使用 ||| 代替，它不依赖于备选方案的顺序，因此不易出错。 ||| 的工作方式与 | 类似，只是它会尝试所有备选方案，然后 returns 最长的成功结果 - 而不是第一个。

PS：这与您的问题无关，但您目前正在限制括号的嵌套深度，因为您的语法不是递归的。要允许无限嵌套，您需要 expr 和 multiExpr 规则如下所示：

lazy val expr: Parser[List[String]] =
  "(" ~> multiExpr <~ ")" | elem
lazy val multiExpr: Parser[List[String]] =
  repsep(expr, "and" | "or") ^^ { _.foldLeft(List.empty[String])(_ ++ _) }

不过，我建议将 expr 重命名为 primaryExpr，将 multiExpr 重命名为 expr。

_.foldLeft(List.empty[String])(_ ++ _) 也可以更简洁地表示为 _.flatten.

如何使我的解析器支持逻辑运算和不区分大小写的单词？

How to make my parser support logic operations and word case-insensitive?

scala

parsing

parser-combinators

试用