編譯數據的結構

① 編譯原理的數據結構

編譯原理一直是計算機學習的必修課.
當然，由編譯器的階段使用的演算法與支持這些階段的數據結構之間的交互是非常強大的。編譯器的編寫者盡可能有效實施這些方法且不引起復雜性。理想的情況是：與程序大小成線性比例的時間內編譯器，換言之就是，在0 （ n ）時間內，n是程序大小的度量（通常是字元數）。本節將講述一些主要的數據結構，它們是其操作部分階段所需要的，並用來在階段中交流信息。 臨時文件（temporary file）：計算機過去一直未能在編譯器時將整個程序保留在存儲器中。這一問題已經通過使用臨時文件來保存翻譯時中間步驟的結果或通過「匆忙地」編譯（也就是只保留源程序早期部分的足夠信息用以處理翻譯）解決了。存儲器的限制現在也只是一個小問題了，現在可以將整個編譯單元放在存儲器之中，特別是在可以分別編譯的語言中時。但是偶爾還是會發現需要在某些運行步驟中生成中間文件。其中典型的是代碼生成時需要反填（backpatch）地址。例如，當翻譯如下的條件語句時 if x = 0 then ... else ... 在知道else部分代碼的位置之前必須由文本跳到else部分：
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常，必須為NEXT的值留出一個空格，一旦知道該值後就會將該空格填上，利用臨時文件可以很容易地做到這一點。
如果想利用上面的編譯原理開發一套屬於自己的編程語言，或者想在一個產品中嵌入編程語言，可以參考zengl開源網開發的zengl編程語言，該編程語言為國人使用C語言開發，裡麵包含兩個部分，一個是編譯器，一個是解釋執行中間代碼的虛擬機。編譯器包含了詞法掃描，語法分析，中間代碼輸出等，虛擬機則類似JAVA一樣解釋執行中間代碼。作者將所有的版本都公布出來，好讓讀者可以由淺入深的做研究，並且為了證明該編程語言的實用性，還結合SDL游戲開發庫開發了一款圖形界面和命令行界面的21點撲克小游戲 。
zengl編程語言目前適用平台為windows和linux (最開始在Linux下使用gcc開發，後來移植到windows平台)

② C語言代碼組成 - BSS、Data、Stack、Heap、Code、Const

一段C語言經過編譯連接後，成為一段可以運行的代碼，可運行的代碼可以分為以下四個部分組成：全局變數/靜態變數區、堆、棧、代碼區。其中全局變數/靜態變數區又分為未初始化變數區和初始化變數區，代碼區又分為代碼和常量區。即匯總下來，代碼可以分為6部分組成，包括：BSS區（未初始化的全局變數/靜態變數區）、Data區（實始化的全局變數區）、Stack區（棧區）、heap區（堆區）、Code區（代碼區）、const區（常量區）。

一、BSS區和Data區

C語言編程中定義的全局變數、靜態局部變數，就是分配在全局變數/靜態變數區域，但是為什麼又要分為BSS區域和Data區域呢？其實我們在定義全局或者靜態變數區，有時我會對它賦初始值，有的又不會賦初始化，比如我們定義的全局變數，初始化的賦值，是怎麼樣寫到變數區域中的，我們定義的靜態局部變數，在定義時初始化後，為什麼後面函數被調用，又不會再初始化呢？這個局部靜態變數是怎麼樣實始化的，什麼時候初始化的？

如果分析編譯後的匯編代碼，就會發現在代碼運行起來後，會有一段給變數賦值的指令，這一段代碼，不是我們C代碼對應的匯編，而是C編譯器生成的匯編譯代碼，這段代碼的作用就是給初始化了的靜態變數和全局變數進行初始化。這也是為什麼全局/靜態變數區域，要分BSS和Data的原因。

二、Stack區

