C 語言程序變數作用域的實現機制是什麼?

編譯之後的目標代碼中是不是有一個作用域的標籤來記錄的?


要推薦閱讀材料的話,對這個問題我會推薦lcc書《A Retargetable C Compiler》的第3章:這本書透徹的講解了一個簡單但完整的C語言編譯器lcc 3.x的設計與實現,而第3章整章就是用於講解符號表管理的。

符號表的使用貫穿lcc,一直到最後的代碼生成;第16、17、18章分別講述了對MIPS、SPARC和x86的代碼生成,可以看到符號表在代碼生成過程中的作用——將局部變數映射到寄存器或著調用棧上,將全局變數映射到全局地址上,等等。

在代碼生成後,符號表就消失了,生成出來的代碼里就不再帶有局部變數的符號信息,對局部變數的「作用域」概念也就隨之消失。

不過值得留意的是,雖然執行最終生成的代碼並不需要對局部變數的符號表信息,但涉及鏈接(無論是靜態還是動態鏈接)的地方還是會用到符號表。在目標文件里的函數層面符號表信息通常會以「導入表」(import table)和「導出表」(export table)的方式記錄自己依賴於什麼外部提供的實現,而自己又暴露出了哪些實現給外部使用。對於可重定位的目標文件(relocatable object file),還會有一個「重定位表」(relocation table)來記錄代碼中包含的需要修正的地址的偏移量。

另外,調試符號信息也是一種可選的、源自符號表的信息。這種信息對程序執行本身沒什麼用,但是對調試器是至關緊要的——有了它才可以在調試的時候映射回源程序的行號、變數。所以調試符號信息可能包含局部變數的符號信息(包括變數名、類型、作用域等都有可能包含在內)。

這樣就完美解答了題主的問題。

lcc 4.x的代碼在Github上:drh/lcc · GitHub

講編譯原理的書多半都會介紹符號表的概念,不過既然題主問的是C語言的變數作用域的實現,那我還是首推實際介紹C語言編譯器的實現的書 ^_^

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

然後是我自己碼的回答。

題主的問題:

編譯之後的目標代碼中是不是有一個作用域的標籤來記錄的?

常見情況:不是。

  • 只考慮代碼執行的需求的話,C的變數作用域通常只是編譯器前端里的概念,如果不考慮輸出調試符號信息的需求的話,變數作用域在編譯器後端是不需要的。

  • 如果考慮上生成的目標代碼要支持源碼級調試,那麼行號、變數名及其作用域等信息都得記錄下來。結果就是類似DWARF、PDB這樣的專門存調試符號信息的格式;很重要所以得再說一次,這些信息並不是執行代碼所必須的。

簡單說,編譯器可以分為前端和後端兩部分。

  • 前端負責:詞法分析 -&> 語法分析 -&> 語義分析 -&> 中間代碼生成

  • 後端負責:平台無關優化 -&> 指令選擇 -&> 平台相關優化 -&> 指令調度 -&> 寄存器分配 -&> 目標代碼生成

做優化比較多的編譯器還可以從後端分出一塊「中端」(middle-end)來,專門負責做優化,而讓「後端」只負責做目標代碼生成(可能包括寄存器分配)。

在編譯器前端里,從開始一直到語義分析的階段,會有一種叫做「符號表」(symbol table)的數據結構貫穿於編譯過程中。符號表是實現變數作用域的關鍵——常見做法是用hashtable來實現 (變數名 -&> 變數信息) 的映射關係,並且通過嵌套的符號表來實現作用域。

看個例子,一個用Java實現的C的簡化版C-flat語言的編譯器cbc里的作用域實現:

cbc/LocalScope.java at master · aamine/cbc · GitHub

  • 它用Map&來記錄本作用域的變數名映射關係;
  • 它用parent鏈來構成嵌套的作用域。變數名的搜索總是從當前作用域開始,找不到再到上一層作用域搜索,直到到達頂層作用域為止。

再看個簡單的例子,巨緊湊的迷你C編譯器c4里也有符號表:

c4/c4.c at master · EarlGray/c4 · GitHub

其中的int *sym就是符號表。不過c4不支持嵌套作用域,變數只支持函數級別(local)和全局級別(global)的作用域,所以處理起來相當簡單:

  • 局部變數的處理:見 if (d[Class] == Loc)

  • 全局變數的處理:見 else if (d[Class] == Glo)
  • 還有一些特殊處理的命名空間,例如函數見 else if (d[Class] == Fun)
  • …等等。

關於c4的更詳細的分析,請參考另一個回答:有哪些關於c4 - C in four function 編譯器的文章? - RednaxelaFX 的回答

編譯器的前後端不一定要共用同一份符號表。

