Не легко, потому что успешное совпадение не повторяется. Рассмотрим, например:
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)
}
person
Daniel C. Sobral
schedule
18.10.2011
*
,+
и?
всегда ведут себя жадно, потребляя как можно больше входных данных и никогда не откатываясь: выражениеa*
всегда будет потреблять как можно больше a как последовательно доступны во входной строке, что всегда приводит к сбою(a* a)
. - person Little Alien   schedule 02.11.2016