詞法範圍如何實現？

Question

幾年前，我開始爲一個包含程序員定義的函數的域特定語言編寫一個解釋器。

首先我使用一個簡單的符號表堆棧來實現變量作用域。但是現在我想轉向適當的詞彙範圍界定（可以選擇關閉）。任何人都可以解釋或指出我對詞法作用域背後的數據結構和算法的一個很好的解釋嗎？

Answer 1

沒有單一的正確方法來做到這一點。重要的是要清楚地說明你希望提供的語義，然後將遵循數據結構和算法。

Answer 2

爲了得到正確的詞彙範圍和封鎖在一個解釋，所有你需要做的就是遵循以下規則：

• 在你的解釋中，變量總是在主叫者通過在環境表擡頭/保持爲變量，而不是一些全局的env-stack。那就是eval(expression, env) => value。
• 當解釋代碼調用函數時，環境是而不是傳遞給該函數。 apply(function, arguments) => value。
• 當一個解釋的函數被調用時，它的主體被評估的環境是函數定義被創建的環境，並且與調用者沒有任何關係。所以如果你有一個本地函數，那麼它是一個關閉，也就是一個包含字段{function definition, env-at-definition-time}的數據結構。

要在Python中上下的語法，最後一位拓展：

x = 1 
return lambda y: x + y 

，好像它是

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

被執行，其中第二字典的說法可能只是當前-ENV而不是當時構建的數據結構。 （另一方面，保留整個env而不僅僅是封閉的變量會導致內存泄漏。）

Answer 3

例如，讀取The implementation of Lua 5.0。

Answer 4

有很多不同的方法來實現詞彙範圍。下面是一些我的最愛：

• 如果您不需要超高速的性能，使用純功能的數據結構來實現你的符號表，幷包含一個指向一對代表一個嵌套函數代碼和一個指向符號表的指針。

• 如果您需要本地代碼速度，我最喜歡的技術在Simon Marlow和Simon Peyton Jones的Making a Fast Curry中描述。

• 如果您需要本地代碼速度，但是curried函數並不重要，請考慮closure-passing style。

Answer 5

Stroustrup的實現這在第一C++編譯器簡單地與每一個範圍的符號表，以及向外隨後範圍，直到定義找到一個鏈接規則。這如何工作完全取決於你的精確語義。確保你先把它釘死。

Knuth in 計算機編程的藝術，第1卷，給出了一個Cobol符號表的算法，通過鏈接進行範圍界定。