phân tích cú pháp cấu trúc đệ quy trong scala

Question

Tôi đang cố gắng để đối chiếu một trình phân tích cú pháp trong scala có thể phân tích các chuỗi giống SQL đơn giản. Tôi đã có những điều cơ bản làm việc và có thể phân tích cái gì đó như:

select id from users where name = "peter" and age = 30 order by lastname 

Nhưng bây giờ tôi tự hỏi làm thế nào để phân tích và các lớp lồng nhau, tức là

select name from users where name = "peter" and (age = 29 or age = 30) 

Việc sản xuất hiện tại của 'combinedPredicate' của tôi trông như thế này :

def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ { 
    case l ~ "and" ~ r => And(l,r) 
    case l ~ "or" ~ r => Or(l,r) 
} 

Tôi đã cố gắng đệ quy tham chiếu kết quả sản xuất được kết hợp trong chính nó nhưng kết quả là luồng ngăn xếp.

btw, tôi chỉ thử nghiệm ở đây ... không thực hiện toàn bộ ansi-99 đặc tả;)

Answer 1

Vâng, đệ quy phải được phân định bằng cách nào đó. Trong trường hợp này, bạn có thể thực hiện việc này:

def combinedPredicate = predicate ~ rep(("and" | "or") ~ predicate) 
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate 
def simplePredicate = ... 

Vì vậy, nó sẽ không bao giờ chồng tràn vì, trước tiên phải chấp nhận ký tự. Đây là phần quan trọng - nếu bạn luôn đảm bảo đệ quy sẽ không xảy ra nếu không chấp nhận ký tự đầu tiên, bạn sẽ không bao giờ rơi vào một sự đệ quy vô hạn. Trừ khi, tất nhiên, bạn có đầu vào vô hạn. :-)

Answer 2

Sau khi đọc về các giải pháp cho điều hành ưu tiên và đã đưa ra như sau:

def clause:Parser[Clause] = (predicate|parens) * (
      "and" ^^^ { (a:Clause, b:Clause) => And(a,b) } | 
      "or" ^^^ { (a:Clause, b:Clause) => Or(a,b) }) 

    def parens:Parser[Clause] = "(" ~> clause <~ ")" 

Mà có lẽ chỉ là một cách viết những gì @Daniel viết;)

Answer 3

Các stack overflow bạn' tái trải nghiệm có lẽ là kết quả của ngôn ngữ đệ quy trái:

def combinedPredicate = predicate ~ ... 
def predicate = combinedPrediacate | ... 

Trình kết hợp phân tích cú pháp trong Scala 2.7 là trình phân tích cú pháp gốc đệ quy. Các trình phân tích cú pháp gốc đệ quy có vấn đề với chúng bởi vì chúng không biết làm thế nào biểu tượng đầu cuối là khi chúng lần đầu tiên gặp phải nó. Các loại phân tích cú pháp như combinators sưu tập điện phân tích cú pháp Scala 2.8 sẽ không có vấn đề với điều này, mặc dù bạn sẽ cần phải xác định ngữ pháp sử dụng lazy val s thay vì phương pháp, như vậy:

lazy val combinedPredicate = predicate ~ ... 
lazy val predicate = combinedPrediacate | ... 

Ngoài ra, bạn có thể cấu trúc lại ngôn ngữ để tránh đệ quy trái. Từ ví dụ bạn đang cho tôi, yêu cầu dấu ngoặc đơn trong ngôn ngữ này có thể giải quyết vấn đề một cách hiệu quả.

def combinedPredicate = predicate ~ ... 
def predicate = "(" ~> combinedPrediacate <~ ")" | ... 

Giờ mỗi cấp đệ quy sâu hơn tương ứng với một dấu ngoặc đơn khác được phân tích cú pháp. Bạn biết bạn không phải recurse sâu hơn khi bạn chạy ra khỏi dấu ngoặc đơn.