以解釋型語言存儲變量的數據結構

我正在設計自己的實驗性腳本語言，以便將其嵌入到我的更大的應用程序中。以解釋型語言存儲變量的數據結構

幾乎所有我想做的事情都是順利編程的，但在內存中存儲變量的「簡單」行爲似乎是最難的部分。我不知道如何存儲它們以允許所有類型檢查，全局變量和特殊標誌。首先看一個示例代碼：

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

我稱之爲變量他們level的「局部性」因此，在嵌套塊中的變量有一個較高的水平。在上面的代碼中，a和b是1級變量。 someFunction的局部變量將具有級別2.函數的第一行應該讀取全局變量a（級別1），但第二行應該創建一個變量，再次調用a，但是級別2會從該點開始向全局變化a。第三行應創建級別爲2的變量x。如何在內存中存儲和跟蹤所有這些內容？

我試過到目前爲止：

方法1：存儲variable=>value地圖中的水平排列：

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

但是，這將使變量的查找速度很慢，因爲一個有搜索給定變量的所有級別。

方法2：存儲（變量，電平）對作爲映射的鍵：

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

這如之前因爲我們必須嘗試對（變量，電平）與所有可能有同樣的問題給定變量的級別。

我應該使用什麼方法來優化內存使用和最快的訪問時間？

其他注意事項：

我知道變量是如何在棧和堆其他「真正的」語言管理，但我覺得很棘手做到這一點的一種解釋型語言。「這一定不是Lua和Python如何做到的，」我一直認爲。如我錯了請糾正我。我試圖將變量存儲在地圖和內部C++結構中。

最後，這是我如何表示一個變量。你認爲它很大，可以有更多的高效內存表示？（我也嘗試把「級」作爲一個成員在這裏，但它也有同樣的問題，因爲其他的。）

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 
    }; 
};

來源

2012-02-20 Hossein

我會使用一個映射將每個變量名映射到一個變量實例堆棧當您在一個級別上創建一個新變量時，變量在堆棧上，堆棧中最頂層的元素用這個名字保存當前可見的變量實例，你還必須爲每個級別維護一個分配變量的列表，以便在離開該級別時從堆棧中彈出變量。感覺，我從來沒有自己設計過一種語言 – Nobody 2012-02-20 11:15:56

你可以簡單地使用一堆數組和de Bruijn索引的某種形式，執行一個原始的「compi通過解析所有名字來解釋。 – 2012-02-20 15:21:57

一件容易的事，類似的陣列，是保持一疊地圖。每個映射都包含該範圍的綁定。綁定一個變量，將其添加到頂層地圖;查找變量，從堆棧頂部開始，當到達包含該變量綁定的映射時停止。搜索需要一點點，但從頂部/結尾開始，您只需搜索，直到找到它 - 在大多數情況下，搜索將不會很長。

您也可以通過將此邏輯封裝在Environment類中來使其隱含，該類具有本地綁定和用於解析未知變量的繼承環境。需要進入新的範圍？創建一個以當前環境爲基礎的新環境，使用它，然後在作用域完成時放棄它。根/全局環境只能有一個空的繼承環境。這是我可能會做的。

來源

2012-02-20 15:09:23

看起來這就是Python如何做的事情：[見維基百科]（http://en.wikipedia.org/wiki/Stack_machine） – dantiston 2014-09-04 20:34:30

值得注意的是，如果在一個函數內部，你不能訪問調用者函數中的任何變量，它會降低你需要查看的級別數量。例如：

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 
    } 
}

想法是功能界限限制變量的可見性，全局範圍是「特殊的」。

話雖這麼說，你可以考慮刪除全局變量的特殊性，但允許代碼指定他們希望訪問非本地變量

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; 
}

起初看上去複雜，但它真的很容易瞭解一旦你習慣了它（upvar是一種來自Tcl編程語言的構造）。它允許你訪問調用者範圍內的變量，但它可以避免一些昂貴的查找，因爲它需要你明確指定變量來自哪裏（其中1是調用堆棧的一級，2是兩級，＃0在說「最上面的調用堆棧，全局」時是「特殊的」）

來源

2012-02-21 06:00:09 RHSeeger

以解釋型語言存儲變量的數據結構

回答

相關問題