涵蓋所有考點(diǎn)，復(fù)習(xí)絕對(duì)高效，點(diǎn)贊+留郵箱獲取pdf版本
如果從開(kāi)始符號(hào)依次推導(dǎo)出 A1A2A3，則按其逆序排序時(shí)得到的產(chǎn)生式最少。
3. 消除回溯
通過(guò)反復(fù)提取左公因子可以消除回溯。
4. 提左公因子
5. 后綴表達(dá)式中綴轉(zhuǎn)后綴算法：
初始化符號(hào)棧，順序讀取中綴表達(dá)式，遇到(則將其入棧，遇到)則依次彈出棧頂元素到結(jié)果串中，直到遇到(，將其出棧但不附加到結(jié)果串；
遇到+-，彈出棧頂?shù)乃胁僮鞣郊拥浇Y(jié)果串中，然后自己進(jìn)棧；
遇到*/，先讓棧頂?shù)?code>*/出棧，附加到結(jié)果串中，然后自己進(jìn)棧；
遇到數(shù)字，直接附加到結(jié)果串中；
最后若符號(hào)棧非空，將符號(hào)棧棧頂元素依次附加到結(jié)果串中。
重慶分公司
重慶分公司
// 中綴轉(zhuǎn)后綴
vectorinterToPost(vectorvec)
{
vectorres;
stackop_stack;
for (int i = 0; i< vec.size(); i++) {
if (vec[i] == "(")
op_stack.push(vec[i]);
else if (vec[i] == ")") {
while (op_stack.top() != "(") {
res.push_back(op_stack.top());
op_stack.pop();
}
// 左括號(hào)出棧
op_stack.pop();
}
// 遇到+-，先讓棧中的+-*/出棧
else if (vec[i] == "+" || vec[i] == "-") {
while (!op_stack.empty() && op_stack.top() != "(") {
res.push_back(op_stack.top());
op_stack.pop();
}
op_stack.push(vec[i]);
}
// 遇到*/，先讓棧中的*/出棧
else if (vec[i] == "*" || vec[i] == "/") {
while (!op_stack.empty() && (op_stack.top() == "*" || op_stack.top() == "/")) {
res.push_back(op_stack.top());
op_stack.pop();
}
op_stack.push(vec[i]);
}
else
res.push_back(vec[i]);
}
while (!op_stack.empty()) {
res.push_back(op_stack.top());
op_stack.pop();
}
return res;
} 計(jì)算后綴表達(dá)式：
初始化數(shù)據(jù)棧，順序讀取后綴表達(dá)式，遇到操作符op則將棧次頂元素op棧頂元素，彈出操作數(shù)并壓入運(yùn)算結(jié)果；
遇到數(shù)據(jù)，則直接壓入棧頂；
最終棧頂元素就是結(jié)果。
// 計(jì)算后綴表達(dá)式
double solvePostPrefix(vectorpost_prefix) {
stackdataStack;
double num1, num2, result;
for (auto x : post_prefix) {
if (x == "+" || x == "-" || x == "*" || x == "/") {
num1 = dataStack.top();
dataStack.pop();
num2 = dataStack.top();
dataStack.pop();
if (x == "+")
result = num2 + num1;
if (x == "-")
result = num2 - num1;
if (x == "*")
result = num2 * num1;
if (x == "/")
result = num2 / num1;
dataStack.push(result);
}
else {
double num = strToDouble(x);
dataStack.push(num);
}
}
return dataStack.top();
} 是一種含義明確、便于處理的記號(hào)系統(tǒng)，通常獨(dú)立于具體的硬件但與指令形式有某種程度的接近，或者能夠比較容易的轉(zhuǎn)換為機(jī)器指令，常見(jiàn)的形式有：
把中間代碼變換為特定機(jī)器上的低級(jí)語(yǔ)言代碼，產(chǎn)生出足以發(fā)揮硬件效率的目標(biāo)代碼是一件非常不容易的事情。常見(jiàn)的形式有：
匯編指令代碼：需要匯編才能執(zhí)行；
絕對(duì)指令代碼：可以立即執(zhí)行；
可重定位指令代碼：運(yùn)行前必須借助于一個(gè)鏈接裝配程序，把各個(gè)目標(biāo)模塊（包括系統(tǒng)提供的庫(kù)模塊）連接在一起，確定程序裝入內(nèi)存中的起始地址，使之成為一個(gè)可以運(yùn)行的絕對(duì)指令代碼程序。
強(qiáng)制式語(yǔ)言：面向底層和語(yǔ)句，每個(gè)語(yǔ)句的執(zhí)行引起若干存儲(chǔ)單元中值的改變；
應(yīng)用式語(yǔ)言：更注重程序所表示的功能，每條語(yǔ)句都封裝了復(fù)雜的功能；
基于規(guī)則的語(yǔ)言：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作；
面向?qū)ο蟮恼Z(yǔ)言：主要特征是封裝性、繼承性、多態(tài)性。
用 Σ*表示 Σ 上所有符號(hào)串的全體，空字 ε 也在其中，稱為 Σ 的閉包。
10. 二義文法如果一個(gè)文法的某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，即其最左（ 最右）推導(dǎo)不唯一，稱該文法為二義文法。對(duì)程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，常常希望它的文法是無(wú)二義的，因?yàn)槲覀兿Ｍ麑?duì)它每個(gè)語(yǔ)句的分析是唯一的。
消除文法二義性的關(guān)鍵步驟：
例子：改寫二義文法
E ->E + E
E ->E * E
E ->(E) | -E | id優(yōu)先級(jí)從低到高：[+]；[*]；[( ), -, id]；
結(jié)合性：
左結(jié)合：[+, *]
右結(jié)合：[-]
無(wú)結(jié)合：[id]
非終結(jié)符與運(yùn)算：
E:+（E產(chǎn)生式，左遞歸）T:*（T產(chǎn)生式，左遞歸）F:-,( ),id（F產(chǎn)生式，右遞歸）
E → E + T | T
T → T * F | F
F → (E) | -E | id
**句型：**從文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的任一文法符號(hào)串；
**句子：**從文法開(kāi)始符號(hào)推導(dǎo)出來(lái)的任一終結(jié)符號(hào)串；
**短語(yǔ)：**對(duì)文法G[S]，如果有S =>* αAδ且A =>+ β，則稱β是句型αAδ相對(duì)于非終結(jié)符號(hào)A的短語(yǔ)。
短語(yǔ)是語(yǔ)法樹(shù)中所有子樹(shù)的邊緣，是相對(duì)于子樹(shù)根節(jié)點(diǎn)的短語(yǔ)。
例如：
短語(yǔ)是S，(T)，Sd(T)，b，Sd(T)db，(Sd(T)db)；
**直接短語(yǔ)：**對(duì)文法G[S]，如果有S =>* αAδ且A =>β，則稱β是句型αAδ相對(duì)于非終結(jié)符號(hào)A的短語(yǔ)。
直接斷語(yǔ)是所有二層子樹(shù)的邊緣，在上圖中只有三個(gè)二層子樹(shù)。
例如：上圖的直接短語(yǔ)是S，(T)，b；
**句柄：**最左直接短語(yǔ)；
句柄是最左二層子樹(shù)的邊緣。
例如：上圖的句柄是S；
**素短語(yǔ)：**至少包含一個(gè)終結(jié)符的短語(yǔ)，并且除它自身之外不再包含其他素短語(yǔ)；
例如：上圖的素短語(yǔ)是(T)，b；
**最左素短語(yǔ)：**句型最左邊的素短語(yǔ)，是算符優(yōu)先分析法的規(guī)約對(duì)象；
例如：上圖的最左素短語(yǔ)是(T)；
例子：
**活前綴：**是句型的一個(gè)前綴，不含句柄以后的任何符號(hào)；
例子：
15. 規(guī)范規(guī)約規(guī)范規(guī)約是最右推導(dǎo)的逆過(guò)程，因此也稱為最左規(guī)約。
16. 根據(jù) FA 寫正規(guī)式是根據(jù)正規(guī)式構(gòu)造 FA 的逆過(guò)程。
17. 符號(hào)表用于登記源程序的各類信息，如變量名、常量名、過(guò)程名等，以及編譯各階段的進(jìn)展?fàn)顩r。當(dāng)掃描器識(shí)別出一個(gè)標(biāo)識(shí)符后，把該名字填入符號(hào)表，在語(yǔ)義分析階段回填類型，在目標(biāo)代碼生成階段回填地址。
符號(hào)表的作用和地位：（重點(diǎn)）
符號(hào)表的主要屬性：
static、const等；符號(hào)表的組織方式：
符號(hào)表項(xiàng)的排列：
Hash表，跳表；運(yùn)行時(shí)存儲(chǔ)器的劃分：
存儲(chǔ)分配策略：
活動(dòng)記錄：
為了管理過(guò)程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這樣的一個(gè)連續(xù)存儲(chǔ)塊稱為活動(dòng)記錄， 一般包括：
SP指向當(dāng)前過(guò)程的動(dòng)態(tài)鏈地址（也是幀起始地址），它又指向調(diào)用該過(guò)程的上一過(guò)程的幀起始地址，用于過(guò)程結(jié)束后回收分配的幀；它和函數(shù)的嵌套定義關(guān)系無(wú)關(guān)，只與調(diào)用順序有關(guān)；
DAG優(yōu)化；DAG優(yōu)化；當(dāng)翻譯A = B op C時(shí)：
A、B、C是否還會(huì)在基本塊內(nèi)被引用；
對(duì)于一個(gè)不含回溯和左遞歸的文法，LL(1) 方法從左到右掃描輸入串，維護(hù)一個(gè)狀態(tài)棧和一個(gè)符號(hào)棧，每一步只向右查看一個(gè)符號(hào)，根據(jù)狀態(tài)棧頂、符號(hào)棧頂和分析表的內(nèi)容來(lái)確定下一步的動(dòng)作，最終分析出整個(gè)句子。
22. LR(1)分析LR(1) 分析適合大多數(shù)上下文無(wú)關(guān)文法，它從左到右掃描符號(hào)串，能記住移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，即 “記住歷史”，還可以根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能碰到的輸入符號(hào)，即 “展望未來(lái)”，根據(jù) “歷史”、“展望” 和分析表的內(nèi)容來(lái)確定下一步的動(dòng)作，最終分析出整個(gè)句子。
23. display 表為提高訪問(wèn)非局部變量的速度，引入指針數(shù)組指向本過(guò)程的所有外層，成為嵌套層次顯示表，display 表是一個(gè)棧，自頂向下依次指向當(dāng)前層、直接外層、直接外層的直接外層，直到最外層。
24. 語(yǔ)法制導(dǎo)翻譯法對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。這種有源程序的語(yǔ)法結(jié)構(gòu)驅(qū)動(dòng)的處理辦法就是語(yǔ)法制導(dǎo)翻譯法。
二、綜合題 2.1 詞法分析例題給定正規(guī)式： ①構(gòu)造NFA ②確定化 ③最小化
① + ②
③
例題 前提：LL(1) 適用條件給出文法：①構(gòu)造First集合 ②構(gòu)造Follow集合 ③構(gòu)造LL(1)分析表 ④識(shí)別句子
First(X)
②求A ->Bc
B ->ε
則 First(A) = { c }；
若 A ->B
B ->ε
則 First(A) = { ε }；
Follow(X)
給出文法：①構(gòu)造拓廣文法 ②求First集合 ③構(gòu)造LR(1)項(xiàng)目集規(guī)范族 ④構(gòu)造LR(1)分析表并消除二義性 ⑤識(shí)別句子
構(gòu)造帶向前搜索符的DFA，無(wú)歸約-歸約沖突則是LR(1)文法。
例題1構(gòu)造文法G[S]的LR(1)項(xiàng)目集規(guī)范族：
S ->aCaCb
S ->aDb
C ->a
D ->aS' ->S
S ->aCaCb
S ->aDb
C ->a
D ->aFirst集合：
LR(1)項(xiàng)目集規(guī)范族：
LR(1)分析表并消除二義性：
⑤識(shí)別句子消除二義性需要認(rèn)為定義運(yùn)算優(yōu)先級(jí)，發(fā)生移入-規(guī)約沖突時(shí)選擇正確的項(xiàng)填入。
aaaab和aab：
對(duì)下列文法做 LR(1) ：
S ->AS | b
A ->SA | a
1. 過(guò)程中的說(shuō)明語(yǔ)句給出翻譯模式和高級(jí)語(yǔ)言程序，翻譯句子，一般涉及多種類型句子的綜合，也可能涉及聲明語(yǔ)句填寫符號(hào)表。
3. 布爾表達(dá)式的翻譯重點(diǎn)：回填。
重點(diǎn)：if 和 while 。
例題1給出基本塊代碼：①構(gòu)造DAG ②寫出優(yōu)化后的中間代碼 ③寫出DAG目標(biāo)優(yōu)化后的中間代碼 ④根據(jù)變量活躍性和寄存器信息，寫出目標(biāo)代碼。
給出基本塊代碼為：
(1) T6 = R - r
(2) T2 = R * r
(3) T4 = T2
(4) T1 = 6.28
(5) T3 = 6.28
(6) A = 6.28 * T2
(7) T5 = A
(8) B = A * T6
(9) T0 = 3.14假定B是基本塊出口之后活躍的，有寄存器R0和R1可用，目標(biāo)代碼為：
DAG 優(yōu)化中，不活躍變量，目標(biāo)代碼依然要生成計(jì)算其值的代碼，只是不生成存儲(chǔ)到主存的代碼。計(jì)算代碼被優(yōu)化是后續(xù)優(yōu)化完成的，不是 DAG 完成的。
LD R0, R
SUB R0, r R0: T6 R1: \
LD R1, R
MUL R1, r R0: T6 R1: T2
ST R0, T6
LD R0, 6.28 R0: 6.28 R1: T2
MUL R0, R1 R0: A R1: T2
MUL R0, T6 R0: B R1: T2
ST R0, B
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-MmUNQHdO-1655768860486)(https://s2.loli.net/2022/06/21/kX5Cfm2ILzv4ibW.png)]
一、簡(jiǎn)答（30 分）
1.給了一個(gè)文法（具體忘了），讓證明二義性。
2.寫出文法，表示{0、1}集上的所有正規(guī)式
3.解釋 S-屬性文法
4.說(shuō)出傳地址和傳質(zhì)這兩種參數(shù)傳遞方式的異同
5.結(jié)合具體例子談一談回填思想
二、（babbb）* 畫(huà) NFA 轉(zhuǎn) DFA ，最小化（15 分）
三、（1）一個(gè)文法，判斷是否為 LL（1）文法（10 分）
（2）上題中的文法是否為 SLR 文法，給出證明（15 分）
（與課本上例子不同之處在于有 B ——〉ε）
四、利用語(yǔ)法指導(dǎo)思想寫四元式（15 分）
（比較簡(jiǎn)單，就是一個(gè) while-do 語(yǔ)句）
五、給出一段中間代碼，畫(huà) DAG 圖；只有 R 在代碼塊外是活躍的，做優(yōu)化；如
果有寄存器 R0 和 R1，寫出目標(biāo)代碼。（15 分）
一、簡(jiǎn)答題
1.編譯流程圖及各部分的作用。⒉舉例說(shuō)明文法二義性。
3.什么是L屬性文法?
4.寫出允許過(guò)程嵌套的C活動(dòng)記錄結(jié)構(gòu)。5.中間代碼優(yōu)化有哪幾種?
6.符號(hào)表作用。
二、詞法分析
RE NFA DFA最小化DFA整個(gè)流程走一遍
三、自上而下文法分析
給了一個(gè)文法，證明文法是LL1的，畫(huà)表。
四、自下而上文法分析
給了一個(gè)文法,證明文法是LR1的，畫(huà)表。
五、中間代碼生成
—段代碼，四元式翻譯。涉及循環(huán)和判斷的嵌套。
六、代碼優(yōu)化和目標(biāo)代碼生成。
給了一個(gè)代碼段，
先畫(huà)DAG圖，然后優(yōu)化，最后輸出匯編代碼。
一、五個(gè)小題（25分）
1.判斷一個(gè)文法是否二義
2.編譯的前端，后端，什么是一遍掃描
3.什么是S屬性
4.什么是語(yǔ)法制導(dǎo)翻譯
5.在語(yǔ)法制導(dǎo)翻譯中，空返產(chǎn)生式的作用（M->e）
二、自動(dòng)機(jī)（15分）
一個(gè)單詞表由a，b組成，請(qǐng)寫出代表偶數(shù)個(gè)a的正規(guī)式，NFA，并確定化、最小化
三、判斷一個(gè)文法是不是LL（1）的，如果是就寫出預(yù)測(cè)分析表，不是就說(shuō)明原因（15分）
四、判斷一個(gè)文法是不是SLR（1）的，如果是就寫出預(yù)測(cè)分析表，不是就說(shuō)明原因（15分）
五、中間代碼生成程序（15分）
while a 六、代碼優(yōu)化（15分） DAG優(yōu)化，最后寫出四元式的形式（這個(gè)是一個(gè)坑，四元式是目標(biāo)代碼，也就是此時(shí)要做目標(biāo)代碼生成） 同時(shí)目標(biāo)代碼生成要列表（Rvalue 寄存器描述，Avalue地址描述） 一、簡(jiǎn)答題 二、計(jì)算題 整體比較簡(jiǎn)單，高分應(yīng)該挺多。把本文涉及到的知識(shí)點(diǎn)全部搞清楚，應(yīng)付考試游刃有余 后續(xù)同學(xué)們考完試，可以把回憶版私發(fā)給我，我在此文中持續(xù)更新。 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
while a< b do if c >d then x = y * z，會(huì)給出翻譯規(guī)則。
文章名稱：【編譯原理】山東大學(xué)編譯原理復(fù)習(xí)提綱-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/djpipg.html
