corrispondenza non avida in Scala RegexParsers

Question

Supponiamo che sto scrivendo un parser SQL rudimentale in Scala. Ho il seguente:

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 
} 

Quando si cerca di abbinare selectstatement contro SELECT foo FROM bar, come faccio a impedire che il selectclause dal inghiottendo l'intera frase a causa della rep(token) in ~ tokens?

In altre parole, come si specifica la corrispondenza non avida in Scala?

Per chiarire, sono pienamente consapevole che posso utilizzare la sintassi non greedy standard (*?) O (+?) All'interno del pattern String stesso, ma mi chiedevo se c'è un modo per specificarlo a un livello superiore all'interno di token di sicurezza. Ad esempio, se avessi definita del token in questo modo:

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

Allora come posso specificare corrispondenza non avido per il rappresentante (token) all'interno gettoni def?

Answer 1

Non facile, perché non viene ritentato un incontro riuscito. Si consideri, ad esempio:

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 
^ 

La prima partita ha avuto successo, nel parser all'interno tra parentesi, quindi è proceduto a quello successivo. Quello fallito, quindi p fallito. Se p fosse parte di corrispondenze alternative, l'alternativa sarebbe provata, quindi il trucco è produrre qualcosa che possa gestire quel genere di cose.

Diciamo che abbiamo questo:

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

È quindi possibile utilizzare in questo modo:

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

A proposito, ho sempre trovato che guardando a come le altre cose sono definiti è utile per provando a inventare cose come nonGreedy sopra. In particolare, guarda come è stato definito rep1 e come è stato modificato per evitare di rivalutare il suo parametro di ripetizione: la stessa cosa sarebbe probabilmente utile su nonGreedy.

Ecco una soluzione completa, con un piccolo cambiamento per evitare di consumare il "terminale".

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