Scala RegexParsers'da açgözlü olmayan eşleştirme

Question

Scala'da ilkel bir SQL ayrıştırıcısı yazdığımı varsayalım. Ben nedeniyle ~ tokens içinde rep(token) için tüm öbeği tamamını işgal dan selectclause önlemek, nasıl

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 karşı selectstatement maç için çalışırken: Aşağıdaki var?

Diğer bir deyişle, Scala'da açgözlü olmayan eşleştirmeyi nasıl belirleyebilirim?

Netleştirmek gerekirse, standart olmayan açgözlü sözdizimini (*?) Veya (+?) String deseninin kendisinde kullanabileceğimin tamamen farkındayım, ancak daha yüksek bir düzeyde belirtmenin bir yolu olup olmadığını merak ettim def tokenleri içinde. Örneğin, böyle belirteci tanımlanmış olsaydı:

def jeton içine rep (belirteç) olmayan açgözlü eşleme belirtebilirsiniz nasıl Sonra

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

?

Answer 1

Başarılı bir eşleşme yeniden denenmediği için kolay değil.

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 
^ 

ilk maç parantez içindeki ayrıştırıcı, başarılı oldu, bu yüzden bir sonrakine devam: örneğin, düşünün. Bu başarısız oldu, bu yüzden p başarısız oldu. p alternatif eşleşmelerin bir parçası olsaydı, alternatif denenecek, bu yüzden hile bu tür şeyleri başarabilecek bir şey üretmek.

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

Daha sonra, bu gibi kullanabilirsiniz:

Şimdi bu var diyelim

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

arada, ben her zaman ne kadar başka şeyler tanımlanır bakarak yardımcı olduğunu bulduk Yukarıdaki nonGreedy gibi şeyler ile gelmeye çalışıyor. Özellikle, rep1'un nasıl tanımlandığına ve tekrarlama parametresini yeniden değerlendirmekten kaçınmak için nasıl değiştirildiğine bakın - aynı şey muhtemelen nonGreedy'da yararlı olacaktır.

"Terminal" tüketimini önlemek için küçük bir değişiklikle birlikte tam bir çözüm. Biz (https://en.wikipedia.org/wiki/Parsing_expression_grammar#Operational_interpretation_of_parsing_expressions) burada [PEG özelliği ile] ilgileniyor gibi

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