Zephyr ASDL (Abstract Syntax Description Language)

Question

Câu hỏi:

Zephyr ASDL là gì và làm thế nào nó liên quan đến công nghệ biên dịch khác như lexers và máy phát phân tích cú pháp?

(Tôi sẽ đánh giá cao nếu bạn đã hoàn thành một cách hợp lý, nhưng chỉ đến các tài liệu tham khảo khác trực tuyến khi nó khá kỹ thuật, vì hầu hết những gì tôi biết về trình biên dịch đến từ chơi với yacc và flex, viết một lexer munch tối đa đơn giản trong C, ngước mắt lên và đọc những thứ trên mạng)

Câu hỏi Bối cảnh:

tôi đã đọc http://docs.python.org/devguide/compiler.html và tôi đi qua các dòng sau:

Đặc điểm kỹ thuật của các nút AST được xác định bằng cách sử dụng Zephyr Ngôn ngữ định nghĩa cú pháp trừu tượng (ASDL).

Tôi đã theo dõi trích dẫn ở dưới cùng để tìm: http://www.cs.princeton.edu/research/techreps/TR-554-97.

Lần đọc đầu tiên của tôi thông qua bài viết khá hỗn loạn, và tôi hy vọng tôi có thể hiểu rõ hơn về mục đích của ASDL (trong ngữ cảnh của quá trình biên dịch), trước khi thử lại.

Answer 1

Trình tạo trình phân tích cú pháp và trình phân tích cú pháp chấp nhận các mô tả về từ vựng và ngữ pháp và tạo mã triển khai tạo tác tương ứng. Lex đòi hỏi một sự biểu lộ thường xuyên để mô tả các thẻ. Trình tạo trình phân tích cú pháp nhận các loại ký hiệu BNF mở rộng khác nhau.

Bài báo bạn tham khảo là khá rõ ràng IMHO: ASDL là một ngôn ngữ nhỏ để mô tả trừu tượng một tập hợp các nút cây (kiểu và chữ ký của chúng). Sử dụng ngôn ngữ này, người ta có thể viết (và các tác giả của giấy đã làm như vậy) một công cụ chuyển đổi các mô tả này thành tập hợp các loại bản ghi mà bạn cần phải thực hiện các cây được sử dụng với một trình phân tích cú pháp. Vì vậy, ADSL là loại giống như Regexes và BNF, trong đó mục đích của nó là để được ăn cho một máy phát điện mã sản xuất một phần của một trình biên dịch.

Quan điểm mở rộng là các trình biên dịch là một công nghệ khá được hiểu rõ, và người ta phải có khả năng tạo ra chúng từ các mô tả các phần khác nhau. Regex/BNF/ADSL là các khóa cần thiết cho giai đoạn phân tích cú pháp.

Bạn lý tưởng như ngôn ngữ mô tả cho tập lệnh mục tiêu, phân tích luồng, bản dịch (bạn đã đề cập munch tối đa) từ cây trừu tượng đến tập lệnh mục tiêu và cách mô tả tối ưu hóa. Sau đó, với các công cụ tương ứng cho mỗi phần, bạn có thể xây dựng toàn bộ trình biên dịch từ "thông số kỹ thuật". Có thực sự là rất nhiều công việc trong lĩnh vực này; mọi người đã làm tất cả những điều này một cách riêng biệt và cùng nhau. Không ngạc nhiên khi một số trong số đó xuất phát từ dự án "Zephyr" trước đây ở ngoài Princeton (có vẻ như trang web Zephyr hiện đã chết), mục tiêu của họ là làm điều này.

Dù sao, hãy thử tìm kiếm trong Google Scholar cho "trình tạo trình biên dịch".

Answer 2

ASDL được sử dụng khi bạn cần tạo một cây trong mô-đun và nhập cùng một cây trong mô-đun khác (hoặc gần như cùng một cây, bằng cách nào đó được tối ưu hóa).

Đối với điều này, bạn cần phải có chức năng xây dựng (lý tưởng với bộ kiểm tra kiểu), chức năng in cây như hình dung nó, bạn chắc chắn bạn đã tạo ra nó một cách chính xác.

ASDL lấy làm đầu vào một số cây viết bằng cú pháp gần giống với cú pháp kiểu dữ liệu đại số (như trong haskell hoặc ml), hoặc cú pháp trong BNF nhưng đơn giản hơn nhiều và tự động tạo tất cả các contructors chức năng bắt đầu với mô tả đơn giản của cây.

Ví dụ: nếu bạn có từ khóa, nó sẽ phải tạo ra các từ vựng có loại. Bạn cũng cần xem dòng đầu ra của từ vựng (đây là dạng tuyến tính, vì vậy một cây rất đơn giản). Thay vì viết các chức năng để in, xây dựng các từ, bạn xác định chúng như sau:

lexeme= 
     ID(STRING) 
    | INT(num_integer) 
    | FLOAT(num_float) 
    attributes(int coord_x, int coord_y) 
    num_integer: 
    .... 
    num_float: 
    .... 

và bạn gọi hàm tạo ID, INT, FLOAT, vv từ lexer của bạn. ASDL sẽ chuyển đổi cú pháp đơn giản này trong tất cả các chức năng bạn cần, hoặc là xây dựng các nút cho AST, hoặc để in, hoặc bất cứ thứ gì bạn cần. ASDL không áp đặt các hạn chế đối với mã được tạo ra.

Nếu bạn thêm attributes vào một loại, chẳng hạn như tọa độ của mã thông báo, các thuộc tính đó sẽ được nối thêm vào các thông số của mỗi contructor từ loại đó.

Một cây phức tạp hơn, tạo ra bởi một phân tích cú pháp sẽ trông như thế

expr: SUM(expr, expr) 
     |PRODUCT(expr, expr) 
     |number 
number: num_integer 

Trong trường hợp này asdl sẽ kiểm tra xem các cuộc gọi của SUM (_ _) thực hiện bởi các phân tích cú pháp sẽ vượt qua để tổng hợp các nút tạo ra với một trong những nhà thầu của expr. num_integer được định nghĩa bên ngoài, có thể bởi một cây asdl cho lexer.

Lưu ý rằng bạn không được phép xác định các hàm tạo có chứa cụm từ thông dụng, chẳng hạn như number: [0-9]+. ASDL đơn giản hơn EBNF.

Các nhà xây dựng này sẽ được xác định sao cho xây dựng những gì bạn cần và hơn thế nữa, họ gõ kiểm tra, để đảm bảo rằng trình tạo mã/trình phân tích cú pháp/mã của bạn xuất ra các cây phù hợp với ngôn ngữ được định nghĩa bởi asdl.

Để hiểu rõ ASDL, bạn cần viết 3-4 trình phân tích cú pháp và xem điều gì phổ biến trong mã mà chúng tạo ra. Đó là một phần phổ biến trong thực tế ASDL, vì vậy đây là một trừu tượng cho đầu ra của các trình phân tích cú pháp nói riêng.