編譯原理課件（完整）

1、1編譯原理一 什么是編譯程序？2 計(jì)算機(jī)經(jīng)過幾十年的開展， 在程序設(shè)計(jì)語言方面,已經(jīng)從低級語言開展到高級語言;然而,計(jì)算機(jī)內(nèi)部的本質(zhì)只能識別 0 , 1 代碼序列機(jī)器語言,而對高級語言甚至符號語言仍然一竅不通。 因此用高級語言編寫的程序,必須先翻譯為機(jī)器語言，才能被計(jì)算機(jī)理解執(zhí)行。第一個(gè)完成這種翻譯任務(wù)的編譯程序?yàn)镕ORTRAN編譯程序,是上世紀(jì)五十年代設(shè)計(jì)的. 第一章 引論第一節(jié)、編譯程序概述3定義:設(shè)源語言為L1,目標(biāo)語言為L2, 翻譯程序是一個(gè)程序,它能將L1轉(zhuǎn)換為邏輯上等價(jià)的L2。 假設(shè) L1 為高級語言，L2 為低級語言或機(jī)器語言，稱這種 翻譯程序?yàn)榫幾g程序。 假設(shè) L1 為低級語言

2、，L2 為機(jī)器語言，稱這種翻譯程序?yàn)?匯編程序。 解釋程序是指逐條翻譯 L1的語句，并立即執(zhí)行翻譯出的 目標(biāo)代碼序列。 編譯原理 就是介紹編譯程序的一般規(guī)律及設(shè)計(jì)方法的一門課程。高級語言程序機(jī)器語言程序翻譯為4二 編譯過程概述 編譯程序從接受源程序到輸出目標(biāo)代碼的整個(gè)過程，可邏輯的分為 5 個(gè)階段，詞 法 分 析語 法 分 析 中間代碼生成 代 碼 優(yōu) 化 目標(biāo)代碼生成 1 詞法分析：把源程序作為字符串進(jìn)行掃描 ，根據(jù)單詞詞法，識別出所有單詞，過濾無用符，并檢查是否為合法的單詞。 單詞一般分為如下幾種： 根本字，標(biāo)識符，常數(shù)，算符，界符 5例如： if n=1 then f:=1 else f

3、:=n*f(n); 該程序經(jīng)過語法分析,得到如下單詞序列:ifn=1thenf:=1 elsef:=n*f(n);過濾掉回車換行,空格,注釋等62) 語法分析: 根據(jù)語言的語法規(guī)那么,從單詞符號串中識別出各種語法單位 ,進(jìn)行句子分析,并檢查整個(gè)輸入字串是否為合法的程序; 重要的語法單位有: 程序,子程序,語句,短語,表達(dá)式等例如: program add;var a,b:real;begin read(a,b);write (a+b);end.7程序首部說明段執(zhí)行部program程序名及參數(shù)var說明語句add變量名表變量類型a,brealbegin多語句endread(a,b)write(a

4、+b)83) 中間代碼生成:根據(jù)語義規(guī)那么,把各種語法單位翻譯成中間代碼序列. 中間代碼有三種: 四元式,三元式,逆波蘭式. 中間代碼的特點(diǎn):結(jié)構(gòu)簡單,語義明確,易于理解及優(yōu)化. 四元式可表示為: (操作符,操作數(shù)1,操作數(shù)2,結(jié)果)例如: 語句 Z:=(x+0.4)*Y/W; 翻譯后得到右面 的四元式序列: 四元式序列(+ , x, 0.4, T1)(* , T1, Y, T2)(/ , T2, w, T3)(:= , T3, , Z)從例如可看出:每條四元式只進(jìn)行一次最根本的操作.94) 代碼優(yōu)化：對產(chǎn)生的中間代碼序列進(jìn)行加工變換，使變換后的代碼更為高效 時(shí)間，空間上。 優(yōu)化主要有： 循環(huán)

5、優(yōu)化，公共表達(dá)式提取，強(qiáng)度削弱等。5) 目標(biāo)代碼生成：把中間代碼程序翻譯為機(jī)器指令或匯編指令程序。 這一局部的處理，與計(jì)算機(jī)硬件及操作系統(tǒng)密切相關(guān)。 如存放器數(shù)目，機(jī)器指令功能及指令條數(shù)；操作系統(tǒng)的 BIOS，內(nèi)存管理，文件管理等。三 編譯程序的結(jié)構(gòu) 編譯程序可以劃分為如下幾個(gè)根本模塊：10詞法分析器語法分析器中間代碼生成中間代碼優(yōu)化目標(biāo)代碼生成源程序單詞符號語法單位四元式四元式目標(biāo)程序 表格管理 錯(cuò)誤處理編譯程序總框11表格管理:對各種表格進(jìn)行管理,包括表格的構(gòu)造、查找、修改、 刪除、插入 等； 編譯程序中，表格的種類較多，最主要的有如下幾種： 符號表，常量表，標(biāo)號表，子程序名表，四元式表等

6、。 表格由假設(shè)干結(jié)構(gòu)相同的表格項(xiàng)組成，表格項(xiàng)由二元式表示：項(xiàng)名 信息表格項(xiàng)表格項(xiàng)名 1 信息項(xiàng)名 2 信息項(xiàng)名 n 信息12四 設(shè)計(jì)編譯程序 編譯程序的設(shè)計(jì)方式可以分為兩類：方式人工設(shè)計(jì)自動(dòng)生成低級語言高級語言自動(dòng)生成掃描器自動(dòng)生成分析器自動(dòng)生成編譯程序13第二節(jié)、高級語言概述一 什么是程序設(shè)計(jì)語言 程序設(shè)計(jì)語言是一符號系統(tǒng)，由語法和語義兩方面所定義。語法：是一組規(guī)那么，規(guī)定了語言的形式結(jié)構(gòu)，包括單詞結(jié)構(gòu)， 句子結(jié)構(gòu)，程序結(jié)構(gòu)等。 語法=詞法規(guī)那么+句法規(guī)那么 詞法規(guī)那么：規(guī)定了形成單詞的規(guī)那么；如常數(shù)，標(biāo)識符， 根本字，算符等。 句法規(guī)那么：規(guī)定了由單詞構(gòu)造更大語法單位的規(guī)那么； 如表達(dá)式，

