編譯原理 第二章

2/5/2023溫故知新翻譯程序：它是一個(gè)程序，能把一種語(yǔ)言程序轉(zhuǎn)換成另一種語(yǔ)言程序，且二者在邏輯上是等價(jià)的。這兩種語(yǔ)言分別稱(chēng)為源語(yǔ)言和目標(biāo)語(yǔ)言。編譯程序：一種翻譯程序，它的源語(yǔ)言是“高級(jí)語(yǔ)言”（C,Java,Pascal），目標(biāo)語(yǔ)言是“低級(jí)語(yǔ)言”(匯編語(yǔ)言，機(jī)器語(yǔ)言)12/5/2023中國(guó)科大溫故知新編譯前端編譯后端編譯前端：與源語(yǔ)言有關(guān)，與目標(biāo)機(jī)無(wú)關(guān)詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼生成器源程序優(yōu)化器目標(biāo)代碼生成器目標(biāo)代碼表格管理出錯(cuò)處理單詞符號(hào)語(yǔ)法單位中間代碼中間代碼編譯后端：與源語(yǔ)言無(wú)關(guān)，與目標(biāo)機(jī)有關(guān)2第二章高級(jí)語(yǔ)言及其語(yǔ)法描述本章內(nèi)容簡(jiǎn)介本章描述程序設(shè)計(jì)語(yǔ)言的基本結(jié)構(gòu)和主要共同特征并介紹程序設(shè)計(jì)語(yǔ)言主要語(yǔ)句的文法描述與形式定義。

與機(jī)器語(yǔ)言或匯編語(yǔ)言比較，高級(jí)語(yǔ)言的優(yōu)點(diǎn)：較接近于數(shù)學(xué)語(yǔ)言和工程語(yǔ)言，比較直觀、自然和易于理解;便于驗(yàn)證其正確性，易于改錯(cuò);編寫(xiě)效率高;易于移植.2.1程序語(yǔ)言的定義任何語(yǔ)言實(shí)現(xiàn)的基礎(chǔ)是語(yǔ)言定義語(yǔ)言的定義決定了該語(yǔ)言具有什么樣的語(yǔ)言功能、什么樣的程序結(jié)構(gòu)、什么樣的數(shù)據(jù)結(jié)構(gòu)以及具體的使用形式等細(xì)節(jié)問(wèn)題。對(duì)于語(yǔ)言用戶來(lái)說(shuō)：語(yǔ)言定義就是一本用戶手冊(cè)。對(duì)于編譯程序設(shè)計(jì)者來(lái)說(shuō)：語(yǔ)言定義就是具體實(shí)現(xiàn)的理論依據(jù)。對(duì)程序設(shè)計(jì)語(yǔ)言的描述是從語(yǔ)法、語(yǔ)義和語(yǔ)用三個(gè)因素來(lái)考慮。語(yǔ)法是對(duì)語(yǔ)言結(jié)構(gòu)的定義。語(yǔ)義是描述了語(yǔ)言的含義語(yǔ)用則是從使用的角度去描述語(yǔ)言。例如賦值語(yǔ)句s＝2*3.1416*r*(r+h)的非形式化的描述為：語(yǔ)法：賦值語(yǔ)句由一個(gè)變量，后隨一個(gè)賦值號(hào)“＝”，再在其后面跟一個(gè)表達(dá)式構(gòu)成。語(yǔ)義：首先計(jì)算語(yǔ)句右部表達(dá)式的值，然后把所得結(jié)果送給左部變量中。語(yǔ)用：賦值語(yǔ)句可用來(lái)計(jì)算和保存表達(dá)式的值。2.1.1語(yǔ)法語(yǔ)言的語(yǔ)法是指這樣一組規(guī)則，用它可產(chǎn)生一個(gè)程序。規(guī)則：詞法規(guī)則語(yǔ)法規(guī)則詞法規(guī)則：?jiǎn)卧~符號(hào)的形成規(guī)則。單詞符號(hào)是語(yǔ)言中具有獨(dú)立意義的最基本結(jié)構(gòu)。一般包括：常數(shù)、標(biāo)識(shí)符、基本字、算符、界符等。描述工具：有限自動(dòng)機(jī)語(yǔ)法規(guī)則：語(yǔ)法單位的形成規(guī)則。語(yǔ)法單位通常包括：表達(dá)式、語(yǔ)句、分程序、過(guò)程、函數(shù)、程序等;描述工具：上下文無(wú)關(guān)文法2.1.2語(yǔ)義語(yǔ)義：一組規(guī)則，用它可以定義一個(gè)程序的意義。程序語(yǔ)言的基本功能：描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。所謂程序，本質(zhì)上說(shuō)是描述一定數(shù)據(jù)的處理過(guò)程。程序的層次結(jié)構(gòu)程序|子程序或分程序、過(guò)程、函數(shù)|語(yǔ)句|表達(dá)式|數(shù)據(jù)引用算符函數(shù)調(diào)用程序語(yǔ)言每個(gè)組成成分的邏輯和實(shí)現(xiàn)意義

