編譯原理ppt課件

1、1一 什么是編譯程序？2 計(jì)算機(jī)經(jīng)過(guò)幾十年的發(fā)展，計(jì)算機(jī)經(jīng)過(guò)幾十年的發(fā)展， 在程序設(shè)計(jì)語(yǔ)言方面在程序設(shè)計(jì)語(yǔ)言方面,已經(jīng)從已經(jīng)從低級(jí)語(yǔ)言發(fā)展到高級(jí)語(yǔ)言低級(jí)語(yǔ)言發(fā)展到高級(jí)語(yǔ)言;然而然而,計(jì)算機(jī)內(nèi)部的本質(zhì)只能識(shí)別計(jì)算機(jī)內(nèi)部的本質(zhì)只能識(shí)別 0 , 1 代碼序列機(jī)器語(yǔ)言）代碼序列機(jī)器語(yǔ)言）,而對(duì)高級(jí)語(yǔ)言甚至符號(hào)語(yǔ)言仍然一竅而對(duì)高級(jí)語(yǔ)言甚至符號(hào)語(yǔ)言仍然一竅不通。不通。 因此用高級(jí)語(yǔ)言編寫的程序因此用高級(jí)語(yǔ)言編寫的程序,必須先翻譯為機(jī)器語(yǔ)言，必須先翻譯為機(jī)器語(yǔ)言，才能被計(jì)算機(jī)理解執(zhí)行。第一個(gè)完成這種翻譯任務(wù)的編譯程序才能被計(jì)算機(jī)理解執(zhí)行。第一個(gè)完成這種翻譯任務(wù)的編譯程序?yàn)闉镕ORTRAN編譯程序編譯程序,是

2、上世紀(jì)五十年代設(shè)計(jì)的是上世紀(jì)五十年代設(shè)計(jì)的. 第一章第一章 引論引論第一節(jié)、編譯程序概述第一節(jié)、編譯程序概述3定義定義:設(shè)源語(yǔ)言為設(shè)源語(yǔ)言為L(zhǎng)1,目標(biāo)語(yǔ)言為目標(biāo)語(yǔ)言為L(zhǎng)2, 翻譯程序是一個(gè)程序翻譯程序是一個(gè)程序,它能將它能將L1轉(zhuǎn)換為邏輯上等價(jià)的轉(zhuǎn)換為邏輯上等價(jià)的L2。 假設(shè)假設(shè) L1 為高級(jí)語(yǔ)言，為高級(jí)語(yǔ)言，L2 為低級(jí)語(yǔ)言或機(jī)器語(yǔ)言，稱這為低級(jí)語(yǔ)言或機(jī)器語(yǔ)言，稱這種種 翻譯程序?yàn)榫幾g程序。翻譯程序?yàn)榫幾g程序。 假設(shè)假設(shè) L1 為低級(jí)語(yǔ)言，為低級(jí)語(yǔ)言，L2 為機(jī)器語(yǔ)言，稱這種翻譯程序?yàn)闄C(jī)器語(yǔ)言，稱這種翻譯程序?yàn)闉?匯編程序。匯編程序。 解釋程序是指逐條翻譯解釋程序是指逐條翻譯 L1的語(yǔ)句，并

3、立即執(zhí)行翻譯出的的語(yǔ)句，并立即執(zhí)行翻譯出的 目標(biāo)代碼序列。目標(biāo)代碼序列。 編譯原理編譯原理 就是介紹編譯程序的一般規(guī)律及設(shè)計(jì)方法的一門就是介紹編譯程序的一般規(guī)律及設(shè)計(jì)方法的一門課程。課程。高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序機(jī)器語(yǔ)言程序機(jī)器語(yǔ)言程序翻譯為翻譯為4二二 編譯過(guò)程概述編譯過(guò)程概述 編譯程序從接受源程序到輸出目標(biāo)代碼的整個(gè)編譯程序從接受源程序到輸出目標(biāo)代碼的整個(gè)過(guò)程，可邏輯的分為過(guò)程，可邏輯的分為 5 個(gè)階段，個(gè)階段，詞詞 法法 分分 析析語(yǔ)語(yǔ) 法法 分分 析析 中間代碼生成中間代碼生成 代代 碼碼 優(yōu)優(yōu) 化化 目標(biāo)代碼生成目標(biāo)代碼生成 1） 詞法分析：把源程序作為字符串進(jìn)行掃描詞法分析：把源程

4、序作為字符串進(jìn)行掃描 ，根，根據(jù)單詞詞法，識(shí)別出所有單詞，過(guò)濾無(wú)用符，并檢據(jù)單詞詞法，識(shí)別出所有單詞，過(guò)濾無(wú)用符，并檢查是否為合法的單詞。查是否為合法的單詞。 單詞一般分為如下幾種：?jiǎn)卧~一般分為如下幾種： 基本字，標(biāo)識(shí)符，常數(shù)，算符，界符基本字，標(biāo)識(shí)符，常數(shù)，算符，界符 5例如：例如： if n=1 then f:=1 else f:=n*f(n); 該程序經(jīng)過(guò)語(yǔ)法分析該程序經(jīng)過(guò)語(yǔ)法分析,得到如下單詞序列得到如下單詞序列:ifn=1thenf:=1 elsef:=n*f(n);過(guò)濾掉回車換行過(guò)濾掉回車換行,空格空格,注釋等注釋等62) 語(yǔ)法分析語(yǔ)法分析: 根據(jù)語(yǔ)言的語(yǔ)法規(guī)則根據(jù)語(yǔ)言的語(yǔ)法規(guī)則,

5、從單詞符號(hào)串中識(shí)別出從單詞符號(hào)串中識(shí)別出各種語(yǔ)法單位各種語(yǔ)法單位 ,進(jìn)行句子分析進(jìn)行句子分析,并檢查整個(gè)輸入字串是否為合并檢查整個(gè)輸入字串是否為合法的程序法的程序; 重要的語(yǔ)法單位有重要的語(yǔ)法單位有: 程序程序,子程序子程序,語(yǔ)句語(yǔ)句,短語(yǔ)短語(yǔ),表達(dá)式等表達(dá)式等例如例如: program add;var a,b:real;begin read(a,b);write (a+b);end.7程程序序首首部部說(shuō)明說(shuō)明段段執(zhí)行執(zhí)行部部program程序名及程序名及參數(shù)參數(shù)var說(shuō)明說(shuō)明語(yǔ)句語(yǔ)句add變量變量名表名表變量變量類型類型a,brealbegin多多語(yǔ)語(yǔ)句句endread(a,b)write(

6、a+b)83) 中間代碼生成中間代碼生成:根據(jù)語(yǔ)義規(guī)則根據(jù)語(yǔ)義規(guī)則,把各種語(yǔ)法單位翻譯成中間把各種語(yǔ)法單位翻譯成中間代碼序列代碼序列. 中間代碼有三種中間代碼有三種: 四元式四元式,三元式三元式,逆波蘭式逆波蘭式. 中間代碼的特點(diǎn)中間代碼的特點(diǎn):結(jié)構(gòu)簡(jiǎn)單結(jié)構(gòu)簡(jiǎn)單,語(yǔ)義明確語(yǔ)義明確,易于理解及優(yōu)化易于理解及優(yōu)化. 四元式可表示為四元式可表示為: (操作符操作符,操作數(shù)操作數(shù)1,操作數(shù)操作數(shù)2,結(jié)果結(jié)果)例如例如: 語(yǔ)句語(yǔ)句 Z:=(x+0.4)*Y/W; 翻譯后得到右面翻譯后得到右面 的四元式序列的四元式序列: 四元式序列四元式序列(+ , x, 0.4, T1)(* , T1, Y, T2)(

7、/ , T2, w, T3)(:= , T3, , Z)從示例可看出從示例可看出:每條四元式只進(jìn)行一次最基本的操作每條四元式只進(jìn)行一次最基本的操作.94) 代碼優(yōu)化：對(duì)產(chǎn)生的中間代碼序列進(jìn)行加工變換，使變換代碼優(yōu)化：對(duì)產(chǎn)生的中間代碼序列進(jìn)行加工變換，使變換后的代碼更為高效后的代碼更為高效 （時(shí)間，空間上）。（時(shí)間，空間上）。 優(yōu)化主要有：優(yōu)化主要有： 循環(huán)優(yōu)化，公共表達(dá)式提取，強(qiáng)度削弱等。循環(huán)優(yōu)化，公共表達(dá)式提取，強(qiáng)度削弱等。5) 目標(biāo)代碼生成：把中間代碼程序翻譯為機(jī)器指令或匯編指目標(biāo)代碼生成：把中間代碼程序翻譯為機(jī)器指令或匯編指令程序。令程序。 這一部分的處理，與計(jì)算機(jī)硬件及操作系統(tǒng)密切相關(guān)