簡單的編譯器可能會選擇讓前後端共享同一個符號表,因為後端生成的代碼的模式可能跟語言層面的概念仍然有緊密聯繫(例如說源碼中的局部變數概念可能一直持續到了代碼生成階段);上面舉的lcc、cbc、c4都是如此。

而更複雜的編譯器中,後端處於優化的需求可能不會維護與前端一一對應的「變數」概念,例如說源碼層面的一個變數的多次定義(賦值)可能會在後端里被拆分為多個變數,或者說後端可能根本不需要符號表,這樣的話跟前端共享符號表的意義就不大了。

另一方面,如果一個編譯器後端是想獨立出來作為一個庫,允許多種前端插在上面搭配使用的話,為了解耦也會選擇不與前端共享符號表,例如Clang(前端)的符號表就不會持久到LLVM(後端)里。

如果後端根本不需要符號表的話,那作用域信息到後端就已經消失了——反正前端已經在語義分析檢查過代碼的正確性,而變數的定義與使用不可能超過其可見範圍——作用域——所以其實後端在知道變數的定義與使用的情況下也就不需要額外的符號表信息了。

這方面請參考另一個問題的回答:如果變數在後面的代碼中不再被引用, 在生存期內, 它的寄存器可以被編譯器挪為他用嗎? - RednaxelaFX 的回答

最開頭也提到過,雖然只是為了生成可執行代碼並不需要在目標代碼裡帶有符號表,但如果要支持調試的話這種信息可能還是需要的。基本上這就是要求編譯器後端要有機制能跟蹤優化後的變數跟源碼層面的變數的對應關係(不過此時不一定是一一對應了,可能有多個後端變數對應一個源碼層面的變數),並且將該信息輸出到編譯生成的產物里(不一定在目標代碼里,而可能在附帶的外部數據結構,例如前面提到的DWARF格式或PDB格式的文件)。


先佔個坑,爪機打字沒資料參考,晚上回去接著寫啊。

作用域的處理有兩種方式。1.對於那些將語法,語義分析,中間代碼生成等作為一遍 的編譯器來說,每個作用域用一個env類表示,裡面存有一個基於hash表的名字表names,存儲該作用域下所有的符號,一個指向外層作用域的outer指針。有一個指向當前分析所處的作用域top,每次進入一個作用域,保存top指針,令top指向一個新建的作用域env類,這是龍書編譯原理 (豆瓣)裡面講解編譯器前端的做法。

2. 對於那種語法分析,語義分析,中間代碼生成分成多遍的編譯器來說,就不能採用上面的方法了。對於Java的內部編譯器——Generic Java Compiler,源代碼可以看openJdk裡面的的編譯器,建議看低版本的。它採用一個符號表的類Symtab保存整個程序中所有的符號名字(使用Names類保存,所有的名字字元串都存放在一個公共的字元串池中,通過hash查找)頂層的TopLevel作用域scope,然後每一個作用域都有一個指向該作用域內部的指針next

符號表的處理單獨在一趟中完成。分兩個階段:第一:也就是遞歸下降遍歷AST,將遇到的符號添加到它們相應的範圍scope,這個階段完成對類中本身符號的添加,包括該類的參數parameters,父類型supertype,實現的介面類型interfaces。

下面的代碼分別是進入到頂層——即一個Java源文件的開始,類和方法時的處理函數

/**
* Create a fresh environment for method bodies.
* @param tree The method definition.
* @param env The environment current outside of the method definition.
*/
Env methodEnv(MethodDef tree, Env env) {
Env localEnv = env.dup(tree,
((AttrContext) env.info).dup(
((AttrContext) env.info).scope.dupUnshared()));
localEnv.enclMethod = tree;
((AttrContext) localEnv.info).scope.owner = tree.sym;
if ((tree.flags STATIC) != 0)
((AttrContext) localEnv.info).staticLevel++;
return localEnv;
}

/**
* Create a fresh environment for class bodies.
* This will create a fresh scope for local symbols of a class, referred
* to by the environments info.scope field.
* This scope will contain
* - symbols for this and super
* - symbols for any type parameters
* In addition, it serves as an anchor for scopes of methods and initializers
* which are nested in this scope via Scope.dup().
* This scope should not be confused with the members scope of a class.
*
* @param tree The class definition.
* @param env The environment current outside of the class definition.
*/
public Env classEnv(ClassDef tree, Env env) {
Env localEnv =
env.dup(tree, ((AttrContext) env.info).dup(new Scope(tree.sym)));
localEnv.enclClass = tree;
localEnv.outer = env;
((AttrContext) localEnv.info).isSelfCall = false;
return localEnv;
}