7、短語，語句，程序等。14語義：也是一組規(guī)那么，規(guī)定了各語法單位確實(shí)切含義。 例如：A=B，可解釋為：A賦值為B；C語言 也可以解釋為 ：A等于B P語言 這完全由語義規(guī)那么所確定。二 數(shù)據(jù)類型 各種語言都提供了一些最根本的數(shù)據(jù)類型,稱為初等數(shù)據(jù)類型，這些數(shù)據(jù)類型的特征是數(shù)據(jù)的單一性；還提供了由初等數(shù)據(jù)類型構(gòu)造復(fù)雜結(jié)構(gòu)類型的手段。1初等數(shù)據(jù)類型數(shù)值類型：整數(shù)，實(shí)數(shù)可進(jìn)行算術(shù)運(yùn)算和比較運(yùn)算；邏輯類型：可進(jìn)行邏輯運(yùn)算；字符類型：可進(jìn)行比較遠(yuǎn)算及字符串操作；指針類型：指向另一變量的地址。152）結(jié)構(gòu)類型-數(shù)組 數(shù)組是由同一類型數(shù)據(jù)所組成的多維結(jié)構(gòu)，數(shù)組元素是多維空間的一個(gè)點(diǎn)，代表了一個(gè)存儲(chǔ)空間。數(shù)組的

8、存儲(chǔ)，是通過按行或按列方式，把每個(gè)數(shù)組元素存放在一個(gè)連續(xù)的存儲(chǔ)空間中。設(shè)數(shù)組類型為 A:arrayL1 .u1,L2 . u2,.Ln . un of elemtype, 數(shù)組元素為 Ai1,i2,.in, di=ui -Li+1則該元素的地址可按如下公式計(jì)算: addr= a + (i1 - L1)*d2d3d4.dn + (i2 - L2)* d3d4.dn + (in-1 - Ln-1)* dn + (in - Ln ) *elemlength16addr=a -c +v c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.dn + ( Ln-1)* dn + ( L

9、n ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlengthv = (.(i1d2+i2)d3+i3)d4+i4).) dn + in *elemlength C是常量,在編譯時(shí)可以計(jì)算出;V是可變部分,只能在程序運(yùn)行時(shí)才能計(jì)算出。 從上可知：計(jì)算數(shù)組元素地址涉及到如下幾個(gè)因素： a c L1.Ln d1.dn elemlength i1.in 17 這些因素中,在編譯時(shí)能確定的局部,用一個(gè)數(shù)組內(nèi)情向量表來記錄, 以便計(jì)算數(shù)組元素地址使用。換句話說：當(dāng)編譯程序掃描到數(shù)組說明語句時(shí)，就把數(shù)組的各確定局部登記到內(nèi)情向量表中。 內(nèi)情向

10、量表組織如下：L1 u1 d1 L2 u2 d2 Ln un dn a c n elemlength 183）結(jié)構(gòu)類型- 記錄 是由多種類型的數(shù)據(jù)組合起來的一種數(shù)據(jù)結(jié)構(gòu)。Pascal 語言中，可如下定義一種記錄類型type = record :; :; :; end; 域名即記錄分量,域的類型可以是簡單數(shù)據(jù)類型,也可以是已經(jīng)定義過的數(shù)據(jù)類型。 可采用分量順序方式,分配記錄的地址空間。由于每個(gè)域類型及空間大小都可能不同,因此,只能通過表映射方式計(jì)算各個(gè)域在記錄中的地址。19記錄分量表：域名 相對位移 域類型name1 offset1 type1name2 offset2 type2 namen

11、offsetn typen因此，name i 在記錄中的地址為：addr=a+offset ia 為記錄的第一個(gè)分量的地址；20三 表達(dá)式 表達(dá)式是由算符和運(yùn)算量組成,可遞規(guī)定義如下: 1 變量,常量,函數(shù)為表達(dá)式 E; 2 若 E1,E2為表達(dá)式,則: E1 op E2, op E, (E) 為表達(dá)式。 算符間存在如下優(yōu)先順序： 乘冪（*） 負(fù)號 （） 乘除（* /） 加減（+ -） 關(guān)系符（ = = 類型定義段 type = set of ; = array of ; = record end;222 變量說明段var :;:;:;3 函數(shù)及過程定義 function (參數(shù)說明):; ;

12、 procedure (參數(shù)說明) ; ;4 賦值句 := ; 左邊變量取其地址,右邊表達(dá)式取其值.235 分支語句 if then else ; case of :; : else : end; goto ;246 循環(huán)控制語句 while do ; for := to do ; repeat ;. until 7 子程序調(diào)用 函數(shù)調(diào)用一般出現(xiàn)在表達(dá)式中,形式如下: (實(shí)際參數(shù)) 過程調(diào)用一般作為語句,形式如下: (實(shí)際參數(shù));258 輸入輸出語句 read(); write();9 簡單句和復(fù)合句 簡單句是指不包含其它語句的根本語句, 復(fù)合句是指句中有句.例如: V:=E,goto L ,

13、read(a,b) 等都是簡單句; if B then S else S, while B do S 等都是復(fù)合句.26五 子程序參數(shù)傳遞 當(dāng)調(diào)用一個(gè)子程序時(shí),首先應(yīng)將所需的數(shù)據(jù)傳遞給子程序,傳遞方式主要有三種: 傳值,傳地址,傳名 設(shè)有如下函數(shù): function distence(x1,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) end; x1,y1,x2,y2 稱為形式參數(shù) 設(shè)主程序調(diào)用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 稱為實(shí)際參數(shù).271傳值 調(diào)用程序把實(shí)際參數(shù)的值傳遞

14、到形式參數(shù)的空間中.1145x1y1x2y21145a1b1a2b2主程序空間子程序空間這種方式,子程序一般不改變實(shí)際參數(shù)的值.282傳地址 調(diào)用程序把實(shí)際參數(shù)的地址傳遞到形式參數(shù)的空間中. addr(a1) addr(b1) addr(a2) addr(b2)x1y1x2y21145a1b1a2b2主程序空間子程序空間 這種方式,子程序間接訪問主程序?qū)嶋H參數(shù)的值,改變了實(shí)際參數(shù)的值.293傳名 傳名是一種宏替換,直接在調(diào)用處產(chǎn)生一個(gè)子程序副本,并且用實(shí)際參數(shù)名替代形式參數(shù)名. 設(shè)主程序調(diào)用如下: d:=distence(a1,b1,a2,b2);相當(dāng)于在此處產(chǎn)生一段程序: d:=sqrt(a

15、2-a1)*2+(b2-b1)*2);30六 存儲(chǔ)分配 程序運(yùn)行時(shí),必須分配相應(yīng)的存儲(chǔ)空間. 這些空間包括:變量空間,常量空間,臨時(shí)空間,連接單元 等.有的空間在編譯時(shí)就能確定其大小,而有的空間必須在程序運(yùn)行時(shí)才能確定.根據(jù)這一特性,把空間分配分為兩種: 靜態(tài)存儲(chǔ)分配 動(dòng)態(tài)存儲(chǔ)分配1 靜態(tài)存儲(chǔ)分配 假設(shè)在編譯時(shí)能完全確定程序所需空間大小,并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址,就可在編譯時(shí)分配所需空間,這種分配方法稱為靜態(tài)存儲(chǔ)分配. 假設(shè)一個(gè)語言無遞歸調(diào)用,無可變數(shù)據(jù)項(xiàng),那么可靜態(tài)地確定各數(shù)據(jù)項(xiàng)的空間大小和地址. Fortran語言滿足這種定義.312 動(dòng)態(tài)存儲(chǔ)分配 是指在程序運(yùn)行時(shí)才能確定存儲(chǔ)空間和地址的

