資源描述：
《編譯原理第5章語法制導翻譯及中間代碼生成.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第五章語法制導翻譯及中間代碼生成§5.1語法制導翻譯概述§5.2中間語言§5.3自底向上語法制導翻譯§5.4自頂向下語法制導翻譯§5.5屬性文法與屬性翻譯1§5.1語法制導翻譯概述一、語法制導翻譯定義二、語法制導翻譯原理三、語法制導翻譯實現(xiàn)2一、語法制導翻譯定義語法制導翻譯就是以語法分析為主導的語義處理。在語法分析過程中嵌入語義動作，即調(diào)用對應的語義子程序。例如在前面語法分析時分析a+b*c表達式，其分析語法樹如下：E+EE*EEabc在語法分析同時進行語義分析3二、語法制導翻譯原理語法制導翻譯的原理就是先為每個文法規(guī)確定相應的語義，即編寫
2、出相應語義處理子程序，整個分析是以語法分析為主導。語義動作：給每個文法符號X賦以各種不同的語義值4例如，假定有如下規(guī)則和語義動作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}5例5.1設有文法E∷=E+EE∷=digit這里digit代表0和9之間任一數(shù)字，如果我們的目的僅是為了求值，則語義動作如下(1)E∷=E(1)+E(２){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定語義動作中的“+”代表是整型加算術(shù)運算。6例如，假定有輸入串1+2+3，我們通
3、過語法樹的分析來看如何進行語法制導翻譯，來求出該句子最后值。輸入串1+2+3的語法樹如下圖所示.E+EE+EE1237(1)X∷=…{動作1}(2)Y∷=…{動作2}(3)A∷=XY{動作3}現(xiàn)在對LR分析器的分析棧加以擴充，為了在語法分析過程中平行地進行語義處理，使得每個文法符號之后都跟著它的語義值，因此，設置一個語義信息棧，為了清晰起見，我們把這個分析棧每一項分三部分組成：狀態(tài)STATE、文法符號SYM和語義值VAL。三、語法制導翻譯實現(xiàn)8SmY?VALYSm-1X?VALXS0－#………TOPSTATEVALSYM分析棧如下圖所示:9
4、我們假定先歸約后執(zhí)行語義子程序，所以當X，Y歸約為A,Sm和Sm-1歸約為新狀態(tài)S后，執(zhí)行語義子程序X和Y的值也歸約為A的值。10SmSm-1Y?VALX?VALYXTOP歸約前SiX?VALATOP歸約后Y?VALSiA?VALATOP求值后A?VAL:=Y?VAL+X?VAL11例5.2考慮下面文法及其語義描述：規(guī)則語義動作(0)S’∷=E{printE·VAL}(1)E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=E(1)*E(2){E·VAL:=E(1)·VAL*E(2)·VAL}(3)E∷=
5、(E(1)){E·VAL=E(1)·VAL}(4)E∷=i{E·VAL:=LEXVAL}12規(guī)則程序段(0)S’∷=E{printVAL［TOP］}(1)E∷=E(1)+E(2){VAL[TOP]：=VAL[TOP]+VAL[TOP+2]}(2)E∷=E(1)*E(2){VAL[TOP]：=VAL[TOP]*VAL[TOP+2]}(3)E∷=(E(1)){VAL［TOP］:=VAL［TOP+1］}(4)E∷=i{VAL［TOP］:=LEXVAL}13根據(jù)上述程序段，若輸入2*3+2，就有如下圖所示的語法制導翻譯的分析樹。S’EEEEE+*2
6、23E?VAL=8E?VAL=6E?VAL=4E?VAL=2E?VAL=3LEXVAL=2LEXVAL=3LEXVAL=214對2*3+2進行分析和翻譯(實為計算值)該輸入串過程如下表所示。當狀態(tài)1面臨#時對應的分析動作為acc(接受)，此時，相應的語義動作為printVAL[TOP]，即輸出語義程序的計值結(jié)果：8。步驟狀態(tài)棧語義值棧符號棧輸入串歸約規(guī)則及動作10－＃2*3+2＃S3203－－＃2*3+2＃r4301－2＃E*3+2＃GOTO[0,E]=1,S54015－2－＃E*3+2＃S350153－2－－＃E*3+2＃r460158－
7、2－3＃E*E+2＃GOTO[5,E]=8,r2701－6＃E+2＃GOTO[0,E]=1,S48014－6－＃E+2＃S390143－6－－＃E+2＃r4100147－6－2＃E+E＃GOTO[4,E]=7,r11101－8＃E＃acc15§5.2中間語言一、引言二、逆波蘭表示三、三元式四、樹形表示五、四元式16一、引言1.什么是中間語言2.為什么要引入中間語言17一、引言1.什么是中間語言就是和源程序等價的一種編碼形式，其復雜性介于源程序和機器語言中間。源程序前端中間代碼代碼優(yōu)化器中間代碼代碼生成器目標程序符號表182.為什么要引入中間
8、語言（1）為了使編譯程序結(jié)構(gòu)上邏輯簡單明確（2）為了便于目標代碼優(yōu)化工作（3）便于目標代碼生成19二、逆波蘭表示1.表達式逆波蘭表示（1）逆波蘭表示的概念對于一個算術(shù)表達式A+B