8、。這一部分的處理，與計(jì)算機(jī)硬件及操作系統(tǒng)密切相關(guān)。 如寄存器數(shù)目，機(jī)器指令功能及指令條數(shù)；操作系統(tǒng)的如寄存器數(shù)目，機(jī)器指令功能及指令條數(shù)；操作系統(tǒng)的 BIOS，內(nèi)存管理，文件管理等。，內(nèi)存管理，文件管理等。三三 編譯程序的結(jié)構(gòu)編譯程序的結(jié)構(gòu) 編譯程序可以劃分為如下幾個(gè)基本模塊：編譯程序可以劃分為如下幾個(gè)基本模塊：10詞法分析器詞法分析器語(yǔ)法分析器語(yǔ)法分析器中間代碼生成中間代碼生成中間代碼優(yōu)化中間代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序源程序單詞符號(hào)單詞符號(hào)語(yǔ)法單位語(yǔ)法單位四元式四元式四元式四元式目標(biāo)程序目標(biāo)程序 表表格格管管理理 錯(cuò)錯(cuò)誤誤處處理理編譯程序總框編譯程序總框11表格管理表格管理:對(duì)各

9、種表格進(jìn)行管理對(duì)各種表格進(jìn)行管理,包括表格的構(gòu)造、查找、修正、包括表格的構(gòu)造、查找、修正、 刪除、插入刪除、插入 等；等； 編譯程序中，表格的種類較多，最主要的有如下幾種：編譯程序中，表格的種類較多，最主要的有如下幾種： 符號(hào)表，常量表，標(biāo)號(hào)表，子程序名表，四元式表等。符號(hào)表，常量表，標(biāo)號(hào)表，子程序名表，四元式表等。 表格由若干結(jié)構(gòu)相同的表格項(xiàng)組成，表格項(xiàng)由二元式表示：表格由若干結(jié)構(gòu)相同的表格項(xiàng)組成，表格項(xiàng)由二元式表示：項(xiàng)名項(xiàng)名 信息信息表格項(xiàng)表格項(xiàng)表格表格項(xiàng)名項(xiàng)名 1 信息信息項(xiàng)名項(xiàng)名 2 信息信息項(xiàng)名項(xiàng)名 n 信息信息12四四 設(shè)計(jì)編譯程序設(shè)計(jì)編譯程序 編譯程序的設(shè)計(jì)方式可以分為兩類：編譯

10、程序的設(shè)計(jì)方式可以分為兩類：方式方式人工設(shè)計(jì)人工設(shè)計(jì)自動(dòng)生成自動(dòng)生成低級(jí)語(yǔ)言低級(jí)語(yǔ)言高級(jí)語(yǔ)言高級(jí)語(yǔ)言自動(dòng)生成掃描器自動(dòng)生成掃描器自動(dòng)生成分析器自動(dòng)生成分析器自動(dòng)生成編譯程序自動(dòng)生成編譯程序13第二節(jié)、高級(jí)語(yǔ)言概述第二節(jié)、高級(jí)語(yǔ)言概述一一 什么是程序設(shè)計(jì)語(yǔ)言什么是程序設(shè)計(jì)語(yǔ)言 程序設(shè)計(jì)語(yǔ)言是一符號(hào)系統(tǒng)，由語(yǔ)法和語(yǔ)義兩方面程序設(shè)計(jì)語(yǔ)言是一符號(hào)系統(tǒng)，由語(yǔ)法和語(yǔ)義兩方面所定義。所定義。語(yǔ)法：是一組規(guī)則，規(guī)定了語(yǔ)言的形式結(jié)構(gòu)，包括單詞語(yǔ)法：是一組規(guī)則，規(guī)定了語(yǔ)言的形式結(jié)構(gòu)，包括單詞結(jié)構(gòu)，結(jié)構(gòu)， 句子結(jié)構(gòu)，程序結(jié)構(gòu)等。句子結(jié)構(gòu)，程序結(jié)構(gòu)等。 語(yǔ)法語(yǔ)法=詞法規(guī)則詞法規(guī)則+句法規(guī)則句法規(guī)則 詞法規(guī)則：規(guī)定了形

11、成單詞的規(guī)則；如常數(shù)，詞法規(guī)則：規(guī)定了形成單詞的規(guī)則；如常數(shù)，標(biāo)識(shí)符，標(biāo)識(shí)符， 基本字，算符等。基本字，算符等。 句法規(guī)則：規(guī)定了由單詞構(gòu)造更大語(yǔ)法單位的句法規(guī)則：規(guī)定了由單詞構(gòu)造更大語(yǔ)法單位的規(guī)則；規(guī)則； 如表達(dá)式，短語(yǔ)，語(yǔ)句，程序等。如表達(dá)式，短語(yǔ)，語(yǔ)句，程序等。14語(yǔ)義：也是一組規(guī)則，規(guī)定了各語(yǔ)法單位的確切含義。語(yǔ)義：也是一組規(guī)則，規(guī)定了各語(yǔ)法單位的確切含義。 例如：例如：A=B，可解釋為：，可解釋為：A賦值為賦值為B；（；（C語(yǔ)語(yǔ)言）言） 也可以解釋為也可以解釋為 ：A等于等于B （P語(yǔ)語(yǔ)言）言） 這完全由語(yǔ)義規(guī)則所確定。這完全由語(yǔ)義規(guī)則所確定。二二 數(shù)據(jù)類型數(shù)據(jù)類型 各種語(yǔ)言都提供了