抽象的邏輯的意義數(shù)學(xué)意義計(jì)算機(jī)實(shí)現(xiàn)的意義具體實(shí)現(xiàn)2.2高級(jí)語(yǔ)言的一般特性

高級(jí)語(yǔ)言的分類(lèi)

強(qiáng)制式語(yǔ)言(ImperativeLanguge)也稱(chēng)過(guò)程式語(yǔ)言：命令驅(qū)動(dòng)，面向語(yǔ)句FORTRAN、C、Pascal，Ada應(yīng)用式語(yǔ)言（ApplicativeLanguage）：注重程序所表示的功能，而不是具體語(yǔ)句的執(zhí)行LISP、ML2.2高級(jí)語(yǔ)言的一般特性

2.2.1高級(jí)語(yǔ)言的分類(lèi)

基于規(guī)則的語(yǔ)言（Rule-basedLanguage）：檢查一定的條件，當(dāng)它滿足值，則執(zhí)行適當(dāng)?shù)膭?dòng)作Prolog面向?qū)ο笳Z(yǔ)言（Object-OrientedLanguage）：封裝性、繼承性和多態(tài)性Smalltalk，C++，Java2.2.2程序結(jié)構(gòu)FORTRAN一個(gè)程序由一個(gè)主程序段和若干輔程序段組成。輔程序段可以是子程序、函數(shù)段或數(shù)據(jù)塊。每個(gè)程序段有一系列的說(shuō)明語(yǔ)句和執(zhí)行語(yǔ)句組成。各段可以獨(dú)立編譯。模塊結(jié)構(gòu)，沒(méi)有嵌套和遞歸各程序段中的名字相互獨(dú)立，同一個(gè)標(biāo)識(shí)符在不同的程序段中代表不同的名字。主程序PROGRAM… …end輔程序1SUBROUTINE… …end輔程序2FUNCTION… …endPASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過(guò)程，過(guò)程可以嵌套和遞歸。一個(gè)PASCAL過(guò)程：過(guò)程頭；說(shuō)明段（由一系列的說(shuō)明語(yǔ)句組成）；begin執(zhí)行體（由一系列的執(zhí)行語(yǔ)句組成）；end2/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性2.2.2程序結(jié)構(gòu)–JavaclassCar{intcolor_number;intdoor_number;intspeed;Push_break(){…}Add_oil(){…}}classTrash_CarextendsCar{doubleamount;Fill_trash(){…}}封裝、繼承、多態(tài)(2)public、protected、private202.2.3數(shù)據(jù)類(lèi)型與操作一個(gè)數(shù)據(jù)類(lèi)型通常包括以下三種要素：用于區(qū)別這種類(lèi)型數(shù)據(jù)對(duì)象的屬性這種類(lèi)型的數(shù)據(jù)對(duì)象可以具有的值可以作用于這種類(lèi)型的數(shù)據(jù)對(duì)象的操作2.2.3數(shù)據(jù)類(lèi)型與操作一．初等數(shù)據(jù)類(lèi)型數(shù)值類(lèi)型：整型、實(shí)型、復(fù)數(shù)、雙精度，運(yùn)算：+，-，*，/等邏輯類(lèi)型：布爾運(yùn)算：∨，∧，┑字符類(lèi)型：符號(hào)處理指針類(lèi)型：值指向另外一些數(shù)據(jù)標(biāo)識(shí)符與名字標(biāo)識(shí)符：以字母開(kāi)頭的，由字母數(shù)字組成的字符串。標(biāo)識(shí)符與名字兩者有本質(zhì)區(qū)別：標(biāo)識(shí)符是語(yǔ)法概念名字有確切的意義和屬性標(biāo)識(shí)符與名字名字：值：?jiǎn)卧械膬?nèi)容屬性：類(lèi)型和作用域名字的性質(zhì)的說(shuō)明方式：由說(shuō)明語(yǔ)句來(lái)明確規(guī)定的隱含說(shuō)明：FORTRAN以I,J,K,…N為首的名字代表整型，否則為實(shí)型。動(dòng)態(tài)確定：走到哪里，是什么，算什么2/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性1、數(shù)組數(shù)組：同一類(lèi)型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)下標(biāo)：沿著某一維的距離數(shù)組元素：由數(shù)組名連同各維的下標(biāo)值命名確定數(shù)組、可變數(shù)組intarray[3];