棧是一種先進後出的數據結構，這種數據結構正好完美的匹配函數調用時的模型過程，比如函數f(a)在運行過程中調用函數f(b)，f(a）在運行過程中的變數就是分配在棧中，通過在調用f(b)前，會將代碼中用到的R0~Rn寄存器的值保存到棧中，同時將函數的傳入參數寫入到棧中，然後進入f(b)函數，函數f(b)的變數b分配在棧中，當函數運行完畢後，釋放變數b，將棧中存放的f（a）函數的運行的R0~Rn寄存器值恢復到寄存器中，同時f(b)的返回結果存入到棧中，這樣f（a）繼續運行。當一個函數運行完畢後，它在棧中分配的臨時變數會全部釋放。

對於中斷也是一樣的，中斷發生時，也是一個函數打斷了另一個函數的運行，這種現場的保存（即寄存器的值）,都是通過棧來完成的。所以棧的作用有：

三、Heap區

全局變數分配的內存在代碼整個運行周期內都是有效的，而在棧區分配的內存在函數調用完成後，就會釋放。這兩種內存模型都是由編譯器決定它的使用，代碼是無法控制的。那有沒有內存是由用戶控制的，要用時，就自由分配，不用時，就自行釋放？答案是肯定的，這部分內存就是堆。

用戶需要使用的動態內存，就是通過malloc函數，調用分配的，在沒有釋放前，可一直由代碼使用。當這部分內存不再需要使用時，可以通過free函數進行釋放，將它歸還到堆中。從這中可以看出，堆的內存，是按需分配的。這就是賦予了代碼很大的自由度，但這也是會帶來負作用的，比如：內存碎片化導致的malloc失敗；忘記釋放內存導致的內存泄露，而這些往往是致命的失誤。

四、Code區

代碼區就是編譯後機器指令，這些指令決定了功能的執行。我們編譯的代碼一般是下載進flash中，但是運行，卻有兩種方式：在RAM中運行和在ROM中運行。 在RAM中運行，即是boot啟動後，將flash中的代碼復制到RAM中，然後PC指針在指到RAM中的代碼中開始運行。 有時在調試時，我們可以直接將代碼下載進RAM中運行進行調試，這樣加快調試速度。便是大部分的情況我們的代碼是從flash中開始運行的。

五、常量區

代碼中的常量，一部分是作為立即數，在代碼區中，但是像定義的字元串、給某數組賦值的一串數值，這些常量，就存在常量區，我們常用const來定義一個常量，即該變數不能再必變。這部分的變數，編譯器一般將它定義的flash中。

六、各個區域大小的是如何決定的：

code區和const區：是由代碼的大小和代碼中常量的多少來決定的。

bss區和data區：這是由代碼中定義的全局變數和局部變數的多少來決定的。

stack區：這個可以由使用都自行定義大小，但使用都要根據自已代碼的情況，評估出一個合理的值，再定義其大小，如果定義的太小，很容易爆棧，導至代碼異常，但是如果定義的太大，就容易浪費內存。

heap區：RAM剩下的部分，編譯器就會作為堆區使用。

七、嵌入式代碼一般啟動過程

以STM32為例，通過分析其匯編啟支代碼，大致可以分為以下幾個步驟：

如果大家想看編譯扣，代碼文件的組成，可以查看統後生的map文件，裡面有詳細的數據，包括各個函數的分配內存，BSS，Data，Stack，Heap，Text的分配情況。

如果相要了解詳細的代碼啟動過程，可看它的啟動匯編文件。

③ 編譯程序包括哪幾個主要組成部分

數據結構 分析和綜合時所用的主要數據結構，包括符號表、常數表和中間語言程序。符號表由源程序中所用的標識符連同它們的屬性組成，其中屬性包括種類（如變數、數組、結構、函數、過程等）、類型（如整型、實型、字元串、復型、標號等），以及目標程序所需的其他信息。常數表由源程序中用的常數組成，其中包括常數的機內表示，以及分配給它們的目標程序地址。中間語言程序是將源程序翻譯為目標程序前引入的一種中間形式的程序，其表示形式的選擇取決於編譯程序以後如何使用和加工它。常用的中間語言形式有波蘭表示、三元組、四元組以及間接三元組等。

分析部分 源程序的分析是經過詞法分析、語法分析和語義分析三個步驟實現的。詞法分析由詞法分析程序（又稱為掃描程序）完成，其任務是識別單詞（即標識符、常數、保留字，以及各種運算符、標點符號等）、造符號表和常數表，以及將源程序換碼為編譯程序易於分析和加工的內部形式。語法分析程序是編譯程序的核心部分，其主要任務是根據語言的語法規則，檢查源程序是否合乎語法。如不合乎語法，則輸出語法出錯信息；如合乎語法，則分解源程序的語法結構，構造中間語言形式的內部程序。語法分析的目的是掌握單詞是怎樣組成語句的，以及語句又是如何組成程序的。語義分析程序是進一步檢查合法程序結構的語義正確性，其目的是保證標識符和常數的正確使用，把必要的信息收集和保存到符號表或中間語言程序中，並進行相應的語義處理。

綜合部分 綜合階段必須根據符號表和中間語言程序產生出目標程序，其主要工作包括代碼優化、存儲分配和代碼生成。代碼優化是通過重排和改變程序中的某些操作，以產生更加有效的目標程序。存儲分配的任務是為程序和數據分配運行時的存儲單元。代碼生成的主要任務是產生與中間語言程序符等價的目標程序，順序加工中間語言程序，並利用符號表和常數表中的信息生成一系列的匯編語言或機器語言指令。

結構編譯過程分為分析和綜合兩個部分，並進一步劃分為詞法分析、語法分析、 語義分析、 代碼優化、存儲分配和代碼生成等六個相繼的邏輯步驟。這六個步驟只表示編譯程序各部分之間的邏輯聯系，而不是時間關系。編譯過程既可以按照這六個邏輯步驟順序地執行，也可以按照平行互鎖方式去執行。在確定編譯程序的具體結構時，常常分若干遍實現。對於源程序或中間語言程序，從頭到尾掃視一次並實現所規定的工作稱作一遍。每一遍可以完成一個或相連幾個邏輯步驟的工作。例如，可以把詞法分析作為第一遍；語法分析和語義分析作為第二遍；代碼優化和存儲分配作為第三遍；代碼生成作為第四遍。反之，為了適應較小的存儲空間或提高目標程序質量，也可以把一個邏輯步驟的工作分為幾遍去執行。例如，代碼優化可劃分為代碼優化准備工作和實際代碼優化兩遍進行。

一個編譯程序是否分遍,以及如何分遍,根據具體情況而定。其判別標准可以是存儲容量的大小、源語言的繁簡、解題范圍的寬窄，以及設計、編制人員的多少等。分遍的好處是各遍功能獨立單純、相互聯系簡單、邏輯結構清晰、優化准備工作充分。缺點是各遍之中不可避免地要有些重復的部分，而且遍和遍之間要有交接工作，因之增加了編譯程序的長度和編譯時間。

一遍編譯程序是一種極端情況，整個編譯程序同時駐留在內存,彼此之間採用調用轉接方式連接在一起(圖2)。當語法分析程序需要新符號時，它就調用詞法分析程序；當它識別出某一語法結構時，它就調用語義分析程序。語義分析程序對識別出的結構進行語義檢查，並調用「存儲分配」和「代碼生成」程序生成相應的目標語言指令。

隨著程序設計語言在形式化、結構化、直觀化和智能化等方面的發展，作為實現相應語言功能的編譯程序，也正向自動程序設計的目標發展，以便提供理想的程序設計工具。

參考書目

陳火旺、錢家驊、孫永強編：《編譯原理》，國防工業出版社，北京，1980

④ 我想了解c語言中內存分配問題方面的知識

C語言程序編譯的內存分配：
1.棧區（stack） --編譯器自動分配釋放，主要存放函數的參數值，局部變數值等；
2.堆區（heap） --由程序員分配釋放；
3.全局區或靜態區 --存放全局變數和靜態變數；程序結束時由系統釋放，分為全局初始化區和全局未初始化區；
4.字元常量區 --常量字元串放與此，程序結束時由系統釋放；
5.程序代碼區--存放函數體的二進制代碼
例： //main.c
int a=0; //全局初始化區
char *p1; //全局未初始化區
void main()
{
int b; //棧
char s[]="bb"; //棧
char *p2; //棧
char *p3="123"; //其中，「123\0」常量區，p3在棧區
static int c=0; //全局區
p1=(char*)malloc(10); //10個位元組區域在堆區
strcpy(p1,"123"); //"123\0"在常量區，編譯器 可能 會優化為和p3的指向同一塊區域
｝
一個C程序佔用的內存可分為以下幾類：
(一) 棧
這是由編譯器自動分配和釋放的區域。主要存儲函數的參數，函數的局部變數等。當一個函數開始執行時，該函數所需的實參，局部變數就推入棧中，該函數執行完畢後，之前進入棧中的參數和變數等也都出棧被釋放掉。它的運行方式類似於數據結構中的棧。
(二) 堆
這是由程序員控制分配和釋放的區域，在C里，用malloc()函數分配的空間就存在於堆上。在堆上分配的空間不像棧一樣在某個函數執行完畢就自動釋放，而是一直存在於整個程序的運行期間。當然，如果你不手動釋放(free()函數)這些空間，在程序運行結束後系統也會將之自動釋放。對於小程序來說可能感覺不到影響的存在，但對於大程序，例如一個大型游戲，就會遇到內存不夠用的問題了
(三) 全局區
C里的全局變數和靜態變數存儲在全局區。它們有點像堆上的空間，也是持續存在於程序的整個運行期間，但不同的是，他們是由編譯器自己控制分配和釋放的。
(四) 文字常量區
例如char *c = 「123456」；則」123456」為文字常量，存放於文字常量區。也由編譯器控制分配和釋放。
(五) 程序代碼區
存放函數體的二進制代碼。
2． 例子(一)
int a = 0; //全局區
void main()
{
int b; //棧
char s[] = "abc"; //s在棧,"abc"在文字常量區
char *p1,*p2; //棧
char *p3 = "123456"; //"123456"在常量區，p3在棧上
static int c =0; //全局區
p1 = (char *)malloc(10); //p1在棧，分配的10位元組在堆
p2 = (char *)malloc(20); //p2在棧，分配的20位元組在堆
strcpy(p1, "123456"); //"123456"放在常量區
//編譯器可能將它與p3所指向的"123456"優化成一個地方。
}
3． 例子(二)
//返回char型指針
char *f()
{
//s數組存放於棧上
char s[4] = {'1','2','3','0'};
return s; //返回s數組的地址，但程序運行完s數組就被釋放了
}
void main()
{
char *s;
s = f();
printf ("%s", s); //列印出來亂碼。因為s所指向地址已經沒有數據
}
還有就是函數調用時會在棧上有一系列的保留現場及傳遞參數的操作。
棧的空間大小有限定，vc的預設是2M。棧不夠用的情況一般是程序中分配了大量數組和遞歸函數層次太深。有一點必須知道，當一個函數調用完返回後它會釋放該函數中所有的棧空間。棧是由編譯器自動管理的，不用你操心。
堆是動態分配內存的，並且你可以分配使用很大的內存。但是用不好會產生內存泄漏。並且頻繁地malloc和free會產生內存碎片（有點類似磁碟碎片），因為C分配動態內存時是尋找匹配的內存的。而用棧則不會產生碎片，在棧上存取數據比通過指針在堆上存取數據快些。一般大家說的堆棧和棧是一樣的，就是棧(stack)，而說堆時才是堆heap.棧是先入後出的，一般是由高地址向低地址生長。
堆(heap)和棧(stack)是C/C++編程不可避免會碰到的兩個基本概念。首先，這兩個概念都可以在講數據結構的書中找到，他們都是基本的數據結構，雖然棧更為簡單一些。在具體的C/C++編程框架中，這兩個概念並不是並行的。對底層機器代碼的研究可以揭示，棧是機器系統提供的數據結構，而堆則是C/C++函數庫提供的。具體地說，現代計算機(串列執行機制)，都直接在代碼底層支持棧的數據結構。這體現在，有專門的寄存器指向棧所在的地址，有專門的機器指令完成數據入棧出棧的操作。種機制的特點是效率高，支持的數據有限，一般是整數，指針，浮點數等系統直接支持的數據類型，並不直接支持其他的數據結構。因為棧的這種特點，對棧的使用在程序中是非常頻繁的。對子程序的調用就是直接利用棧完成的。機器的call指令里隱含了把返回地址推入棧，然後跳轉至子程序地址的操作，而子程序中的ret指令則隱含從堆棧中彈出返回地址並跳轉之的操作。C/C++中的自動變數是直接利棧的例子，這也就是為什麼當函數返回時，該函數的自動變數自動失效的原因。
和棧不同，堆的數據結構並不是由系統(無論是機器系統還是操作系統)支持的，而是由函數庫提供的。基本的malloc/realloc/free函數維護了一套內部的堆數據結構。當程序使用這些函數去獲得新的內存空間時，這套函數首先試圖從內部堆中尋找可用的內存空間，如果沒有可以使用的內存空間，則試圖利用系統調用來動態增加程序數據段的內存大小，新分配得到的空間首先被組織進內部堆中去，然後再以適當的形式返回給調用者。當程序釋放分配的內存空間時，這片內存空間被返回內部堆結構中，可能會被適當的處理(比如和其他空閑空間合並成更大的空閑空間)，以更適合下一次內存分配申請。這套復雜的分配機制實際上相當於一個內存分配的緩沖池(Cache)，使用這套機制有如下若干原因：
1. 系統調用可能不支持任意大小的內存分配。有些系統的系統調用只支持固定大小及其倍數的內存請求(按頁分配)；這樣的話對於大量的小內存分類來說會造成浪費。
2. 系統調用申請內存可能是代價昂貴的。系統調用可能涉及用戶態和核心態的轉換。
3. 沒有管理的內存分配在大量復雜內存的分配釋放操作下很容易造成內存碎片
堆和棧的對比
從以上知識可知，棧是系統提供的功能，特點是快速高效，缺點是有限制，數據不靈活；而堆是函數庫提供的功能，特點是靈活方便，數據適應面廣泛，但是效率有一定降低。棧是系統數據結構，對於進程/線程是唯一的；堆是函數庫內部數據結構，不一定唯一。不同堆分配的內存無法互相操作。棧空間分靜態分配和動態分配兩種。靜態分配是編譯器完成的，比如自動變數(auto)的分配。動態分配由alloca函數完成。棧的動態分配無需釋放(是自動的)，也就沒有釋放函數。為可移植的程序起見，棧的動態分配操作是不被鼓勵的！堆空間的分配總是動態的，雖然程序結束時所有的數據空間都會被釋放回系統，但是精確的申請內存/釋放內存匹配是良好程序的基本要素。

⑤ 編譯程序有哪些主要構成成分它們各自的主要功能是什麼

編譯過程分為分析和綜合兩個部分，並進一步劃分為詞法分析、語法分析、語義分析、代碼優化、存儲分配和代碼生成等六個相繼的邏輯步驟。這六個步驟只表示編譯程序各部分之間的邏輯聯系，而不是時間關系。

編譯過程既可以按照這六個邏輯步驟順序地執行，也可以按照平行互鎖方式去執行。在確定編譯程序的具體結構時，常常分若干遍實現。對於源程序或中間語言程序，從頭到尾掃視一次並實現所規定的工作稱作一遍。每一遍可以完成一個或相連幾個邏輯步驟的工作。

例如，可以把詞法分析作為第一遍；語法分析和語義分析作為第二遍；代碼優化和存儲分配作為第三遍；代碼生成作為第四遍。

反之，為了適應較小的存儲空間或提高目標程序質量，也可以把一個邏輯步驟的工作分為幾遍去執行。例如，代碼優化可劃分為代碼優化准備工作和實際代碼優化兩遍進行。

(5)編譯數據的結構擴展閱讀

從左至右逐個字元地對源程序進行掃描，產生一個個的單詞符號，把作為字元串的源程序改造成為單詞符號串的中間程序。執行詞法分析的程序稱為詞法分析程序或掃描器。

源程序中的單詞符號經掃描器分析，一般產生二元式：單詞種別；單詞自身的值。單詞種別通常用整數編碼，如果一個種別只含一個單詞符號，那麼對這個單詞符號，種別編碼就完全代表它自身的值了。若一個種別含有許多個單詞符號，那麼，對於它的每個單詞符號，除了給出種別編碼以外，還應給出自身的值。

詞法分析器一般來說有兩種方法構造：手工構造和自動生成。手工構造可使用狀態圖進行工作，自動生成使用確定的有限自動機來實現。

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。編譯程序的語法規則可用上下文無關文法來刻畫。

⑥ 定義語法樹和符號表的數據結構

為了維持靜態作用域的程序里各個名字的軌跡，編譯器需要依靠一種稱為符號表的數據結構。從最基本的層次上看，符號表就是一個字典：它把名字映射到編譯器已知的有關信息。這里最基本的操作是把一個新映射關系（名字對象約束）放入表裡，以及（非破壞性的）用一個給定名字去提取映射下的信息，以後我們把

這兩個操作分別稱為insert和lookup。大部分語言里的靜態作用域規則還提出了另外的復雜性，它們要求在程序里的不同部分有不同的引用環境。為了處理作用域規則，我們可能希望簡單增加一個remove操作。由於編譯器在語義分析階段要從頭到尾掃描代碼，這樣它就可以在某個作用域開始時插入新約束，在作用域最後撤銷它們。但是，存在一些因素使這種直接做法並不實際。

¨ 在許多有著嵌套作用域的語言里，內層聲明的效果可以遮蔽外層聲明，這就意味著符號表必須有能力為一個給定名字保存任意數目的映射。lookup操作必須返回最內層的映射，到作用域結束時還必須使外層映射重新變成可見的。

¨ 類Algol語言里的記錄（結構）具有某種作用域性質，但卻又不享有作用域那樣的良好嵌套結構。當語義分析器看到一個記錄聲明時，它就必須記下各個記錄域的名字（它們也是遞歸的，因為記錄可以嵌套）。在這種聲明結束時，各個域的名字又必須變成不可見的。然而，在此之後，一旦這一記錄類型的某個變數出現在程序的正文里（例如在my_rec.field_name），在引用中位於圓點之後的部分，這些域名又必須立即重新變成可見的。在Pascal和另一些有with語句的語言里，記錄域的名字還應該在多個語句的上下文里變成可見的。

¨ 某些時候一些名字有可能在它們被聲明之前使用，即使在類Algol語言里情況也如此。舉例說，Algol 60和Algol 68都允許標號的向前引用。Pascal避免了這種情況，它要求標號必須在作用域開始處聲明，但還是允許指針聲明的向前引用：

type