coincidencia no codiciosa en Scala RegexParsers

Question

Supongamos que estoy escribiendo un analizador sintáctico de SQL rudimentario en Scala. Tengo el siguiente:

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 
} 

Al tratar de igualar selectstatement contra SELECT foo FROM bar, ¿cómo puedo evitar la selectclause de engullir toda la frase debido a la rep(token) en ~ tokens?

En otras palabras, ¿cómo especifico la coincidencia no codiciosa en Scala?

Para aclarar, soy plenamente consciente de que puedo usar la sintaxis estándar no codiciosa (*?) O (+?) Dentro del patrón String, pero me pregunto si hay una forma de especificarlo en un nivel superior dentro def tokens. Por ejemplo, si yo hubiera definido token de la siguiente manera:

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

Entonces, ¿cómo puedo especificar coincidencia no expansivo para el representante (token) en el interior fichas def?

Answer 1

No es fácil, porque una coincidencia exitosa no se reintenta. Consideremos, por ejemplo:

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 
^ 

El primer partido tuvo éxito, en analizador entre paréntesis, por lo que procedieron a la siguiente. Ese falló, por lo que p falló. Si p fue parte de coincidencias alternativas, se probaría la alternativa, por lo que el truco es producir algo que pueda manejar ese tipo de cosas.

Digamos que tenemos esto:

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

A continuación, puede utilizar de esta manera:

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

Por cierto, siempre he encontrado que mirar cómo otras cosas se definen es útil tratando de llegar a cosas como nonGreedy arriba. En particular, observe cómo se define rep1 y cómo se modificó para evitar la reevaluación de su parámetro de repetición; lo mismo probablemente sea útil en nonGreedy.

Aquí hay una solución completa, con un pequeño cambio para evitar consumir el "terminal".

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