Phạm vi Lexical được triển khai như thế nào?

Question

Một vài năm trước, tôi bắt đầu viết một thông dịch viên cho một Ngôn ngữ Cụ thể cho Tên miền bao gồm các hàm do người lập trình xác định.

Lúc đầu, tôi đã triển khai phạm vi biến đổi bằng cách sử dụng một chồng bảng biểu tượng đơn giản. Nhưng bây giờ tôi muốn chuyển sang phạm vi từ vựng thích hợp (với tùy chọn đóng cửa). Bất cứ ai có thể giải thích hoặc chỉ cho tôi một lời giải thích tốt về cấu trúc dữ liệu và thuật toán đằng sau phạm vi từ vựng?

Answer 1

Không có cách nào đúng để thực hiện việc này. Điều quan trọng là nêu rõ các ngữ nghĩa mà bạn đang tìm cách cung cấp, và sau đó các cấu trúc dữ liệu và các thuật toán sẽ tuân theo.

Answer 2

Để có được Phạm vi từ vựng chính xác và đóng cửa trong một thông dịch viên, tất cả các bạn cần làm là làm theo các quy tắc:

• Trong thông dịch viên của bạn, biến luôn nhìn lên trong một bảng môi trường thông qua vào bởi người gọi/được giữ như một biến số, không phải là một số env-stack toàn cầu. Đó là, eval(expression, env) => value.
• Khi mã được giải thích gọi một hàm, môi trường là NOT được chuyển cho hàm đó. apply(function, arguments) => value.
• Khi một hàm được diễn giải được gọi, môi trường mà nội dung của nó được đánh giá là môi trường trong đó định nghĩa hàm được tạo và không liên quan gì đến người gọi. Vì vậy, nếu bạn có hàm cục bộ, thì đó là một cấu trúc đóng, tức là cấu trúc dữ liệu chứa các trường {function definition, env-at-definition-time}.

Mở rộng trên rằng bit cuối cùng trong Python-ish cú pháp:

x = 1 
return lambda y: x + y 

được thực hiện như thể nó là

x = 1 
return makeClosure(<AST for "lambda y: x + y">, {"x": x}) 

nơi đối số dict thứ hai có thể chỉ là hiện tại-env thay vì cấu trúc dữ liệu được xây dựng tại thời điểm đó. (Mặt khác, giữ lại toàn bộ env thay vì chỉ các biến đóng kín có thể gây rò rỉ bộ nhớ.)

Answer 3

Đọc The implementation of Lua 5.0 ví dụ.

Answer 4

Có nhiều cách khác nhau để thực hiện phạm vi từ vựng. Dưới đây là một số yêu thích của tôi:

• Nếu bạn không cần phải thực hiện siêu nhanh, sử dụng một cấu trúc dữ liệu hoàn toàn chức năng để thực hiện bảng biểu tượng của bạn, và đại diện cho một hàm lồng nhau bởi một cặp có chứa một con trỏ đến và một con trỏ đến bảng biểu tượng.

• Nếu bạn cần tốc độ mã nguồn gốc, kỹ thuật yêu thích của tôi được mô tả trong Making a Fast Curry bởi Simon Marlow và Simon Peyton Jones.

• Nếu bạn cần tốc độ mã nguồn gốc, nhưng các hàm được thu thập không quan trọng, hãy xem xét closure-passing style.

Answer 5

Stroustrup đã thực hiện điều này trong trình biên dịch C++ đầu tiên chỉ đơn giản với một biểu tượng trên mỗi phạm vi và một quy tắc chuỗi theo sau cho đến định nghĩa được tìm thấy.Cách hoạt động chính xác tùy thuộc vào ngữ nghĩa chính xác của bạn. Hãy chắc chắn rằng bạn móng tay những người xuống đầu tiên.

Knuth in Nghệ thuật lập trình máy tính, Tập 1, đưa ra thuật toán cho bảng biểu tượng Cobol theo đó phạm vi được thực hiện thông qua liên kết.