kết hợp không tham lam trong Scala RegexParsers

Question

Giả sử tôi đang viết một trình phân tích cú pháp SQL thô sơ trong Scala. Tôi có những điều sau đây:

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 
} 

Khi cố gắng để phù hợp với selectstatement chống SELECT foo FROM bar, làm thế nào để ngăn chặn sự selectclause từ nuốt chửng toàn bộ cụm từ do rep(token) trong ~ tokens?

Nói cách khác, làm cách nào để chỉ định đối sánh không tham lam trong Scala?

Để làm rõ, tôi hoàn toàn biết rằng tôi có thể sử dụng cú pháp tiêu chuẩn không tham lam (*?) Hoặc (+?) Trong chính mẫu Chuỗi, nhưng tôi tự hỏi liệu có cách nào để chỉ định nó ở cấp cao hơn hay không bên trong def thẻ. Ví dụ: nếu tôi đã xác định mã thông báo như thế này:

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

Sau đó, làm cách nào tôi có thể chỉ định đối sánh không tham lam cho mã thông báo trong mã thông báo lỗi?

Answer 1

Không dễ dàng, vì kết quả khớp thành công không được thử lại. Hãy xem xét, ví dụ:

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 
^ 

Kết quả đầu tiên đã thành công, trong trình phân tích cú pháp bên trong dấu ngoặc đơn, vì vậy nó được chuyển sang bước tiếp theo. Điều đó không thành công, vì vậy p không thành công. Nếu p là một phần của các trận đấu thay thế, giải pháp thay thế sẽ được thử, vì vậy mẹo là tạo ra thứ gì đó có thể xử lý những thứ đó.

Hãy nói rằng chúng tôi có điều này:

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

Sau đó bạn có thể sử dụng nó như thế này:

def p = nonGreedy("a", "ab") 

Bằng cách này, tôi luôn luôn thấy rằng nhìn vào cách những thứ khác được định nghĩa là hữu ích trong việc cố gắng tìm ra những thứ như nonGreedy ở trên. Cụ thể, hãy xem cách rep1 được xác định và cách nó được thay đổi để tránh đánh giá lại thông số lặp lại của nó - điều tương tự có thể hữu ích trên nonGreedy.

Đây là giải pháp đầy đủ, với một chút thay đổi để tránh tiêu thụ "thiết bị đầu cuối".

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