12、一些最基本的數(shù)據(jù)類型各種語(yǔ)言都提供了一些最基本的數(shù)據(jù)類型,稱為稱為初等數(shù)據(jù)類型，這些數(shù)據(jù)類型的特征是數(shù)據(jù)的單一性；初等數(shù)據(jù)類型，這些數(shù)據(jù)類型的特征是數(shù)據(jù)的單一性；還提供了由初等數(shù)據(jù)類型構(gòu)造復(fù)雜結(jié)構(gòu)類型的手段。還提供了由初等數(shù)據(jù)類型構(gòu)造復(fù)雜結(jié)構(gòu)類型的手段。1初等數(shù)據(jù)類型初等數(shù)據(jù)類型數(shù)值類型：（整數(shù)，實(shí)數(shù)可進(jìn)行算術(shù)運(yùn)算和比較運(yùn)算；數(shù)值類型：（整數(shù)，實(shí)數(shù)可進(jìn)行算術(shù)運(yùn)算和比較運(yùn)算；邏輯類型：可進(jìn)行邏輯運(yùn)算；邏輯類型：可進(jìn)行邏輯運(yùn)算；字符類型：可進(jìn)行比較遠(yuǎn)算及字符串操作；字符類型：可進(jìn)行比較遠(yuǎn)算及字符串操作；指針類型：指向另一變量的地址。指針類型：指向另一變量的地址。152結(jié)構(gòu)類型結(jié)構(gòu)類型-數(shù)組數(shù)組 數(shù)

13、組是由同一類型數(shù)據(jù)所組成的多維結(jié)構(gòu)，數(shù)組數(shù)組是由同一類型數(shù)據(jù)所組成的多維結(jié)構(gòu)，數(shù)組元素是多維空間的一個(gè)點(diǎn)，代表了一個(gè)存儲(chǔ)空間。數(shù)元素是多維空間的一個(gè)點(diǎn)，代表了一個(gè)存儲(chǔ)空間。數(shù)組的存儲(chǔ)，是通過(guò)按行或按列方式，把每個(gè)數(shù)組元素組的存儲(chǔ)，是通過(guò)按行或按列方式，把每個(gè)數(shù)組元素存放在一個(gè)連續(xù)的存儲(chǔ)空間中。存放在一個(gè)連續(xù)的存儲(chǔ)空間中。設(shè)數(shù)組類型為設(shè)數(shù)組類型為 A:arrayL1 .u1,L2 . u2,.Ln . un of elemtype, 數(shù)組元素為數(shù)組元素為 Ai1,i2,.in, di=ui -Li+1則該元素的地址可按如下公式計(jì)算則該元素的地址可按如下公式計(jì)算: addr= a + (i1 -

14、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 + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlengthv = (.(i1d2+i2)d3+i3)d4+i4).) dn + in *elemlength C是常量是常量,在編譯時(shí)可以計(jì)算出在編譯時(shí)可以計(jì)算出;V是可變部分是可

15、變部分,只能在程序只能在程序運(yùn)行時(shí)才能計(jì)算出。運(yùn)行時(shí)才能計(jì)算出。 從上可知：計(jì)算數(shù)組元素地址涉及到如下幾個(gè)因素：從上可知：計(jì)算數(shù)組元素地址涉及到如下幾個(gè)因素： a c L1.Ln d1.dn elemlength i1.in 17 這些因素中這些因素中,在編譯時(shí)能確定的部分在編譯時(shí)能確定的部分,用一個(gè)數(shù)組內(nèi)情向量用一個(gè)數(shù)組內(nèi)情向量表來(lái)記錄表來(lái)記錄, 以便計(jì)算數(shù)組元素地址使用。換句話說(shuō)：當(dāng)編譯程以便計(jì)算數(shù)組元素地址使用。換句話說(shuō)：當(dāng)編譯程序掃描到數(shù)組說(shuō)明語(yǔ)句時(shí)，就把數(shù)組的各確定部分登記到內(nèi)情序掃描到數(shù)組說(shuō)明語(yǔ)句時(shí)，就把數(shù)組的各確定部分登記到內(nèi)情向量表中。向量表中。 內(nèi)情向量表組織如下：內(nèi)情向量表

16、組織如下：L1 u1 d1 L2 u2 d2 Ln un dn a c n elemlength 183結(jié)構(gòu)類型結(jié)構(gòu)類型- 記錄記錄 是由多種類型的數(shù)據(jù)組合起來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。是由多種類型的數(shù)據(jù)組合起來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。Pascal 語(yǔ)言中，可如下定義一種記錄類型語(yǔ)言中，可如下定義一種記錄類型type = record :; :; :; end; 域名即記錄分量域名即記錄分量,域的類型可以是簡(jiǎn)單數(shù)據(jù)類型域的類型可以是簡(jiǎn)單數(shù)據(jù)類型,也也可以是已經(jīng)定義過(guò)的數(shù)據(jù)類型?？梢允且呀?jīng)定義過(guò)的數(shù)據(jù)類型。 可采用分量順序方式可采用分量順序方式,分配記錄的地址空間。由于分配記錄的地址空間。由于每個(gè)域類型及空間大小

17、都可能不同每個(gè)域類型及空間大小都可能不同,因此因此,只能通過(guò)表映只能通過(guò)表映射方式計(jì)算各個(gè)域在記錄中的地址。射方式計(jì)算各個(gè)域在記錄中的地址。19記錄分量表：記錄分量表：域名域名 相對(duì)位移相對(duì)位移 域類型域類型name1 offset1 type1name2 offset2 type2 namen offsetn typen因此，因此，name i 在記錄中的地址為：在記錄中的地址為：addr=a+offset ia 為記錄的第一個(gè)分量的地址；為記錄的第一個(gè)分量的地址；20三三 表達(dá)式表達(dá)式 表達(dá)式是由算符和運(yùn)算量組成表達(dá)式是由算符和運(yùn)算量組成,可遞規(guī)定義如下可遞規(guī)定義如下: 1 變量變量,常量

18、常量,函數(shù)為表達(dá)式函數(shù)為表達(dá)式 E; 2 假設(shè)假設(shè) E1,E2為表達(dá)式為表達(dá)式,那么那么: E1 op E2, op E, (E) 為表達(dá)式。為表達(dá)式。 算符間存在如下優(yōu)先順序：算符間存在如下優(yōu)先順序： 乘冪（乘冪（*） 負(fù)號(hào)負(fù)號(hào) （） 乘除（乘除（* /） 加減（加減（+ -） 關(guān)系符（關(guān)系符（ = = 類型定義段類型定義段 type = set of ; = array of ; = record end;222 變量說(shuō)明段變量說(shuō)明段var :;:;:;3 函數(shù)及過(guò)程定義函數(shù)及過(guò)程定義 function (參數(shù)說(shuō)明參數(shù)說(shuō)明):; ; procedure (參數(shù)說(shuō)明參數(shù)說(shuō)明) ; ;4 賦值

19、句賦值句 := ; 左邊變量取其地址左邊變量取其地址,右邊表達(dá)式取其值右邊表達(dá)式取其值.235 分支語(yǔ)句分支語(yǔ)句 if then else ; case of :; : else : end; goto ;246 循環(huán)控制語(yǔ)句循環(huán)控制語(yǔ)句 while do ; for := to do ; repeat ;. until 7 子程序調(diào)用子程序調(diào)用 函數(shù)調(diào)用一般出現(xiàn)在表達(dá)式中函數(shù)調(diào)用一般出現(xiàn)在表達(dá)式中,形式如下形式如下: (實(shí)際參數(shù)實(shí)際參數(shù)) 過(guò)程調(diào)用一般作為語(yǔ)句過(guò)程調(diào)用一般作為語(yǔ)句,形式如下形式如下: (實(shí)際參數(shù)實(shí)際參數(shù));258 輸入輸出語(yǔ)句輸入輸出語(yǔ)句 read(); write();9

