傳統編譯原理
計算機程式編譯原理，把程式員員容易了解的進階語言程式代碼流，翻譯成計算機可執行的機器指令代碼流。可以使用“一斷、二比、三譯”形象說明實質。
1、斷。按照語言的文法規則掃描斷詞，結合文法詞典，把程式字元串流，分解成為計算機語言能夠識别的基本單元（辨別詞、運算符）。
2、比。從程式流中找出擴充辨別詞的定義，建立辨別詞結構，放入文法詞典，服務于新的定義和函數程式代碼的編譯。程式語句、表達式裡面使用的辨別可以從詞典中比較找到。
3、譯。把函數程式文本字元串流中的算術表達式、指派語句、控制語句，翻譯成為計算機機器語言二進制代碼流。
4、組裝函數翻譯後的二進制代碼流，明确資料空間位址和大小，生成計算機裸機或作業系統可以執行目标代碼。
1、 翻譯——将語言L1轉換為邏輯上等價的語言L2
編譯——将源程式（進階語言）翻譯成目标程式（低級語言或機器語言）
彙編——将低級語言翻譯成機器語言
解釋（程式）——逐條翻譯語句，并立即執行結果
2、 單詞——關鍵字、辨別符、常數、界符、運算符
單詞 = (單詞種别碼,單詞自身值)
文法機關——短語、表達式、語句、子程式、程式
中間代碼——四元式、三元式、逆波蘭式、樹式
3、 初等資料類型——邏輯、數值、字元、指針
文法：是一組規則，規定了語言的形式結構，包括單詞結構，句子結構，程式結構等。
文法={詞法規則+句法規則}
語義：也是一組規則，規定了各文法機關的确切含義。
語句
說明性語句——用于定義各種資料類型,變量,函數或過程.
可執行性語句——用于描述資料處理的過程和動作
4、 參數傳遞——傳名、傳位址、傳值
5、正規式
6、狀态轉換圖
是一有向圖,由有限個結點及有向邊連接配接而成;
每個結點稱為狀态;
狀态圖有一個初态，多個終态;
每條邊上有相應的字元.
狀态轉換圖用于表示單詞結構從狀态轉換圖的初态到終态間，每條路徑上字元的連接配接,就構成了該狀态圖的合法單詞.
可以表示單詞規則,也可以用于識别單詞
由三種結構構成 —— 分支結構、循環結構、終結點
7、 确定有限自動機（DFM）和非确定有限自動機（NFM）
DFAM=(S, ∑, f,s0,Z)
狀态集、符号集、單/多值映射函數、初态（1個）、終态集
DFAM 是 NFAM 的特例
DFAM案例：
8、 可識别單詞的全體記為:L(M)
設 V 為字集,且 V0={ε}， 令 V*=V0∪V1 ∪ V2 ∪........ ，稱V* 為V的閉包。 V+= V* - {ε}， 稱V+ 為V的正則閉包。
9、 句子——由文法的開始符号出發通過0步或若幹步推導産生的終結符号串
若 S=>α，則α ∈VT *
句型——由文法的開始符号出發通過0步或若幹步推導産生的符号串
若 S=>α，則α ∈(VT ∪ VN) *
10、語言——所有句子的集合，記為L(G)={α |S=>α, α ∈VT * }
一個語言的文法是不唯一的
11、句柄——一個句型的最左直接短語
簡單（直接）短語
短語
素短語——至少含有一個終結點，且除自身外不含有更小的素短語
12、 上下文無關文法——它定義的文法機關獨立于該文法機關可能出現的環境
自然語言不是上下文無關文法，程式語言是上下文無關文法
G =(VT,VN,S,P)
終結符集、非終結符集、開始符号、産生式
13、最左推導——每次直接推導,對句型的最左非終結符實行替換
最右推導——每次直接推導,對句型的最右非終結符實行替換
解決文法二義性：E—>i*i+i
14、文法分析方法_自下而上
根據文法,對輸入字串進行歸約,若能正确地歸約 為文法的初始符号,則表示輸入字串是合法的。典型方法是算符優先分析法。
規範歸約（歸約棧）——最右推導的逆過程（算符優先分析法）
(1)優先關系表
- aQb a=b
- aQ a<FIRSTVT(Q)
- Qb LASTVT(Q)>b
(2)存在的問題
1.文法的左遞歸
2.文法的回溯
15、文法分析方法_自上而下
從文法的初始符号進行推導,若能推導出與輸入字串相同的句子,則表示輸入字串是合法的。 典型方法是遞歸下降分析法。
規範推導——最左推導的逆過程（遞歸下降分析法）
16、歸約串——棧頂形成的某産生式候選
可歸約串（最左素短語）——可正确歸約的歸約串
17、文法樹 —— 可以表示同一句型的多種推導，是多種推導的共性抽象；但未必代表了同一句型的所有推導
LL(1)文法（無回溯文法）——無二義性、無左遞歸
LR（0）<SLR（1）<LALR（1）<LR（1）
18、消除左遞歸
若 P→P α | β ，則 P→ βP ’， P’ → αP ’ | ε
19、 符号表的作用：用于紀錄各種名字的資訊, 并提供給編譯各階段使用
種屬、類型、位址、長度、形參标志、其它資訊
20、中間代碼的特點: 結構簡單，功能明确，易于優化，易于翻譯。
21、文法制導翻譯——在文法分析的每次歸約或推導時，根據産生式的語義進行翻譯的一種方法。
一些基本操作：
- newtemp( ) 産生一臨時變量;
- gen(操作符,操作數1,操作數2,結果) 填入四元式表;
- fill( i,屬性) 填入符号表;
- entry( i ) 查符号表,傳回 i 在符号表中的位置;
- backpatch( m,n) 把 n 填入 四元式表第 m 個四元式中;
22、語義動作——描述了一定的輸入和一定的輸出之間的對應關系。
24、基本塊——順序執行的中間代碼序列，僅包含一個入口四元式和一個出口四元式。第一條四元式為入口四元式，最後一條四元式為出口四元式，中間部分不含轉移四元式。
四元式程式中所有基本入口四元式,包括:
a) 程式的第一條四元式;
b) 轉移語句轉移到的四元式;
c) 條件語句之後的第一條四元式.
基本塊内可以進行以下幾種優化:（優化手段: DAG ）
合并已知量，删除多餘運算(公共子表達式)，删除無用指派。
25、回邊——若有邊b->a且a是b的必經結點，則b->a是回邊
控制流程圖——具有唯一首結點的有向圖，簡稱為流圖
必經結點——從流圖首結點出發到達b的通路都必須經過點a，則稱a是b的必經結點，記a DOM b
必經結點集——D(n)
26、可歸約流圖——流圖中去除回邊後，構成無環路流圖
循環——對于回邊b->a，包括a、b在内的，有通路到b而不經過a的所有結點構成一個循環
(1) 結點序列為強連通的;(任意兩點間都有通路,且通路上的結點都屬于結點序列)
(2) 結點序列中僅有一個入口結點.
三種循環優化:代碼外提，強度削弱，删除歸納變量。
27、引用--定值集ud[A]
如在 u 處引用了變量 A,則凡能到達 u 的 A 的所有定值點,構成了 A 在 u 處的引用--定值集 ,記為: ud[A].
- IN[B] : 代表到達基本塊 B 入口點時的各變量的所有定值點集
- OUT[B]:代表到達基本塊 B 出口點時的各變量的所有定值點集
- GEN[B]:表示 B 中所定值的且到達 B 之後的定值點集
- KILL[B]: 表示屬于 B 外的定值點,而這些定值點所定值的變量，在B中又被重新定值
這幾個集合滿足如下方程:
- OUT[B]=(IN[B] - KILL(B)) ∪ GEN[B]
- IN[B] = OUT[p1] ∪ OUT[p2] ∪...... ∪ OUT[pk]
- p1 , p2...... pk 為B的前趨結點
該方程即為到達--定值方程,求解該方程,得到IN[B]。
28、不變運算——對于循環中的語句 A:= B op C, 若 B 及 C 均為常量,或者為循環中未改變的變量, 那麼每次循環 A的值都一樣,稱A:= B op C為不變運算.
運算對象是常量；
運算對象的定值點均在循環外；
運算對象的再循環内的定值點均已被标記為不變運算；
29、基本歸納變量——若循環中對 B 隻有唯一的遞歸指派 B:=B+C 且 C 為循環不變量,則稱 B 為循環的基本歸納變量
歸納變量——若B為基本歸納變量，而A在循環中的定值可以化歸為B的線性函數:A:=C1*B+C2(C1 , C2為循環不變量)，則稱A 為歸納變量,并稱 A與 B同族
待用資訊表——指針指向下一個引用的地方
設四元式(i) 對A定值且到達四元式(j) ,四元式 ( j) 中引用 A ,則稱 j 是四元式 i 的變量A 的待用資訊; 滿足上述定義的所有 j, 構成了 A 的待用資訊集。
30、目标代碼
生成原則：
(1)生成的目标代碼短而高效；
(2) 充分利用寄存器,減少通路記憶體的次數；
形式：
(1)能立即執行的目标代碼；
(2)待裝配的浮動目标代碼；
(3)彙編語言目标代碼；
31、空間配置設定