स्कैला रेगेक्सपार्स में गैर-लालची मिलान

Question

मान लीजिए कि मैं स्कैला में एक प्राथमिक एसक्यूएल पार्सर लिख रहा हूं। कैसे मैं ~ tokens में rep(token) की वजह से पूरे वाक्यांश ऊपर gobbling से selectclause रोकूँ

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 मिलान करने के लिए कोशिश कर रहा है, मैं निम्नलिखित है?

दूसरे शब्दों में, मैं स्कैला में गैर-लालची मिलान कैसे निर्दिष्ट करूं?

स्पष्टीकरण के लिए, मुझे पूरी तरह से पता है कि मैं स्ट्रिंग पैटर्न के भीतर मानक गैर-लालची वाक्यविन्यास (*?) या (+?) का उपयोग कर सकता हूं, लेकिन मुझे आश्चर्य हुआ कि उच्च स्तर पर इसे निर्दिष्ट करने का कोई तरीका है या नहीं डीफ टोकन के अंदर। उदाहरण के लिए, अगर मैं इस तरह टोकन परिभाषित किया था:

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

फिर मैं कैसे प्रतिनिधि (टोकन) डीईएफ़ टोकन के अंदर के लिए गैर लालची मिलान निर्दिष्ट कर सकते हैं?

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