20、簡(jiǎn)單句和復(fù)合句簡(jiǎn)單句和復(fù)合句 簡(jiǎn)單句是指不包含其它語(yǔ)句的基本語(yǔ)句簡(jiǎn)單句是指不包含其它語(yǔ)句的基本語(yǔ)句, 復(fù)合句是指句中有句復(fù)合句是指句中有句.例如例如: V:=E,goto L ,read(a,b) 等都是簡(jiǎn)單句等都是簡(jiǎn)單句; if B then S else S, while B do S 等都是復(fù)合句等都是復(fù)合句.26五五 子程序參數(shù)傳遞子程序參數(shù)傳遞 當(dāng)調(diào)用一個(gè)子程序時(shí)當(dāng)調(diào)用一個(gè)子程序時(shí),首先應(yīng)將所需的數(shù)據(jù)傳遞給子程序首先應(yīng)將所需的數(shù)據(jù)傳遞給子程序,傳遞方式主要有三種傳遞方式主要有三種: 傳值傳值,傳地址傳地址,傳名傳名 設(shè)有如下函數(shù)設(shè)有如下函數(shù): function distence(x1

21、,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) end; x1,y1,x2,y2 稱為形式參數(shù)稱為形式參數(shù) 設(shè)主程序調(diào)用如下設(shè)主程序調(diào)用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 稱為實(shí)際參數(shù)稱為實(shí)際參數(shù).271傳值傳值 調(diào)用程序把實(shí)際參數(shù)的值傳遞到形式參數(shù)的空間中調(diào)用程序把實(shí)際參數(shù)的值傳遞到形式參數(shù)的空間中.1145x1y1x2y21145a1b1a2b2主程序空間主程序空間子程序空間子程序空間這種方式這種方式,子程序一般不改變實(shí)際參數(shù)的值子程序一般不改變實(shí)際參數(shù)的值.282傳地址傳地址

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

23、nce(a1,b1,a2,b2);相當(dāng)于在此處產(chǎn)生一段程序相當(dāng)于在此處產(chǎn)生一段程序: d:=sqrt(a2-a1)*2+(b2-b1)*2);30六六 存儲(chǔ)分配存儲(chǔ)分配 程序運(yùn)行時(shí)程序運(yùn)行時(shí),必須分配相應(yīng)的存儲(chǔ)空間必須分配相應(yīng)的存儲(chǔ)空間. 這這些空間包括些空間包括:變量空間變量空間,常量空間常量空間,臨時(shí)空間臨時(shí)空間,連接單元連接單元 等等.有的有的空間在編譯時(shí)就能確定其大小空間在編譯時(shí)就能確定其大小,而有的空間必須而有的空間必須在程序運(yùn)行時(shí)才能確定在程序運(yùn)行時(shí)才能確定.根據(jù)這一特性根據(jù)這一特性,把空間分把空間分配分為兩種配分為兩種: 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配 動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配1 靜態(tài)

24、存儲(chǔ)分配靜態(tài)存儲(chǔ)分配 若在編譯時(shí)能完全確定程序所需空間大小若在編譯時(shí)能完全確定程序所需空間大小,并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址并能確定每個(gè)數(shù)據(jù)項(xiàng)的地址,就可在編譯時(shí)分配就可在編譯時(shí)分配所需空間所需空間,這種分配方法稱為靜態(tài)存儲(chǔ)分配這種分配方法稱為靜態(tài)存儲(chǔ)分配. 若一個(gè)語(yǔ)言無(wú)遞歸調(diào)用若一個(gè)語(yǔ)言無(wú)遞歸調(diào)用,無(wú)可變數(shù)據(jù)項(xiàng)無(wú)可變數(shù)據(jù)項(xiàng),則可則可靜態(tài)地確定各數(shù)據(jù)項(xiàng)的空間大小和地址靜態(tài)地確定各數(shù)據(jù)項(xiàng)的空間大小和地址. Fortran語(yǔ)言滿足這種定義語(yǔ)言滿足這種定義.312 動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配 是指在程序運(yùn)行時(shí)才能確定存儲(chǔ)空間和地址的一種分配方法是指在程序運(yùn)行時(shí)才能確定存儲(chǔ)空間和地址的一種分配方法.適用于允

25、許遞歸和可變數(shù)據(jù)項(xiàng)的語(yǔ)言適用于允許遞歸和可變數(shù)據(jù)項(xiàng)的語(yǔ)言,如如pascal 和和 c 言語(yǔ)言語(yǔ). 一般采用堆棧動(dòng)態(tài)地分配空間一般采用堆棧動(dòng)態(tài)地分配空間, 當(dāng)調(diào)用子程序時(shí)當(dāng)調(diào)用子程序時(shí),就在堆棧中就在堆棧中為該子程序分配所需空間為該子程序分配所需空間;而子程序運(yùn)行結(jié)束后而子程序運(yùn)行結(jié)束后,就釋放該子程序就釋放該子程序空間空間.子程序空間子程序空間編譯時(shí)可確定編譯時(shí)可確定(活動(dòng)記錄活動(dòng)記錄)運(yùn)行時(shí)可確定運(yùn)行時(shí)可確定(可變空間可變空間)活動(dòng)記錄活動(dòng)記錄連接數(shù)據(jù)連接數(shù)據(jù)形式參數(shù)形式參數(shù)局部變量局部變量數(shù)組內(nèi)情向量表數(shù)組內(nèi)情向量表臨時(shí)變量等臨時(shí)變量等活動(dòng)記錄活動(dòng)記錄可變空間可變空間堆棧堆棧子子程程序序

26、S 32內(nèi)容提要內(nèi)容提要:狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖正規(guī)式與有限制動(dòng)機(jī)正規(guī)式與有限制動(dòng)機(jī)詞法分析器的自動(dòng)生成詞法分析器的自動(dòng)生成詞法分析器詞法分析器源程序源程序單詞序列單詞序列34第一節(jié)第一節(jié) 狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖一一 單詞分類及表示單詞分類及表示 編譯中編譯中,把高級(jí)語(yǔ)言的單詞分為五類把高級(jí)語(yǔ)言的單詞分為五類: 標(biāo)識(shí)符標(biāo)識(shí)符,基本字基本字,常數(shù)常數(shù),運(yùn)算符運(yùn)算符,界符界符 基本字基本字,運(yùn)算符運(yùn)算符,界符都是有限可枚舉的界符都是有限可枚舉的;而標(biāo)識(shí)而標(biāo)識(shí)符符,常數(shù)可認(rèn)為是無(wú)限的常數(shù)可認(rèn)為是無(wú)限的. 簡(jiǎn)單起見(jiàn)簡(jiǎn)單起見(jiàn),單詞可表示為如下二元組單詞可表示為如下二元組: (單詞分類號(hào)單詞分類號(hào),單詞自身值

27、單詞自身值); 或者為或者為: (單詞種別碼單詞種別碼,單詞自身值單詞自身值); 標(biāo)識(shí)符標(biāo)識(shí)符,常數(shù)常數(shù) 各為一個(gè)種別碼各為一個(gè)種別碼,而由于基本字而由于基本字,運(yùn)運(yùn)算符算符,界符的有限性界符的有限性,可以設(shè)計(jì)為一字一個(gè)種別碼可以設(shè)計(jì)為一字一個(gè)種別碼.35例如例如:單詞單詞 單詞種別碼單詞種別碼分類號(hào)分類號(hào) 標(biāo)識(shí)符標(biāo)識(shí)符1 1常數(shù)常數(shù) 2 2if 3 3then4 3end90 3,91 4;92 4=151 5+152 5保留字保留字界符界符運(yùn)算符運(yùn)算符36二二 詞法分析器的設(shè)計(jì)詞法分析器的設(shè)計(jì)1 源程序的預(yù)處理子程序源程序的預(yù)處理子程序 源程序中源程序中,存在許多編輯用的符號(hào)存在許多編輯用

