Lấy biểu đồ luồng điều khiển từ Cây cú pháp trừu tượng

Question

Tôi có một AST bắt nguồn từ Trình tạo phân tích cú pháp ANTLR cho Java. Những gì tôi muốn làm là bằng cách nào đó xây dựng một biểu đồ dòng điều khiển của mã nguồn, trong đó mỗi câu lệnh hoặc biểu thức là một nút duy nhất. Tôi hiểu rằng phải có một số đệ quy để nhận dạng này, tôi đã tự hỏi những gì bạn sẽ đề nghị như là lựa chọn tốt nhất và nếu ANTLR có một bộ công cụ tôi có thể sử dụng cho công việc này. Chúc mừng, Chris

---

EDIT - mối quan tâm chính của tôi là để có được một đồ thị luồng điều khiển (CFG) từ AST. Bằng cách này tôi có thể có được một đại diện cây của nguồn. Để làm rõ, cả mã nguồn và ngôn ngữ thực hiện là Java.

Answer 1

Thường CFGs được tính trên một đại diện cấp thấp hơn (ví dụ JVM bytecode). Ai đó đã làm a thesis về những thứ như vậy vài năm trước. Có thể có một cách hữu ích được mô tả trong đó để biết cách lấy biểu diễn đó.

Vì ngôn ngữ nguồn và đích của bạn giống nhau, không có bước tạo mã - bạn đã hoàn tất! Tuy nhiên, bây giờ bạn có thể đi bộ AST. Tại mỗi nút của AST, bạn phải tự hỏi mình: đây có phải là lệnh "nhảy" hay không? Các cuộc gọi phương thức và câu lệnh if là các ví dụ về hướng dẫn nhảy. Vì vậy, các cấu trúc vòng lặp (chẳng hạn như for và while). Các hướng dẫn như bổ sung và phép nhân không nhảy.

Kết hợp đầu tiên với mỗi câu lệnh java một nút trong CFG, cùng với nút nhập và thoát.Là lần đầu tiên gần đúng, hãy đi bộ trên cây và:

1. nếu câu lệnh hiện tại là cuộc gọi phương thức, tìm ra nút nhập cho cơ thể tương ứng của cuộc gọi phương thức đó và chỉ tay cạnh từ câu lệnh hiện tại đến nút nhập đó. nếu câu lệnh là một phương thức trả về, liệt kê các địa điểm có thể đã gọi nó và thêm một cạnh vào đó.
2. cho mỗi tuyên bố không nhảy, tạo một cạnh giữa tuyên bố và tuyên bố tiếp theo.

Điều này sẽ cung cấp cho bạn một số loại của CFG. Quy trình này hơi khó khăn trong bước 2 vì phương thức được gọi có thể được khai báo trong thư viện và không phải ở đâu đó trong AST - nếu vậy, hoặc không tạo cạnh hoặc tạo cạnh cho nút đặc biệt biểu thị mục nhập đó phương pháp thư viện.

Điều này có hợp lý không?

Answer 2

Bạn đã bao giờ thử ANTLR Studio chưa? Nó không tạo ra biểu đồ AST lỗ, nhưng để xem xét, nó đã khá hữu ích.

Answer 3

Khi tôi đã thực hiện điều này trong quá khứ, tôi đã sử dụng graphviz, cụ thể là công cụ chấm, để tạo biểu đồ. Tôi đã tạo tệp đầu vào dấu chấm bằng cách thực sự duyệt qua biểu đồ luồng kiểm soát tại thời gian biên dịch.

Bố cục biểu đồ là một vấn đề khó khăn và graphviz thực hiện một công việc tuyệt vời. Nó có thể xuất ra định dạng ps, pdf và nhiều định dạng hình ảnh khác nhau và bố cục thường trực quan để xem xét. Tôi khuyên bạn nên nó.

Answer 4

Dựa trên một số nhận xét, có vẻ như OP thực sự muốn làm code generation - để chuyển AST thành chuỗi hướng dẫn cấp thấp hơn dựa trên các khối cơ bản và điểm nhảy.

Tạo mã rất cụ thể về ngôn ngữ và rất nhiều công việc đã được đưa vào chủ đề này. Trước khi tạo mã, bạn cần biết ngôn ngữ đích đích - cho dù đó là trình biên dịch hay chỉ đơn giản là một số ngôn ngữ cấp cao khác. Một khi bạn đã xác định điều này, bạn chỉ cần đi bộ AST và tạo ra một chuỗi các hướng dẫn thực hiện mã trong AST. (Tôi nói điều này là đơn giản, nhưng nó có thể khó khăn - thật khó để khái quát hóa vì những cân nhắc ở đây là khá cụ thể về ngôn ngữ.)

Biểu diễn bạn chọn để tạo mã sẽ chứa biểu đồ dòng điều khiển, ngầm hoặc một cách rõ ràng. Nếu ngôn ngữ đích của bạn là khá thấp (gần với trình biên dịch), thì biểu đồ luồng điều khiển phải tương đối dễ dàng để trích xuất.

(Xin vui lòng bình luận nếu bạn muốn làm rõ thêm.)

Answer 5

Tạo biểu đồ luồng kiểm soát đầy đủ thực sự xem xét tất cả các vấn đề ngôn ngữ khó hơn. Bạn không chỉ phải xác định những gì dường như là "khối cơ bản", nhưng bạn phải xác định các cuộc gọi chức năng (loại dễ dàng, nhưng xác định mục tiêu có thể khó hơn), nơi hoạt động hậu trường như khởi tạo lớp có thể xảy ra. và phải lo lắng về các điểm mà các ngoại lệ có thể xảy ra và điều khiển sẽ xảy ra nếu ngoại lệ xảy ra.

Nếu bạn kiểm tra hầu hết ngôn ngữ, chúng cũng sẽ là rõ ràng về thứ tự đánh giá tính toán trong biểu thức, và điều này quan trọng nếu bạn có hai tác dụng phụ trong biểu thức; luồng kiểm soát phải phản ánh thứ tự (hoặc không theo thứ tự, nếu nó không được xác định).

Có thể bạn chỉ muốn trừu tượng luồng kiểm soát có các khối cơ bản và các điều kiện. Đó là rõ ràng là dễ dàng hơn một chút.

Trong cả hai trường hợp (CFG đơn hoặc CFG đầy đủ), bạn cần đi bộ AST, tại mỗi điểm có tham chiếu đến các mục tiêu kiểm soát có thể (ví dụ, đối với hầu hết các trường hợp, chẳng hạn như câu lệnh IF) mục tiêu lưu lượng: mệnh đề THEN và ELSE). Tại mỗi nút, liên kết nút đó với mục tiêu điều khiển thích hợp , có thể thay thế các mục tiêu luồng (ví dụ: khi bạn gặp phải IF).

Để làm điều này cho ngữ nghĩa đầy đủ ngôn ngữ của Java (hoặc C) là khá rất nhiều công việc. Bạn có thể chỉ cần sử dụng một công cụ tính toán số này ngoài giá. Xem http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html để biết điều này trông như thế nào, sắp ra khỏi các công cụ của chúng tôi.