/**
* Create a fresh environment for toplevels.
* @param tree The toplevel tree.
*/
Env topLevelEnv(TopLevel tree) {
Env localEnv = new Env(tree, new AttrContext());
localEnv.toplevel = tree;
localEnv.enclClass = predefClassDef;
tree.namedImportScope = new Scope(tree.packge);
tree.starImportScope = new Scope(tree.packge);
((AttrContext) localEnv.info).scope = tree.namedImportScope;
return localEnv;
}

第二:通過一個方法完成對類中成員的添加,保證在該類中定義的符號均被添加到相應的可見域scope。

相應的代碼如下,採用訪問子visitor模式:

/**
* Enter all members of a class. This is done in a second phase
* after the classes themselves have been entered.
*/
protected class MemberEnter extends Tree.Visitor {

protected MemberEnter() {
super();
}

最後,當該Enter訪問子類處理完成之後,類相應的符號就處理完了,接下來就是同樣的繼承抽象訪問子Visitor類,對不同的語法樹成分進行處理,下面是抽象訪問子類的實現:

package tree;

/**
* 用於對抽象語法樹(AST)中每個結點訪問的抽象類 針對不同的處理階段,生成不同的子類, 比如:進行類型檢查的TypeCheckingVisitor。
* 而針對每一種類型的樹結點,都有相應的visit方法的重載形式。
*
* @author Jian p Zeng.
* @version 1.0
*/
public abstract class Visitor
{
/**
* A generic visitor class for trees.
*/

public Visitor()
{
super();
}

/**
* A method visits topLevel tree node.
* @param that
*/
public void visitTopLevel(TopLevel that)
{
visitTree(that);
}

/**
* A method visits import declaration tree node.
* @param that
*/
public void visitImport(Import that)
{
visitTree(that);
}

/**
* A method visits Class and interface definition tree node.
* @param that
*/
public void visitClassDef(ClassDef that)
{
visitTree(that);
}

/**
* A method visits method declaration tree node.
* @param that
*/
public void visitMethodDef(MethodDef that)
{
visitTree(that);
}

/**
* A method visits variable definition tree node.
* @param that
*/
public void visitVarDef(VarDef that)
{
visitTree(that);
}

/**
* Skips no-op statements.
* @param that
*/
public void visitSkip(Skip that)
{
visitTree(that);
}

/**
* A method visits Block statements tree node.
* @param that
*/
public void visitBlock(Block that)
{
visitTree(that);
}

/**
* A method visits do while loop tree node.
* @param that
*/
public void visitDoLoop(DoLoop that)
{
visitTree(that);
}

/**
* A method visits while loop tree node.
* @param that
*/
public void visitWhileLoop(WhileLoop that)
{
visitTree(that);
}

/**
* A method visits for loop tree node.
* @param that
*/
public void visitForLoop(ForLoop that)
{
visitTree(that);
}

/**
* A method visits labeled statement tree node.
* @param that
*/
public void visitLabelled(Labelled that)
{
visitTree(that);
}

/**
* A method visits switch statement tree node.
* @param that
*/
public void visitSwitch(Switch that)
{
visitTree(that);
}

/**
* A method visits case statement of switch tree node.
* @param that
*/
public void visitCase(Case that)
{
visitTree(that);
}

/**
* A method visits synchronize block tree node.
* @param that
*/
public void visitSynchronized(Synchronized that)
{
visitTree(that);
}

/**
* A method visits try tree node.
* @param that
*/
public void visitTry(Try that)
{
visitTree(that);
}

/**
* A method visits catch tree node.
* @param that
*/
public void visitCatch(Catch that)
{
visitTree(that);
}

public void visitConditional(Conditional that)
{
visitTree(that);
}

public void visitIf(If that)
{
visitTree(that);
}

public void visitExec(Exec that)
{
visitTree(that);
}

public void visitBreak(Break that)
{
visitTree(that);
}

public void visitContinue(Continue that)
{
visitTree(that);
}

public void visitReturn(Return that)
{
visitTree(that);
}

public void visitThrow(Throw that)
{
visitTree(that);
}

public void visitAssert(Assert that)
{
visitTree(that);
}

public void visitApply(Apply that)
{
visitTree(that);
}

public void visitNewClass(NewClass that)
{
visitTree(that);
}

public void visitNewArray(NewArray that)
{
visitTree(that);
}

public void visitParens(Parens that)
{
visitTree(that);
}

public void visitAssign(Assign that)
{
visitTree(that);
}

public void visitAssignop(Assignop that)
{
visitTree(that);
}

public void visitUnary(Unary that)
{
visitTree(that);
}

public void visitBinary(Binary that)
{
visitTree(that);
}

public void visitTypeCast(TypeCast that)
{
visitTree(that);
}

public void visitTypeTest(TypeTest that)
{
visitTree(that);
}

public void visitIndexed(Indexed that)
{
visitTree(that);
}

public void visitSelect(Select that)
{
visitTree(that);
}

public void visitIdent(Ident that)
{
visitTree(that);
}

public void visitLiteral(Literal that)
{
visitTree(that);
}

public void visitTypeIdent(TypeIdent that)
{
visitTree(that);
}

public void visitTypeArray(TypeArray that)
{
visitTree(that);
}

public void visitErroneous(Erroneous that)
{
visitTree(that);
}

public void visitTree(Tree that)
{
assert false;
}

}


不是。

編譯期之後,作用域這個概念就不存在了。每一個變數就變成了一個一個的地址。

以我的水平,這個問題想講清楚實在是很困難。

我可以推薦你一本書。

如果你有基礎,了解彙編語言,了解 CPU 寄存器和各種指令的工作原理,了解編程中常用的一些數據結構,那我推薦著名的「龍書」:《Compilers (豆瓣)》。

如果只是想了解一下,科普水平的話,那我推薦這一本:《編譯器構造C語言描述 (豆瓣)》


寫個程序看下反彙編代碼就明白了。C語言的變數就兩種,全局變數和局部變數,全局變數是存放在數據節裡面,通過它們的虛擬地址去訪問,所以它們的作用域是程序的整個運行期,局部變數是在當前棧幀的棧上,通過ebp寄存器去訪問,所以它們的作用域是當前棧幀未被銷毀期間


以單片機(不上操作系統)的C語言和彙編語言為例,全局變數是存在於內存區(RAM)的,編譯成彙編代碼後,引用的全局變數就直接是一個絕對地址。局部變數在函數里,調用函數的時候會有現場(cpu寄存器)入棧(硬體有棧stack結構)的操作,函數引用的變數也是在同一個棧結構裡面的,引用的地址是棧指針的加減某個偏移量後所確定的地址,是一個相對地址,函數返回時,把之前入棧的cpu寄存器出棧(還原現場),棧指針重置,局部變數丟失。而這些也不是固定的,要依據編譯器來看,據說51單片機的C語言編譯器局部變數是定義在RAM區的,所以函數是不可重入的(操作系統中多個線程調用同個函數會出現資源衝突)。

如果是計算機的話,編譯器應該是有結合操作系統的,使用到堆棧這些應該是使用軟體方式來提供,不過原理應該是一樣的。

有什麼說的不對的地方歡迎更正指教。


堆和棧


作用域只是高層語言的抽象概念,編譯後表現為對變數的可訪問性(變數的地址),注意可訪問性與作用域的方向不一樣。其中的機制就是語法規則等。


賦值


用malloc動態申請的內存則是動態的在堆中申請,申請順序是從上向下,按地址來說就是從低地址向高地址寫,這種內存你不釋放他,他是不會自動釋放的,假如你忘了用free,那麼這塊內存就泄露了.


變數分成全局,局部,又可分為靜態(static),非靜態,初始化或非初始化。對應的內存區域都不同。比如局部變數,在stack中,出了函數調用,變數就消失了。


c語言的話,在linux32位系統里差不多是這樣的:

在硬碟上每個進程都有一塊4G的虛擬內存,其中分為3G的用戶空間和1G的內核空間,其中用戶空間是這樣分配的

代碼載入到內存就放在代碼段里,然後初始化後的全局變數和靜態變數就放在初始化數據段里,未初始化的全局變數就放在未初始化數據段里,接著開始一行一行執行代碼碰到一個函數就放到最底下的棧里,其中局部變數都在這.注意棧是從下往上寫的,按地址來說就是從高地址往低地址寫,就像落盤子,進入一層函數就落一個盤子,返回一個函數就拿走一個盤子,所以最先進入的函數總是最後一個返回....因為用戶空間大概3G所以棧地址的開始值差不多是比0xbf8a6a1c稍微大一些的一個值.

而,用malloc動態申請的內存則是動態的在堆中申請,申請順序是從上向下,按地址來說就是從低地址向高地址寫,這種內存你不釋放他,他是不會自動釋放的,假如你忘了用free,那麼這塊內存就泄露了.

總之,你要是用太狠了,堆和棧會在內存的某個位置相遇,報一個錯然後退出,差不多是這樣.C語言的變數作用域差不多是這樣,C艹的命名空間俺就不懂了............................


推薦閱讀:

哪些字體適合程序員用來維護代碼?
達到什麼樣的程度才算精通 Android開發?
這段代碼為何能輸出"Hello World"?
如何高效自學編程?
視頻網站的彈幕是如何保存的?

TAG:程序員 | C編程語言 | 程序 | 編譯原理 |