28、的符號(hào),它們對(duì)程序邏它們對(duì)程序邏輯功能無(wú)任何影響輯功能無(wú)任何影響. 例如例如:回車回車,換行換行,多余空白符多余空白符,注釋注釋行等行等.在詞法分析之前在詞法分析之前,首先要剔除掉這些符號(hào)首先要剔除掉這些符號(hào),使得詞使得詞法分析更為簡(jiǎn)單法分析更為簡(jiǎn)單.源程序源程序輸入緩沖區(qū)輸入緩沖區(qū)預(yù)處理子程序預(yù)處理子程序掃描緩沖區(qū)掃描緩沖區(qū)2掃描緩沖區(qū)掃描緩沖區(qū)1 緩沖區(qū)分為兩部分緩沖區(qū)分為兩部分,每每個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為256字節(jié)字節(jié),這樣這樣單詞的總長(zhǎng)度可達(dá)到單詞的總長(zhǎng)度可達(dá)到256字節(jié)字節(jié).預(yù)處理子程序預(yù)處理子程序把處理好的字符串輪把處理好的字符串輪流放入兩個(gè)緩沖區(qū)中流放入兩個(gè)緩沖區(qū)中,供詞法分析程序使用

29、供詞法分析程序使用.372 詞法分析程序詞法分析程序 詞法分析程序又稱為詞法分析器或掃描器詞法分析程序又稱為詞法分析器或掃描器.可以單獨(dú)為一個(gè)程序可以單獨(dú)為一個(gè)程序;也可以也可以作為整個(gè)編譯程序的一個(gè)子程序作為整個(gè)編譯程序的一個(gè)子程序,當(dāng)需要一個(gè)單詞時(shí)當(dāng)需要一個(gè)單詞時(shí),就調(diào)用詞法分析子程序就調(diào)用詞法分析子程序返回一個(gè)單詞返回一個(gè)單詞.這里這里,作為子程序介紹作為子程序介紹. 詞法分析器的結(jié)構(gòu)詞法分析器的結(jié)構(gòu):源程序源程序輸入緩沖區(qū)輸入緩沖區(qū)預(yù)處理子程序預(yù)處理子程序掃描緩沖區(qū)掃描緩沖區(qū)2掃描緩沖區(qū)掃描緩沖區(qū)1詞法分析子程序詞法分析子程序調(diào)用調(diào)用返回一單詞返回一單詞數(shù)據(jù)數(shù)據(jù)383 詞法規(guī)則的表示詞

30、法規(guī)則的表示-狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖定義定義:狀態(tài)轉(zhuǎn)換圖是一有向圖狀態(tài)轉(zhuǎn)換圖是一有向圖,由有限個(gè)結(jié)點(diǎn)及有向邊連接而成由有限個(gè)結(jié)點(diǎn)及有向邊連接而成; 每個(gè)結(jié)點(diǎn)稱為狀態(tài)每個(gè)結(jié)點(diǎn)稱為狀態(tài);狀態(tài)圖有一個(gè)初態(tài)狀態(tài)圖有一個(gè)初態(tài),多個(gè)終態(tài)多個(gè)終態(tài);每條邊上每條邊上 有相應(yīng)的字符有相應(yīng)的字符. 狀態(tài)轉(zhuǎn)換圖用于表示單詞結(jié)構(gòu)狀態(tài)轉(zhuǎn)換圖用于表示單詞結(jié)構(gòu),從狀態(tài)轉(zhuǎn)換圖的初態(tài)到終態(tài)從狀態(tài)轉(zhuǎn)換圖的初態(tài)到終態(tài)間間,每條路徑上字符的連接每條路徑上字符的連接,就構(gòu)成了該狀態(tài)圖的合法單詞就構(gòu)成了該狀態(tài)圖的合法單詞.例如例如: 012初態(tài)初態(tài)終態(tài)終態(tài)字母字母字母字母數(shù)字?jǐn)?shù)字其它其它*1標(biāo)識(shí)符的狀態(tài)圖表示標(biāo)識(shí)符的狀態(tài)圖表示:星號(hào)表示單

31、詞尾部多跟一個(gè)星號(hào)表示單詞尾部多跟一個(gè)字符字符,應(yīng)該去掉應(yīng)該去掉.39012初態(tài)初態(tài)終態(tài)終態(tài)數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它*2整數(shù)的狀態(tài)圖表示整數(shù)的狀態(tài)圖表示:016初態(tài)初態(tài)終態(tài)終態(tài)數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字其它其它*3實(shí)數(shù)的狀態(tài)圖表示實(shí)數(shù)的狀態(tài)圖表示:23456數(shù)字?jǐn)?shù)字?jǐn)?shù)字?jǐn)?shù)字 數(shù)字?jǐn)?shù)字E+或或 數(shù)字?jǐn)?shù)字E其它其它數(shù)字?jǐn)?shù)字404 單詞的識(shí)別單詞的識(shí)別 狀態(tài)圖即可以表示單詞規(guī)則狀態(tài)圖即可以表示單詞規(guī)則,同時(shí)也可以用于識(shí)別單詞同時(shí)也可以用于識(shí)別單詞. 設(shè)有一字符串設(shè)有一字符串S = s1s2.sn, 若狀態(tài)圖中存在一初態(tài)到終態(tài)的若狀態(tài)圖中存在一初態(tài)到終態(tài)的途徑途徑,且路徑上字符的連接為且路徑上字符的連接為: s

32、1s2.sn, 稱稱 S 可被狀態(tài)圖識(shí)別可被狀態(tài)圖識(shí)別.例如例如: S=var1012初態(tài)初態(tài)終態(tài)終態(tài)var1其它其它* 保留字由于滿足標(biāo)識(shí)符定義保留字由于滿足標(biāo)識(shí)符定義,因此可以跟標(biāo)識(shí)符用同樣的狀因此可以跟標(biāo)識(shí)符用同樣的狀態(tài)圖表示與識(shí)別態(tài)圖表示與識(shí)別,只需增加一個(gè)保留字表只需增加一個(gè)保留字表,當(dāng)識(shí)別出一個(gè)標(biāo)識(shí)符時(shí)當(dāng)識(shí)別出一個(gè)標(biāo)識(shí)符時(shí),通過(guò)查保留字表來(lái)區(qū)別保留字及普通標(biāo)識(shí)符通過(guò)查保留字表來(lái)區(qū)別保留字及普通標(biāo)識(shí)符.因此因此 var1 是一個(gè)合法的標(biāo)識(shí)符是一個(gè)合法的標(biāo)識(shí)符.415 一個(gè)簡(jiǎn)單示例一個(gè)簡(jiǎn)單示例 構(gòu)造一個(gè)簡(jiǎn)單語(yǔ)言所有單詞的狀態(tài)轉(zhuǎn)換圖構(gòu)造一個(gè)簡(jiǎn)單語(yǔ)言所有單詞的狀態(tài)轉(zhuǎn)換圖.該語(yǔ)言的單詞種類如