16、一種分配方法.適用于允許遞歸和可變數(shù)據(jù)項(xiàng)的語言,如pascal 和 c 語言. 一般采用堆棧動(dòng)態(tài)地分配空間, 當(dāng)調(diào)用子程序時(shí),就在堆棧中為該子程序分配所需空間;而子程序運(yùn)行結(jié)束后,就釋放該子程序空間.子程序空間編譯時(shí)可確定(活動(dòng)記錄)運(yùn)行時(shí)可確定(可變空間)活動(dòng)記錄連接數(shù)據(jù)形式參數(shù)局部變量數(shù)組內(nèi)情向量表臨時(shí)變量等活動(dòng)記錄可變空間堆棧子程序 S 32第二章 詞法分析內(nèi)容提要:狀態(tài)轉(zhuǎn)換圖正規(guī)式與有限制動(dòng)機(jī)詞法分析器的自動(dòng)生成詞法分析器源程序單詞序列34第一節(jié) 狀態(tài)轉(zhuǎn)換圖一 單詞分類及表示 編譯中,把高級語言的單詞分為五類: 標(biāo)識符,根本字,常數(shù),運(yùn)算符,界符 根本字,運(yùn)算符,界符都是有限可枚舉的;

17、而標(biāo)識符,常數(shù)可認(rèn)為是無限的. 簡單起見,單詞可表示為如下二元組: (單詞分類號,單詞自身值); 或者為: (單詞種別碼,單詞自身值); 標(biāo)識符,常數(shù) 各為一個(gè)種別碼,而由于根本字,運(yùn)算符,界符的有限性,可以設(shè)計(jì)為一字一個(gè)種別碼.35例如:單詞 單詞種別碼分類號 標(biāo)識符1 1常數(shù) 2 2if 3 3then4 3end90 3,91 4;92 4=151 5+152 5保留字界符運(yùn)算符36二 詞法分析器的設(shè)計(jì)1 源程序的預(yù)處理子程序 源程序中,存在許多編輯用的符號,它們對程序邏輯功能無任何影響. 例如:回車,換行,多余空白符,注釋行等.在詞法分析之前,首先要剔除掉這些符號,使得詞法分析更為簡單

18、.源程序輸入緩沖區(qū)預(yù)處理子程序掃描緩沖區(qū)2掃描緩沖區(qū)1 緩沖區(qū)分為兩局部,每個(gè)長度為256字節(jié),這樣單詞的總長度可到達(dá)256字節(jié).預(yù)處理子程序把處理好的字符串輪流放入兩個(gè)緩沖區(qū)中,供詞法分析程序使用.372 詞法分析程序 詞法分析程序又稱為詞法分析器或掃描器.可以單獨(dú)為一個(gè)程序;也可以作為整個(gè)編譯程序的一個(gè)子程序,當(dāng)需要一個(gè)單詞時(shí),就調(diào)用詞法分析子程序返回一個(gè)單詞.這里,作為子程序介紹. 詞法分析器的結(jié)構(gòu):源程序輸入緩沖區(qū)預(yù)處理子程序掃描緩沖區(qū)2掃描緩沖區(qū)1詞法分析子程序調(diào)用返回一單詞數(shù)據(jù)383 詞法規(guī)那么的表示-狀態(tài)轉(zhuǎn)換圖定義:狀態(tài)轉(zhuǎn)換圖是一有向圖,由有限個(gè)結(jié)點(diǎn)及有向邊連接而成; 每個(gè)結(jié)點(diǎn)稱

19、為狀態(tài);狀態(tài)圖有一個(gè)初態(tài),多個(gè)終態(tài);每條邊上 有相應(yīng)的字符. 狀態(tài)轉(zhuǎn)換圖用于表示單詞結(jié)構(gòu),從狀態(tài)轉(zhuǎn)換圖的初態(tài)到終態(tài)間,每條路徑上字符的連接,就構(gòu)成了該狀態(tài)圖的合法單詞.例如: 012初態(tài)終態(tài)字母字母數(shù)字其它*1標(biāo)識符的狀態(tài)圖表示:星號表示單詞尾部多跟一個(gè)字符,應(yīng)該去掉.39012初態(tài)終態(tài)數(shù)字?jǐn)?shù)字其它*2整數(shù)的狀態(tài)圖表示:016初態(tài)終態(tài)數(shù)字?jǐn)?shù)字其它*3實(shí)數(shù)的狀態(tài)圖表示:23456數(shù)字?jǐn)?shù)字 數(shù)字E+或 數(shù)字E其它數(shù)字404 單詞的識別 狀態(tài)圖即可以表示單詞規(guī)那么,同時(shí)也可以用于識別單詞. 設(shè)有一字符串S = s1s2.sn, 假設(shè)狀態(tài)圖中存在一初態(tài)到終態(tài)的路徑,且路徑上字符的連接為: s1s2.s

20、n, 稱 S 可被狀態(tài)圖識別.例如: S=var1012初態(tài)終態(tài)var1其它* 保存字由于滿足標(biāo)識符定義,因此可以跟標(biāo)識符用同樣的狀態(tài)圖表示與識別,只需增加一個(gè)保存字表,當(dāng)識別出一個(gè)標(biāo)識符時(shí),通過查保存字表來區(qū)別保存字及普通標(biāo)識符.因此 var1 是一個(gè)合法的標(biāo)識符.415 一個(gè)簡單例如 構(gòu)造一個(gè)簡單語言所有單詞的狀態(tài)轉(zhuǎn)換圖.該語言的單詞種類如下表所示:單詞符號 種別碼 助記符 內(nèi)碼值 DIMIFDOSTOPEND標(biāo)識符正常數(shù)=+*,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR

21、$RPAR( 1 , )( 2 , )( 3 , )( 4 , )( 5 , )( 6 , 串值)( 7 , 數(shù)值)( 8 , )( 9 , )( 10, )( 11, )( 12, )( 13, )( 14, )420 1 2初態(tài)終態(tài)字母字母數(shù)字其它*空白 3 4 終態(tài)數(shù)字?jǐn)?shù)字非數(shù)字* 5 = 6 + 7* 9 8*非 * *10,11(12)13其它436 狀態(tài)轉(zhuǎn)換圖的程序?qū)崿F(xiàn) 為便于程序?qū)崿F(xiàn),假設(shè)每個(gè)單詞間都有界符或運(yùn)算符或空格隔開,并引入下面的全局變量及子程序:1) CHAR 字符變量2) TOKEN 單詞字符串3) GETCHAR 讀一個(gè)字符到 CHAR 中4) GETBC 讀一個(gè)非

