Khi nào nên sử dụng cây cú pháp trừu tượng hoặc cụ thể?

Question

Tôi đã nghiên cứu về các trình biên dịch. Lexer có vẻ rất thẳng về phía trước: Lấy một "câu" và chia nó thành các từ (hoặc các thẻ). Để đảm bảo ngữ pháp chính xác, một trình phân tích cú pháp là cần thiết. Trình phân tích cú pháp thường lấy các thẻ và xây dựng một cây dẫn đến nút gốc (các từ thành các câu, các đoạn văn, các trang, v.v ...).

Từ this question có vẻ như một trình phân tích cú pháp sẽ tạo AST. AST chỉ chứa những gì cần thiết để thực thi mã, vì vậy những thứ như dấu ngoặc đơn sẽ không cần thiết vì ưu tiên toán tử được xây dựng thành một AST. Một AST có lẽ là tất cả các nhu cầu của trình biên dịch.

Nhưng điều gì về việc chuyển đổi mã từ ngôn ngữ này sang ngôn ngữ khác? Lấy một ngôn ngữ được tạo sẵn (ngữ pháp) hoặc một ngữ pháp hiện có và chuyển đổi nó thành ngữ pháp khác, nơi các quy tắc ưu tiên toán tử có thể hoặc không khác nhau? Ưu tiên của nhà điều hành có được "tích hợp sẵn" với CST không?

Ví dụ: giả sử tôi đã tạo ngôn ngữ và muốn dịch nó sang mã PHP. Toán tử bậc ba trên hầu hết các ngôn ngữ có liên kết từ phải sang trái. PHP không chính xác sử dụng kết hợp từ trái qua phải (see more about this here). Tôi muốn "ngôn ngữ của tôi" sử dụng từ phải sang trái nhưng mã PHP kết quả phải áp dụng dấu ngoặc đơn để có được kết quả chính xác trong PHP (với số link to Wikipedia, kết quả cần phải là "đào tạo" thay vì "ngựa").

Vì vậy, để dịch ngôn ngữ CST sẽ tốt hơn? Quyền ưu tiên của toán tử thường được xây dựng thành CST? Có điều gì ở giữa không? Có ví dụ nào so sánh cả hai cây với một phương trình đại số đơn giản? Bất kỳ ví dụ minh họa một toán tử bậc ba?

(Is "chuyển mã" thuật ngữ chính xác cho "dịch ngôn ngữ lập trình" Một tìm kiếm Google sẽ trả về chuyển đổi phương tiện truyền thông?.)

Những gì tôi đang cố gắng tìm ra là: Khi nào thì thích hợp hơn để sử dụng một khác?

Answer 1

Một AST mô hình tất cả các chi tiết ngữ nghĩa của ngôn ngữ nguồn là tất cả những gì bạn cần. Theo định nghĩa, nếu nó mô hình chính xác ngữ nghĩa, và langauge của bạn bao gồm toán tử bậc ba, thì nó sẽ mô hình thứ tự cụ thể trong đó các toán tử được áp dụng (ví dụ, kết quả của hàm chồng chéo trước đó như dấu ngoặc đơn).

Vì vậy, sự cố của bạn không có trong AST. Nó được tạo ra cho một ngôn ngữ khác sử dụng các toán tử tương tự (ternary) có ưu tiên khác nhau.

Đây là một vấn đề cũ trong quá trình tạo mã: các toán tử của đích không hoàn toàn khớp với toán tử của nguồn và do đó đầu ra không thể là một-một. Trong trường hợp của bạn, bạn sẽ có thể giải quyết vấn đề bằng cách tạo ra các toán tử ternary PHP với các dấu ngoặc đơn xung quanh chúng để kiểm soát thứ tự để đạt được ngữ nghĩa ban đầu, vì vậy đây không phải là vấn đề lớn.