33、下表所示該語(yǔ)言的單詞種類如下表所示:單詞符號(hào)單詞符號(hào) 種別碼種別碼 助記符助記符 內(nèi)碼值內(nèi)碼值 DIMIFDOSTOPEND標(biāo)識(shí)符標(biāo)識(shí)符正常數(shù)正常數(shù)=+*,()1234567891011121314$DIM$IF$DO$STOP$END$ID$INT$ASSIGN$PLUS$STAR$POWER$COMMA$LPAR$RPAR( 1 , )( 2 , )( 3 , )( 4 , )( 5 , )( 6 , 串值串值)( 7 , 數(shù)值數(shù)值)( 8 , )( 9 , )( 10, )( 11, )( 12, )( 13, )( 14, )420 1 2初態(tài)初態(tài)終態(tài)終態(tài)字母字母字母字母數(shù)字?jǐn)?shù)字其它其

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

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

36、 i2i1 inc1c2cnstate i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT；state i2: . cn :CONCAT；state in: . ELSE ERROR END;452循環(huán)結(jié)構(gòu)程序設(shè)計(jì)循環(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ì)終結(jié)點(diǎn)程序設(shè)計(jì) 一般對(duì)應(yīng)一條返回語(yǔ)句一般對(duì)應(yīng)一條返回語(yǔ)句: return( c,val); c 為種別碼為種別碼, val 為單詞值為

37、單詞值. 帶帶 * 號(hào)的終結(jié)點(diǎn)號(hào)的終結(jié)點(diǎn),必須用必須用RETRACT 退還多余字符退還多余字符 下面程序?yàn)楹?jiǎn)單示例語(yǔ)言的實(shí)現(xiàn)下面程序?yàn)楹?jiǎn)單示例語(yǔ)言的實(shí)現(xiàn):46TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END；FUNCTION RETURN_WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE2: C:=RESER

38、VE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) 47 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE4: RETURN($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9: IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN(

39、$STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); ELSE STATE13: ERROR 這節(jié)介紹詞法規(guī)則的形式表示這節(jié)介紹詞法規(guī)則的形式表示(正規(guī)式正規(guī)式),從正規(guī)式向有限自動(dòng)從正規(guī)式向有限自動(dòng)機(jī)的轉(zhuǎn)化機(jī)的轉(zhuǎn)化.正規(guī)式正規(guī)式有限自動(dòng)機(jī)有限自動(dòng)機(jī)詞法分析器詞法分析器控制程序控制程序自動(dòng)生成器自動(dòng)生成器轉(zhuǎn)化轉(zhuǎn)化合成合成第二節(jié)第二節(jié) 正規(guī)式與有限自動(dòng)機(jī)正規(guī)式與有限自動(dòng)機(jī)49一一 基本概念基本概念 定義定義 1 字與字集字與字集 假設(shè)假設(shè): 是一有

40、窮字符集是一有窮字符集,它的每個(gè)元素稱為一個(gè)字符它的每個(gè)元素稱為一個(gè)字符; 字字- 上的一個(gè)字上的一個(gè)字,是由是由 中的字符所構(gòu)成的一個(gè)有窮序列中的字符所構(gòu)成的一個(gè)有窮序列;空串空串-不包含任何元素的序列稱為空串不包含任何元素的序列稱為空串,記為記為;閉包閉包*- 上所有可能的字的全體上所有可能的字的全體; 空字集空字集-不含任何字的集合稱為空字集不含任何字的集合稱為空字集;記為記為 = ; 例如例如: =a,b 那么那么 *=,a,b,aa,ab,ba,bb. 留意留意: , , 三者間的關(guān)系三者間的關(guān)系定義定義 2 連接運(yùn)算連接運(yùn)算 設(shè)設(shè) U,V * 那么那么 UV= | U, V 普通普

41、通 UVVU Vn =VV.V 稱為稱為 V 的的 n 次積次積50例如例如: 設(shè)設(shè) U=a,aa, V=b 則則UV=ab,aab VU=ba,baa定義定義 3 V的閉包的閉包 設(shè)設(shè) V 為字集為字集,且且 V0= 令令 V*=V0V1 V2 . V+= V* - 稱稱V* 為為V的閉包的閉包 稱稱V+ 為為V的正則閉包的正則閉包 留意留意: * 與與 V* 的區(qū)別的區(qū)別.51 二二 正規(guī)式與正規(guī)集正規(guī)式與正規(guī)集 *是一個(gè)無(wú)窮集是一個(gè)無(wú)窮集,在程序語(yǔ)言中在程序語(yǔ)言中,我們只研究滿足詞法規(guī)則我們只研究滿足詞法規(guī)則(正規(guī)式正規(guī)式)的單的單詞集詞集(正規(guī)集正規(guī)集).定義定義 1 正規(guī)式與正規(guī)集的

42、遞歸定義正規(guī)式與正規(guī)集的遞歸定義 : 1) , 是是 上的正規(guī)式上的正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 , ; 2) 假設(shè)假設(shè) a ,那么那么 a 為正規(guī)式為正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 a; 3) 設(shè)設(shè)U,V 為為 上的正規(guī)式上的正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 L(U),L(V); 那么那么 U|V為為 上的正規(guī)式上的正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 L(U) L(V); UV為為 上的正規(guī)式上的正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 L(U) L(V); V* 為為 上的正規(guī)式上的正規(guī)式, 所表示的正規(guī)集為所表示的正規(guī)集為 L(V)* ; 4

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

44、 L(V)=L(U), 則稱兩個(gè)正規(guī)式等價(jià)則稱兩個(gè)正規(guī)式等價(jià),記為記為 U=V.正規(guī)式的運(yùn)算正規(guī)式的運(yùn)算: 設(shè)設(shè) U V W 為正規(guī)式為正規(guī)式, 則滿足以下關(guān)系則滿足以下關(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ī)確定有限自動(dòng)機(jī) 一個(gè)確定有限自動(dòng)機(jī)一個(gè)確定有限自動(dòng)機(jī)(DFA M)是一個(gè)五元式是一個(gè)五元式: DFA M=(S, , f,s0,Z) 其中其中 S 是一有限集是一有限集,每個(gè)元素稱為一個(gè)狀態(tài)每個(gè)元素稱為一個(gè)狀態(tài); 是一個(gè)有窮字母表是