22、空白字符到CHAR 中5) CONCAT 把CHAR 中字符連接到TOKEN 之后6) LETTER 判斷CHAR 中字符是否為字母7) DIGIT 判斷CHAR 中字符是否為數(shù)字8) RESERVE 用TOKEN中的字符串查找保存字表,并返回保存 字種別碼,假設(shè)返回零,那么非保存字9) RETRACT 把CHAR 中字符回送到緩沖區(qū)44 下面分析狀態(tài)圖的結(jié)構(gòu)特點(diǎn).每個(gè)狀態(tài)圖都由三種結(jié)構(gòu)構(gòu)成: 分支結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 終結(jié)點(diǎn)1分支結(jié)構(gòu)程序設(shè)計(jì) i i2i1 inc1c2cnstate i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT

23、；state i2: . cn :CONCAT；state in: . ELSE ERROR END;452循環(huán)結(jié)構(gòu)程序設(shè)計(jì) i j C其它state i:GETCHAR; WHILE CHAR=C DO CONCAT;GETCHAR; RETRACT；state j: . 3終結(jié)點(diǎn)程序設(shè)計(jì) 一般對應(yīng)一條返回語句: return( c,val); c 為種別碼, val 為單詞值. 帶 * 號的終結(jié)點(diǎn),必須用RETRACT 退還多余字符 下面程序?yàn)楹唵卫缯Z言的實(shí)現(xiàn):46TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END；FUNCTION RETURN_

24、WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) 47 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE4: RETUR

25、N($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9: IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN($STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); ELSE STATE13: ERROR 這節(jié)介紹詞法規(guī)那么的形式表示(正規(guī)式)

26、,從正規(guī)式向有限自動(dòng)機(jī)的轉(zhuǎn)化.正規(guī)式有限自動(dòng)機(jī)詞法分析器控制程序自動(dòng)生成器轉(zhuǎn)化合成第二節(jié) 正規(guī)式與有限自動(dòng)機(jī)49一 根本概念 定義 1 字與字集 假設(shè): 是一有窮字符集,它的每個(gè)元素稱為一個(gè)字符; 字- 上的一個(gè)字,是由 中的字符所構(gòu)成的一個(gè)有窮序列;空串-不包含任何元素的序列稱為空串,記為;閉包*- 上所有可能的字的全體; 空字集-不含任何字的集合稱為空字集;記為 = ; 例如: =a,b 那么 *=,a,b,aa,ab,ba,bb. 注意: , , 三者間的關(guān)系定義 2 連接運(yùn)算 設(shè) U,V * 那么 UV= | U, V 一般 UVVU Vn =VV.V 稱為 V 的 n 次積50例如:

27、 設(shè) U=a,aa, V=b 那么UV=ab,aab VU=ba,baa定義 3 V的閉包 設(shè) V 為字集,且 V0= 令 V*=V0V1 V2 . V+= V* - 稱V* 為V的閉包 稱V+ 為V的正那么閉包 注意: * 與 V* 的區(qū)別.51 二 正規(guī)式與正規(guī)集 *是一個(gè)無窮集,在程序語言中,我們只研究滿足詞法規(guī)那么(正規(guī)式)的單詞集(正規(guī)集).定義 1 正規(guī)式與正規(guī)集的遞歸定義 : 1) , 是 上的正規(guī)式, 所表示的正規(guī)集為 , ; 2) 假設(shè) a ,那么 a 為正規(guī)式, 所表示的正規(guī)集為 a; 3) 設(shè)U,V 為 上的正規(guī)式, 所表示的正規(guī)集為 L(U),L(V); 那么 U|V為

28、 上的正規(guī)式, 所表示的正規(guī)集為 L(U) L(V); UV為 上的正規(guī)式, 所表示的正規(guī)集為 L(U) L(V); V* 為 上的正規(guī)式, 所表示的正規(guī)集為 L(V)* ; 4) 僅當(dāng)有限次使用上述三步驟而定義的表達(dá)式,才是 上的正規(guī)式 , 而這些正規(guī)式所表示的字集才是上的正規(guī)集.52例如: 令=A.Z,0.9 那么整數(shù)的正規(guī)式為: (0|1|2.|9)(0|1|2.|9) * 所表示的正規(guī)集為所有整數(shù); 標(biāo)識符的正規(guī)式為:(A|B|.Z)(A|B|.Z| 0|1|.|9) * 所表示的正規(guī)集為所有標(biāo)識符定義 2 假設(shè)兩個(gè)正規(guī)式 U,V 所表示的正規(guī)集相同,即 L(V)=L(U), 那么稱兩

29、個(gè)正規(guī)式等價(jià),記為 U=V.正規(guī)式的運(yùn)算: 設(shè) U V W 為正規(guī)式, 那么滿足以下關(guān)系: 1) U|V=V|U 2) U|(V|W)=(U|V)|W 3) U(VW)=(UV)W 4) U(V|W)=UV|UW (U|V)W=UW|VW 5) U=U =U53三 確定有限自動(dòng)機(jī) 一個(gè)確定有限自動(dòng)機(jī)(DFA M)是一個(gè)五元式: DFA M=(S, , f,s0,Z) 其中 S 是一有限集,每個(gè)元素稱為一個(gè)狀態(tài); 是一個(gè)有窮字母表,每個(gè)元素為一字符; f 是一個(gè)單值映射函數(shù),f(si,a)=sj ( si , sj S, a ); 其含義為:在狀態(tài) si ,輸入字符 a 時(shí),將轉(zhuǎn)換到下一狀態(tài)sj

30、. 稱sj為 si的后繼狀態(tài). s0 S, 是唯一的初態(tài); Z S ,是終態(tài)集. 一個(gè)DFAM可用狀態(tài)轉(zhuǎn)換矩陣或狀態(tài)圖表示54例如: DFAM=( 0,1,2,3, a,b, f, 0, 3) 其中f為: f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3狀態(tài)轉(zhuǎn)換矩陣可表示為: 狀態(tài)圖可表示為:ab012132213333狀態(tài)字 符013初態(tài)終態(tài)2abbaaabb55四 非確定有限自動(dòng)機(jī) 一個(gè)非確定有限自動(dòng)機(jī)(NFA M)是一個(gè)五元式: NFA M=(S, , f,S0,Z) 其中 S 是一有限集,每個(gè)