Nói chung, việc tạo chuỗi mã đạt được kết quả mong muốn có thể khá phức tạp và có nhiều cách để thực hiện. Đó là lý do tại sao các trình biên dịch sách dày hơn là mỏng. Bạn dường như đã giải quyết hoàn toàn về "lấy AST, đi bộ AST, mã nhổ"; đây gần như là một bộ tạo mã trực tiếp. Và điều này hoạt động đầy đủ nếu bạn không quan tâm nếu mã được tạo ra đặc biệt tốt và ngôn ngữ đích là khá gần với ngôn ngữ nguồn. Nếu vấn đề tạo mã phức tạp hơn, AST thường được sử dụng để tạo ra số tiền cho mô hình luồng dữ liệu của phép tính, bao gồm các toán tử tạo ra các kết quả, và tiêu thụ kết quả từ các toán tử trước đó. trong "toán tử" tìm nạp các giá trị và hằng số biến.Sau đó, biểu diễn luồng dữ liệu được duyệt qua để tạo mã; điều này có lợi thế là bạn có thể chọn một toán tử trong biểu diễn luồng dữ liệu, tìm một chuỗi mã phù hợp trong ngôn ngữ đích, tạo ra nó, và sau đó lo lắng về cách các toán hạng được thu thập. Đề án tốt hơn phù hợp với đồ thị dòng dữ liệu (đại diện cho các cấu trúc ngôn ngữ đích hợp chất tương đương) với biểu đồ luồng dữ liệu được tạo ra; điều này có thể tạo ra mã tốt hơn đáng kể. Thông thường, người ta có thể áp dụng tối ưu hóa ngôn ngữ mục tiêu cụ thể sau khi tạo mã thô để tạo ra mã tốt hơn. Trong cả hai trường hợp, bạn phải lo lắng về việc quản lý các kết quả của toán tử; chúng có thể được cấp trực tiếp cho toán tử ngôn ngữ đích tiếp theo hay chúng phải đi vào một loại lưu trữ tạm thời nào đó (đối với mã máy, đây có thể là một thanh ghi khác hoặc vị trí bộ nhớ). Làm tất cả điều này là không dễ dàng; một lần nữa, đó là lý do tại sao các cuốn sách biên dịch không phải là mỏng.

Biến thể trên ý tưởng này là chuyển đổi chương trình nguồn thành nguồn. Bản đồ này xây dựng trong mã nguồn "trực tiếp" để xây dựng trong mã đích, mặc dù điều này thường được thực hiện phía sau hậu trường bằng cách hoạt động trên AST vì văn bản ngôn ngữ lập trình chưa được phân tích khó khớp. DMS Software Reengineering Toolkit của chúng tôi là một ví dụ về loại hệ thống này. Với công cụ như vậy, bạn viết các mẫu trong ngôn ngữ nguồn (mà hoàn toàn phù hợp với một cây phân tích cú pháp), và các mẫu tương ứng trong ngôn ngữ đích (ngầm định tạo ra các ngôn ngữ đích AST). Bạn có thể viết các cấu trúc nguồn hoặc đích phức tạp cho nhiều ảnh hưởng của biểu đồ luồng dữ liệu khớp với ở trên. Tối ưu hóa sau thế hệ bao gồm các quy tắc viết lại nhiều hơn để chuyển đổi mã đích thành mã đích.

Điểm mấu chốt: Có AST không thực sự đủ trừ khi bản dịch của bạn thực sự tầm thường. Bạn có thể đọc thêm về những gì bạn cần tại câu trả lời SO này: https://stackoverflow.com/a/3460977/120163

CẢNH BÁO: Ý kiến ​​lớn sau.

Re "Transcoder": Tôi thích trình biên dịch "biên dịch", "dịch" hoặc "nguồn-sang-nguồn". Tôi đã xây dựng các công cụ phân tích và thao tác chương trình trong gần 40 năm. Tôi chưa bao giờ nghe thuật ngữ "transcoder" cho đến khi tôi gặp phải câu hỏi SO này: Experience migrating legacy Cobol/PL1 to Java và một phản hồi mô tả IMHO một chương trình dịch mã thực sự khủng khiếp được gọi là NACA. Tôi đã nghe kể từ đó thuật ngữ này đang đạt được lực kéo; Tôi không thấy lý do tại sao chúng tôi phải phát minh ra một thuật ngữ khác khi chúng tôi có những thuật ngữ hoàn hảo. Thông thường đây là một dấu hiệu của ai đó phát minh ra một chức tư tế cao; "hãy tạo ra một thuật ngữ mới sáng bóng để mọi người không thực sự hiểu những gì chúng tôi đang làm". Tôi vui mừng để lại thuật ngữ đó cho những bản dịch thật sự khủng khiếp đó.