861第二章簡(jiǎn)單的一遍編譯器

1、1/35第二章：簡(jiǎn)單的一遍編譯器v概述v語法制導(dǎo)翻譯技術(shù)語法定義語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式語法分析v實(shí)例：一個(gè)簡(jiǎn)單表達(dá)式的翻譯器（下次）2/35第二章：簡(jiǎn)單的一遍編譯器：概述v如何描述程序語言？詞法+語法+語義+語用程序模式：語法v比較容易描述v上下文無關(guān)文法或bnf程序含義：語義v比較難以描述v非形式化方法、啟發(fā)性實(shí)例3/35第二章：簡(jiǎn)單的一遍編譯器：概述v任務(wù)：表達(dá)式計(jì)算編譯器前端：中綴表達(dá)式=后綴表達(dá)式v例：9+5-2 =95+2-v編譯器前端結(jié)構(gòu) 圖2-1詞法分析器：字符流=符號(hào)流語法制導(dǎo)翻譯器：記號(hào)流=中間表示v語法分析器+中間代碼生成器v語法制導(dǎo)翻譯技術(shù)：面向語法的翻譯技

2、術(shù)編譯器后端：后綴表達(dá)式=機(jī)器代碼v堆棧v例： 用堆棧計(jì)算95+2-4/35第二章：簡(jiǎn)單的一遍編譯器v概述v語法制導(dǎo)翻譯技術(shù)語法定義語法定義語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式語法分析5/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v上下文無關(guān)文法：定義產(chǎn)生式集合v例：產(chǎn)生式stmt - if (expr) stmt else stmt終結(jié)符集合：記號(hào)集合v例：終結(jié)符/記號(hào)：if、else由詞法分析器產(chǎn)生：字符串=記號(hào)流非終結(jié)符集合：表示記號(hào)序列v例：非終結(jié)符stmt、expr開始非終結(jié)符6/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v上下文無關(guān)文法：實(shí)例例2.1：由數(shù)字、加號(hào)和減號(hào)組成的表達(dá)式vlis

3、t - list + digit | list digit | digitvdigit - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 97/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v上下文無關(guān)文法：實(shí)例例2.3：pascal的begin-end語句塊vblock - begin opt_stmts endvopt_stmts - stmt_list | vstmt_list - stmt_list ; stmt | stmt8/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v分析樹：定義樹根節(jié)點(diǎn)為開始非終結(jié)符每個(gè)葉節(jié)點(diǎn)由一個(gè)終結(jié)符（記號(hào)）或標(biāo)記每個(gè)內(nèi)節(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記如

4、果a是某個(gè)內(nèi)節(jié)點(diǎn)的，x1、x2xn是該節(jié)點(diǎn)的從左到右的所有子節(jié)點(diǎn)的標(biāo)記（終結(jié)符或非終結(jié)符），則a -x1x2xn是一個(gè)產(chǎn)生式。9/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v分析樹：實(shí)例例2.4： 9+5-2 =分析樹（圖2-2）分析樹生成的結(jié)果v一顆分析樹從左到右的葉節(jié)點(diǎn)v由樹根節(jié)點(diǎn)的開始非終結(jié)符生成或?qū)С龅拇?0/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v幾個(gè)概念語言（文法）：文法的分析樹導(dǎo)出的串的集合語法分析：記號(hào)串=句法樹（語法樹）v同自然語言的句法分析：i love this game .11/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v文法的二義性一個(gè)記號(hào)串對(duì)應(yīng)幾個(gè)不同的句法樹例2.5：9-

5、5+2 =(9-5)+2 | 9-(5+2) ？（圖2-3） v文法string - string + string | string string string - 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9例：i saw a dog with a telescope .va dog with a telescopevsaw with a telescope12/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v上下文無關(guān)文法的應(yīng)用定義語言的語法v表達(dá)式的語法v語句的語法指導(dǎo)源程序的翻譯v語法制導(dǎo)翻譯技術(shù)13/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v表達(dá)式的語法：操作符

6、的結(jié)合性和優(yōu)先級(jí)操作符的結(jié)合規(guī)則v左結(jié)合（如加減乘除）：操作數(shù)與左操作符結(jié)合left - left + digit | left digit | digit digit - 0 | 1 | 9例：9-5+2 =（9-5）+214/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v表達(dá)式的語法:操作符的結(jié)合性和優(yōu)先級(jí)操作符的結(jié)合規(guī)則（續(xù)）v右結(jié)合： ：操作數(shù)與右操作符結(jié)合指數(shù)運(yùn)算符：423 = 4(23)運(yùn)算操作符：a=b=c = a=(b=c)right - letter = right | letter right | letterletter - a | b | zv例：圖2-415/35第二章：簡(jiǎn)