inta=array[2];intsize=3;//或用戶輸入的數(shù)int*array=newint[size];

inta=array[2];Delete[]array;確定數(shù)組可變數(shù)組252/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性1、數(shù)組數(shù)組存儲(chǔ)方式：按行存放、按列存放數(shù)組元素地址計(jì)算：數(shù)據(jù)結(jié)構(gòu)1A[2][3]={{1,2,3},{4,5,6}}23456123456按行存放142536按列存放26內(nèi)情向量把數(shù)組的有關(guān)信息記錄在一個(gè)“內(nèi)情向量”中，每個(gè)數(shù)組的內(nèi)情向量必須包括：維數(shù)，各維的上、下限，首地址，以及數(shù)組（元素）的類(lèi)型。對(duì)于確定數(shù)組來(lái)說(shuō)，內(nèi)情向量可登記在符號(hào)表中；

對(duì)于可變數(shù)組，內(nèi)情向量的信息在編譯時(shí)無(wú)法全部知道，只有到運(yùn)行階段才能全部確定下來(lái)，存貯分配也要等到運(yùn)行時(shí)方能進(jìn)行2記錄邏輯上說(shuō)，記錄結(jié)構(gòu)由已知類(lèi)型的數(shù)據(jù)組合在一起的一種結(jié)構(gòu)。 record{charNAME[20]; integerAGE; boolMARRIED; }CARD[1000]訪問(wèn)：復(fù)合名CARD[k].NAME存儲(chǔ)：連續(xù)存放域的地址計(jì)算：相對(duì)于記錄結(jié)構(gòu)起點(diǎn)的相對(duì)數(shù)OFFSET。3字符串、表格、棧字符串：符號(hào)處理、公式處理表格：本質(zhì)上是一種記錄結(jié)構(gòu)線性表：一組順序化的記錄結(jié)構(gòu)棧：一種線性表，后進(jìn)先出，POP,PUSH三抽象數(shù)據(jù)類(lèi)型一個(gè)抽象數(shù)據(jù)類(lèi)型包括：數(shù)據(jù)對(duì)象的一個(gè)集合；作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合；這種類(lèi)型對(duì)象的封裝，即，除了使用類(lèi)型中所定義的運(yùn)算外，用戶不能對(duì)這些對(duì)象進(jìn)行操作。程序設(shè)計(jì)語(yǔ)言對(duì)抽象數(shù)據(jù)類(lèi)型的支持Ada語(yǔ)言通過(guò)程序包（package）提供了數(shù)據(jù)封裝的支持Smalltalk、C++和Java語(yǔ)言則通過(guò)類(lèi)（Class）對(duì)抽象數(shù)據(jù)類(lèi)型提供支持。2.2.4語(yǔ)句與控制結(jié)構(gòu)一．表達(dá)式表達(dá)式由運(yùn)算量（也稱(chēng)操作數(shù)，即數(shù)據(jù)引用或函數(shù)調(diào)用）和算符（操作符）組成。形式：中綴、前綴、后綴X*Y-AP↑表達(dá)式形成規(guī)則(1)變量（包括下標(biāo)變量）、常數(shù)是表達(dá)式(2)若E1、E2為表達(dá)式，θ為二元運(yùn)算符，則E1θE2是表達(dá)式(3)若E是表達(dá)式，θ為一元運(yùn)算符，則θE或Eθ是表達(dá)式(4)若E是表達(dá)式，則（E）是表達(dá)式5、a、5+a、-a、(a+5)、2+(4+a)-(-5)都是表達(dá)式2/5/20232.2高級(jí)語(yǔ)言的一般特性表達(dá)式的結(jié)合性和優(yōu)先集與數(shù)學(xué)習(xí)慣類(lèi)似不同的語(yǔ)言，這兩種性質(zhì)各有差異FORTRAN結(jié)合性優(yōu)先集X–Y-Z等于(X–Y)-Z左結(jié)合X–Y+Z等于(X-Y)+Z左結(jié)合X**Y**Z等于X**(Y**Z)右結(jié)合332/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性表達(dá)式的結(jié)合性和優(yōu)先集與數(shù)學(xué)習(xí)慣類(lèi)似不同的語(yǔ)言，這兩種性質(zhì)各有差異FORTRAN結(jié)合性優(yōu)先集乘冪**或↑一元負(fù)-乘、除*，/，÷加、減+，-關(guān)系符<,=,>,<=,<>,>=非﹁，not或.NOT.與∧，&，and或.AND.或∨，|，or或.OR.隱含imp或等值≡，～或epui342/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性例：令+、*和↑代表加、乘和乘冪，按照如下的非標(biāo)準(zhǔn)優(yōu)先集和結(jié)合性的約定（1）優(yōu)先順序（從高至低）為+、*和↑（2）同級(jí)優(yōu)先采用左結(jié)合計(jì)算1+1*2↑2*1↑2的值

