Non-chciwe dopasowanie w Scala RegexParsers

Question

Załóżmy, że piszę podstawowy parser SQL w Scala. Mam następujący:

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 
} 

Gdy próbuje dopasować SelectStatement przed SELECT foo FROM bar, w jaki sposób mogę zapobiec selectclause z wydziobujących całą frazę powodu rep(token) w ~ tokens?

Innymi słowy, w jaki sposób mogę określić dopasowanie nie będące chciwością w Scali?

Aby wyjaśnić, jestem w pełni świadomy, że mogę używać standardowej składni nie chciwy (*?) Lub (+?), W samej strukturze String, ale zastanawiałem się, czy istnieje sposób, aby określić ją na wyższym poziomie wewnątrz tokenów def. Na przykład, gdybym zdefiniowany znacznik tak:

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

Więc jak mogę określić non-chciwy dopasowanie dla rep (tokena) wewnątrz def tokeny?

Answer 1

Niełatwo, ponieważ pomyślne dopasowanie nie jest ponawiane. Rozważmy na przykład:

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 
^ 

Pierwszy mecz był udany, w parsera wewnątrz nawiasu, więc udał się do następnego. To się nie udało, więc nie udało się. Jeśli p byłby częścią alternatywnych dopasowań, alternatywa byłaby wypróbowana, więc sztuczka polega na stworzeniu czegoś, co poradzi sobie z takimi rzeczami.

Powiedzmy mamy to:

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

Następnie można go używać tak:

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

Nawiasem mówiąc, ja zawsze uważałem, że patrząc na to, jak inne rzeczy są zdefiniowane jest pomocne w próbując wymyślić powyższe informacje, takie jak nonGreedy. W szczególności spójrz, jak zdefiniowano rep1 i jak został zmieniony, aby uniknąć ponownej oceny jego parametru powtarzania - ta sama funkcja byłaby prawdopodobnie przydatna na nonGreedy.

Oto pełne rozwiązanie, z niewielką zmianą, aby uniknąć zużycia "terminala".

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