7、單的一遍編譯器：語法定義v表達(dá)式的語法：操作符的結(jié)合性和優(yōu)先級(jí)操作符的優(yōu)先級(jí)v例：9+5*2 =（9+5）*2 | 9+（5*2）？v括號(hào)、乘除、加減16/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v表達(dá)式的語法：如何運(yùn)用操作符兩原則先優(yōu)先級(jí)高的后優(yōu)先級(jí)低的左結(jié)合vs右結(jié)合例：左結(jié)合（page 21）例：右結(jié)合（課堂練習(xí)）17/35第二章：簡(jiǎn)單的一遍編譯器：語法定義v語句的語法：例page 22 stmt - id := expr| if expr then stmt| if expr then stmt else stmt| while expr do stmt| begin opt_stmts

8、 end18/35第二章：簡(jiǎn)單的一遍編譯器v概述v語法制導(dǎo)翻譯技術(shù)語法定義語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式語法分析19/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v表達(dá)式e的后綴表示如果e是一個(gè)變量或者常量，則e的后綴是e本身如果e是形如e1 op e2的表達(dá)式，其中op是一個(gè)二元操作符，則e的后綴表示是e1e2op，這里e1和e2分別是e1和e2的后綴表示如果e是形如（e1）的表達(dá)式，則e的后綴表示就是e1的后綴表示v實(shí)例表達(dá)式(9-5)+2的后綴表示是95-2+表達(dá)式9-(5+2)的后綴表示是952+-20/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v程序設(shè)計(jì)語言結(jié)構(gòu)的翻譯生成代碼保存

9、相關(guān)的任意信息：屬性v結(jié)構(gòu)類型v目標(biāo)代碼中第一指令的位置v生成的指令個(gè)數(shù)v屬性：對(duì)應(yīng)于分析樹的某個(gè)節(jié)點(diǎn)綜合屬性（本章）v由其子節(jié)點(diǎn)的屬性值確定v一刻分析樹的所有綜合屬性值的計(jì)算只需要分析樹的一次自底向上遍歷繼承屬性（第五章）21/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v兩種翻譯技術(shù)語法制導(dǎo)定義v一種形式化方法：各種結(jié)構(gòu)的翻譯v根據(jù)與其語義部分相關(guān)聯(lián)的屬性說明一個(gè)結(jié)構(gòu)的翻譯翻譯模式v一種過程化方法22/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v語法制導(dǎo)定義例2.6：使用語法制導(dǎo)定義實(shí)現(xiàn)中綴=后綴v中綴=后綴的語法制導(dǎo)定義 圖2-5v分析樹各節(jié)點(diǎn)的屬性值 圖2-6上下文無關(guān)文法規(guī)則+語義規(guī)則

10、v每個(gè)文法符號(hào)和一個(gè)屬性集合相關(guān)聯(lián)：文法符號(hào)expr與屬性t相關(guān)聯(lián)（t是文法符號(hào)expr 產(chǎn)生的表達(dá)式的后綴表示）v每一個(gè)產(chǎn)生式和一個(gè)語義規(guī)則集合相關(guān)聯(lián)：產(chǎn)生式expr - expr1 + term 與語義規(guī)則expr.t := expr1.t | term.t | +相關(guān)聯(lián)v語義規(guī)則用來計(jì)算與產(chǎn)生式中出現(xiàn)的文法符號(hào)相關(guān)聯(lián)的屬性的值：如：語義規(guī)則expr.t := expr1.t | term.t | +通過連接expr1.t 、term.t 和 +產(chǎn)生expr.t 的值23/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v語法制導(dǎo)定義例2.7：使用語法制導(dǎo)定義機(jī)器人位置計(jì)算v機(jī)器人位置的跟蹤 圖

11、2-7v機(jī)器人位置的語法制導(dǎo)定義 圖2-9vbegin west south的注釋分析樹 圖2-824/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v語法制導(dǎo)定義分析樹中綜合屬性的計(jì)算順序自底向上遍歷：深度優(yōu)先遍歷v盡可能訪問一個(gè)節(jié)點(diǎn)未訪問的子節(jié)點(diǎn)v例圖2-1125/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v翻譯模式一個(gè)上下文無關(guān)文法v語義動(dòng)作嵌入產(chǎn)生式右部前綴變中綴產(chǎn)生式rest - + term print (+) rest126/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v翻譯模式對(duì)比：語法指導(dǎo)定義v語義動(dòng)作和產(chǎn)生式分開，語義規(guī)則的計(jì)算順序顯式給出v簡(jiǎn)單語法指導(dǎo)定義：可以用（簡(jiǎn)單）翻譯模