45、一個(gè)有窮字母表,每個(gè)元素為一字符每個(gè)元素為一字符; f 是一個(gè)單值映射函數(shù)是一個(gè)單值映射函數(shù),f(si,a)=sj ( si , sj S, a ); 其含義為其含義為:在狀態(tài)在狀態(tài) si ,輸入字符輸入字符 a 時(shí)時(shí),將轉(zhuǎn)換到下一狀態(tài)將轉(zhuǎn)換到下一狀態(tài)sj. 稱稱sj為為 si的后繼狀態(tài)的后繼狀態(tài). s0 S, 是唯一的初態(tài)是唯一的初態(tài); Z S ,是終態(tài)集是終態(tài)集. 一個(gè)一個(gè)DFAM可用狀態(tài)轉(zhuǎn)換矩陣或狀態(tài)圖表示可用狀態(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,

46、a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3狀態(tài)轉(zhuǎn)換矩陣可表示為狀態(tài)轉(zhuǎn)換矩陣可表示為: 狀態(tài)圖可表示為狀態(tài)圖可表示為:ab012132213333狀狀態(tài)態(tài)字字 符符013初態(tài)初態(tài)終態(tài)終態(tài)2abbaaabb55四四 非確定有限自動(dòng)機(jī)非確定有限自動(dòng)機(jī) 一個(gè)非確定有限自動(dòng)機(jī)一個(gè)非確定有限自動(dòng)機(jī)(NFA M)是一個(gè)五元式是一個(gè)五元式: NFA M=(S, , f,S0,Z) 其中其中 S 是一有限集是一有限集,每個(gè)元素稱為一個(gè)狀態(tài)每個(gè)元素稱為一個(gè)狀態(tài); 是一個(gè)由窮字母表是一個(gè)由窮字母表,每個(gè)元素為一字符每個(gè)元素為一字符; f 是一個(gè)多值映射函數(shù)是一個(gè)多值映射函數(shù),f

47、(si,)=s i1 , s i2 ,. s ik ( si , si1 ,. , s ik S, *); 其含義為其含義為:在狀態(tài)在狀態(tài) si ,輸入字串輸入字串 時(shí)時(shí),將轉(zhuǎn)換到下一狀態(tài)集將轉(zhuǎn)換到下一狀態(tài)集: s i1 , s i2 ,. s ik S0 S, 是初態(tài)集是初態(tài)集; Z S ,是終態(tài)集是終態(tài)集. 一個(gè)一個(gè)NFAM也可用狀態(tài)圖表示也可用狀態(tài)圖表示,此時(shí)每條邊用字串表示此時(shí)每條邊用字串表示.56例如例如:01初態(tài)初態(tài)終態(tài)終態(tài)2aabba,ba,ba,b終態(tài)終態(tài)DFAM 是是 NFAM 的特例的特例.定義定義: 狀態(tài)圖中狀態(tài)圖中,從初態(tài)到終態(tài)任一路徑上的字串連接從初態(tài)到終態(tài)任一路徑上

48、的字串連接,稱為該狀稱為該狀態(tài)圖可識(shí)別的單詞態(tài)圖可識(shí)別的單詞,可識(shí)別單詞的全體記為可識(shí)別單詞的全體記為:L(M). 若若L(M)= L(M),稱稱M 與與M等價(jià)等價(jià). 57五五 正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性 前面前面,介紹了正規(guī)式介紹了正規(guī)式,DFAM,NFAM, 下面討論這三個(gè)概念間的下面討論這三個(gè)概念間的關(guān)系關(guān)系.定理定理1 : 對(duì)任意正規(guī)式對(duì)任意正規(guī)式V,存在一個(gè)存在一個(gè)NFAM ,使得使得L(V)=L(NFAM);證明證明: (1)構(gòu)造一個(gè)拓廣轉(zhuǎn)換圖構(gòu)造一個(gè)拓廣轉(zhuǎn)換圖 顯然顯然,該轉(zhuǎn)換圖能識(shí)別的該轉(zhuǎn)換圖能識(shí)別的 單詞集為單詞集為:L(V)XYV58(2) 進(jìn)行如

49、下等價(jià)變換進(jìn)行如下等價(jià)變換,直到轉(zhuǎn)換圖的每條邊上的標(biāo)志為直到轉(zhuǎn)換圖的每條邊上的標(biāo)志為上的上的 字符字符. ijV1V2ijV1kV2aijV1 | V2iV1jV2bijV*ijkcV 等價(jià)變換后的轉(zhuǎn)換圖等價(jià)變換后的轉(zhuǎn)換圖M 符合符合 NFAM的定義的定義,顯然有顯然有 L(V)=L(M).該定理說(shuō)明該定理說(shuō)明,從正規(guī)式可逐步構(gòu)造一個(gè)從正規(guī)式可逐步構(gòu)造一個(gè)NFAM.59定義定義:設(shè)設(shè) S 是一個(gè)狀態(tài)集是一個(gè)狀態(tài)集, _CLOSURE(S)定義如下定義如下: a) 假設(shè)假設(shè) s S,那么那么 s _CLOSURE(S); b) 假設(shè)假設(shè) s S,那么那么 從從 s 出發(fā)經(jīng)過(guò)任意條出發(fā)經(jīng)過(guò)任意條

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

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