31、元素稱為一個(gè)狀態(tài); 是一個(gè)由窮字母表,每個(gè)元素為一字符; f 是一個(gè)多值映射函數(shù),f(si,)=s i1 , s i2 ,. s ik ( si , si1 ,. , s ik S, *); 其含義為:在狀態(tài) si ,輸入字串 時(shí),將轉(zhuǎn)換到下一狀態(tài)集: s i1 , s i2 ,. s ik S0 S, 是初態(tài)集; Z S ,是終態(tài)集. 一個(gè)NFAM也可用狀態(tài)圖表示,此時(shí)每條邊用字串表示.56例如:01初態(tài)終態(tài)2aabba,ba,ba,b終態(tài)DFAM 是 NFAM 的特例.定義: 狀態(tài)圖中,從初態(tài)到終態(tài)任一路徑上的字串連接,稱為該狀態(tài)圖可識別的單詞,可識別單詞的全體記為:L(M). 假設(shè)L(M

32、)= L(M),稱M 與M等價(jià). 57五 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性 前面,介紹了正規(guī)式,DFAM,NFAM, 下面討論這三個(gè)概念間的關(guān)系.定理1 : 對任意正規(guī)式V,存在一個(gè)NFAM ,使得L(V)=L(NFAM);證明: (1)構(gòu)造一個(gè)拓廣轉(zhuǎn)換圖 顯然,該轉(zhuǎn)換圖能識別的 單詞集為:L(V)XYV58(2) 進(jìn)行如下等價(jià)變換,直到轉(zhuǎn)換圖的每條邊上的標(biāo)志為上的 字符. ijV1V2ijV1kV2aijV1 | V2iV1jV2bijV*ijkcV 等價(jià)變換后的轉(zhuǎn)換圖M 符合 NFAM的定義,顯然有 L(V)=L(M).該定理說明,從正規(guī)式可逐步構(gòu)造一個(gè)NFAM.59定義:設(shè) S 是一個(gè)狀態(tài)集,

33、 _CLOSURE(S)定義如下: a) 假設(shè) s S,那么 s _CLOSURE(S); b) 假設(shè) s S,那么 從 s 出發(fā)經(jīng)過任意條 邊所能到達(dá)的狀態(tài) s 都屬于 _CLOSURE(S). 狀態(tài)集_CLOSURE(S)稱為 S 的_ 閉包.定理2: 對任意NFAM,存在一個(gè)DFAM ,使得L(DFAM)=L(NFAM);證明: (1) 對 NFAM 進(jìn)行等價(jià)變換,使得變換后的轉(zhuǎn)換圖NFAM中 僅含邊和 上的字符邊; (2) 用狀態(tài)轉(zhuǎn)換矩陣M 表示NFAM;60其中, I0 為初態(tài)集的_ 閉包.Ii a = _ CLOSURE f(si 1 , a) f(si 2 , a) f(sik

34、, a) si 1 , si 2 ,. sik Ii (3) 將M 中的狀態(tài)集換名, si = Ii 得到一新的狀態(tài)轉(zhuǎn)換矩陣 M , M 滿足 DFAM 的定義.Iabc.I0I1Ii Ii a Ii b Ii cInM61證畢.推論: 對任意正規(guī)式V,存在一個(gè)DFAM ,使得L(DFAM)= L(V).Sabc.s0s1si si a si b si csnM62例如: 設(shè)正規(guī)式為 ( a|b) *(aa|bb)(a|b) *,求與之等價(jià)的DFAM. (1) 由定理 1 的證明方法,可如下構(gòu)造NFAMXY( a|b) *(aa|bb)(a|b) *等價(jià)變換得到:513264aaaabbbbN

35、FAMXY(2) 用狀態(tài)轉(zhuǎn)換矩陣M 表示NFAM;63Iabx,5,1 5,1,3 5,1,45,1,3 5,1,3,2,6,y 5,1,45,1,4 5,1,3 5,1,4,2,6,y5,1,3,2,6,y 5,1,3,2,6,y 5,1,4,6,y5,1,4,2,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,4,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,3,6,y 5,1,3,2,6,y 5,1,4,6,yM(3) 將M 中的狀態(tài)集換名, si = Ii 得到一新的狀態(tài)轉(zhuǎn)換矩陣 M注意: M 與 M等價(jià).64Sabs0 s1 s2s1 s3 s2s2 s1 s4

36、 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM滿足確定有限自動(dòng)機(jī)的定義,狀態(tài)圖表示如下: s0s1s3s5s6s4abbs2aaaaaabbbbb65 第三節(jié) 詞法分析器的 自動(dòng)生成原理及LEX語言正規(guī)式確定自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換矩陣詞法分析器控制程序自動(dòng)生成器轉(zhuǎn)化合成一 自動(dòng)生成原理66二 LEX 語言 LEX 語言用正規(guī)式描述單詞的詞法規(guī)那么,并通過LEX編譯,自動(dòng)生成詞法掃描器.LEX語言源程序LEX編譯詞法分析器 LEX語言源程序由兩部分組成:正規(guī)式輔助定義式識別規(guī)則671 輔助定義式 輔助定義式是如下形式的 LEX 語句D1 R1D2 R2Dn Rn Ri為正規(guī)

37、式, Di為簡名. 規(guī)定Ri中只能出現(xiàn)上的字符及之前已定義過的D1. Di -1 .例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden Letter(Letter| Digit)*682 識別規(guī)那么Unsignedint Digit( Digit)*Sign +| - | signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi為正規(guī)式, 規(guī)定Pi中只能出現(xiàn)上的字符及D1. Dn ;P1. Pm 代表了某種高級語言的所有詞形. Ai為一段程序代碼,指出當(dāng)識別出滿足規(guī)那么Pi的單詞時(shí),掃描器應(yīng)采取的動(dòng)作.693 LEX編譯的工

38、作原理 LEX編譯對源程序進(jìn)行處理, 產(chǎn)生一個(gè)詞法分析器.主要有三個(gè)步驟: 1 對每條識別規(guī)那么Pi ,構(gòu)造一個(gè)非確定有限自動(dòng)機(jī) Mi , 設(shè)一 初態(tài)X ,用邊連接每個(gè)Mi的初態(tài),構(gòu)成一個(gè)總的NFAM; M1 M2 Mm x P1 P2Pm NFAM702根據(jù)定理 3 ,把 NFAM 確定化,得到一確定有限自動(dòng)機(jī) DFAM 的狀態(tài)轉(zhuǎn)換矩陣;3產(chǎn)生一個(gè)控制程序.輸出如下所示的詞法分析器:狀態(tài)轉(zhuǎn)換矩陣控制程序 控制程序用于掃描輸入字符串,控制狀態(tài)的轉(zhuǎn)移;(對任何 轉(zhuǎn)換矩陣,其控制程序是一樣的)當(dāng)識別出某詞形Pi后,執(zhí)行Ai. (返回種別碼及值)詞法分析器 71 本章習(xí)題1) 構(gòu)造如下正規(guī)式相應(yīng)的D