1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256352/5/2023中國(guó)科大2.2高級(jí)語(yǔ)言的一般特性2.2.4語(yǔ)句和控制結(jié)構(gòu)二、語(yǔ)句從功能上說(shuō)，語(yǔ)句大體可分執(zhí)行性語(yǔ)句和說(shuō)明性語(yǔ)句。從形式上說(shuō)，語(yǔ)句還可分為簡(jiǎn)單句、復(fù)合句和分程序等。36二．語(yǔ)句賦值語(yǔ)句：A:=B名字左值：該名字代表的那個(gè)單元（地址）稱(chēng)為該名字的左值。(所代表的存貯單元的地址)右值：一個(gè)名字的值稱(chēng)為該名字的右值。(所代表的存貯單元的內(nèi)容)控制語(yǔ)句：無(wú)條件轉(zhuǎn)移語(yǔ)句

gotoL條件語(yǔ)句

ifBthenSifB

thenS1elseS2循環(huán)語(yǔ)句

whileBdoSrepeatSuntilBfori:=E1stepE2untilE3doS過(guò)程調(diào)用語(yǔ)句

callP(X1,X2,...,Xn)返回語(yǔ)句

return(E)說(shuō)明語(yǔ)句：定義各種不同數(shù)據(jù)類(lèi)型的變量或運(yùn)算，定義名字的性質(zhì)。簡(jiǎn)單句和復(fù)合句簡(jiǎn)單句：不包含其他語(yǔ)句成分的基本句復(fù)合句：句中有句的語(yǔ)句復(fù)習(xí)：高級(jí)語(yǔ)言的一般特性

