861第二章簡單的一遍編譯器

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

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

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

4、果a是某個內(nèi)節(jié)點的，x1、x2xn是該節(jié)點的從左到右的所有子節(jié)點的標記（終結(jié)符或非終結(jié)符），則a -x1x2xn是一個產(chǎn)生式。9/35第二章：簡單的一遍編譯器：語法定義v分析樹：實例例2.4： 9+5-2 =分析樹（圖2-2）分析樹生成的結(jié)果v一顆分析樹從左到右的葉節(jié)點v由樹根節(jié)點的開始非終結(jié)符生成或?qū)С龅拇?0/35第二章：簡單的一遍編譯器：語法定義v幾個概念語言（文法）：文法的分析樹導出的串的集合語法分析：記號串=句法樹（語法樹）v同自然語言的句法分析：i love this game .11/35第二章：簡單的一遍編譯器：語法定義v文法的二義性一個記號串對應幾個不同的句法樹例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第二章：簡單的一遍編譯器：語法定義v上下文無關(guān)文法的應用定義語言的語法v表達式的語法v語句的語法指導源程序的翻譯v語法制導翻譯技術(shù)13/35第二章：簡單的一遍編譯器：語法定義v表達式的語法：操作符

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

7、單的一遍編譯器：語法定義v表達式的語法：操作符的結(jié)合性和優(yōu)先級操作符的優(yōu)先級v例：9+5*2 =（9+5）*2 | 9+（5*2）？v括號、乘除、加減16/35第二章：簡單的一遍編譯器：語法定義v表達式的語法：如何運用操作符兩原則先優(yōu)先級高的后優(yōu)先級低的左結(jié)合vs右結(jié)合例：左結(jié)合（page 21）例：右結(jié)合（課堂練習）17/35第二章：簡單的一遍編譯器：語法定義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第二章：簡單的一遍編譯器v概述v語法制導翻譯技術(shù)語法定義語法制導翻譯：語法制導定義/翻譯模式語法分析19/35第二章：簡單的一遍編譯器：語法制導翻譯v表達式e的后綴表示如果e是一個變量或者常量，則e的后綴是e本身如果e是形如e1 op e2的表達式，其中op是一個二元操作符，則e的后綴表示是e1e2op，這里e1和e2分別是e1和e2的后綴表示如果e是形如（e1）的表達式，則e的后綴表示就是e1的后綴表示v實例表達式(9-5)+2的后綴表示是95-2+表達式9-(5+2)的后綴表示是952+-20/35第二章：簡單的一遍編譯器：語法制導翻譯v程序設(shè)計語言結(jié)構(gòu)的翻譯生成代碼保存

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

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

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

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

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

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

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