39、FA 11(0|1)*1012) 構(gòu)造一個(gè)DFA,它接受=0,1上所有滿足如下 條件的字符串: 每個(gè)1后都有0直接根在后邊;根 據(jù)DFA的狀態(tài)圖,編寫一個(gè)識別程序. 72第三章 語法分析 內(nèi)容提要:上下文無關(guān)文法算符優(yōu)先分析法遞歸下降分析法 語法分析的任務(wù): 把單詞符號作為根本單位,分析程序是否為 合法的程序.74第一節(jié) 上下文無關(guān)文法 上下文無關(guān)文法是這樣一種文法: 它定義的語法單位,獨(dú)立于該語法單位可能出現(xiàn)的環(huán)境,不必考慮上下文關(guān)系. 自然語言不是上下文無關(guān)文法; 程序語言是上下文無關(guān)文法;1. 上下文無關(guān)文法定義 上下文無關(guān)文法 G 是一個(gè)四元式: G =(VT,VN,S,P) 75VT

40、 : 是一個(gè)非空有限單詞集,每個(gè)元素稱為終結(jié)符號.VN: 是一個(gè)非空有限集,每個(gè)元素為非終結(jié)符號,代表了一 種語法單位. 且 VT VN=. 例如:表達(dá)式,短語,語句等S: 是一個(gè)非終結(jié)符號,稱為開始符號,S VN. S 是文法 G 的最高層次的語法單位. 在程序語言中, S代表了程序這一語法概念.P: 是一個(gè)非空有限集,每個(gè)元素稱為一條產(chǎn)生式;一條產(chǎn) 生式定義了一個(gè)非終結(jié)符.產(chǎn)生式形式如下: Pi i (Pi VN , i (VT VN ) * ) 稱Pi定義為i . 762 文法的幾點(diǎn)約定 a) 若 Pi i1 Pi i2 Pi ik則簡寫為: Pi i1|i2|. |ikb) 用英文大寫

41、字母串代表非終結(jié)符; 英文小寫字母串代表終結(jié)符; 希臘字母 等代表由VT,VN組成的符號串; 即: , (VT VN) * .c) 一個(gè)文法,可以僅用開始符號及產(chǎn)生式代替.例如:表達(dá)式的文法可以定義如下: E E+E|E-E|E*E|E/E|(E)|i E 為文法的開始符號, + - * / ( ) 為終結(jié)符.773 文法 G 與語言L(G)的關(guān)系及術(shù)語 從文法初始符開始,反復(fù)用產(chǎn)生式右部替換左部的非終結(jié)符,直到推出的符號串全部由終結(jié)符組成.得到G所定義的各種句子. 例如:E=E+E=E*E +E=i * E + E= i * i + E = i * i + i定義: 若B,經(jīng)產(chǎn)生式 B替換后

42、得到 ,稱B直接 推出. , , (VT VN) *,用=表示直接推出. 若存在1= 2 = 3.= n ,稱1可推出n; 1= n表示經(jīng)一步或若干步1可推出n. 1= n表示經(jīng)零步或若干步1可推出n.定義:設(shè)S 是G的開始符號,若 S=, (VT VN) *, 則稱 是 G的一個(gè)句型;若 VT *,則稱是 G的一個(gè)句子. (*各概念舉例)+*78定義: 文法 G 所產(chǎn)生的句子的全體,為G所描述的語言,記為 L(G)= |S=, VT * + 文法 G 正規(guī)式 V G: 描述句子結(jié)構(gòu); V:描述單詞結(jié)構(gòu); L(G):G的全體句子; L(V):V的全體單詞. 一個(gè)句型到另一個(gè)句型的推導(dǎo)有兩種方式

43、:最左推導(dǎo)和最右推導(dǎo): 最左推導(dǎo)是指每次直接推導(dǎo),對句型的最左非終結(jié)符實(shí)行替換; 最右推導(dǎo)是指每次直接推導(dǎo),對句型的最右非終結(jié)符實(shí)行替換.794 語法樹與文法的二義性 語法樹可以表示句型的推導(dǎo)及句型的層次結(jié)構(gòu). 語法樹是一棵倒立樹,根結(jié)點(diǎn)表示了文法的初始符號,每進(jìn)行一步推導(dǎo),樹的葉結(jié)點(diǎn)構(gòu)成的有序序列構(gòu)成一個(gè)句型. 例如:E=E+E=E*E +E=i * E + E= i * i + E = i * i + i 可表示為: 語法樹可以表示同一句型的多種推導(dǎo),是多種推導(dǎo)的共性抽象.但未必代表了同一句型的所有推導(dǎo):E=E*E=E*E +E =i * E + E = i * i + E = i * i

44、 + i EEE+EE*iii語法樹EEE*EE+iii80定義: 假設(shè)文法 G 的某個(gè)句型存在兩個(gè)不同的語法樹表示,稱該文法 是二義文法. 因此,文法 E 是二義文法. 二義性導(dǎo)致了i * i + i 的兩種不同運(yùn)算結(jié)果: (i*i)+i 以及 i*(i+i). 編譯中應(yīng)防止二義文法. E 文法的二義性是因?yàn)闆]有規(guī)定*,+ 運(yùn)算符的優(yōu)先順序,改進(jìn) E 后,得到: ET|E+T TF|T*F F(E)| iE為表達(dá)式,T 為項(xiàng),F 為因子 該文法對于句子i * i + i的各種推導(dǎo),對應(yīng)的語法樹是唯一的.EET+TFT*iFiFi815 喬姆斯基文法分類定義:假設(shè)G =(VT,VN,S,P)的

45、每一個(gè)產(chǎn)生式型如: , (VT VN) * , 且 至少含有一個(gè)非終結(jié)符, 稱 G 為 0 型文法; , (VT VN) * , 至少含有一個(gè)非終結(jié)符, 且滿足 | , 稱 G 為 1 型文法;A A VN , (VT VN) * , 稱 G 為 2 型文法(上下文無關(guān)文法);A B 或A , A,B VN , VT * , 稱 G 為 3 型文法(正那么文法).82第二節(jié) 語法分析概述語法分析的任務(wù): 把單詞符號作為根本單位,根據(jù)文法,分析源程序 (字串)是否為合法的程序.1 語法分析方法自下而上分析法自上而下分析法自下而上是指: 根據(jù)文法,對輸入字串進(jìn)行歸約,假設(shè)能正確地歸約 為文法的初始

