編譯原理存儲空間分配
⑴ 編譯原理全部的名詞解釋
書上有別那麼懶!.
編譯過程的六個階段:詞法分析,語法分析,語義分析,中間代碼生成,代碼優化,目標代碼生成
解釋程序:把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序,然後再執行目標程序.解釋方式是接受某高級語言的一個語句輸入,進行解釋並控制計算機執行,馬上得到這句的執行結果,然後再接受下一句.
編譯程序:就是指這樣一種程序,通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序).
解釋程序和編譯程序的根本區別:是否生成目標代碼
句子的二義性(這里的二義性是指語法結構上的.):文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導),或者存在兩棵不同的語法樹,則稱這個句子是二義性的.
文法的二義性:一個文法如果包含二義性的句子,則這個文法是二義文法,否則是無二義文法.
LL(1)的含義:(LL(1)文法是無二義的; LL(1)文法不含左遞歸)
第1個L:從左到右掃描輸入串 第2個L:生成的是最左推導
1 :向右看1個輸入符號便可決定選擇哪個產生式
某些非LL(1)文法到LL(1)文法的等價變換: 1. 提取公因子 2. 消除左遞歸
文法符號的屬性:單詞的含義,即與文法符號相關的一些信息.如,類型、值、存儲地址等.
一個屬性文法(attribute grammar)是一個三元組A=(G, V, F)
G:上下文無關文法.
V:屬性的有窮集.每個屬性與文法的一個終結符或非終結符相連.屬性與變數一樣,可以進行計算和傳遞.
F:關於屬性的斷言或謂詞(一組屬性的計算規則)的有窮集.斷言或語義規則與一個產生式相聯,只引用該產生式左端或右端的終結符或非終結符相聯的屬性.
綜合屬性:若產生式左部的單非終結符A的屬性值由右部各非終結符的屬性值決定,則A的屬性稱為綜合屬
繼承屬性:若產生式右部符號B的屬性值是根據左部非終結符的屬性值或者右部其它符號的屬性值決定的,則B的屬性為繼承屬性.
(1)非終結符既可有綜合屬性也可有繼承屬性,但文法開始符號沒有繼承屬性.
(2) 終結符只有綜合屬性,沒有繼承屬性,它們由詞法程序提供.
在計算時: 綜合屬性沿屬性語法樹向上傳遞;繼承屬性沿屬性語法樹向下傳遞.
語法制導翻譯:是指在語法分析過程中,完成附加在所使用的產生式上的語義規則描述的動作.
語法制導翻譯實現:對單詞符號串進行語法分析,構造語法分析樹,然後根據需要構造屬性依賴圖,遍歷語法樹並在語法樹的各結點處按語義規則進行計算.
中間代碼(中間語言)
1、是復雜性介於源程序語言和機器語言的一種表示形式.
2、一般,快速編譯程序直接生成目標代碼.
3、為了使編譯程序結構在邏輯上更為簡單明確,常採用中間代碼,這樣可以將與機器相關的某些實現細節置於代碼生成階段仔細處理,並且可以在中間代碼一級進行優化工作,使得代碼優化比較容易實現.
何謂中間代碼:源程序的一種內部表示,不依賴目標機的結構,易於代碼的機械生成.
為何要轉換成中間代碼:(1)邏輯結構清楚;利於不同目標機上實現同一種語言.
(2)便於移植,便於修改,便於進行與機器無關的優化.
中間代碼的幾種形式:逆波蘭記號 ,三元式和樹形表示 ,四元式
符號表的一般形式:一張符號表的的組成包括兩項,即名字欄和信息欄.
信息欄包含許多子欄和標志位,用來記錄相應名字和種種不同屬性,名字欄也稱主欄.主欄的內容稱為關鍵字(key word).
符號表的功能:(1)收集符號屬性 (2) 上下文語義的合法性檢查的依據: 檢查標識符屬性在上下文中的一致性和合法性.(3)作為目標代碼生成階段地址分配的依據
符號的主要屬性及作用:
1. 符號名 2. 符號的類型 (整型、實型、字元串型等))3. 符號的存儲類別(公共、私有)
4. 符號的作用域及可視性 (全局、局部) 5. 符號變數的存儲分配信息 (靜態存儲區、動態存儲區)
存儲分配方案策略:靜態存儲分配;動態存儲分配:棧式、 堆式.
靜態存儲分配
1、基本策略
在編譯時就安排好目標程序運行時的全部數據空間,並能確定每個數據項的單元地址.
2、適用的分配對象:子程序的目標代碼段;全局數據目標(全局變數)
3、靜態存儲分配的要求:不允許遞歸調用,不含有可變數組.
FORTRAN程序是段結構,不允許遞歸,數據名大小、性質固定. 是典型的靜態分配
動態存儲分配
1、如果一個程序設計語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間,那麼,就需要採用動態存儲管理技術.
2、兩種動態存儲分配方式:棧式,堆式
棧式動態存儲分配
分配策略:將整個程序的數據空間設計為一個棧.
【例】在具有遞歸結構的語言程序中,每當調用一個過程時,它所需的數據空間就分配在棧頂,每當過程工作結束時就釋放這部分空間.
過程所需的數據空間包括兩部分
一部分是生存期在本過程這次活動中的數據對象.如局部變數、參數單元、臨時變數等;
另一部分則是用以管理過程活動的記錄信息(連接數據).
活動記錄(AR)
一個過程的一次執行所需要的信息使用一個連續的存儲區來管理,這個區 (塊)叫做一個活動記錄.
構成
1、臨時工作單元;2、局部變數;3、機器狀態信息;4、存取鏈;
5、控制鏈;6、實參;7、返回地址
什麼是代碼優化
所謂優化,就是對代碼進行等價變換,使得變換後的代碼運行結果與變換前代碼運行結果相同,而運行速度加快或佔用存儲空間減少.
優化原則:等價原則:經過優化後不應改變程序運行的結果.
有效原則:使優化後所產生的目標代碼運行時間較短,佔用的存儲空間較小.
合算原則:以盡可能低的代價取得較好的優化效果.
常見的優化技術
(1) 刪除多餘運算(刪除公共子表達式) (2) 代碼外提 +刪除歸納變數+ (3)強度削弱; (4)變換循環控制條件 (5)合並已知量與復寫傳播 (6)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列,稱為程序的一個基本塊.
給我分數啊.
⑵ 編譯程序包括哪幾個主要組成部分
編譯過程分為分析和綜合兩個部分,並進一步劃分為詞法分析、語法分析、語義分析、代碼優化、存儲分配和代碼生成等六個相繼的邏輯步驟。這六個步驟只表示編譯程序各部分之間的邏輯聯系,而不是時間關系。
編譯過程既可以按照這六個邏輯步驟順序地執行,也可以按照平行互鎖方式去執行。在確定編譯程序的具體結構時,常常分若干遍實現。對於源程序或中間語言程序,從頭到尾掃視一次並實現所規定的工作稱作一遍。每一遍可以完成一個或相連幾個邏輯步驟的工作。
(2)編譯原理存儲空間分配擴展閱讀:
對於c編譯程序來說,其語言的特點如下:
1、c語言是一種結構化語言。它層次清晰,便於按模塊化方式組織程序,易於調試和維護,而且表現能力和處理能力極強。
2、c語言具有豐富的運算符和數據類型,便於實現各類復雜的數據結構。它還可以直接訪問內存的物理地址,進行位(bit)一級的操作。
3、由於c語言實現了對硬體的編程操作,因此集高級語言和低級語言的功能於一體。它既可用於系統軟體的開發,也適合於應用軟體的開發。
4、此外,c語言還具有效率高、可移植性強等特點。因此它廣泛地移植到了各類各型計算機上,從而形成了多種版本。
⑶ 編譯時分配內存和運行時分配內存
編譯其實只是一個掃描過程,進行詞法語法檢查,代碼優化而已,編譯程序越好,程序運行的時候越高效。
我想你說的「編譯時分配內存」是指「編譯時賦初值」,它只是形成一個文本,檢查無錯誤,並沒有分配內存空間。
當你運行時,系統才把程序導入內存。一個進程(即運行中的程序)在主要包括以下五個分區:
棧、堆、bss、data、code
代碼(編譯後的二進制代碼)放在code區,代碼中生成的各種變數、常量按不同類型分別存放在其它四個區。系統依照代碼順序執行,然後依照代碼方案改變或調用數據,這就是一個程序的運行過程。
⑷ c語言數組在內存中是怎麼分配的
C語言中內存為分三類:棧區、堆區、靜態數據區。
局部變數在棧上分配,函數調用前的棧指針,要和函數返回後的棧指針一樣,否則就會出錯。
void test(void)
{
char i,a[10];
printf("0x%x", &i);
printf("0x%x", a);
printf("0x%x", a+1);
printf("0x%x", a+2);
printf("0x%x", a+3);
}
(4)編譯原理存儲空間分配擴展閱讀
c語言數組在內存分配
示例:
#include<stdio.h>
int main()
{
int a[4] = {11,12,13,14};
int b[4] = {21,22,23,24};
int *pa = &a;
int i = 0;
while(i<8)
{
i++;
printf("now *p value = %d and",*pa);
printf("p addr value = %d ",pa);
pa++;
}
return 0;
}
⑸ 靜態存儲分配和動態存儲分配之間有什麼不同 編譯原理
動態存儲方式
所謂動態存儲方式是指在程序運行期間根據需要進行動態的分配存儲空間的方式。動態存儲變數是在程序執行過程中,使用它時才分配存儲單元,
使用完畢立即釋放。
典型的例子是函數的形式參數,在函數定義時並不給形參分配存儲單元,只是在函數被調用時,才予以分配,
調用函數完畢立即釋放。如果一個函數被多次調用,則反復地分配、
釋放形參變數的存儲單元。
靜態存儲方式
所謂靜態存儲方式是指在程序編譯期間分配固定的存儲空間的方式。該存儲方式通常是在變數定義時就分定存儲單元並一直保持不變,
直至整個程序結束。全局變數,靜態變數等就屬於此類存儲方式。
總結
從以上分析可知,
靜態存儲變數是一直存在的,
而動態存儲變數則時而存在時而消失。我們又把這種由於變數存儲方式不同而產生的特性稱變數的生存期。
生存期表示了變數存在的時間。
生存期和作用域是從時間和空間這兩個不同的角度來描述變數的特性,這兩者既有聯系,又有區別。
一個變數究竟屬於哪一種存儲方式,
並不能僅從其作用域來判斷,還應有明確的存儲類型說明。