Scala中的非貪婪匹配RegexParsers

Question

假設我在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 foo FROM bar selectstatement，我該如何防止吞噬了整句話的selectclause由於~ tokens的rep(token)？

換句話說，我該如何在Scala中指定非貪婪匹配？爲了澄清，我完全知道我可以在字符串模式本身中使用標準的非貪婪語法（*？）或（+？），但是我想知道是否有辦法在更高級別指定它在def令牌中。例如，如果我是這樣定義的標記：

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

然後，我怎麼可以指定代表（令牌）DEF令牌內非貪婪匹配？

Answer 1

不容易，因爲成功的匹配不會重試。舉個例子：

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