46、符號,那么表示輸入字串是合法的. 典型方法是算符優(yōu)先分析法.自上而下是指: 從文法的初始符號進(jìn)行推導(dǎo),假設(shè)能推導(dǎo)出與輸入 字串相同的句子,那么表示輸入字串是合法的. 典型方法是遞歸下降分析法.832 歸約棧 自下而上分析的根本技術(shù)是采用歸約棧,如以下圖所示:a1a2.an歸約棧 字串 把輸入符號依次移入棧內(nèi),當(dāng)棧頂符號串形成某產(chǎn)生式的右部時(shí),就歸約為產(chǎn)生式左部非終結(jié)符;繼續(xù)移入輸入字串,直到棧中歸約為文法初始符號S. 這種方法也稱為移進(jìn)歸約法.84例如: G: SaAcBe分析句子 abbcde 是否 Ab|Ab 為合法的句子 BdbbcdeabcdeabbcdeaAcdeaAcdeaAbde

47、aAceaAcdeaAcBaAcBeS移入移入移入移入移入移入歸約歸約歸約歸約經(jīng)分析,判定該句子是合法的句子.85定義:棧頂形成的某產(chǎn)生式候選稱為歸約串. 在上例中,當(dāng)棧中為 aAb 時(shí),存在兩個(gè)歸約串: b 及 Ab,它們都可以歸約為 A. 假設(shè)使用 b 進(jìn)行歸約, 棧中得到 aAA, 導(dǎo)致最終不能歸約為 S,因此,判定輸入字串非法.這是一種錯(cuò)誤歸約, 原因在于棧中同時(shí)存在多個(gè)歸約串,而只有一個(gè)歸約串的選擇是正確的,如 Ab. 把 Ab 稱為可歸約串,而 b 為非可歸約串. 移進(jìn)歸約的關(guān)鍵問題,就是在棧中如何尋找可歸約串.一旦能確定可歸約串,句子分析的難點(diǎn)就迎刃而解.863 分析樹 分析樹也

48、是一棵倒立的樹,用于描述歸約過程.分析樹是從葉結(jié)點(diǎn)開始建立的,每進(jìn)行一次歸約,就生成相應(yīng)的節(jié)點(diǎn).例如,上例中的歸約過程可描述為如下分析樹:SaAcBeAbbd分析樹1234該歸約樹與句子abbcde 的語法樹是一樣的.874 標(biāo)準(zhǔn)歸約簡介 標(biāo)準(zhǔn)歸約是一種較常用的自下而上分析方法.該方法實(shí)質(zhì)上是最右推導(dǎo)的逆過程.例如:最右推導(dǎo): S =aAcBe = aAcde = aAbcde =abbcde標(biāo)準(zhǔn)歸約: abbcde = aAbcde= aAcde= aAcBe = S 標(biāo)準(zhǔn)歸約采用句柄來刻畫可歸約串.定義:設(shè) S 為文法 G 的開始符號,假設(shè)S A 且 A 其中 , (VT VN) * =*

49、=+那么稱 為句型 相對于 A 的短語;假設(shè)A 那么稱 為句型 相對于 A 的直接短語;一個(gè)句型的最左直接短語,稱為句柄.88例如: 設(shè)句型為 aAbcde 該句型有兩個(gè)直接短語: Ab, d S=aAcBe = aAcde AAb 所以Ab為直接短語; S=aAcBe = aAbcBe Bd 所以d為直接短語; 注意:b 不是句型 aAbcde 的直接短語; 因此,該句型的句柄為 AbcdeaAb 假設(shè)輸入串是合法的,那么棧中內(nèi)容與棧外內(nèi)容的連接正好為 S 的一個(gè)句型. 當(dāng)棧頂出現(xiàn)句柄時(shí)就進(jìn)行歸約.89標(biāo)準(zhǔn)歸約分析算法: (1) 在棧底放入 # ,在輸入串尾附上 #; (2) 逐個(gè)移入輸入符

50、號,當(dāng)棧頂形成句柄時(shí),進(jìn)行歸約; (3) 重復(fù) (2) 直到輸入串已全部進(jìn)棧,僅剩 #, 假設(shè)棧中歸約為 #S, 表示分析成功,輸入串為合法的句子, 否那么為非法句子. 這里,雖然指出對句柄進(jìn)行歸約,但并沒有指出如何在棧中 確定句柄,這是第四章的內(nèi)容.#S90第三節(jié) 算符優(yōu)先分析法 算符優(yōu)先分析法是一種簡單實(shí)用的自下而上分析方法,本節(jié)將詳細(xì)介紹該方法,包括 介紹 什么是算符優(yōu)先文法,優(yōu)先關(guān)系表構(gòu)造,可歸約串的刻畫與尋找方法,算符優(yōu)先分析算法等內(nèi)容.1 算符優(yōu)先文法定義1: 假設(shè)一個(gè)文法 G 的任何產(chǎn)生式右部,都不含兩個(gè)相繼出現(xiàn)的 非終結(jié)符, 那么稱 G 為算符文法.91定義2: 設(shè) G 是一個(gè)

51、算符文法,任何相繼出現(xiàn)的終結(jié)符對之間存在如下三種歸約優(yōu)先順序: 1) a b 當(dāng)且僅當(dāng) G 中含有型如 P .ab. 或 P .aQb.的產(chǎn)生式; 2) a b 當(dāng)且僅當(dāng) G 中含有型如 P .aR., 且 R b. 或 R Qb. ; 3) a b 當(dāng)且僅當(dāng) G 中含有型如 P . Rb., 且 R .a 或 R .aQ. 優(yōu)先關(guān)系可以用矩陣表示,稱為優(yōu)先關(guān)系表.+=+=+=+92定義3: 假設(shè)文法 G 的任何相繼終結(jié)符對至多只滿足以上關(guān)系之一, 稱該文法為算符優(yōu)先文法.2 優(yōu)先關(guān)系表的構(gòu)造 給定一個(gè)算符優(yōu)先文法,求各終結(jié)符對間的優(yōu)先關(guān)系.定義: FIRSTVT(P)=a | P a., 或

