스칼라 RegexParsers에서 욕심없는 일치

Question

내가 스칼라에서 기본적인 SQL 파서를 작성한다고 가정 해 보겠습니다. 내가 인해 ~ tokens의 rep(token)에 전체 문구를 삼키고에서 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에 대한 SELECT 문을 일치하려고 할 때 : 나는 다음 있나요?

즉, 스칼라에서 비 욕심 많은 일치를 지정하려면 어떻게해야합니까?

분명히하기 위해 String 패턴 자체에서 표준이 아닌 greedy 구문 (*?) 또는 (+?)을 사용할 수 있다는 것을 완전히 알고 있지만 상위 수준에서 지정하는 방법이 있는지 궁금해했습니다. 내부 def 토큰. 예를 들어,이 같은 토큰을 정의했다면 :

내가 데프 토큰 내부 담당자 (토큰) 비 욕심 일치를 지정할 수있는 방법을 다음

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

?

Answer 1

쉽게 일치가 성공하지 않기 때문에 쉽지 않습니다. 예를 들어, 다음과 같이 고려하십시오.

첫 번째 일치가 괄호 안에있는 구문 분석기에서 성공 했으므로 다음으로 진행했습니다. 그 중 하나가 실패 했으므로 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에서 유용 할 것입니다.

"터미널"을 사용하지 않도록 약간의 변경이 추가 된 완전한 솔루션입니다. 우리가 (https://en.wikipedia.org/wiki/Parsing_expression_grammar#Operational_interpretation_of_parsing_expressions) 여기 [PEG 기능과 함께] 다루고있는 것처럼

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