Chuỗi phân tích cú pháp thành một cấu trúc cây?

Question

Tôi đang cố gắng tìm ra cách phân tích cú pháp một chuỗi ở định dạng này thành một cây như cấu trúc dữ liệu có chiều sâu tùy ý.

"{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}" 

[[["Hello big" "Hi" "Hey"] 
    ["world" "earth"]] 
[["Goodbye" "farewell"] 
    ["planet" "rock" "globe" ["." 
          "!"]]]] 

Tôi đã thử chơi một số biểu thức chính quy cho điều này (chẳng hạn như # "{([^ {}] *)}"), nhưng mọi thứ tôi đã thử dường như "làm phẳng" cây thành một danh sách lớn các danh sách. Tôi có thể tiếp cận điều này từ góc độ sai, hoặc có thể một regex không phải là công cụ thích hợp cho công việc.

Cảm ơn sự giúp đỡ của bạn!

Answer 1

Không sử dụng cụm từ thông dụng cho tác vụ này. Một phương pháp dễ dàng hơn là mô tả chuỗi của bạn bằng ngữ pháp (BNF hoặc EBNF) và sau đó viết một trình phân tích cú pháp để phân tích cú pháp chuỗi theo ngữ pháp. Bạn có thể tạo ra một phân tích cây từ EBNF và BNF của bạn và do đó bạn tự nhiên kết thúc với một cấu trúc cây.

Bạn có thể bắt đầu với một cái gì đó như thế này:

element  ::= element-type, { ["|"], element-type } 
element-type ::= primitive | "{", element, "}" 
primitive ::= symbol | word 
symbol  ::= "." | "!" 
word   ::= character { character } 
character ::= "a" | "b" | ... | "z" 

Lưu ý: Tôi viết này lên một cách nhanh chóng, và vì vậy nó có thể không hoàn toàn chính xác. Nhưng nó sẽ cho bạn một ý tưởng.

Answer 2

nếu bạn muốn có một hack nhanh chóng:

• thay thế {chars với [
• thay thế} chars với]
• thay thế | ký tự có dấu cách
• hy vọng bạn không nhận được dữ liệu nhập bằng dấu cách.

read trong đó nó xuất hiện dưới dạng mảng lồng nhau.

ps: Tôi đồng ý rằng reg-ex không thể thực hiện việc này.

PSS: set * đọc eval * false (bạn không muốn đầu vào chạy, điều đó tự)

Answer 3

Đang cố gắng để phù hợp với điều toàn bộ với một biểu thức chính quy duy nhất là sẽ không giúp bạn có được quá xa , vì cụm từ thông dụng xuất ra nhiều nhất một danh sách các vị trí chuỗi con phù hợp, không có gì giống cây. Bạn muốn một từ vựng hoặc ngữ pháp thực hiện một cái gì đó như thế này:

Chia đầu vào thành mã - các phần tử nguyên tử như '{', '|', và 'thế giới', sau đó xử lý các mã thông báo đó theo thứ tự. Bắt đầu với một cây trống với một nút gốc duy nhất.

Mỗi khi bạn tìm thấy {, hãy tạo và chuyển đến nút con.

Mỗi khi bạn tìm thấy |, hãy tạo và chuyển đến nút anh chị em.

Mỗi khi bạn tìm thấy }, hãy chuyển đến nút chính.

Mỗi khi bạn tìm thấy một từ, hãy đặt từ đó vào nút lá hiện tại.

Answer 4

Bạn có thể sử dụng để xây dựng amotoen ngữ pháp và phân tích cú pháp này:

(ns pegg.core 
    (:gen-class) 
    (:use 
    (com.lithinos.amotoen 
    core string-wrapper)) 
    (:use clojure.contrib.pprint)) 

(def input "{{Hello big|Hi|Hey} {world|earth}|{Goodbye|farewell} {planet|rock|globe{.|!}}}") 

(def grammar 
    { 
     :Start :List 
     :ws #"^[ \n\r\t]*" 
     :Sep "|" 
     :String #"^[A-Za-z !.]+" 
     :Item '(| :String :List) 
     :Items [:Item '(+ [:Sep :Item])] 
     :List [:ws "{" '(* (| :Items :Item)) "}" :ws] 
     }) 

(def parser (create-parser grammar)) 

(defn parse 
    [^String input] 
    (validate grammar) 
    (pprint (parser (wrap-string input)))) 

Kết quả:

pegg.core> (parse input) 
{:List [{:ws ""} "{" ({:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Hello big"}} ([{:Sep "|"} {:Item {:String "Hi"}}] [{:Sep "|"} {:Item {:String "Hey"}}])]}) "}" {:ws " "}]}} {:Items [{:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "world"}} ([{:Sep "|"} {:Item {:String "earth"}}])]}) "}" {:ws ""}]}} ([{:Sep "|"} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "Goodbye"}} ([{:Sep "|"} {:Item {:String "farewell"}}])]}) "}" {:ws " "}]}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "planet"}} ([{:Sep "|"} {:Item {:String "rock"}}] [{:Sep "|"} {:Item {:String "globe"}}])]} {:Item {:List [{:ws ""} "{" ({:Items [{:Item {:String "."}} ([{:Sep "|"} {:Item {:String "!"}}])]}) "}" {:ws ""}]}}) "}" {:ws ""}]}}) "}" {:ws ""}]} 

T.B. Đây là một trong những ngữ pháp đầu tiên của tôi và nó có thể tốt hơn. Ngoài ra, hãy xem http://en.wikipedia.org/wiki/Parsing_expression_grammar