52、 P Qa. LASTVT(P)=a | P . a,或 P .aQ=+=+=+=+ 對每個(gè)非終結(jié)符求出這兩個(gè)集合后,可按如下規(guī)則求出各終結(jié)符對之間的優(yōu)先關(guān)系: 1) 對每一條產(chǎn)生式,若存在型如 P.ab.或 P.aQb. ,則令 a b; 該關(guān)系表示 a b 同時(shí)歸約. 932) 對每一條產(chǎn)生式,若存在型如 P.aQ.的產(chǎn)生式,對 所有 b FIRSTVT(Q) , 令 a b; 該關(guān)系表示 b 應(yīng)先于 a 歸約為 Q.例如: 設(shè)文法 G 為: EE+T|T TT*F|F F (E)|i根據(jù)定義1,這是一個(gè)算符文法.94對每個(gè)非終結(jié)符,求出:FIRSTVT(F)= ( , i LASTVT(

53、F)= ) , i FIRSTVT(T)= * , ( , i LASTVT(T)= * , ) , i FIRSTVT(E)= + , * , ( , i LASTVT(E)= + , * , ) , i 優(yōu)先關(guān)系表如下: +*()i+(i 根據(jù)定義3,該文法是算符優(yōu)先文法953 可歸約串 在算符優(yōu)先分析法中,用最左素短語描述可歸約串.定義:素短語是一個(gè)短語,它至少含有一個(gè)終結(jié)符,且除自身之外不 含更小的素短語. 一個(gè)句型的最左素短語即為可歸約串.例如:設(shè)文法 G 為: EE+T|T 句型 為: F*F+i TT*F|F F (E)|i根據(jù)短語的定義,F*F+i 有如下四個(gè)短語:其中,素短語

54、有: F*F, i 兩個(gè),最左素短語為: F*FE E E F*F+iE E+i E F*FE F*F+T T iE T*F+i T F=*=*=*=*=+=+=+=+964 尋找最左素短語 根據(jù)定義,算符優(yōu)先文法的句型必為如下形式: N1a1N2a2.NmamNm+1 其中 ai Vt Ni Vn Ni可有可無.定理: 一個(gè)算符優(yōu)先文法 G 的任何句型的最左素短語,為滿足 如下條件的最左子串: 最左素短語 = Niai.NjajNj+1 且滿足ai -1 aiai ai +1 . aj aj aj+1 因此,可以在歸約棧中,通過比較優(yōu)先關(guān)系,尋找最左素短語.975 算符優(yōu)先分析算法 1) 置

55、棧底及輸入串尾為 # ,并設(shè) # VT , VT #; 棧頂終結(jié)符為 ,輸入字為 a ; 2) 若 a 或 a 且 a#, 則 a 移入棧中. 重復(fù) 2); 若 a, 則在棧中尋找最左素短語, 歸約為 N ,重復(fù) 2); 若=a=#, 且棧中為 #N, 則分析成功;否則,輸入串為非法字串.98例如: 設(shè)文法 G 為: EE+T|T TT*F|F F (E)|i +*()i+(i優(yōu)先關(guān)系表如右,分析表達(dá)式 i+i*i 是否為合法的表達(dá)式i+i*i#+i*i#i+i*i#N i*i#N+移入歸約移入移入99*i# N+i*i#N+Ni# N+N*歸約移入移入# N+N* i歸約# N+N* N歸約

56、# N+N歸約# N為合法句子 算符優(yōu)先分析過程中,產(chǎn)生式以及非終結(jié)符名已不再起作用,只有優(yōu)先關(guān)系表決定了分析過程.100第四節(jié) 遞歸下降分析法 遞歸下降分析法是一種自頂向下分析方法,從文法開始符號自左向右進(jìn)行推導(dǎo),假設(shè)能推出一個(gè)與輸入串相等的句子,說明輸入串是合法的句子.1 遞歸下降分析法存在的問題 遞歸下降分析法本質(zhì)上是一種最左推導(dǎo),根據(jù)輸入串選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo).101例如: 設(shè)文法為 G : Sa | icT輸入串為: icta TtSeS | tS推導(dǎo)如下: S icta 根據(jù)輸入字 i icT icta 根據(jù)輸入字 t ictSeS icta 根據(jù)輸入字 a ictaeS ict

57、a 不匹配 T 有兩個(gè)候選產(chǎn)生式,如果選擇第二個(gè)候選推導(dǎo),則 S icta 根據(jù)輸入字 i icT icta 根據(jù)輸入字 t ictS icta 根據(jù)輸入字 a icta icta 匹配=102 從上面分析可知: 假設(shè)允許 P a |a . 的產(chǎn)生式,那么輸入字 a 面臨多個(gè)產(chǎn)生式可選擇用于推導(dǎo),這種情況下,推導(dǎo)只能試探性的進(jìn)行,一旦后續(xù)推導(dǎo)中不能匹配,再回過頭( 回溯 ) 選擇下一個(gè)產(chǎn)生式候選進(jìn)行推導(dǎo). 這種方式效率低, 因此,應(yīng)消除回溯. 另外,遞歸下降分析中,不允許有如下的左遞歸推導(dǎo): P P 這種左遞歸推導(dǎo),會(huì)導(dǎo)致不匹配任何輸入字而無止境的推導(dǎo)(死循環(huán)). 因此,遞歸下降分析法中存在兩

58、個(gè)主要問題: 1) 文法的左遞歸 2) 文法的回溯=+1032 無回溯遞歸下降分析 對文法的要求 要做到無回溯分析, 實(shí)際上就是要求文法無回溯及左遞歸.定義: 設(shè) A 1| 2. | m , A VN , i (VT VN) * ; 令 FIRST(i ) = a | i a., a VT 若 i ,則 FIRST(i ) (i 可能推出的所有首終結(jié)符的集合)定義: 設(shè) S為 G的開始符, 令 FOLLOW(A)=a | S .Aa., a VT 若 S .A ,則 # FOLLOW(A) ( 從 S 開始的推導(dǎo)中,所有可能緊跟在 A 之后的終結(jié)符)=*=*=+=+104定義: 設(shè) A 1|

59、2. | m , 且有 1) FIRST(i ) FIRST(j )= ,i j ; 2) 假設(shè) FIRST(i ),那么對任意 i ( 1im) 滿足 FIRST(i ) FOLLOW(A) = ; 假設(shè)文法 G 滿足上面條件,那么 G 就是無回溯文法,也稱為 LL(1) 文法. 換句話說,只要根據(jù)輸入的一個(gè)字,就能唯一地確定產(chǎn)生式候選,進(jìn)行最左推導(dǎo). 一個(gè)文法是LL(1) 文法,且不含左遞歸,就可以進(jìn)行無回溯的遞歸下降分析.1053 消除文法的左遞歸 1) 直接左遞歸的消除 假設(shè) 文法 G 中含有型如 PP | 的產(chǎn)生式, 稱 G 含有直接左遞歸. 可將直接左遞歸改寫為等價(jià)的不含左遞歸的產(chǎn)

60、生式: P P P P | 這兩組產(chǎn)生式都可推導(dǎo)出: *; 一般而言,假設(shè)產(chǎn)生式為: PP 1 | P 2 |. |P m| 1 | 2 |.| n 那么可改寫為如下等價(jià)的產(chǎn)生式: P 1 P | 2 P |.| n P P 1 P | 2 P |. | m P | 1062) 間接左遞歸的消除 若 文法 G 中含有型如 P P 的推導(dǎo), 稱 G 含有間接左遞歸. 間接左遞歸可通過如下算法消除:a) 令 VN =P1 ,P2 ,., Pn b) for i:=1 to n do for j:=1 to i-1 do 把型如PiPj 的規(guī)則改寫為: Pi 1 | 2 |.| k 其中 Pj 1