Grammars, Scala Parsing Combinators and Orderless Sets

Question

Tôi đang viết một ứng dụng sẽ thực hiện các chuỗi "lệnh" khác nhau. Tôi đã nhìn vào thư viện tổ hợp Scala để mã hóa các lệnh. Tôi tìm thấy trong rất nhiều trường hợp tôi muốn nói: "Những thẻ này là một bộ đơn đặt hàng, và vì vậy chúng có thể xuất hiện theo bất kỳ thứ tự nào, và một số có thể không xuất hiện".

Với kiến ​​thức hiện tại của tôi về văn phạm tiếng tôi sẽ phải xác định tất cả các kết hợp của các chuỗi như vậy (giả ngữ pháp):

command = action~content 
action = alphanum 
content = (tokenA~tokenB~tokenC | tokenB~tokenC~tokenA | tokenC~tokenB~tokenA .......) 

Vì vậy, câu hỏi của tôi là, xem xét tokenA-C là duy nhất, là có một cách ngắn để xác định một tập hợp bất kỳ thứ tự nào bằng cách sử dụng ngữ pháp?

Answer 1

Có nhiều cách xung quanh. Hãy xem trình phân tích cú pháp here, ví dụ. Nó chấp nhận 4 số được xác định trước, có thể xuất hiện ở bất kỳ số nào khác, nhưng phải xuất hiện một lần và chỉ một lần.

OTOH, bạn có thể viết một combinator, nếu mô hình này xảy ra thường xuyên:

def comb3[A](a: Parser[A], b: Parser[A], c: Parser[A]) = 
    a ~ b ~ c | a ~ c ~ b | b ~ a ~ c | b ~ c ~ a | c ~ a ~ b | c ~ b ~ a 

Answer 2

Tất nhiên, bạn có thể viết quy tắc kết hợp thực hiện điều này cho bạn nếu bạn gặp phải tình huống này thường xuyên.

Mặt khác, có thể tùy chọn tồn tại để làm cho "tokenA..C" chỉ là "dấu hiệu" và sau đó phân biệt bên trong xử lý các "token"

Answer 3

Tôi không biết những loại cấu trúc bạn muốn để hỗ trợ, nhưng tôi thu thập bạn nên xác định một ngữ pháp cụ thể hơn. Từ nhận xét của bạn cho câu trả lời khác:

todo nhắn: link Todo lớp cơ sở dữ liệu

Tôi đoán bạn không muốn chấp nhận một cái gì đó như tin nhắn

todo: cơ sở dữ liệu để Todo liên kết lớp

Vì vậy, bạn có thể muốn xác định một số từ khóa cấp thư như "liên kết" và "thành" ...

def token = alphanum~':'~ "link" ~ alphanum ~ "class" ~ "to" ~ alphanum 
    ^^ { (a:String,b:String,c:String) => /* a == "message", b="Todo", c="database" */ } 

Tôi đoán bạn sẽ phải xác định ngữ pháp của bạn ở cấp đó.

Answer 4

tôi sẽ không cố gắng để thực thi yêu cầu này cú pháp. Tôi muốn viết một sản phẩm thừa nhận nhiều mã thông báo từ tập hợp được phép và sau đó sử dụng cách tiếp cận không phân tích cú pháp để xác định khả năng chấp nhận của các từ khóa thực sự được đưa ra. Ngoài việc cho phép một ngữ pháp đơn giản hơn, nó sẽ cho phép bạn dễ dàng tiếp tục phân tích cú pháp sau khi phát ra một chẩn đoán về việc sử dụng sai.

Randall Schulz

Answer 5

Bạn có thể sử dụng "Parser. ^?" toán tử để kiểm tra một nhóm các phần tử phân tích cú pháp cho các bản sao.

def tokens = tokenA | tokenB | tokenC 
    def uniqueTokens = (tokens*) ^? (
    { case t if (t == t.removeDuplicates) => t }, 
    { "duplicate tokens found: " + _ }) 

Dưới đây là một ví dụ cho phép bạn nhập bất kỳ trong bốn Stooges trong bất kỳ thứ tự, nhưng thất bại trong việc phân tích nếu một bản sao được gặp phải:

package blevins.example 

import scala.util.parsing.combinator._ 

case class Stooge(name: String) 

object StoogesParser extends RegexParsers { 
    def moe = "Moe".r 
    def larry = "Larry".r 
    def curly = "Curly".r 
    def shemp = "Shemp".r 
    def stooge = (moe | larry | curly | shemp) ^^ { case s => Stooge(s) } 
    def certifiedStooge = stooge | """\w+""".r ^? (
    { case s: Stooge => s }, 
    { "not a stooge: " + _ }) 

    def stooges = (certifiedStooge*) ^? (
    { case x if (x == x.removeDuplicates) => x.toSet }, 
    { "duplicate stooge in: " + _ }) 

    def parse(s: String): String = { 
    parseAll(stooges, new scala.util.parsing.input.CharSequenceReader(s)) match { 
     case Success(r,_) => r.mkString(" ") 
     case Failure(r,_) => "failure: " + r 
     case Error(r,_) => "error: " + r 
    } 
    } 

} 

Và một số cách sử dụng ví dụ:

package blevins.example 

object App extends Application { 

    def printParse(s: String): Unit = println(StoogesParser.parse(s)) 

    printParse("Moe Shemp Larry") 
    printParse("Moe Shemp Shemp") 
    printParse("Curly Beyonce") 

    /* Output: 
    Stooge(Moe) Stooge(Shemp) Stooge(Larry) 
    failure: duplicate stooge in: List(Stooge(Moe), Stooge(Shemp), Stooge(Shemp)) 
    failure: not a stooge: Beyonce 
    */ 
}