52、的證明方法的證明方法,可如下構(gòu)造可如下構(gòu)造NFAMXY( a|b) *(aa|bb)(a|b) *等價(jià)變換得到等價(jià)變換得到:513264aaaabbbbNFAMXY(2) 用狀態(tài)轉(zhuǎn)換矩陣用狀態(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,

53、1,4,6,yM(3) 將將M 中的狀態(tài)集換名中的狀態(tài)集換名, si = Ii 得到一新的狀態(tài)轉(zhuǎn)換矩陣得到一新的狀態(tài)轉(zhuǎn)換矩陣 M留意留意: M 與與 M等價(jià)等價(jià).64Sabs0 s1 s2s1 s3 s2s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5MM滿足確定有限自動(dòng)機(jī)的定義滿足確定有限自動(dòng)機(jī)的定義,狀態(tài)圖狀態(tài)圖表示如下表示如下: s0s1s3s5s6s4abbs2aaaaaabbbbb65 第三節(jié)第三節(jié) 詞法分析器的詞法分析器的 自動(dòng)生成原理及自動(dòng)生成原理及LEX語(yǔ)言語(yǔ)言正規(guī)式正規(guī)式確定自動(dòng)機(jī)確定自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換矩陣詞法分析器詞法分析器控

54、制程序控制程序自動(dòng)生成器自動(dòng)生成器轉(zhuǎn)化轉(zhuǎn)化合成合成一一 自動(dòng)生成原理自動(dòng)生成原理66二二 LEX 言語(yǔ)言語(yǔ) LEX 語(yǔ)言用正規(guī)式描述單詞的詞法規(guī)則語(yǔ)言用正規(guī)式描述單詞的詞法規(guī)則,并通過(guò)并通過(guò)LEX編譯編譯,自自動(dòng)生成詞法掃描器動(dòng)生成詞法掃描器.LEX語(yǔ)言語(yǔ)言源程序源程序LEX編譯編譯詞法分析器詞法分析器 LEX語(yǔ)言源程序由兩部分組成語(yǔ)言源程序由兩部分組成:正規(guī)式輔助定義式正規(guī)式輔助定義式識(shí)別規(guī)則識(shí)別規(guī)則671 輔助定義式輔助定義式 輔助定義式是如下形式的輔助定義式是如下形式的 LEX 語(yǔ)句語(yǔ)句D1 R1D2 R2Dn Rn Ri為正規(guī)式為正規(guī)式, Di為簡(jiǎn)名為簡(jiǎn)名. 規(guī)定規(guī)定Ri中只能出現(xiàn)中只

55、能出現(xiàn)上的字符及之前上的字符及之前已定義過(guò)的已定義過(guò)的D1. Di -1 .例如例如:Letter A|B|.|Z|a|b|.|zDigit 0|1|2.|9Iden Letter(Letter| Digit)*682 識(shí)別規(guī)則識(shí)別規(guī)則Unsignedint Digit( Digit)*Sign +| - | signedint Sign Unsignedint P1 A1P2 A2Pm Am Pi為正規(guī)式為正規(guī)式, 規(guī)定規(guī)定Pi中只能出現(xiàn)中只能出現(xiàn)上的字符及上的字符及D1. Dn ;P1. Pm 代表了某種高級(jí)語(yǔ)言的所代表了某種高級(jí)語(yǔ)言的所有詞形有詞形. Ai為一段程序代碼為一段程序代碼,指

56、出當(dāng)識(shí)別出滿足規(guī)則指出當(dāng)識(shí)別出滿足規(guī)則Pi的單詞時(shí)的單詞時(shí),掃描器應(yīng)采取的動(dòng)作掃描器應(yīng)采取的動(dòng)作.693 LEX編譯的工作原理編譯的工作原理 LEX編譯對(duì)源程序進(jìn)行處理編譯對(duì)源程序進(jìn)行處理, 產(chǎn)生一個(gè)詞法分析器產(chǎn)生一個(gè)詞法分析器.主要有三個(gè)步驟主要有三個(gè)步驟: 1 對(duì)每條識(shí)別規(guī)則對(duì)每條識(shí)別規(guī)則Pi ,構(gòu)造一個(gè)非確定有限自動(dòng)機(jī)構(gòu)造一個(gè)非確定有限自動(dòng)機(jī) Mi , 設(shè)一設(shè)一 初態(tài)初態(tài)X ,用邊連接每個(gè)用邊連接每個(gè)Mi的初態(tài)的初態(tài),構(gòu)成一個(gè)總的構(gòu)成一個(gè)總的NFAM; M1 M2 Mm x P1 P2Pm NFAM702根據(jù)定理根據(jù)定理 3 ,把把 NFAM 確定化確定化,得到一確定有限自動(dòng)機(jī)得到一確定

57、有限自動(dòng)機(jī) DFAM 的狀態(tài)轉(zhuǎn)換矩陣的狀態(tài)轉(zhuǎn)換矩陣;3產(chǎn)生一個(gè)控制程序產(chǎn)生一個(gè)控制程序.輸出如下所示的詞法分析器輸出如下所示的詞法分析器:狀態(tài)轉(zhuǎn)狀態(tài)轉(zhuǎn)換矩陣換矩陣控制控制程序程序 控制程序用于掃描輸入字符串控制程序用于掃描輸入字符串,控制狀態(tài)的轉(zhuǎn)移控制狀態(tài)的轉(zhuǎn)移;(對(duì)任何對(duì)任何 轉(zhuǎn)換矩陣轉(zhuǎn)換矩陣,其控制程序是一樣的其控制程序是一樣的)當(dāng)識(shí)別出某詞形當(dāng)識(shí)別出某詞形Pi后后,執(zhí)行執(zhí)行Ai. (返回種別碼及值返回種別碼及值)詞法分析器詞法分析器 71 本章習(xí)題本章習(xí)題1) 構(gòu)造如下正規(guī)式相應(yīng)的構(gòu)造如下正規(guī)式相應(yīng)的DFA 11(0|1)*1012) 構(gòu)造一個(gè)構(gòu)造一個(gè)DFA,它接受它接受=0,1上所有滿

58、足如下上所有滿足如下 條件的字符串條件的字符串: 每個(gè)每個(gè)1后都有后都有0直接根在后邊直接根在后邊;根根 據(jù)據(jù)DFA的狀態(tài)圖的狀態(tài)圖,編寫一個(gè)識(shí)別程序編寫一個(gè)識(shí)別程序. 72 內(nèi)容提要內(nèi)容提要:上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法算符優(yōu)先分析法算符優(yōu)先分析法遞歸下降分析法遞歸下降分析法 語(yǔ)法分析的任務(wù)語(yǔ)法分析的任務(wù): 把單詞符號(hào)作為基本單位把單詞符號(hào)作為基本單位,分析程序是否為分析程序是否為 合法的程序合法的程序.74第一節(jié)第一節(jié) 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法 上下文無(wú)關(guān)文法是這樣一種文法上下文無(wú)關(guān)文法是這樣一種文法: 它定義的語(yǔ)法單位它定義的語(yǔ)法單位,獨(dú)立獨(dú)立于該語(yǔ)法單位可能出現(xiàn)的環(huán)境于該語(yǔ)法單位可

59、能出現(xiàn)的環(huán)境,不必考慮上下文關(guān)系不必考慮上下文關(guān)系. 自然語(yǔ)言不是上下文無(wú)關(guān)文法自然語(yǔ)言不是上下文無(wú)關(guān)文法; 程序語(yǔ)言是上下文無(wú)關(guān)文法程序語(yǔ)言是上下文無(wú)關(guān)文法;1. 上下文無(wú)關(guān)文法定義上下文無(wú)關(guān)文法定義 上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法 G 是一個(gè)四元式是一個(gè)四元式: G =(VT,VN,S,P) 75VT : 是一個(gè)非空有限單詞集是一個(gè)非空有限單詞集,每個(gè)元素稱為終結(jié)符號(hào)每個(gè)元素稱為終結(jié)符號(hào).VN: 是一個(gè)非空有限集是一個(gè)非空有限集,每個(gè)元素為非終結(jié)符號(hào)每個(gè)元素為非終結(jié)符號(hào),代表了一代表了一 種語(yǔ)法單位種語(yǔ)法單位. 且且 VT VN=. 例如例如:表達(dá)式表達(dá)式,短語(yǔ)短語(yǔ),語(yǔ)句等語(yǔ)句等S: 是一個(gè)

60、非終結(jié)符號(hào)是一個(gè)非終結(jié)符號(hào),稱為開始符號(hào)稱為開始符號(hào),S VN. S 是文法是文法 G 的最高層次的語(yǔ)法單位的最高層次的語(yǔ)法單位. 在程序語(yǔ)言中在程序語(yǔ)言中, S代表了程序這一語(yǔ)法概念代表了程序這一語(yǔ)法概念.P: 是一個(gè)非空有限集是一個(gè)非空有限集,每個(gè)元素稱為一條產(chǎn)生式每個(gè)元素稱為一條產(chǎn)生式;一條產(chǎn)一條產(chǎn) 生式定義了一個(gè)非終結(jié)符生式定義了一個(gè)非終結(jié)符.產(chǎn)生式形式如下產(chǎn)生式形式如下: Pi i (Pi VN , i (VT VN ) * ) 稱稱Pi定義為定義為i . 762 文法的幾點(diǎn)約定文法的幾點(diǎn)約定 a) 假設(shè)假設(shè) Pi i1 Pi i2 Pi ik則簡(jiǎn)寫為則簡(jiǎn)寫為: Pi i1|i2|.