не жадное сопоставление в Scala RegexParsers - PullRequest
Новая
       16

не жадное сопоставление в Scala RegexParsers

14 голосов
/ 18 октября 2011

Предположим, я пишу элементарный парсер SQL в Scala.У меня есть следующее: 

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 сожрать всю фразу из-за rep(token) в ~ tokens?

Другими словами, как мне указать не жадное сопоставление в Scala?

Чтобы уточнить, я полностью осознаю, что могу использовать стандартный не жадный синтаксис (*?) Или (+?) внутри самого шаблона String, но мне было интересно, есть ли способ указать его на более высоком уровне внутри токенов def.Например, если я определил токен следующим образом: 

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

Тогда как я могу указать не жадное соответствие для rep (токена) внутри токенов def?

1 Ответ

12 голосов
/ 19 октября 2011

Не легко, потому что успешное совпадение не повторяется.Рассмотрим, например: 

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 было частью альтернативных совпадений, альтернатива была бы опробована, поэтому хитрость заключается в том, чтобы создать нечто, способное справиться с подобными вещами.

Предположим, у нас есть это:1010 * Затем вы можете использовать это следующим образом: 

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