sun編譯原理總復(fù)習(xí)(第24講).ppt

1、2020/7/15,信息學(xué)院 孫麗云,1,總復(fù)習(xí), 第1章,1、編譯程序是一種翻譯程序，它將高級語言所寫的源程序翻譯成等價的機器語言或者匯編語言的目標(biāo)程序。 2、編譯程序是計算機系統(tǒng)中重要的系統(tǒng)軟件！ 3、解釋程序與編譯程序的主要區(qū)別是解釋程序在執(zhí)行過程中不產(chǎn)生目標(biāo)程序。 4、編譯的各個階段。 5、T型圖。,2020/7/15,信息學(xué)院 孫麗云,2,總復(fù)習(xí),第2章,1、符號串的基本運算。 2、簡單的說文法由產(chǎn)生式組成；產(chǎn)生式中的符號分為兩類：終結(jié)符號和非終結(jié)符號。 3、推導(dǎo)（最左、最右）、句型、句子、短語、句柄 4、 喬姆斯基層次中：L3 L2 L1 L0,2020/7/15,信息學(xué)院 孫麗云

2、,3,已知文法GE： ET|E+T|E-T TF|T*F|T/F F(E)|i （1）該文法的開始符號是什么？（2）請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。 （3）找出句型T+T*F+i的所有短語、直接（簡單）短語、句柄。,第2章例題,2020/7/15,信息學(xué)院 孫麗云,4,總復(fù)習(xí),第3章,1、詞法分析程序的輸出是單詞符號序列。 2、 DFA的三種表示形式狀態(tài)轉(zhuǎn)移圖、狀態(tài)轉(zhuǎn)換表和五元組表示（ Q, , f, S, Z ） ； 3、正規(guī)式向DFA的轉(zhuǎn)換： （1）正規(guī)式NFA;（轉(zhuǎn)換原則見下頁） （2）NFADFA； （3）DFA的最小化。 4、DFA向正規(guī)式的轉(zhuǎn)換。,2020/7/

3、15,信息學(xué)院 孫麗云,5,若r,s為正則式：,r*,r|s,rs,第3章,正則式向NFA轉(zhuǎn)換的原則：,例：構(gòu)造與正則表達(dá)式R=ba(a|b)*等價的狀態(tài)最少的DFA，并寫出該DFA的五元組形式或狀態(tài)轉(zhuǎn)換表。,2020/7/15,信息學(xué)院 孫麗云,6,遞歸下降法 LL(1)分析法,回溯分析方法 預(yù)測分析方法,LR(0) parsing SLR(1) parsing LR(1) parsing LALR(1) parsing,自頂向下分析方法,從根結(jié)點出發(fā)構(gòu)造語法樹,自底向上分析方法,從葉結(jié)點出發(fā)構(gòu)造語法樹,語法分析方法,L:由左向右的處理輸入 L:為輸入串構(gòu)造最左推導(dǎo),L:由左向右的處理輸入

4、R:為輸入串構(gòu)造最右推導(dǎo)的逆過程, 第4章,2020/7/15,信息學(xué)院 孫麗云,7, 第4章,1、語法分析方法的各種分類； 2、LL(1)分析方法。 提示：在此算法中注意First集和Follow集的求法。并且一定要注意分析過程中步驟要完整。（分析步驟見下頁總結(jié)）,例：文法：Sa|(T) TT,S|S 試判斷該文法是否是LL(1)文法。有左遞歸,習(xí)題4：P100 4.3 4.7 4.9,（1）簡單直接左遞歸的消除 A A| ,1、消除文法中的左遞歸或提取左因子；, LL(1)分析方法相關(guān)知識總結(jié),（2）將文法G： A|提取左因子。,解： AA A|,2、求改寫文法中的非終結(jié)符的First集和

5、Follow集； 3、判斷文法是否是LL(1)文法； 一個上下文無關(guān)文法G是LL(1)文法，當(dāng)且僅當(dāng)對G中每個非終結(jié)符A的任何兩個不同的規(guī)則A 滿足： Select(A ) Select(A ) = 4、若該文法是LL(1)文法，則構(gòu)造預(yù)測分析表； （1）對于First()中的每個記號a，都將A 添加到表項MA, a中； （2）若在First()中，則對于Follow(A)的每個元素a(記號或是$)，都將A 添加到MA, a中。 5、根據(jù)分析表進(jìn)行自頂向下的語法分析。,2020/7/15,信息學(xué)院 孫麗云,9, 第4章,3、LR分析的四種方法LR(0)、SLR(1)、LR(1)、LALR(1)

