Cấu trúc dữ liệu để lưu các biến trong ngôn ngữ thông dịch

Question

Tôi đang thiết kế ngôn ngữ kịch bản thử nghiệm của riêng mình cho mục đích nhúng biến đó vào ứng dụng lớn hơn của tôi.

Hầu như mọi thứ tôi muốn làm đều được lập trình suôn sẻ, nhưng hành động lưu trữ đơn giản trong bộ nhớ dường như là phần khó nhất ở đây. Tôi không biết làm thế nào để lưu trữ chúng để cho phép tất cả các loại kiểm tra, biến toàn cầu và cờ đặc biệt trên chúng. Đầu tiên nhìn vào một mẫu mã:

a = 1 
b = 2 

someFunction() 
    print(a) --> This should read the global variable and print `1` 
    a = 3  --> Now `a` should become a local variable of this function 
       and the global `a` remain unchanged 
    x = 4  --> `x` should always be local of this function 
end 

tôi gọi là "địa bàn" của các biến họ level s nên biến trong khối lồng nhau có một trình độ cao hơn. Trong đoạn mã trên, a và b là các biến cấp 1. Các biến cục bộ của hàm someFunction sẽ có cấp 2. Dòng đầu tiên của hàm cần đọc biến global a (cấp 1) nhưng dòng thứ hai sẽ tạo biến một lần nữa được gọi là a nhưng với cấp 2 che toàn cầu a từ thời điểm đó trở đi. Dòng thứ ba sẽ tạo biến số x với cấp 2. Làm thế nào để lưu trữ và theo dõi tất cả các bộ nhớ này?

gì tôi đã cố gắng cho đến nay:

Phương pháp 1: Lưu trữ bản đồ của variable=>value trong mảng Vị trí tầng:

variables 
{ 
    level=1 //global variables 
    { 
     a => 1, 
     b => 2 
    }, 
    level=2 //function variables 
    { 
     a => 3, 
     x => 4 
    } 
} 

Nhưng điều đó sẽ làm cho biến nhìn lên rất chậm kể từ khi người ta phải tìm kiếm tất cả các cấp cho một biến nhất định.

Cách 2: Lưu trữ các (biến, mức độ) cặp như phím của bản đồ:

variables 
{ 
    (a, 1) => 1, //global 
    (b, 1) => 2, //global 
    (a, 2) => 3, //function 
    (x, 2) => 3 //function 
} 

này có cùng một vấn đề như trước đây vì chúng ta phải cố gắng cặp (biến, mức độ) với tất cả khả năng mức cho một biến nhất định.

Tôi nên sử dụng phương pháp nào để sử dụng bộ nhớ tối ưu và thời gian truy cập nhanh nhất?

Ghi chú thêm:

tôi biết về cách biến được quản lý trên stack và heap trên các ngôn ngữ khác "thực", nhưng tôi thấy nó khó khăn để làm điều này trên một ngôn ngữ giải thích. "Đây không phải là cách Lua và Python làm điều đó," tôi luôn nghĩ. Đúng nếu tôi sai. Tôi đang cố gắng lưu trữ biến trong bản đồ và cấu trúc C++ bên trong.

Và cuối cùng, đây là cách tôi đại diện cho một biến. Bạn có nghĩ rằng nó lớn và có thể có nhiều biểu diễn hiệu quả về bộ nhớ hơn không? (Tôi cũng đã cố gắng để đưa các "Cấp" như một thành viên ở đây nhưng nó có cùng một vấn đề như người kia quá.)

struct Member 
{ 
    uchar type; //0=num, 1=str, 2=function, 3=array, etc 
    uchar flags; //0x80 = read-only, 0x40 = write-only, etc 
    union { 
     long double value_num; 
     char* value_str; 
     int value_func; 
     //etc 
    }; 
}; 

Answer 1

Một điều dễ dàng để làm, tương tự như mảng của bạn, là để duy trì một chồng bản đồ. Mỗi bản đồ chứa các ràng buộc cho phạm vi đó. Để liên kết một biến, hãy thêm biến đó vào bản đồ trên cùng; để tìm kiếm một biến, hãy bắt đầu ở đầu ngăn xếp và dừng lại khi bạn đến một bản đồ có chứa một ràng buộc cho biến đó. Tìm kiếm mất một chút, nhưng bắt đầu từ đầu/cuối bạn chỉ phải tìm kiếm cho đến khi bạn tìm thấy nó - trong hầu hết các trường hợp, tìm kiếm này sẽ không quá dài.

Bạn cũng có thể làm cho ngăn xếp tiềm ẩn bằng cách đóng gói logic này trong lớp Environment có gắn kết cục bộ và môi trường thừa kế được sử dụng để giải quyết các biến không xác định. Cần phải đi vào một phạm vi mới?Tạo một môi trường mới với môi trường hiện tại làm cơ sở của nó, sử dụng nó, sau đó loại bỏ nó khi phạm vi kết thúc. Môi trường root/global chỉ có thể có một môi trường thừa kế rỗng. Đây là những gì tôi có thể làm.

Answer 2

Cần lưu ý rằng nếu bên trong một hàm, bạn không có quyền truy cập vào bất kỳ biến nào từ hàm người gọi, nó sẽ làm giảm số lượng các cấp bạn cần xem xét. Ví dụ:

variable a; 

function one() { 
    variable b; 
    // in this function, we can see the global a, local b 
    two(); 
} 

function two() { 
    // in this function, we can see the global a, local c 
    // we cannot see the local b of our caller 
    variable c; 
    while (true) { 
     variable d; 
     // here we can see local d, local c, global a 
    } 
} 

Ý tưởng là ranh giới chức năng giới hạn khả năng hiển thị của các biến, phạm vi toàn cầu là "đặc biệt".

đó đang được nói, bạn có thể xem xét loại bỏ các specialness của các biến toàn cầu, nhưng cho phép mã để xác định rằng họ muốn truy cập vào các đại lượng không địa phương

variable a; 

function one() { 
    global a; // or upvar #0 a; 
    variable b; 
    // in this function, we can see the global a, local b 
    two(); 
} 

function two() { 
    // in this function, we can see the local c 
    // and the local b of our caller 
    // (since we specifically say we want access to "b" one level up) 
    upvar 1 b; 
    variable c; 
} 

Có vẻ phức tạp lúc đầu, nhưng nó thực sự dễ dàng để hiểu một khi bạn quen với nó (upvar là một cấu trúc từ ngôn ngữ lập trình Tcl). Điều này cho phép bạn truy cập vào các biến trong phạm vi của người gọi, nhưng tránh một số tra cứu tốn kém có liên quan bằng cách yêu cầu bạn chỉ định chính xác vị trí của biến đó (với 1 là một cấp lên ngăn xếp cuộc gọi, 2 là hai cấp, và # 0 là "đặc biệt" khi nói "ngăn xếp cao nhất, toàn cầu)