編譯器或解釋器前端對於作用域的處理方法？

01-05

在現今主流的編譯或解釋器前端（例如gcc，clang，javac，cpython，v8等）在語義分析過程中對於名字的作用域是如何進行記錄的？對於具體的名字查找又有什麼較為高效的演算法？

隨便寫點哈。題主限定於編譯器前端來提問，這個很好，可以很有針對性地回答。

有詞法作用域的語言的編譯器前端，在處理作用域的時候，常規做法是用嵌套哈希表（nested hashtable）作為核心數據結構來構成符號表（symbol table），記錄作用域信息。

最簡單地說，這個數據結構最核心的部分就像是這樣：

class Scope& { Scope next; // or spell as parent, enclosing, ... HashMap& table;


  public Entry findLocal(Symbol sym) {

    return this.table.get(sym);

  }
  public Entry find(Symbol sym) {

    Entry e = findLocal(sym);

    if (e == null  this.next != null) {

      return this.next.find(sym); // recursive lookup

    }

    return e;

  }

// ... }

這種Scope類為節點構成的嵌套哈希表，有時候也叫做「作用域棧」（scope stack），因為如果是一趟遍歷AST（或者做等價的語法制導翻譯）去構建並使用這樣的符號表，對這個符號表的操作就會是：

每當進入一個新的嵌套作用域，就push一個新的Scope進去，用於記錄該作用域里新引入的符號；
每當離開一個嵌套作用域時，就pop掉「棧頂」的Scope，恢復到外圍作用域的狀態。

其中的「Entry」里放什麼東西就取決於這個編譯器想幹什麼了。

不同的語言功能，例如類或結構體、函數或方法，它們對作用域的影響各有特點；而如果它們相互之間能有嵌套關係，則會進一步使得符號查找變得複雜。

但歸根到底，上面所說的核心數據結構都是適用的，只要根據具體需求適配一下。

===========================================

javac

OpenJDK 8u的javac里的符號表由Scope結構實現，請參考源碼：jdk8u/jdk8u/langtools: 2baeb96fa198 src/share/classes/com/sun/tools/javac/code/Scope.java

遍歷AST創建Scope並且向其中填充符號信息的是Enter pass，請參考源碼在這裡：jdk8u/jdk8u/langtools: 2baeb96fa198 src/share/classes/com/sun/tools/javac/comp/Enter.java

這個Scope里的Entry比較有趣，反映了Java多種能影響符號語義的功能的需求。例如說：

可以import / static import。需要把import相關信息也看作一種「作用域」；
頂層聲明只能是類 / 枚舉 / 介面 / 註解類型等類型聲明。它們都包含進一步嵌套的作用域；
頂層類型聲明裡面可以嵌套聲明其它包含自己作用域的元素，例如方法以及嵌套類型；
方法支持塊作用域；
方法里可以進一步嵌套聲明類型，例如局部類（local class）與匿名內部類；方法里也可以有lambda表達式，同樣可以有嵌套作用域。

對javac的工作流程不熟悉的同學，可以參考我以前寫的一組演示稿，第29頁開始的部分簡單介紹了一下javac：http://www.valleytalk.org/wp-content/uploads/2011/05/Java_Program_in_Action_20110727.pdf

===========================================

cbc（C-Flat）與C4

之前發過一帖介紹倆小眾簡易編譯器的作用域實現機制，請跳傳送門：

C 語言程序變數作用域的實現機制是什麼？ - RednaxelaFX 的回答
有哪些關於c4 - C in four function 編譯器的文章？ - RednaxelaFX 的回答

具體到C4的情況，可以看到，當源語言只允許兩種作用域：全局作用域與函數作用域，而不允許其它類型的嵌套作用域（例如函數內的塊作用域，又或者是嵌套函數），那麼符號表的時候可以非常簡單，只要一層（外加一層shadow）就夠用了。C4所支持的C語言子集就是這樣一種可以簡單實現的情況。

而具體到cbc的情況，它所支持的作用域有齊全局作用域、函數作用域以及函數內的塊級作用域；不支持嵌套函數。所以它的符號表設計就比較常規，跟本回答開頭提到的形式類似。

===========================================

LCC

LCC 4.x的符號表也很常規，同樣跟本回答開頭提到的形式類似。

其實現請參考源碼：lcc/sym.c at master · drh/lcc · GitHub 實現得還是相當直觀的。

===========================================

CPython

CPython的位元組碼編譯器（從Python源碼到CPython位元組碼）的實現有不少特別…偷懶的地方。

先放個傳送門：[新聞] CPython / 微軟 Pyjion / IBM Python+OMR - 編程語言與高級語言虛擬機雜談（仮） - 知乎專欄

參考裡面提到「作用域棧」的那一小塊。對CPython解釋器里的block stack熟悉的同學肯定知道我說的是什麼…

===========================================

其它

先放個傳送門，回頭再補充別的編譯器的設計/實現。

符號表和抽象語法樹是什麼關係？兩者在編譯器設計中是否必需？ - RednaxelaFX 的回答

每一個scope都有一個parent scope，那是一棵樹，查找名字的時候就從child通過parent往上爬到頂就好了。中間有一些節點可能會有特殊的name resolving的方法，譬如說你搜進了一個class，你就要去看this-&>有什麼額外的名字。搜到了module，你還要去看using。

只了解非主流編譯器的做法：GHC前端里有一個renaming pass，遍歷從parser出來的AST，分析結果就是滿足Barendregt convention的AST：每個綁定參數名都是獨特的。演算法本身就是一個簡單的state monad，遍歷AST時生成fresh identifier，並無新奇之處。

ref：https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/Renamer

戰五渣前來稍微解釋一下

可以用一個帶層級的scope 表來記錄，簡單實現就是一個scope類型就是一個hash表

在進入一個作用域的時候就新建一個scope，把所有聲明變數記錄進去

讀取變數的時候先從最低級的scope找一層層往上找，找到了就停止

這樣就可以很簡單處理變數名在不同作用域同名的問題。

如果是最簡單的那種，出作用域就可以捨棄scope不要了，那不會佔內存

但是如果要做掃描，優化的話可以記錄一下

可以很簡單的知道哪個變數聲明了沒有用之類的。