để chuyển đổi cây nút

Question

Tôi muốn có thể thể hiện sự biến đổi chung của một cây thành cây khác mà không cần viết một chuỗi mã spaghetti lặp đi lặp lại. Có thư viện nào để giúp giải quyết vấn đề này không? Ngôn ngữ đích của tôi là Python, nhưng tôi sẽ xem xét các ngôn ngữ khác miễn là nó khả thi để chuyển sang Python.

Ví dụ: Tôi muốn chuyển đổi cây nút này: (xin vui lòng tha các S-expressions)

(A (B) (C) (D)) 

Into này một:

(C (B) (D)) 

Chừng nào phụ huynh là A và thứ hai tổ tiên là C, bất kể bối cảnh (có thể có nhiều cha mẹ hoặc tổ tiên hơn). Tôi muốn thể hiện sự biến đổi này theo cách đơn giản, ngắn gọn và có thể sử dụng lại được. Tất nhiên, ví dụ này rất cụ thể. Hãy cố gắng giải quyết trường hợp chung.

Chỉnh sửa: RefactoringNG là loại điều tôi đang tìm kiếm, mặc dù nó giới thiệu một ngữ pháp hoàn toàn mới để giải quyết vấn đề, mà tôi muốn tránh. Tôi vẫn đang tìm kiếm nhiều hơn và/hoặc các ví dụ tốt hơn.

---

Bối cảnh:

Tôi có thể chuyển đổi python và cheetah (đừng hỏi!) Tập tin vào cơ quan đại diện cây tokenized, và lần lượt chuyển đổi những thành lxml cây. Tôi dự định sau đó tổ chức lại cây và viết ra các kết quả để thực hiện tái cấu trúc tự động. XSLT có vẻ là công cụ chuẩn để viết lại XML, nhưng cú pháp là khủng khiếp (theo ý kiến ​​của tôi, rõ ràng) và không ai ở cửa hàng của chúng tôi sẽ hiểu nó.

Tôi có thể viết một số chức năng chỉ đơn giản là sử dụng các phương pháp lxml (.xpath và như vậy) để thực hiện các phép tái cấu trúc của mình, nhưng tôi lo rằng mình sẽ kết thúc với một chuỗi mã spaghetti tái sử dụng.

Answer 1

gì bạn thực sự muốn IMHO là một program transformation system, cho phép bạn phân tích và chuyển đổi mã sử dụng các mô hình thể hiện bằng cú pháp bề mặt của mã nguồn (và thậm chí ngôn ngữ đích) để diễn tả được ghi đè trực tiếp.

Bạn sẽ thấy rằng ngay cả khi bạn có thể nhận được bàn tay của bạn trên một biểu diễn XML của cây Python, rằng nỗ lực để viết một phép chuyển đổi XSLT/XPath là nhiều hơn bạn mong đợi; cây đại diện cho mã thực sự lộn xộn hơn bạn mong đợi, XSLT không phải là ký hiệu thuận tiện và không thể biểu thị các điều kiện chung trực tiếp trên cây mà bạn muốn kiểm tra (ví dụ: hai subtrees giống nhau). Một biến chứng cuối cùng với XML: giả sử nó đã được biến đổi. Làm thế nào để bạn tái tạo cú pháp mã nguồn mà từ đó đến? Bạn cần một số loại người đẹp.

Một vấn đề chung bất kể mã được thể hiện như thế nào mà không có thông tin về phạm vi và loại (nơi bạn có thể nhận được), việc viết các phép biến đổi chính xác là khá khó. Sau khi tất cả, nếu bạn định biến python thành ngôn ngữ sử dụng các toán tử khác nhau cho chuỗi ký tự và số học (không giống Java sử dụng "+" cho cả hai), bạn cần có khả năng quyết định toán tử nào tạo ra. Vì vậy, bạn cần loại thông tin để quyết định. Python được cho là không có kiểu chữ, nhưng trong thực tế hầu hết các biểu thức liên quan đến các biến chỉ có một kiểu cho toàn bộ vòng đời của chúng. Vì vậy, bạn cũng sẽ cần phân tích luồng để tính toán các loại.

DMS Software Reengineering Toolkit của chúng tôi có tất cả các khả năng này (phân tích cú pháp, phân tích luồng, đối sánh mẫu/viết lại, in đẹp) và robust parsers cho nhiều ngôn ngữ bao gồm Python.(Trong khi nó có khả năng phân tích dòng chảy được khởi tạo cho C, COBOL, Java, điều này không được khởi tạo cho Python. Nhưng sau đó, bạn đã nói bạn muốn thực hiện phép chuyển đổi bất kể ngữ cảnh).

