Java 符號表設計的相關問題
========================
翻譯自：http://www.bearcave.com/software/java/java_symtab.html
很多Java語言處理器不會讀Java，而是讀Java類文件，并從類文件生成符號表和抽象語法樹。Java類文件里的代碼在語法和語義上都是正確的。結果就是這些工具的作者避免考慮實現一個Java前端時會遇到的很多困難的問題。
Java編程語言的設計者在設計這個語言時沒有考慮實現的簡單性。確實應當如此，因為更重要的是語言容易使用。設計Java編譯器前端的語義分析時遇到的一個很困難的問題就是符號表的設計。這個頁面零散地討論了一些Java符號表設計時遇到的問題。
編譯器的前端主要工作包括一下幾點：
1. 解析源代碼識別正確的程序，對不正確的結構報錯。對BPI這個Java前端來說，這個工作由ANTLR生成的一個解析器完成。解析器的輸出是一個抽象語法樹（AST），包括了源代碼里所有的聲明。
2. 從Java類文件中讀取聲明信息，對于本地Java編譯器來說，把AST編譯為字節碼。這也包括了下面的transitive closure（圖中所有可以從根節點到達的節點，從這個角度講這個圖是一個類組成的樹，通過這個樹可以定義所有需要被編譯器讀取的類文件。
3. 處理AST和類文件中的聲明，構造符號表。一旦這些聲明節點被處理，就從AST當中剔除掉。
前端的輸出是一個語法和語義上都正確的AST，每個節點都有一個指針指向一個標識符（如果這是一個葉節點的話）或一個類型（如果這是一個非終結節點或著一個類型引用，如MyType.class）。
“符號表”這個詞通常指代一種比表格（比如struct組成的數組）數據結構。當符號和類型被解析的時候，符號表必須反應當前正在被處理的AST的作用域。比如，下面的C語言代碼有三個叫`x`的變量，分散在不同的作用域里。
```c
static char x;
int foo() {
int x;
{
float x;
}
}
```
解析符號和類型需要遍歷AST來處理各種聲明。在遍歷AST中不同的作用域時，符號表始終反應當前作用域，這樣在查找`x`的時候，當前作用域的符號會被返回。
符號表的作用域結構只在解析符號和類型時有用。名字一旦解析完成。AST中名字和它的符號的關系可以直接通過一個指針找到。
Pascal和C語言（這兩種語言只有簡單的分層作用域）的編譯器使用的符號表通常都是直接鏡像語言的作用域。每個作用域都有一個符號表。每個符號表都有一個指針指向它上層作用域。最上層的根符號表就是全局符號表，包含了全局的符號和函數（或者是Pascal里的過程）。當進入一個函數作用域時，就創建一個函數符號表。這個函數符號表的父指針指向前面緊接著的一個“上面的”層（或是全局符號表，或是Pascal里一個閉合的過程或函數）。一個塊符號表指向它的父符號表，也就是函數符號表。符號搜索從當前作用域向全局作用域向上遍歷進行。
一旦符號和類型解析完畢，作用域層級就不需要了。然而函數或是類的局部作用域仍然很重要，而且這些局部作用域必須仍然可以被編譯器訪問這個作用域里的所有符號。比如，為了在函數調用時分配堆棧，編譯器必須能找到所有與這個方法相關的變量。Java編譯器必須能購跟蹤類的成員，因為這些變量會被分配到可以被垃圾回收的內存中。
大多數面向對象語言的作用域都比過程語言（C或PASCAL）要更復雜。C++支持多重繼承，Java支持多接口定義（多重繼承的一種正確方式）。符號表必須足夠高效這樣編譯器前端才不會花大量時間在查找符號上。Java編譯器的符號表設計主要有一下一些考慮：
1. Java有一個非常大的全局作用域，因為所有的類和包都被導入到這個全局的命名空間。全局符號必須存儲在一個大容量的數據結構中，而且查找的時間復雜度是O(n)，比如一個哈希表。
2. Java有非常多的局部作用域（類，方法和塊）只包含較少的符號（相對全局作用域而言），對于它們使用支持大容量和高速查找的數據結構有點過于復雜了（不論是內存使用還是代碼復雜度）。局部作用域應該用一個簡單而且相對快速（比如O(log2(n))）的數據結構實現。比如平衡樹和跳躍列表。
3. 符號表應該能支持一個作用域里定義多個相同名字。符號表必須能幫助編譯器解析兩種相同類型（比如都是函數）的相同名字在同一作用域中多次聲明產生的沖突。
在C語言里一個作用域里的名字必須是唯一的。比如，在C語言里一個叫MyType的類型和一個叫MyType的函數是不被允許的。在Java里一個作用域里的名字可以不是唯一的。名稱會根據它所在的上下文來解析。比如：
```java
class Rose {
Rose( int val ) { juliette = val; }
public int juliette;
} // Rose
class Venice {
void thorn {
garden = new Rose( 42 );
Rose( 86 );
garden.Rose( 94 );
}
Rose Rose( int val ) { garden.juliette = val; }
Rose garden;
} // venice
```
這個例子中有一個名為Rose的類，一個名為Rose的構造函數，一個名為Rose的方法返回一個類型為Rose的對象。編譯器必須要聯系上下文才知道哪個是哪個。而且注意引用的Rose方法和garden類型是在引用后面聲明的。
Java中大部分符號作用域可以被描述為一個簡單的層次關系（低層有指向高層的指針），除了和Java類相關的接口列表。注意接口也可以從上次接口繼承。下面是Java里作用域的分級：
```
Global (objects imported via import statements)
Parent Interface (this may be a list)
Interface (there may be a list of interfaces)
Parent class
Class
Method
Block
```
符號表和語義分析（檢查Java解析器返回的AST）代碼必須能夠解析一個符號定義是否在語義上是正確的。一個名稱的多個定義是允許的（比如多個類成員）。然而不明確的符號使用是不允許的：
>Java語言規范 (JLS) 8.3.3.3
>
>一個類可以繼承兩個或更多相同名字的屬性，或從兩個接口繼承或一個從父類繼承一個從接口繼承。只有在試圖只用簡稱來模糊的引用時才會發生編譯錯誤。明確的全稱或帶`super`關鍵字的屬性訪問是允許的。
父類和接口都可以把其中定義的符號導入本地作用域。下面的例子中符號`x`在`bar`和`fu`中都定義了，這是允許的，因為在`DoD`類中沒有引用`x`。
```Java
interface bar {
int x = 42;
}
class fu {
double x;
}
class DoD extends fu implements bar {
int y; // No error, since there is no local reference to x
}
```
如果`x`在類`DoD`中被引用了，編譯器必須報告一個錯誤，因為這種引用是不明確的
```java
class DoD extends fu implements bar {
int y;
DoD() {
y = x + 1; // Error, since the reference to x is ambiguous
}
}
```
簡稱的不明確性還會出現在接口定義的內部類和父類中：
```java
interface BuildEmpire
{
class KhubilaiKahn {
public int a, b, c;
}
}
class GengisKahn
{
class KhubilaiKahn {
public double x, y, z;
}
}
class mongol extends GengisKahn implements BuildEmpire
{
void mondo() {
KhubilaiKahn TheKahn; // Ambiguous reference to class KhubilaiKahn
}
}
```
Java不支持類的多重繼承，但是允許一個類實現多個接口或一個接口擴展（繼承）多個接口
>Java語言規范9.3
>
>一個接口可以繼承多個相同的名字，這種情況不會引起編譯錯誤。然而在接口內部試圖用簡稱來引用這個屬性會導致編譯錯誤，因為這樣的引用是不明確的。
比如，在下面的代碼中`key`是不明確的：
```java
interface Maryland
{
String key = "General William Odom";
}
interface ProcurementOffice
{
String key = "Admiral Bobby Inman";
}
interface NoSuchAgency extends Maryland, ProcurementOffice
{
String RealKey = key + "42"; // ambiguous reference to key
}
```
當當語義分析查找符號`key`時，符號表必須允許語義檢查代碼來決定有兩個對`key`的定義。符號表必須對作用域里的符號分類（成員和成員在一起，類和類在一起）。不像有些符號（方法，類和成員變量）沒有分類因為它們可以通過上下文區分。
一個方法的多次定義不會在Java中產生語義錯誤，因為沒有多重繼承。比如，如果一個同名方法從兩個接口中繼承，這個方法要么是相同的，要么是冗余版本。如果有一個本地方法和一個在父類中定義的方法有相同的名字和參數（簽名）。本地方法會在一個“更低的”作用域并且覆蓋父類的。
# Java 符號表的實現
## 符號表需求
考慮以上討論的幾點，一個符號表必須滿足以下需求：
1. 支持一個標識符的多種定義。
2. 在全局符號庫中快速查找，時間復雜度O(n)
3. 在局部（類、方法和塊）符號中相對快速的查找O(log2(n))
4. 支持Java的分層作用域
5. 可以按照符號類型搜索（成員、方法，類）
6. 快速決定一個符號定義是否是不明確的
## 符號的生存期
類似C的語言可以一次編譯一個函數。全局符號表必須保留當前文件中函數和它們的參數的符號信息。但是其他局部符號信息可以在函數編譯后忽略。當編譯器處理完一個`.c`文件（和被它引用的文件）中所有的函數后，所有的符號都被忽略了。
C++可以用類似的方法來編譯。定義在頭文件中的類引用一個對象。當文件處理后所有的符號可以忽略了。
Java更復雜。Java編譯器必須讀取Java符號定義來構建Class樹，這個樹用來確定當前正在編譯的類所引用的所有類文件。也就是包含`main`方法的對象。這點出發可以找到所有被引用的類。
理論上一旦所有引用的Java符號的類被編譯后，這些符號就可以被忽略了。實際上這樣造成如此多的問題還不如換一個內存大一點的系統。所以Java符號在整個編譯期間都存在。
## 構建符號表作用域
符號表中分層的作用域只在語義分析時有用。分析結束后，所有的符號（標識符節點）都會指到正確的符號上。然而，一旦作用域構建完，它就在那里了。
每個局部作用域（塊、方法和類）有一個局部的符號表指向包圍它的符號表。在頂層是全局符號表包含所有全局類和導入的符號。進行語義分析時從局部符號表向上層搜索，搜索每個符號表直到全局符號表搜索完。如果搜完全局符號表還沒有找到，這個符號就不存在。
Java的作用域不是一個由唯一的符號組成的簡單分層結構（像C語言一樣）。一個符號可能會有多個定義（類成員、方法或類名）。一個給定作用域的符號可能來自多個地方。比如下面的Java代碼中類`gin`和接口`tonic`在同一層定義了相同的符號。
```java
interface tonic {
int water = 1;
int quinine = 2;
int sugar = 3;
int TheSame = 4;
}
class gin {
public int water, alcohol, juniper;
public float TheSame;
}
class g_and_t extends gin implements tonic {
class contextName {
public int x, y, z;
} // contextName
public int contextName( int x ) { return x; }
public contextName contextName;
}
```
## 作用域、局部變量、參數
Java里的局部變量是方法中的變量，這些變量被分配到一個由塊或語句創建的堆棧中。如：
```java
class bogus {
public void foobar() {
int a, b, c;
{ // this is a scope block
int x, y, z;
}
}
}
```
不像C或C++，Java不允許重新聲明局部變量：
>Java語言規范JLS 14.3.2
>
>如果一個標識符被聲明為局部變量，而在其作用域內已有一個參數或本地變量，編譯器會報錯。因此下面的例子無法通過編譯：
> ```java
> class Test {
> public static void main( String[] args ) {
> int i;
>
> for (int i = 0; i < 10; i++) // Error: local variable redefinition
> redeclared
> System.out.println(i);
> }
> }
> ```
本地局部變量允許被重定義為類成員，這讓變量重定義檢查也成為語義分析的一部分工作。
## 向前引用
向前應用是引用一個聲明寫在該引用后面的符號。
當一個類屬性被初始化時，初始器必須在前面已經聲明并且初始化了。下面的例子（摘自JLS6.3）會報錯：
```java
class Test {
int i = j; // compile-time error: incorrect forward reference
int j = 1;
}
```
本地局部變量也不能向前引用，如：
```java
class geomancy {
public float circleArea( float r ) {
float area;
area = pie * r * r; // undefined variable 'pie'
float pie = (float)Math.PI;
return area;
}
}
```
然而，向前引用允許從一個局部作用域（一個方法）引用一個在同一個類中定義的類成員。比如，在下面的Java代碼中方法`getHexChar`向后引用了類成員`hexTab`：
```java
class HexStuff {
public char getHexChar( byte digit ) {
digit = (byte)(digit & 0xf);
char ch = hexTab[digit]; // legal forward reference to class member
return ch;
} // getHexchar
private static char hexTab[] = new char[] {
'0','1','2','3','4','5','6','7','8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
};
} // HexStuff
```
## 包
Java中最頂層編譯單元是包，要么是一個顯式命名的包或是一個未命名的包（包含`main`方法的函數）。所有的包都自動導入了默認的包`java.lang.*`和其他被本地系統所需要的包。用戶可以顯式的導入其他包。
當包A導入了包B，包B提供了：
* 用`public`修飾符標記的所有類和接口
* 子包（如導入到B中的其他包）
如果B包導入了包X，其中有一個公開類`foo`，這個類可以用全稱`X.foo`引用。
包給符號表加入了另一層復雜度。一個包好比一個對象，該對象定義了一堆類，接口和子包。一旦包被編譯器讀取，在下面如果有相同的導入語句就不會再讀了，因為它的定義編譯器都已經知道了。
一個包所定義的類、接口和包被導入到當前包的全局作用域。在Java代碼中，導入的包所定義的類名可以用簡稱來引用（JLS6.5.4），在被導入的包的子包中定義的類名可以用全稱引用。然而在符號表中所有的類名都與一個全名關聯著。
# 符號表實現概述
1. 支持一個給定標識符的多重定義。
所有有相同名字的標識符都被放在一個容器中。就像上面提到的，一個標識符可能是一個類成員，方法名或一個類名。一個定義可以有多個實例。比如上面Java代碼中類成員`TheSame`有兩個定義。容器可以用標識符的類型（成員，方法或類）來搜索，而且可以快速決定是否某個類型被多次定義（確定性引用）。如果一個對象命名了，符號會有一個屬性指向它的上層（函數或類）。對于一個塊這個指針是Null。注意上層不一定是上層作用域，定義在類`gin`和接口`tonic`中的符號在同一個作用域，但是它們有不同的上層。
2. 快速的全局搜索
全局符號表用大容量哈希表實現（哈希表能支持大量符號不用長的哈希鏈）
3. 包信息
一旦一個包被導入全局作用域，*這個包就不再被引用了*，導入的類名（類或接口）可以被引用，就如同它們是在當前編譯單元中定義的（通過簡稱）。子包也成了全局作用域中的對象。包類型名和額外的子包可以用全稱引用。
包定義保存在一個分開的包表里。包從這個表里導入到編譯單元的全局作用域。包信息在整個編譯期間都存在。
4. 局部查找
通常局部Java作用域中的符號很少。本地符號查找必須要快，但是不用像全局那么快，因為通常符號很少。
我設想了三種數據結構來實現局部符號表：
* [跳躍列表](http://www.cs.umd.edu/~pugh/)（也可以查看[Thomas Nienann關于跳躍列表的精彩網頁](http://members.xoom.com/_XMCM/thomasn/s_skl.htm)
* [紅黑樹](http://members.xoom.com/_XMCM/thomasn/s_rbt.htm)（一種平衡二叉樹）
* 簡單的二叉樹
對于小的符號表這三種數據結構的搜索時間都差不多。二叉樹在測試中是最小最簡單的算法，所以選擇它作為局部符號表。
5. 支持Java層次作用域
每個符號表都包含一個上層作用域的指針。
6. 支持以符號類型搜索
語義分析知道它所搜索符號的上下文（這個符號是成員、方法還是類）。符號表層次以標識符和類型來搜索。
7. 快速檢測一個符號定義是否是模糊的
多個相同類型的符號定義（比如兩個成員）被串在一起。如果`next`指針是NULL，那就有多個定義。錯誤報告代碼可以用這些定義報告給用戶沖突的符號是在哪里定義的。
## 符號表構造
在方法被處理之前，所有類成員引用都被處理并塞進符號表。這樣在方法中對成員的引用就可以正確的解析了。
方法內的聲明被順序處理。如果函數中一個名字的引用不能“看到”，就報告一個錯誤（未定義的名稱）。
## 遞歸編譯和符號表
當一個編譯單元（包）被編譯時，所有它引用的類和包信息必須存在。《Java語言規范》沒有準確定義這是怎么做的。規范中只說被編譯的Java代碼可以存在一個數據庫里或在一個目錄下，這個目錄結構和包和類的全名一一對應。類和包必須可以訪問。《Java虛擬機規范》定義了Java`.class`字節碼文件中的信息，但是沒有說編譯順序。盡管沒有規范Java是如何編譯的，但還是有“通用方法”。至少對于這個設計，“通用方法”基于Sun公司的`javac`編譯器和微軟的`Visual J++`編譯器`jvc`。
當一個編譯單元編譯完成時，所有該編譯單元所引用的外部類信息被記錄在編譯生成的字節碼文件中。字節碼文件可以打包成jar文件。就是一個用ZIP文件格式壓縮存放的字節碼文件層次。字節碼或jar文件存放在當前文件夾或CLASSPATH環境變量指定的目錄下。為了讓這個機制工作。文件名最好和相關聯的類名保持一致（如類`FooBar`用`FooBar.java`實現）
如果，當搜索類定義時，Java編譯器只找到一個`.java`文件定義了這個類或者這個`.java`文件的時間戳比相應的字節碼文件要新的話，Java編譯器會重新編譯這個類定義。
當編譯頂層的編譯單元時，Java編譯器跟蹤被導入到當前編譯單元的包對象（一個包括了多個類和子包的包）。包中不是public的類定義不會被編譯器保存，因為它們無法在包的外面看到。
Ian Kaplan, May 2, 2000
Revised most recently: May 31, 2000