高級(jí)語(yǔ)言的分類(lèi)

程序結(jié)構(gòu)數(shù)據(jù)類(lèi)型與操作初等數(shù)據(jù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類(lèi)型語(yǔ)句與控制結(jié)構(gòu)2/5/2023中國(guó)科大作業(yè)P35頁(yè)，第3、4題422.3程序語(yǔ)言的語(yǔ)法描述為了精確定義和描述程序設(shè)計(jì)語(yǔ)言,需采用形式化的方法。所謂形式化的方法,是用一整套帶有嚴(yán)格規(guī)定的符號(hào)體系來(lái)描述問(wèn)題的方法。形式語(yǔ)言理論是編譯的重要理論基礎(chǔ)。重點(diǎn)介紹如何采用形式化的方法描述程序設(shè)計(jì)語(yǔ)言。字母表字母表：元素的非空有窮集例如，∑={a,b,c}根據(jù)字母表的定義，Σ是字母表，它由a、b、c三個(gè)元素組成。注意：

(1)字母表中至少包含一個(gè)元素。

(2)字母表中的元素,可以是字母、數(shù)字或其他符號(hào)。例如，∑‘={0,1}是一個(gè)字母表，由0、1兩個(gè)元素組成。字母表中的元素稱(chēng)為符號(hào)或稱(chēng)為字符。例如，前述例子中2.符號(hào)（字符）a、b、c是字母表Σ中的符號(hào)；0、1是字母表Σ'中的符號(hào)。例如，設(shè)有字母表∑={a,b,c}符號(hào)的有窮序列稱(chēng)為符號(hào)串。符號(hào)串總是建立在某個(gè)特定字母表上的且只由字母表上的有窮多個(gè)符號(hào)組成。則有符號(hào)串a(chǎn)，b，ab，ba，cba，

abc…

3.符號(hào)串（字）說(shuō)明：符號(hào)串中符號(hào)的順序很重要ab和ba是字母表Σ上的兩個(gè)不同符號(hào)串。不包含任何符號(hào)的符號(hào)串被稱(chēng)為是空符號(hào)串。用ε表示2/5/20232.3程序語(yǔ)言的語(yǔ)法描述符號(hào)串的長(zhǎng)度串中符號(hào)的個(gè)數(shù)為符號(hào)串的長(zhǎng)度。若x=ab是符號(hào)串，則|x|表示符號(hào)串的長(zhǎng)度。|x|=2。注意：|ε|=049字符串的連接：設(shè)X是個(gè)字符串，Y是個(gè)字符串，則XY就是字符串的連接。例如設(shè)X＝ABC，Y＝10A則XY＝ABC10A，YX＝10AABC。對(duì)于任意一個(gè)字符串X，都有εx＝xε＝x。注意在U≠V下，UV≠VU，即不滿足交換率(UV)W=U(VW)，即滿足結(jié)合率2、集合乘積

設(shè)A和B是符號(hào)串的集合,則A和B的乘積定義為：

AB={xy|x∈A,y∈B}集合的乘積是滿足于x∈A,y∈B的所有符號(hào)串xy所構(gòu)成的集合。例如：設(shè)A={a,b},B={c,d}則AB={ac,ad,bc,bd}由于對(duì)任意的符號(hào)串x，總有

x=x=x所以,對(duì)任意集合A,我們有:{}A=A{}=A特別指出的是，是符號(hào)串,不是集合，而{}表示由空符號(hào)串所組成的集合,但這樣的集合不是空集合Φ={}。3.符號(hào)串的冪運(yùn)算設(shè)x是符號(hào)串,則x的冪運(yùn)算定