Để bày tỏ viết lại của bạn trong DMS trên Python cú pháp chặt chẽ để dụ của bạn (mà không phải là Python?)

domain Python; 

    rule revise_arguments(f:IDENTIFIER,A:expression,B:expression, 
            C:expression,D:expression):primary->primary 
    = " \f(\A,(\B),(\C),(\D)) " 
    -> " \f(\C,(\B),(\D)) "; 

Các ký hiệu trên là DMS quy tắc viết lại ngôn ngữ (RSL). "..." là các metaquotes tách biệt cú pháp Python (bên trong các dấu ngoặc kép đó, DMS biết nó là Python vì khai báo ký hiệu tên miền) từ ngôn ngữ RSL của DMS. \ N bên trong báo giá meta đề cập đến trình giữ chỗ biến cú pháp của loại nonterminal được định nghĩa trong danh sách tham số quy tắc. Có, (...) bên trong các metaquotes là Python() ... chúng tồn tại trong các cây cú pháp như xa như DMS là có liên quan, bởi vì chúng, giống như phần còn lại của ngôn ngữ, là chỉ cú pháp.

Quy tắc trên có vẻ hơi lạ vì tôi đang cố gắng làm theo ví dụ của bạn càng gần càng tốt, và từ và ngôn ngữ biểu thức quan điểm, ví dụ của bạn là lẻ chính xác bởi vì nó có dấu ngoặc đơn bất thường.

Với quy định này, DMS có thể phân tích Python (sử dụng phân tích cú pháp Python của nó) như

 foobar(2+3,(x-y),(p),(baz())) 

xây dựng một AST, phù hợp với quy tắc (phân tích-to-AST) so với AST đó, viết lại nó để AST khác tương ứng tới:

 foobar(p,(x-y),(baz())) 

và sau đó đánh dấu lại cú pháp bề mặt (hợp lệ) python.

Nếu bạn dự định biến đổi mã LISP, bạn cần ngữ pháp LISP cho DMS (không khó để xây dựng, nhưng chúng tôi không có nhiều cuộc gọi) và viết bề mặt tương ứng cú pháp:

domain Lisp; 

    rule revise_form(A:form,B:form, C:form, D:form):form->form 
    = " (\A,(\B),(\C),(\D)) " 
    -> " (\C,(\B),(\D)) "; 

Bạn có thể cảm nhận rõ hơn về điều này bằng cách xem Algebra as a DMS domain.

Nếu mục tiêu của bạn là triển khai tất cả điều này bằng Python ... Tôi không có nhiều trợ giúp. DMS là một hệ thống khá lớn, và nó sẽ là rất nhiều nỗ lực để nhân rộng.

Answer 2

Hãy thử điều này bằng mã Python. Tôi đã sử dụng dây cho lá, nhưng điều này sẽ làm việc với bất kỳ đối tượng.

def lift_middle_child(in_tree): 
    (A, (B,), (C,), (D,)) = in_tree 

    return (C, (B,), (D,)) 

print lift_middle_child(('A', ('B',), ('C',), ('D',))) # could use lists too 

loại này chuyển đổi cây thường được thực hiện tốt hơn trong một phong cách chức năng - nếu bạn tạo ra một loạt các chức năng này, bạn có thể soạn một cách rõ ràng chúng, hoặc tạo một hàm thành phần làm việc với họ trong một điểm miễn phí Phong cách.

Vì bạn đã sử dụng biểu thức s, tôi cho rằng bạn thấy thoải mái khi đại diện cho cây như danh sách lồng nhau (hoặc tương đương - trừ khi tôi nhầm lẫn, các nút lxml có thể lặp lại theo cách đó). Rõ ràng, ví dụ này dựa trên cấu trúc đầu vào đã biết, nhưng câu hỏi của bạn ngụ ý điều đó. Bạn có thể viết các hàm linh hoạt hơn và vẫn soạn chúng, miễn là chúng có giao diện đồng nhất này.

Dưới đây là mã trong hành động: http://ideone.com/02Uv0i

Bây giờ, đây là một chức năng để đảo ngược trẻ em, và sử dụng đó và hàm trên, một để nâng và đảo ngược:

def compose2(a,b): # might want to get this from the functional library 
    return lambda *x: a(b(*x)) 

def compose(*funcs): #compose(a,b,c) = a(b(c(x))) - you might want to reverse that 
    return reduce(compose2,funcs) 

def reverse_children(in_tree): 
    return in_tree[0:1] + in_tree[1:][::-1] # slightly cryptic, but works for anything subscriptable 

lift_and_reverse = compose(reverse_children,lift_middle_child) # right most function applied first - if you find this confusing, reverse order in compose function. 

print lift_and_reverse(('A', ('B',), ('C',), ('D',)))