Scala RegexParsers中的非贪婪匹配

Question

Scala RegexParsers中的非贪婪匹配

14

假设我正在使用Scala编写一个基本的SQL解析器。我有以下代码：

class Arith extends RegexParsers {
    def selectstatement: Parser[Any] = selectclause ~ fromclause
    def selectclause: Parser[Any] = "(?i)SELECT".r ~ tokens
    def fromclause: Parser[Any] = "(?i)FROM".r ~ tokens
    def tokens: Parser[Any] = rep(token) //how to make this non-greedy?
    def token: Parser[Any] = "(\\s*)\\w+(\\s*)".r
}

在尝试将 select 语句与 SELECT foo FROM bar 匹配时，如何避免由于 rep(token) 中的 ~ tokens 导致选择子句吞噬整个短语？换句话说，在 Scala 中如何指定非贪婪匹配？

为了澄清，我完全知道可以在字符串模式本身中使用标准的非贪婪语法 (*?) 或 (+?) ，但我想知道是否有办法在 def tokens 的更高级别上指定它。例如，如果我定义了这样的 token：

def token: Parser[Any] = stringliteral | numericliteral | columnname

那么我如何在def tokens内指定rep（token）的非贪婪匹配？

- Magnus

看起来我们正在处理 PEG 功能：虽然正则表达式匹配器可能会开始贪婪地匹配，但如果它们失败并且 CFG 尝试每种可能性，则会回溯并尝试更短的匹配，而 PEG 的 *、+ 和 ? 运算符始终表现出贪婪行为，尽可能消耗尽量多的输入并且不进行回溯：表达式 a* 将始终消耗在输入字符串中连续可用的 a，导致 (a* a) 总是失败。 - Little Alien

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel C. Sobral · Accepted Answer

不容易，因为成功的匹配不会重试。例如：

object X extends RegexParsers {
  def p = ("a" | "aa" | "aaa" | "aaaa") ~ "ab"
}

scala> X.parseAll(X.p, "aaaab")
res1: X.ParseResult[X.~[String,String]] = 
[1.2] failure: `ab' expected but `a' found

aaaab
 ^

第一个匹配成功了，位于括号内的解析器进行了下一步。那个失败了，所以p也失败了。如果p是备选匹配的一部分，那么将尝试备选方案，因此关键是要产生能够处理这种情况的东西。

假设我们有以下内容：

def nonGreedy[T](rep: => Parser[T], terminal: => Parser[T]) = Parser { in =>
  def recurse(in: Input, elems: List[T]): ParseResult[List[T] ~ T] =
    terminal(in) match {
      case Success(x, rest) => Success(new ~(elems.reverse, x), rest)
      case _ => 
        rep(in) match {
          case Success(x, rest) => recurse(rest, x :: elems)
          case ns: NoSuccess    => ns
        }
    }

  recurse(in, Nil)
}

您可以像这样使用它：

def p = nonGreedy("a", "ab")

顺便说一下，我发现查看其他事物的定义对于尝试想出像上面的nonGreedy这样的东西是有帮助的。特别是，请查看rep1是如何定义的，以及它是如何更改以避免重新评估其重复参数的-相同的方法可能对nonGreedy也有用。

这是一个完整的解决方案，并进行了一些更改，以避免消耗“终端”。

trait NonGreedy extends Parsers {
    def nonGreedy[T, U](rep: => Parser[T], terminal: => Parser[U]) = Parser { in =>
      def recurse(in: Input, elems: List[T]): ParseResult[List[T]] =
        terminal(in) match {
          case _: Success[_] => Success(elems.reverse, in)
          case _ => 
            rep(in) match {
              case Success(x, rest) => recurse(rest, x :: elems)
              case ns: NoSuccess    => ns
            }
        }

      recurse(in, Nil)
    }  
}

class Arith extends RegexParsers with NonGreedy {
    // Just to avoid recompiling the pattern each time
    val select: Parser[String] = "(?i)SELECT".r
    val from: Parser[String] = "(?i)FROM".r
    val token: Parser[String] = "(\\s*)\\w+(\\s*)".r
    val eof: Parser[String] = """\z""".r

    def selectstatement: Parser[Any] = selectclause(from) ~ fromclause(eof)
    def selectclause(terminal: Parser[Any]): Parser[Any] = 
      select ~ tokens(terminal)
    def fromclause(terminal: Parser[Any]): Parser[Any] = 
      from ~ tokens(terminal)
    def tokens(terminal: Parser[Any]): Parser[Any] = 
      nonGreedy(token, terminal)
}