251
有關編譯原理
有關編譯原理
編譯程序的邏輯結構：詞法分析、語法分析、語義分析、中間代碼生成、代碼優化、目標代碼生成。六個階段。
1.詞法分析
目的：識別字符串，識別出關鍵字、數字、運算符、變量名等，以二元式（類別，值）的形式存儲，供後續的語法分析器用。
1.1文法：
一個文法可表示成形如G[S]=(Vn,Vt,P,S)的四元式。
Vn:非終結符號集；
Vt:終結符號集；
P:產生式集；
S:文法的開始符號。
文法的分類：分析略，有以下幾種。
|
0型 |
1型 |
2型 |
3型 |
|
短語結構文法 |
前後文有關文法 |
前後文無關文法 |
正規文法 |
確定的有限自動機（DFA）
DFA，Deterministic Finite Automaton。
DFA 用M=（K,∑,f,S0,Z）五元式表示。
K:狀態集合；
∑,：符號集合；
f：單值映射，f(p,a)=q:指明若當前的狀態為p，而輸入字符為a時下一個狀態就是q；
S0：一個初始狀態，屬於K；
Z：若幹個結束狀態，屬於K。
非確定的有限自動機（NFA）
NFA，Non-deterministic Finite Automaton。
NFA 用M=（K,∑,f,S0,Z）五元式表示，同DFA，區別為f可以不是單值映射，即f(p,a)={q1。q2,q3,...}。
NFA與DFA的等價性論證：
1.DFA是特殊的NFA；
2.NFA可等價德轉換到DFA。
文法－＞DFA的步驟：
文法->具有ε動作的NFA->DFA確定化->DFA狀態數最小化。
圖1-1 詞法分析的自動機示意圖
1.2正則表達式
又稱正規文法，用來描述符合特定文法的字符串。
符號有：
* • |
名字分別叫閉包、連接、或。這三個的優先級依次降低。
正規集：某文法下的全體字符串構成了相應的正規集。
|
正規式 |
正規集（ε代表空串） |
|
a|b |
{a,b} |
|
a|ba* |
{a,b,ba,baa,...} |
|
a* |
{ε,a,aa,aaa,...} |
|
(a|b)*abb |
任何以abb結尾的a、b符號串 |
增強版的 正則表達式見：
https://blog.csdn.net/chuchus/article/details/34109787
2.語法分析
以詞法分析的二元式作為輸入，判斷是否合乎特定文法。如int a 後缺少分號，語法分析器會報錯。
有自頂向下和自底向上兩種思想。對於前者，試著為源程序構造一棵完整的語法樹，若成功則無語法錯誤。
遞歸下降分析法，屬於自頂向下。是指對文法的每一非終結符號，都根據相應產生式各候選式的結構，為其編寫一個子程序，用來識別該非終結符號所表示的語法。
該方法要求文法不能有直接左遞歸。若有，可以對文法進行改造以達到要求。
例：
T->aFb 為語法的一部分，為非終結符號T、F分別構造相應的語法檢驗函數，T的判別函數見下：
T(){ ...;//判斷a
F();//判斷F
...;判斷b
}//若中間任一環節出錯則說明源程序不符合語法規定。
此類函數之間允許相互嵌套和遞歸。
3.語義分析
較複雜，不詳述。通常與語法分析並行進行。
定義函數 void fun(int);調用 fun();時會因參數不去匹配由語義分析器報錯。
4.中間代碼生成
四則運算表達式的表示方法：後綴表示法。
流程控製語句的翻譯：
while(a<b){if(c>d) x=y+z;}
|
地址 |
operator |
參數一 |
參數二 |
結果（地址） |
|
100 |
j< |
a |
b |
102 |
|
101 |
j |
/ |
/ |
107 |
|
102 |
j> |
c |
d |
104 |
|
103 |
j |
/ |
/ |
100 |
|
104 |
+ |
y |
z |
tmp |
|
105 |
= |
tmp |
/ |
x |
|
106 |
j |
/ |
/ |
100 |
|
107 |
... |
... |
... |
... |
5.代碼優化及目標代碼生成
略。
消除產生式中的直接左遞歸是比較容易的。例如假設非終結符P的規則為
P→Pα|β
其中，β是不以P開頭的符號串。那麼，我們可以把P的規則改寫為如下的非直接左遞歸形式：
P→βP’ P’→αP’|ε
這兩條規則和原來的規則是等價的，即兩種形式從P推出的符號串是相同的。
最後更新：2017-04-03 12:56:03