12、式實(shí)現(xiàn)每個(gè)產(chǎn)生式左部的非終結(jié)符的翻譯是將產(chǎn)生式右部的非終結(jié)符的翻譯按照他們?cè)谟也砍霈F(xiàn)的順序連接起來得到的在連接過程中可能還需要附加（也可能不需要）一些額外的串。v產(chǎn)生式：expr-expr1+termv語義規(guī)則：expr.t := expr1.t | term.t | +27/35第二章：簡(jiǎn)單的一遍編譯器：語法制導(dǎo)翻譯v翻譯模式例2.8：使用翻譯模式實(shí)現(xiàn)中綴=后綴v圖2-13 ：中綴變后綴的翻譯模式v圖2-14：9-5+2 =95-2+的語義動(dòng)作（即9-5+2對(duì)應(yīng)的句法樹）v在簡(jiǎn)單翻譯模式中，語義動(dòng)作也是按照從左到右的順序執(zhí)行的，可以在語法分析的時(shí)候執(zhí)行語義動(dòng)作，完全沒有必要構(gòu)造分析樹。28/

13、35第二章：簡(jiǎn)單的一遍編譯器v概述v語法制導(dǎo)翻譯技術(shù)語法定義語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式語法分析語法分析29/35第二章：簡(jiǎn)單的一遍編譯器：語法分析v功能：記號(hào)串=分析樹決定一個(gè)記號(hào)串是否合乎一個(gè)給定文法=能否由給定文法產(chǎn)生=能否產(chǎn)生一個(gè)合乎給定文法的分析樹v語法分析方法分類自頂向下語法分析自頂向下語法分析v從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的順序構(gòu)造分析樹v常用于手工構(gòu)建語法分析器自底向上語法分析v可以處理大量文法和翻譯模式v常用于直接從文法生成語法分析器的軟件工具30/35第二章：簡(jiǎn)單的一遍編譯器：語法分析v自頂向下語法分析如何自頂向下構(gòu)造一個(gè)分析樹？從標(biāo)有開始非終結(jié)符的根節(jié)點(diǎn)開始，反復(fù)執(zhí)行下面兩步

14、v從標(biāo)有非終結(jié)符a的節(jié)點(diǎn)n，選擇a的一個(gè)產(chǎn)生式，用該產(chǎn)生式右部的符號(hào)構(gòu)造節(jié)點(diǎn)n的子節(jié)點(diǎn)v尋找下一個(gè)要構(gòu)造子樹的節(jié)點(diǎn)圖2-15：使用自頂向下方法構(gòu)造分析樹圖2-16：從左到右掃描輸入串時(shí)的自頂向下語法分析問題：回溯（產(chǎn)生式選擇不合適）31/35第二章：簡(jiǎn)單的一遍編譯器：語法分析v預(yù)測(cè)分析法遞歸下降分析法：自頂向下v執(zhí)行一組遞歸過程來處理輸入串，每一個(gè)過程都唯一地與文法的一個(gè)過程相關(guān)聯(lián)預(yù)測(cè)分析法：一種特殊的遞歸下降分析法v超前掃描符號(hào)無二義v依賴于產(chǎn)生式右部產(chǎn)生的第一個(gè)符號(hào)是什么v若a-a, a-b, 則first(a) 和first(b)不相交圖2-17：預(yù)測(cè)語法分析器的偽代碼32/35第二章：

15、簡(jiǎn)單的一遍編譯器：語法分析v預(yù)測(cè)語法分析器由多個(gè)過程組成，每個(gè)過程對(duì)應(yīng)一個(gè)非終結(jié)符v檢查超前掃描符號(hào)，決定使用哪個(gè)產(chǎn)生式：產(chǎn)生式右部不存在沖突v過程通過模仿其右部來使用一個(gè)產(chǎn)生式非終結(jié)符：對(duì)應(yīng)過程被調(diào)用記號(hào)：若與超前掃描符號(hào)匹配，讀入下一個(gè)輸入記號(hào)，否則報(bào)告出錯(cuò)33/35第二章：簡(jiǎn)單的一遍編譯器：語法分析v語法分析器+語義動(dòng)作=語法指導(dǎo)翻譯器文法+語義動(dòng)作(分開)=語法制導(dǎo)定義文法+語義動(dòng)作(合并)=翻譯模式v擴(kuò)展預(yù)測(cè)語法分析器構(gòu)建語法制導(dǎo)翻譯器：類似于擴(kuò)展文法形成翻譯模式構(gòu)造一個(gè)預(yù)測(cè)語法分析器，忽略產(chǎn)生式中的語義動(dòng)作。把翻譯模式中的語義動(dòng)作拷貝到語法分析器，插入相應(yīng)位置。34/35第二章：簡(jiǎn)單的一遍編譯器：語法分析v左遞歸問題遞歸下降語