編譯原理里推導的定義
Ⅰ 編譯原理筆記9:語法分析樹、語法樹、二義性的消除
語法分析樹和語法樹不是一種東西 。習慣上,我們把前者叫做「具體語法樹」,其能夠體現推導的過程;後者叫做「抽象語法樹」,其不體現過程,只關心最後的結果。
語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。
定義:對於 CFG G 的句型,分析樹被定義為具有下述性質的一棵樹:
推導,有最左推導和最右推導,這兩種推導方式在推導過程中的分析樹可能不同,但因最終得到的句子是相同的,所以最終的分析樹是一樣的。
分析樹能反映句型的推導過程,也能反映句型的結構。然而實際上,我們往往不關心推導的過程,而只關心推導的結果。因此,我們要對 分析樹 進行改造,得到 語法樹 。語法樹中全是終結符,沒有非終結符。而且語法樹中沒有括弧
定義:
說白了,語法樹這玩意,就一句話: 葉子全是操作數,內部全是操作符 ,樹里沒有非終結符也不能有括弧。
語法樹要表達的東西,是操作符(運算)作用於操作數(運算對象)
舉倆例子吧:
【例】: -(id+id) 的語法樹:
【例】:-id+id 的語法樹:
顯然,我們從上面這兩個語法樹中,直接就能觀察出來它們的運算順序。
【例】:句型 if C then s1 else s2
二義性問題:一個句子可能對應多於一棵語法樹。
【例】: 設文法 G: E → E+E | E*E | (E) | -E | id
則,句子 id+id*id、id+id+id 可能的分析樹有:
在該例中,雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一,萬一「+」的含義變成了「減法」,那麼左結合和右結合就會引起很大的問題了。
我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」,尚未到需要研究語言背後含義的階段。
我們現在講的「二義性」指的是一個句子對應多種分析樹。
二義性的體現,是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題,示例如下。
看下面這么個例子。。
(其實,我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。)上面的產生式中並沒體現出來該咋算分一塊,所以兩種完全不同的句子結構都是合法的。
二義性問題是有救的,大概有以下這三種辦法:
這些辦法的核心,其實都是將優先順序和結合性說明白。
核心:把優先順序和結合性說明白
既然要說明白,那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。(對分析樹的一個內部節點,不會有出現在其下面的分支是相同的非終結符的情況。如果有得選,那就有得歧義了。沒得選才能確定地一路走到黑)
改寫為非二義文法的二義文法大概有下面這幾個特點:
改寫的關鍵步驟:
【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性
改寫的核心其實就兩句話:
所以能夠得到非終結符與運算的對應關系(因為不同的運算有不同的優先順序,我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號,也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字)如下:
優先順序由低到高分別是 +、 、-,而距離開始符號越近,優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性,則可確定是左遞歸還是右遞歸,以確定新的產生式長什麼樣子
【例】:規定優先順序和結合性,寫出改寫的非二義文法
我們已經掌握了一種叫做【改寫】的工具,能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題!
懸空 else 問題出現的原因是 then 數量多於 else,讓 else 有多個可以結合的 then。在二義文法中,由於選哪兩個 then、else 配對都可以,故會引起出現二義的情況。在這里,我們規定 else 右結合,即與左邊最靠近的 then 結合。
為改寫此文法,可以將 S 分為完全匹配(MS)和不完全匹配(UMS)兩類。在 MS 中體現 then、else 個數相等即匹配且右結合;在UMS 中 then、else 不匹配,體現 else 右結合。
【例】:用改寫後的文法寫一個條件語句
經過檢查,無法再根據文法寫出其他分析樹,故已經消除了二義性
雖然二義文法會導致二義性,但是其並非一無是處。其有兩個顯著的優點:
在 Yacc 中,我們可以直接指定優先順序、結合性而無需自己重寫文法。
left 表示左結合,right 表示右結合。越往下的算符優先順序越高。
嗯就這么簡單。。。
我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制,哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。
比如在 Ada 中:
在 Pascal 中,給表達式加括弧:
Ⅱ 編譯原理
C語言編譯過程詳解
C語言的編譯鏈接過程是要把我們編寫的一個C程序(源代碼)轉換成可以在硬體上運行的程序(可執行代碼),需要進行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機器語言形式的目標文件的過程。鏈接是把目標文件、操作系統的啟動代碼和用到的庫文件進行組織形成最終生成可執行代碼的過程。過程圖解如下:
從圖上可以看到,整個代碼的編譯過程分為編譯和鏈接兩個過程,編譯對應圖中的大括弧括起的部分,其餘則為鏈接過程。
一、編譯過程
編譯過程又可以分成兩個階段:編譯和匯編。
1、編譯
編譯是讀取源程序(字元流),對之進行詞法和語法的分析,將高級語言指令轉換為功能等效的匯編代碼,源文件的編譯過程包含兩個主要階段:
第一個階段是預處理階段,在正式的編譯階段之前進行。預處理階段將根據已放置在文件中的預處理指令來修改源文件的內容。如#include指令就是一個預處理指令,它把頭文件的內容添加到.cpp文件中。這個在編譯之前修改源文件的方式提供了很大的靈活性,以適應不同的計算機和操作系統環境的限制。一個環境需要的代碼跟另一個環境所需的代碼可能有所不同,因為可用的硬體或操作系統是不同的。在許多情況下,可以把用於不同環境的代碼放在同一個文件中,再在預處理階段修改代碼,使之適應當前的環境。
主要是以下幾方面的處理:
(1)宏定義指令,如 #define a b。
對於這種偽指令,預編譯所要做的是將程序中的所有a用b替換,但作為字元串常量的 a則不被替換。還有 #undef,則將取消對某個宏的定義,使以後該串的出現不再被替換。
(2)條件編譯指令,如#ifdef,#ifndef,#else,#elif,#endif等。
這些偽指令的引入使得程序員可以通過定義不同的宏來決定編譯程序對哪些代碼進行處理。預編譯程序將根據有關的文件,將那些不必要的代碼過濾掉
(3) 頭文件包含指令,如#include "FileName"或者#include <FileName>等。
在頭文件中一般用偽指令#define定義了大量的宏(最常見的是字元常量),同時包含有各種外部符號的聲明。採用頭文件的目的主要是為了使某些定義可以供多個不同的C源程序使用。因為在需要用到這些定義的C源程序中,只需加上一條#include語句即可,而不必再在此文件中將這些定義重復一遍。預編譯程序將把頭文件中的定義統統都加入到它所產生的輸出文件中,以供編譯程序對之進行處理。包含到C源程序中的頭文件可以是系統提供的,這些頭文件一般被放在/usr/include目錄下。在程序中#include它們要使用尖括弧(<>)。另外開發人員也可以定義自己的頭文件,這些文件一般與C源程序放在同一目錄下,此時在#include中要用雙引號("")。
(4)特殊符號,預編譯程序可以識別一些特殊的符號。
例如在源程序中出現的LINE標識將被解釋為當前行號(十進制數),FILE則被解釋為當前被編譯的C源程序的名稱。預編譯程序對於在源程序中出現的這些串將用合適的值進行替換。
預編譯程序所完成的基本上是對源程序的「替代」工作。經過此種替代,生成一個沒有宏定義、沒有條件編譯指令、沒有特殊符號的輸出文件。這個文件的含義同沒有經過預處理的源文件是相同的,但內容有所不同。下一步,此輸出文件將作為編譯程序的輸出而被翻譯成為機器指令。
第二個階段編譯、優化階段。經過預編譯得到的輸出文件中,只有常量;如數字、字元串、變數的定義,以及C語言的關鍵字,如main,if,else,for,while,{,}, +,-,*,\等等。
編譯程序所要作得工作就是通過詞法分析和語法分析,在確認所有的指令都符合語法規則之後,將其翻譯成等價的中間代碼表示或匯編代碼。
優化處理是編譯系統中一項比較艱深的技術。它涉及到的問題不僅同編譯技術本身有關,而且同機器的硬體環境也有很大的關系。優化一部分是對中間代碼的優化。這種優化不依賴於具體的計算機。另一種優化則主要針對目標代碼的生成而進行的。
對於前一種優化,主要的工作是刪除公共表達式、循環優化(代碼外提、強度削弱、變換循環控制條件、已知量的合並等)、復寫傳播,以及無用賦值的刪除,等等。
後一種類型的優化同機器的硬體結構密切相關,最主要的是考慮是如何充分利用機器的各個硬體寄存器存放的有關變數的值,以減少對於內存的訪問次數。另外,如何根據機器硬體執行指令的特點(如流水線、RISC、CISC、VLIW等)而對指令進行一些調整使目標代碼比較短,執行的效率比較高,也是一個重要的研究課題。
2、匯編
匯編實際上指把匯編語言代碼翻譯成目標機器指令的過程。對於被翻譯系統處理的每一個C語言源程序,都將最終經過這一處理而得到相應的目標文件。目標文件中所存放的也就是與源程序等效的目標的機器語言代碼。目標文件由段組成。通常一個目標文件中至少有兩個段:
代碼段:該段中所包含的主要是程序的指令。該段一般是可讀和可執行的,但一般卻不可寫。
數據段:主要存放程序中要用到的各種全局變數或靜態的數據。一般數據段都是可讀,可寫,可執行的。
UNIX環境下主要有三種類型的目標文件:
(1)可重定位文件
其中包含有適合於其它目標文件鏈接來創建一個可執行的或者共享的目標文件的代碼和數據。
(2)共享的目標文件
這種文件存放了適合於在兩種上下文里鏈接的代碼和數據。
第一種是鏈接程序可把它與其它可重定位文件及共享的目標文件一起處理來創建另一個 目標文件;
第二種是動態鏈接程序將它與另一個可執行文件及其它的共享目標文件結合到一起,創建一個進程映象。
(3)可執行文件
它包含了一個可以被操作系統創建一個進程來執行之的文件。匯編程序生成的實際上是第一種類型的目標文件。對於後兩種還需要其他的一些處理方能得到,這個就是鏈接程序的工作了。
二、鏈接過程
由匯編程序生成的目標文件並不能立即就被執行,其中可能還有許多沒有解決的問題。
例如,某個源文件中的函數可能引用了另一個源文件中定義的某個符號(如變數或者函數調用等);在程序中可能調用了某個庫文件中的函數,等等。所有的這些問題,都需要經鏈接程序的處理方能得以解決。
鏈接程序的主要工作就是將有關的目標文件彼此相連接,也即將在一個文件中引用的符號同該符號在另外一個文件中的定義連接起來,使得所有的這些目標文件成為一個能夠被操作系統裝入執行的統一整體。
根據開發人員指定的同庫函數的鏈接方式的不同,鏈接處理可分為兩種:
(1)靜態鏈接
在這種鏈接方式下,函數的代碼將從其所在地靜態鏈接庫中被拷貝到最終的可執行程序中。這樣該程序在被執行時這些代碼將被裝入到該進程的虛擬地址空間中。靜態鏈接庫實際上是一個目標文件的集合,其中的每個文件含有庫中的一個或者一組相關函數的代碼。
(2) 動態鏈接
在此種方式下,函數的代碼被放到稱作是動態鏈接庫或共享對象的某個目標文件中。鏈接程序此時所作的只是在最終的可執行程序中記錄下共享對象的名字以及其它少量的登記信息。在此可執行文件被執行時,動態鏈接庫的全部內容將被映射到運行時相應進程的虛地址空間。動態鏈接程序將根據可執行程序中記錄的信息找到相應的函數代碼。
對於可執行文件中的函數調用,可分別採用動態鏈接或靜態鏈接的方法。使用動態鏈接能夠使最終的可執行文件比較短小,並且當共享對象被多個進程使用時能節約一些內存,因為在內存中只需要保存一份此共享對象的代碼。但並不是使用動態鏈接就一定比使用靜態鏈接要優越。在某些情況下動態鏈接可能帶來一些性能上損害。
我們在linux使用的gcc編譯器便是把以上的幾個過程進行捆綁,使用戶只使用一次命令就把編譯工作完成,這的確方便了編譯工作,但對於初學者了解編譯過程就很不利了,下圖便是gcc代理的編譯過程:
從上圖可以看到:
預編譯
將.c 文件轉化成 .i文件
使用的gcc命令是:gcc –E
對應於預處理命令cpp
編譯
將.c/.h文件轉換成.s文件
使用的gcc命令是:gcc –S
對應於編譯命令 cc –S
匯編
將.s 文件轉化成 .o文件
使用的gcc 命令是:gcc –c
對應於匯編命令是 as
鏈接
將.o文件轉化成可執行程序
使用的gcc 命令是: gcc
對應於鏈接命令是 ld
總結起來編譯過程就上面的四個過程:預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作,對我們理解頭文件、庫等的工作過程是有幫助的,而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤,以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。
Ⅲ 編譯原理——S、L屬性定義
如果一個語法制導定義的每一個屬性都是綜合屬性,那麼就叫做S屬性定義。
第二類語法制導定義叫做L屬性定義。在產生式中屬性之間的依賴圖邊都是從左到右,不是從右到左。
假設產生式A->X1,X2,...,Xn,而且Xi.a的繼承屬性與以下幾個屬性相關:
1.A的繼承屬性。
2.Xi左邊的產生式符號X1,X2,...,X(i-1)的屬性。
3.與Xi本身的屬性相關,但是只有一種通過Xj屬性生成無環依賴圖的方式。
S屬性定義都是L屬性定義。因為S屬性只限於綜合屬性。
Ⅳ 【編譯原理】第二章:語言和文法
上述文法 表示,該文法由終結符集合 ,非終結符集合 ,產生式集合 ,以及開始符號 構成。
而產生式 表示,一個表達式(Expression) ,可以由一個標識符(Identifier) 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹( )構成。
約定 :在不引起歧義的情況下,可以只寫產生式。如以上文法可以簡寫為:
產生式
可以簡寫為:
如上例中,
可以簡寫為:
給定文法 ,如果有 ,那麼可以將符號串 重寫 為 ,記作 ,這個過程稱為 推導 。
如上例中, 可以推導出 或 或 等等。
如果 ,
可以記作 ,則稱為 經過n步推導出 ,記作 。
推導的反過程稱為 歸約 。
如果 ,則稱 是 的一個 句型(sentential form )。
由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ,記作 。
即:
例
文法
表示什麼呢?
代表小寫字母;
代表數字;
表示若干個字母和數字構成的字元串;
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是,以字母開頭的、非空的字元串,即標識符的構成方式。
並、連接、冪、克林閉包、正閉包。
如上例表示為:
中必須包含一個 非終結符 。
產生式一般形式:
即上式中只有當上下文滿足 與 時,才能進行從 到 的推導。
上下文有關文法不包含空產生式( )。
產生式的一般形式:
即產生式左邊都是非終結符。
右線性文法 :
左線性文法 :
以上都成為正則文法。
即產生式的右側只能有一個終結符,且所有終結符只能在同一側。
例:(右線性文法)
以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串(標識符)。
以上文法等價於 上下文無關文法 :
正則文法能描述程序設計語言中的多數單詞。
正則文法能描述程序設計語言中的多數單詞,但不能表示句子構造,所以用到最多的是CFG。
根節點 表示文法開始符號S;
內部節點 表示對產生式 的應用;該節點的標號是產生式左部,子節點從左到右表示了產生式的右部;
葉節點 (又稱邊緣)既可以是非終結符也可以是終結符。
給定一個句型,其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2,那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。
直接短語一定是某產生式的右部,但反之不一定。
如果一個文法可以為某個句子生成 多棵分析樹 ,則稱這個文法是 二義性的 。
二義性原因:多個if只有一個else;
消岐規則:每個else只與最近的if匹配。
Ⅳ 編譯原理
編譯原理):利用編譯程序從源語言編寫的源程序產生目標程序的過程; 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言,計算機只認識1和0,編譯程序把人們熟悉的語言換成2進制的。
編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段:詞法分析;語法分析;語義檢查和中間代碼生成
(5)編譯原理里推導的定義擴展閱讀:
編譯程序的語法分析器以單詞符號作為輸入,分析單詞符號串是否形成符合語法規則的語法單位,如表達式、賦值、循環等,最後看是否構成一個符合要求的程序,按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構,程序是最終的一個語法單位。
編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種:自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發,向下推導,推出句子。
而自下而上分析法採用的是移進歸約法,基本思想是:用一個寄存符號的先進後出棧,把輸入符號一個一個地移進棧里,當棧頂形成某個產生式的一個候選式時,即把棧頂的這一部分歸約成該產生式的左鄰符號。
Ⅵ 編譯原理-文法定義
文法定義公式如下:
Chomsky 文法分類將文法分為四種,0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。
又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法(Phrase Structure Grammar)
定義: 對於產生式 α→β , α 至少包含一個非終結符。
為什麼要叫無限制文法,明明它要求產生式的左部必須包含一個非終結符。
又被稱為上下文有關文法(Context-Sensitive Grammar)
定義:對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外
為什麼叫做上下文有關文法?
一般情況下,這種產生式的形式為 α1Aα2→α1βα2
又被稱為上下文無關文法(Context-Free Grammar)
定義:對任一產生式 α→β ,都有 α∈VN,β∈(VN∪VT)*
為什麼叫上下文無關文法?
又被稱為正則文法(Regular Grammar,RG),分為右線性(Right Linear)文法和左線性(Left Linear)文法。
定義: 對任一產生式 α→β ,都有 α∈VN,β最多兩個字元元素,如果有二個字元必須是(終結符+非終結符)的格式,如果是一個字元,那麼必須是終結符。
根據產生式右部非終結符位置不同,分為右線性文法和左線性文法。
可以看出,不同文法就是對產生式進行逐層的限制,所以各個文法是包含關系,即0型文法包含1型文法;1型文法又包含2型文法;2型文法最後包含3型文法。
Ⅶ 什麼是(文法的)規范推導(編譯原理))
規范推導:最右推導
最右推導、最左推導、規范推導、規范句型
對於文法:G[S]:S → aAS | a
A → SbA | SS | ba
最右推導:S=> aA S =>a A a=>aSb A a
=>a S bbaa=>aabbaa(每次只推導 最右邊 的非終結符,直到推導完畢)
(得到的句型為 規范句型 )
最左推導: S=>a A S=>a S bAS=>aab A S
=>aabba S =>aabbaa(與最右推導類比理解)
Ⅷ 編譯原理全部的名詞解釋
書上有別那麼懶!.
編譯過程的六個階段:詞法分析,語法分析,語義分析,中間代碼生成,代碼優化,目標代碼生成
解釋程序:把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序,然後再執行目標程序.解釋方式是接受某高級語言的一個語句輸入,進行解釋並控制計算機執行,馬上得到這句的執行結果,然後再接受下一句.
編譯程序:就是指這樣一種程序,通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序).
解釋程序和編譯程序的根本區別:是否生成目標代碼
句子的二義性(這里的二義性是指語法結構上的.):文法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)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列,稱為程序的一個基本塊.
給我分數啊.