Scala RegexParsers中的非贪婪匹配

发布时间：2020-12-16 09:18:15 所属栏目：安全来源：网络整理

导读：假设我正在 Scala中写一个基本的SQL解析器.我有以下几点： class Arith extends RegexParsers { def selectstatement: Parser[Any] = selectclause ~ fromclause def selectclause: Parser[Any] = "(?i)SELECT".r ~ tokens def fromclause: Parser[Any] = "(

假设我正在 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
}

当尝试将selectstatement与SELECT foo FROM bar匹配时,由于?令牌中的rep(令牌),如何防止selectclause从整个短语中移除？

换句话说,如何在Scala中指定非贪婪匹配？

为了澄清,我完全知道我可以在String模式本身内使用标准的非贪婪语法(*？)或(？),但是我想知道是否有一种方法可以在def令牌的更高级别上指定它.例如,如果我已经定义了这样的令牌：

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

那么如何在def令牌内部指定rep(token)的非贪婪匹配？

解决方法

不容易,因为没有重试成功的比赛.考虑一下,例如：

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")

顺便说一下,我总是发现,看看其他的东西是如何定义的,有助于想出一些像上面的非Greedy这样的东西.特别是,看看rep1是如何定义的,以及如何改变以避免重新评估其重复参数 – 同样的事情在非Greedy中可能会有用.

这是一个完整的解决方案,稍作改动以避免消耗“终端”.

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,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)
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!