教學(xué)課件第二章簡單的一遍編譯器

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

2、-4/35v概述v語法制導(dǎo)翻譯技術(shù) 語法定義語法定義 語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式 語法分析5/35v上下文無關(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/35v上下文無關(guān)文法：實例 例2.1：由數(shù)字、加號和減號組成的表達式vlist - list + digit | list digit | digitvdigit - 0 | 1 | 2 | 3 | 4 | 5 |

3、6 | 7 | 8 | 97/35v上下文無關(guān)文法：實例 例2.3：pascal的begin-end語句塊vblock - begin opt_stmts endvopt_stmts - stmt_list | vstmt_list - stmt_list ; stmt | stmt8/35v分析樹：定義 樹根節(jié)點為開始非終結(jié)符 每個葉節(jié)點由一個終結(jié)符（記號）或標記 每個內(nèi)節(jié)點由一個非終結(jié)符標記 如果a是某個內(nèi)節(jié)點的，x1、x2xn是該節(jié)點的從左到右的所有子節(jié)點的標記（終結(jié)符或非終結(jié)符），則a -x1x2xn是一個產(chǎn)生式。9/35v分析樹：實例 例2.4： 9+5-2 =分析樹（圖2-2） 分

4、析樹生成的結(jié)果v一顆分析樹從左到右的葉節(jié)點v由樹根節(jié)點的開始非終結(jié)符生成或?qū)С龅拇?0/35v幾個概念 語言（文法）：文法的分析樹導(dǎo)出的串的集合 語法分析：記號串=句法樹（語法樹）v同自然語言的句法分析：i love this game .11/35v文法的二義性 一個記號串對應(yīng)幾個不同的句法樹 例2.5：9-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

5、telescope .va dog with a telescopevsaw with a telescope12/35v上下文無關(guān)文法的應(yīng)用 定義語言的語法v表達式的語法v語句的語法 指導(dǎo)源程序的翻譯v語法制導(dǎo)翻譯技術(shù)13/35v表達式的語法：操作符的結(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/35v表達式的語法:操作符的結(jié)合性和優(yōu)先級 操作符的結(jié)合規(guī)則（續(xù)）v右結(jié)合： ：操作數(shù)與右操作符結(jié)合 指數(shù)運算符

6、：423 = 4(23) 運算操作符：a=b=c = a=(b=c) right - letter = right | letter right | letter letter - a | b | zv例：圖2-415/35v表達式的語法：操作符的結(jié)合性和優(yōu)先級 操作符的優(yōu)先級v例：9+5*2 =（9+5）*2 | 9+（5*2）？v括號、乘除、加減16/35v表達式的語法：如何運用操作符兩原則 先優(yōu)先級高的后優(yōu)先級低的 左結(jié)合vs右結(jié)合 例：左結(jié)合（page 21） 例：右結(jié)合（課堂練習(xí)）17/35v語句的語法：例page 22 stmt - id := expr| if expr then

7、 stmt| if expr then stmt else stmt| while expr do stmt| begin opt_stmts end18/35v概述v語法制導(dǎo)翻譯技術(shù) 語法定義 語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式 語法分析19/35v表達式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)的后綴表示

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

9、每個文法符號和一個屬性集合相關(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/35v語法制導(dǎo)定義 例2.7：使用語法制導(dǎo)定義機器人位置計算v機器人位置的跟蹤 圖2-7v機器人位置的語法制導(dǎo)定義 圖2

10、-9vbegin west south的注釋分析樹 圖2-824/35v語法制導(dǎo)定義 分析樹中綜合屬性的計算順序 自底向上遍歷：深度優(yōu)先遍歷v盡可能訪問一個節(jié)點未訪問的子節(jié)點v例圖2-1125/35v翻譯模式 一個上下文無關(guān)文法v語義動作嵌入產(chǎn)生式右部 前綴變中綴產(chǎn)生式rest - + term print (+) rest126/35v翻譯模式 對比：語法指導(dǎo)定義v語義動作和產(chǎn)生式分開，語義規(guī)則的計算順序顯式給出v簡單語法指導(dǎo)定義：可以用（簡單）翻譯模式實現(xiàn) 每個產(chǎn)生式左部的非終結(jié)符的翻譯是將產(chǎn)生式右部的非終結(jié)符的翻譯按照他們在右部出現(xiàn)的順序連接起來得到的 在連接過程中可能還需要附加（也可能

11、不需要）一些額外的串。v產(chǎn)生式：expr-expr1+termv語義規(guī)則：expr.t := expr1.t | term.t | +27/35v翻譯模式 例2.8：使用翻譯模式實現(xiàn)中綴=后綴v圖2-13 ：中綴變后綴的翻譯模式v圖2-14：9-5+2 =95-2+的語義動作（即9-5+2對應(yīng)的句法樹）v在簡單翻譯模式中，語義動作也是按照從左到右的順序執(zhí)行的，可以在語法分析的時候執(zhí)行語義動作，完全沒有必要構(gòu)造分析樹。28/35v概述v語法制導(dǎo)翻譯技術(shù) 語法定義 語法制導(dǎo)翻譯：語法制導(dǎo)定義/翻譯模式 語法分析語法分析29/35v功能：記號串=分析樹 決定一個記號串是否合乎一個給定文法=能否由給定

12、文法產(chǎn)生=能否產(chǎn)生一個合乎給定文法的分析樹v語法分析方法分類 自頂向下語法分析自頂向下語法分析v從根節(jié)點到葉節(jié)點的順序構(gòu)造分析樹v常用于手工構(gòu)建語法分析器 自底向上語法分析v可以處理大量文法和翻譯模式v常用于直接從文法生成語法分析器的軟件工具30/35v自頂向下語法分析 如何自頂向下構(gòu)造一個分析樹？從標有開始非終結(jié)符的根節(jié)點開始，反復(fù)執(zhí)行下面兩步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/35v預(yù)

13、測分析法 遞歸下降分析法：自頂向下v執(zhí)行一組遞歸過程來處理輸入串，每一個過程都唯一地與文法的一個過程相關(guān)聯(lián) 預(yù)測分析法：一種特殊的遞歸下降分析法v超前掃描符號無二義v依賴于產(chǎn)生式右部產(chǎn)生的第一個符號是什么v若a-a, a-b, 則first(a) 和first(b)不相交 圖2-17：預(yù)測語法分析器的偽代碼32/35v預(yù)測語法分析器 由多個過程組成，每個過程對應(yīng)一個非終結(jié)符v檢查超前掃描符號，決定使用哪個產(chǎn)生式：產(chǎn)生式右部不存在沖突v過程通過模仿其右部來使用一個產(chǎn)生式 非終結(jié)符：對應(yīng)過程被調(diào)用 記號：若與超前掃描符號匹配，讀入下一個輸入記號，否則報告出錯33/35v語法分析器+語義動作=語法指導(dǎo)翻譯器 文法+語義動作(分開)=語法制導(dǎo)定義 文法+語義動作(合并)=翻譯模式v擴展預(yù)測語法分析器構(gòu)建語法制導(dǎo)翻譯器：類似于擴展文法形成翻譯模式 構(gòu)造一個預(yù)測語法分析器，忽略產(chǎn)生式中的語義動作。 把翻譯模式中的語義動作拷貝到語法分析器，插入相應(yīng)位置。34/35v左遞歸問題 遞歸下降語法分析器（如預(yù)測語