14

Scala で初歩的な SQL パーサーを作成しているとします。私は次のものを持っています：

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
}

selectstatement を に対して一致させようとするとき、 inSELECT foo FROM barのために selectclause がフレーズ全体を飲み込んでしまうのを防ぐにはどうすればよいですか? rep(token)~ tokens

言い換えれば、Scala で非貪欲なマッチングを指定するにはどうすればよいでしょうか?

明確にするために、標準の非貪欲な構文 (*?) または (+?) を文字列パターン自体で使用できることを十分に認識していますが、def トークン内のより高いレベルでそれを指定する方法があるかどうか疑問に思いました。たとえば、次のようにトークンを定義したとします。

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

次に、def トークン内の rep(token) に対して貪欲でないマッチングを指定するにはどうすればよいですか?

4

1 に答える 1

13

成功した一致は再試行されないため、簡単ではありません。たとえば、次のように考えてください。

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)
}
于 2011-10-18T22:26:03.590 に答える