6、，并注意4種方法的區(qū)別。,LR(0)項目 初始項目：A. 歸約項目：A . 移進(jìn)項目： A . a 待約項目： A . B,例：已知文法GS，求其LR(0)的分析表。 S aA | bB A cA | d B cB | d,2020/7/15,信息學(xué)院 孫麗云,10, LR分析方法步驟比較,自底向上的語法分析,共同點：四種LR分析方法的步驟一樣，都有如下四步： (1)拓廣文法并對產(chǎn)生式編號； (2)構(gòu)造識別文法活前綴的DFA，根據(jù)DFA判斷為何文法； (3)分析表的構(gòu)造； (4)分析過程。 不同點：（2）（3）步驟中略有不同： (1)LR(0)與SLR(1)的DFA的狀態(tài)（有效項目集）中全為L

7、R(0)項（產(chǎn)生式中加點）,LR(1)與LALR(1)的DFA的狀態(tài)中全為LR(1)項（由LR(0)項和搜索符組成,并由中括號括起來）。 (2)分析表：移進(jìn)項目都一樣，在歸約項目上不同。,2020/7/15,信息學(xué)院 孫麗云,11,第5章,1、詞法規(guī)則的描述工具、語法規(guī)則的描述工具、語義規(guī)則的常用描述工具： 2、文法符號的語義屬性可分為綜合屬性和繼承屬性； 3、語法制導(dǎo)的翻譯，見下例：,例：給出文法GS： S SaA|A A AbB|B B cSd|e 為文法GS的相應(yīng)產(chǎn)生式寫出語義動作，使句型AacAd經(jīng)該翻譯方案后，輸出為11435,2020/7/15,信息學(xué)院 孫麗云,12,第5章,1、

8、常見的中間語言逆波蘭式、三地址碼、四元式、三元式、間接三元式、樹形表示等； 2、各種語句的中間代碼翻譯（給出一個語句序列能夠?qū)懗鰧?yīng)的四元式序列）； 例如：求下列語句的四元式序列。 while(x1 ,第6章,1、符號表的處理是編譯程序的重要組成部分； 2、課后習(xí)題。,2020/7/15,信息學(xué)院 孫麗云,13,第7章,1、會劃分基本塊，并能夠給出其程序流圖； 2、中間代碼的局部優(yōu)化 會利用DAG對基本塊進(jìn)行優(yōu)化。,練習(xí)題： 1、將下列三地址碼序列劃分基本塊，并畫出程序流圖。,read a read b c=a add b if r=0 goto (8) a=b b=c goto (3) wr

9、ite(b) halt,2020/7/15,信息學(xué)院 孫麗云,14,練習(xí)題： 2、已知一基本塊如下,B=3 D=A+C E=A*C F=E+D G=B*F H=A+C I=A*C J=H+I K=B*5,請應(yīng)用DAG對該基本塊進(jìn)行優(yōu)化。,2020/7/15,信息學(xué)院 孫麗云,15,一、單選題（10分） 二、填空題（10分） 三、判斷題（5分） 四、簡答題（8分） 五、應(yīng)用題（67分）7個小題 前面14頁PPT提到的知識點+期中考試題+列舉的大題題型, 考試題型,2020/7/15,信息學(xué)院 孫麗云,16,考試和答疑時間,考試時間：第18周； 答疑時間：考試前1天； 答疑地點：F103,考試注意事項,1、審題仔細(xì)，步驟完整； 2、題型是平時練習(xí)過的； 3、認(rèn)真復(fù)習(xí)，從容應(yīng)考，誠信考試！,假期作業(yè)在公共郵箱： 密碼：xinxi2008,2020/7/15,信息學(xué)院 孫麗云,17,關(guān)于上機,完成并給我講過語法分析程序的同學(xué)，上機成績?yōu)椤皟?yōu)”；若去上課可考慮語義分析，或者別的語法分析方法； 完成語法分析程